1/*	$NetBSD$	*/
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
21struct node {
22	uint32_t key;
23	struct node *l, *r, *p;
24
25	void *data;
26};
27
28struct btree {
29	struct dm_pool *mem;
30	struct node *root;
31};
32
33struct 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 */
49static 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
60static 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
79void *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
86int 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
106void *btree_get_data(const struct btree_iter *it)
107{
108	return ((struct node *) it)->data;
109}
110
111static struct node *_left(struct node *n)
112{
113	while (n->l)
114		n = n->l;
115	return n;
116}
117
118struct 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
126struct 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