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