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