1 /* $NetBSD: btree.c,v 1.1.1.1 2008/12/22 00:17:54 haad Exp $ */
2
3 /*
4 * Copyright (C) 2001-2004 Sistina Software, Inc. All rights reserved.
5 * Copyright (C) 2004-2007 Red Hat, Inc. All rights reserved.
6 *
7 * This file is part of LVM2.
8 *
9 * This copyrighted material is made available to anyone wishing to use,
10 * modify, copy, or redistribute it subject to the terms and conditions
11 * of the GNU Lesser General Public License v.2.1.
12 *
13 * You should have received a copy of the GNU Lesser General Public License
14 * along with this program; if not, write to the Free Software Foundation,
15 * Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
16 */
17
18 #include "lib.h"
19 #include "btree.h"
20
21 struct node {
22 uint32_t key;
23 struct node *l, *r, *p;
24
25 void *data;
26 };
27
28 struct btree {
29 struct dm_pool *mem;
30 struct node *root;
31 };
32
btree_create(struct dm_pool * mem)33 struct btree *btree_create(struct dm_pool *mem)
34 {
35 struct btree *t = dm_pool_alloc(mem, sizeof(*t));
36
37 if (t) {
38 t->mem = mem;
39 t->root = NULL;
40 }
41
42 return t;
43 }
44
45 /*
46 * Shuffle the bits in a key, to try and remove
47 * any ordering.
48 */
_shuffle(uint32_t k)49 static uint32_t _shuffle(uint32_t k)
50 {
51 #if 1
52 return ((k & 0xff) << 24 |
53 (k & 0xff00) << 8 |
54 (k & 0xff0000) >> 8 | (k & 0xff000000) >> 24);
55 #else
56 return k;
57 #endif
58 }
59
_lookup(struct node * const * c,uint32_t key,struct node ** p)60 static struct node **_lookup(struct node *const *c, uint32_t key,
61 struct node **p)
62 {
63 *p = NULL;
64 while (*c) {
65 *p = *c;
66 if ((*c)->key == key)
67 break;
68
69 if (key < (*c)->key)
70 c = &(*c)->l;
71
72 else
73 c = &(*c)->r;
74 }
75
76 return (struct node **)c;
77 }
78
btree_lookup(const struct btree * t,uint32_t k)79 void *btree_lookup(const struct btree *t, uint32_t k)
80 {
81 uint32_t key = _shuffle(k);
82 struct node *p, **c = _lookup(&t->root, key, &p);
83 return (*c) ? (*c)->data : NULL;
84 }
85
btree_insert(struct btree * t,uint32_t k,void * data)86 int btree_insert(struct btree *t, uint32_t k, void *data)
87 {
88 uint32_t key = _shuffle(k);
89 struct node *p, **c = _lookup(&t->root, key, &p), *n;
90
91 if (!*c) {
92 if (!(n = dm_pool_alloc(t->mem, sizeof(*n))))
93 return_0;
94
95 n->key = key;
96 n->data = data;
97 n->l = n->r = NULL;
98 n->p = p;
99
100 *c = n;
101 }
102
103 return 1;
104 }
105
btree_get_data(const struct btree_iter * it)106 void *btree_get_data(const struct btree_iter *it)
107 {
108 return ((struct node *) it)->data;
109 }
110
_left(struct node * n)111 static struct node *_left(struct node *n)
112 {
113 while (n->l)
114 n = n->l;
115 return n;
116 }
117
btree_first(const struct btree * t)118 struct btree_iter *btree_first(const struct btree *t)
119 {
120 if (!t->root)
121 return NULL;
122
123 return (struct btree_iter *) _left(t->root);
124 }
125
btree_next(const struct btree_iter * it)126 struct btree_iter *btree_next(const struct btree_iter *it)
127 {
128 struct node *n = (struct node *) it;
129 uint32_t k = n->key;
130
131 if (n->r)
132 return (struct btree_iter *) _left(n->r);
133
134 do
135 n = n->p;
136 while (n && k > n->key);
137
138 return (struct btree_iter *) n;
139 }
140