1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
/*
* Copyright (C) 2001 Sistina Software (UK) Limited.
*
* This file is released under the LGPL.
*/
#include "btree.h"
#include "log.h"
struct node {
uint32_t key;
struct node *l, *r, *p;
void *data;
};
struct btree {
struct pool *mem;
struct node *root;
};
struct btree *btree_create(struct pool *mem)
{
struct btree *t = pool_alloc(mem, sizeof(*t));
if (t) {
t->mem = mem;
t->root = NULL;
}
return t;
}
/*
* Shuffle the bits in a key, to try and remove
* any ordering.
*/
static uint32_t _shuffle(uint32_t k)
{
#if 1
return ((k & 0xff) << 24 |
(k & 0xff00) << 8 |
(k & 0xff0000) >> 8 | (k & 0xff000000) >> 24);
#else
return k;
#endif
}
struct node **_lookup(struct node **c, uint32_t key, struct node **p)
{
*p = NULL;
while (*c) {
*p = *c;
if ((*c)->key == key)
break;
if (key < (*c)->key)
c = &(*c)->l;
else
c = &(*c)->r;
}
return c;
}
void *btree_lookup(struct btree *t, uint32_t k)
{
uint32_t key = _shuffle(k);
struct node *p, **c = _lookup(&t->root, key, &p);
return (*c) ? (*c)->data : NULL;
}
int btree_insert(struct btree *t, uint32_t k, void *data)
{
uint32_t key = _shuffle(k);
struct node *p, **c = _lookup(&t->root, key, &p), *n;
if (!*c) {
if (!(n = pool_alloc(t->mem, sizeof(*n)))) {
stack;
return 0;
}
n->key = key;
n->data = data;
n->l = n->r = NULL;
n->p = p;
*c = n;
}
return 1;
}
void *btree_get_data(struct btree_iter *it)
{
return ((struct node *) it)->data;
}
static inline struct node *_left(struct node *n)
{
while (n->l)
n = n->l;
return n;
}
struct btree_iter *btree_first(struct btree *t)
{
if (!t->root)
return NULL;
return (struct btree_iter *) _left(t->root);
}
struct btree_iter *btree_next(struct btree_iter *it)
{
struct node *n = (struct node *) it;
uint32_t k = n->key;
if (n->r)
return (struct btree_iter *) _left(n->r);
do
n = n->p;
while (n && k > n->key);
return (struct btree_iter *) n;
}
|
