| /* |
| * Copyright (C) 2001-2004 Sistina Software, Inc. All rights reserved. |
| * Copyright (C) 2004-2007 Red Hat, Inc. All rights reserved. |
| * |
| * This file is part of the device-mapper userspace tools. |
| * |
| * This copyrighted material is made available to anyone wishing to use, |
| * modify, copy, or redistribute it subject to the terms and conditions |
| * of the GNU Lesser General Public License v.2.1. |
| * |
| * You should have received a copy of the GNU Lesser General Public License |
| * along with this program; if not, write to the Free Software Foundation, |
| * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA |
| */ |
| |
| #include "dmlib.h" |
| #include "ttree.h" |
| |
| struct node { |
| unsigned k; |
| struct node *l, *m, *r; |
| void *data; |
| }; |
| |
| struct ttree { |
| int klen; |
| struct dm_pool *mem; |
| struct node *root; |
| }; |
| |
| __attribute__((nonnull(1))) |
| static struct node **_lookup_single(struct node **c, unsigned int k) |
| { |
| while (*c) { |
| if (k < (*c)->k) |
| c = &((*c)->l); |
| |
| else if (k > (*c)->k) |
| c = &((*c)->r); |
| |
| else { |
| c = &((*c)->m); |
| break; |
| } |
| } |
| |
| return c; |
| } |
| |
| void *ttree_lookup(struct ttree *tt, unsigned *key) |
| { |
| struct node **c = &tt->root; |
| int count = tt->klen; |
| |
| while (*c && count) { |
| c = _lookup_single(c, *key++); |
| count--; |
| } |
| |
| return *c ? (*c)->data : NULL; |
| } |
| |
| static struct node *_tree_node(struct dm_pool *mem, unsigned int k) |
| { |
| struct node *n = dm_pool_zalloc(mem, sizeof(*n)); |
| |
| if (n) |
| n->k = k; |
| |
| return n; |
| } |
| |
| int ttree_insert(struct ttree *tt, unsigned int *key, void *data) |
| { |
| struct node **c = &tt->root; |
| int count = tt->klen; |
| unsigned int k; |
| |
| do { |
| k = *key++; |
| c = _lookup_single(c, k); |
| count--; |
| |
| } while (*c && count); |
| |
| if (!*c) { |
| count++; |
| |
| while (count--) { |
| if (!(*c = _tree_node(tt->mem, k))) |
| return_0; |
| |
| if (count) { |
| k = *key++; |
| c = &((*c)->m); |
| } |
| } |
| } |
| (*c)->data = data; |
| |
| return 1; |
| } |
| |
| struct ttree *ttree_create(struct dm_pool *mem, unsigned int klen) |
| { |
| struct ttree *tt; |
| |
| if (!(tt = dm_pool_zalloc(mem, sizeof(*tt)))) |
| return_NULL; |
| |
| tt->klen = klen; |
| tt->mem = mem; |
| return tt; |
| } |