Joey's btree module.
[ccan] / ccan / btree / btree.h
1 /*
2         Copyright (c) 2010  Joseph A. Adams
3         All rights reserved.
4         
5         Redistribution and use in source and binary forms, with or without
6         modification, are permitted provided that the following conditions
7         are met:
8         1. Redistributions of source code must retain the above copyright
9            notice, this list of conditions and the following disclaimer.
10         2. Redistributions in binary form must reproduce the above copyright
11            notice, this list of conditions and the following disclaimer in the
12            documentation and/or other materials provided with the distribution.
13         3. The name of the author may not be used to endorse or promote products
14            derived from this software without specific prior written permission.
15         
16         THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
17         IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
18         OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
19         IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
20         INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
21         NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22         DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23         THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24         (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
25         THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 */
27
28 #ifndef CCAN_BTREE_H
29 #define CCAN_BTREE_H
30
31 /*
32 Note:  The following should work but are not well-tested yet:
33
34 btree_walk...
35 btree_cmp_iters
36 */
37
38 #include <stdint.h>
39 #include <stddef.h>
40
41 /*
42  * Maximum number of items per node.
43  * The maximum number of branches is BTREE_ITEM_MAX + 1.
44  */
45 #define BTREE_ITEM_MAX 20
46
47 struct btree_node {
48         struct btree_node *parent;
49         
50         /* Number of items (rather than branches). */
51         unsigned char count;
52         
53         /* 0 if node is a leaf, 1 if it has leaf children, etc. */
54         unsigned char depth;
55         
56         /* node->parent->branch[node->k] == this */
57         unsigned char k;
58         
59         const void *item[BTREE_ITEM_MAX];
60         
61         /*
62          * Allocated to BTREE_ITEM_MAX+1 items if this is
63          * an internal node, 0 items if it is a leaf.
64          */
65         struct btree_node *branch[];
66 };
67
68 typedef struct btree_iterator_s {
69         struct btree *btree;
70         struct btree_node *node;
71         unsigned int k;
72         
73         /*
74          * The relationship between item and (node, k) depends on what function
75          * set it.  It is mainly for convenience.
76          */
77         void *item;
78 } btree_iterator[1];
79
80 /*
81  * Instead of a compare function, this library accepts a binary search function
82  * to know how to order the items.
83  */
84 typedef unsigned int btree_search_proto(
85         const void *key,
86         const void * const *base,
87         unsigned int count,
88         int lr,
89         int *found
90 );
91 typedef btree_search_proto *btree_search_t;
92
93 /*
94  * Callback used by btree_delete() and btree_walk...().
95  *
96  * If it returns 0, it causes btree_walk...() to stop traversing and return 0.
97  * Thus, in normal circumstances, this callback should return 1.
98  *
99  * Callback shall not insert/remove items from the btree being traversed,
100  * nor shall anything modify it during a walk.
101  */
102 typedef int (*btree_action_t)(void *item, void *ctx);
103
104 struct btree {
105         struct btree_node *root;
106         size_t count; /* Total number of items in B-tree */
107         
108         btree_search_t search;
109         
110         /*
111          * These are set to NULL by default.
112          *
113          * When destroy is not NULL, it is called on each item in order when
114          * btree_delete() is called.
115          *
116          * When destroy is NULL, btree_delete runs faster because it does not have
117          * to visit each and every item.
118          */
119         btree_action_t destroy;
120         void *destroy_ctx;
121 };
122
123 struct btree *btree_new(btree_search_t search);
124 void btree_delete(struct btree *btree);
125
126
127 /* lr must be 0 or 1, nothing else. */
128 int btree_begin_end_lr(const struct btree *btree, btree_iterator iter, int lr);
129 int btree_find_lr(const struct btree *btree, const void *key,
130                                 btree_iterator iter, int lr);
131
132 int btree_walk_backward(const struct btree *btree,
133                                 btree_action_t action, void *ctx);
134 int btree_walk_forward(const struct btree *btree,
135                                 btree_action_t action, void *ctx);
136
137 #define btree_begin(btree, iter) btree_begin_end_lr(btree, iter, 0)
138 #define btree_end(btree, iter) btree_begin_end_lr(btree, iter, 1)
139
140 int btree_prev(btree_iterator iter);
141 int btree_next(btree_iterator iter);
142
143 #define btree_walk(btree, action, ctx) btree_walk_forward(btree, action, ctx)
144
145 /*
146  * If key was found, btree_find_first will return 1, iter->item will be the
147  * first matching item, and iter will point to the beginning of the matching
148  * items.
149  *
150  * If key was not found, btree_find_first will return 0, iter->item will be
151  * undefined, and iter will point to where the key should go if inserted.
152  */
153 #define btree_find_first(btree, key, iter) btree_find_lr(btree, key, iter, 0)
154
155 /*
156  * If key was found, btree_find_last will return 1, iter->item will be the
157  * last matching item, and iter will point to the end of the matching
158  * items.
159  *
160  * If key was not found, btree_find_last will return 0, iter->item will be
161  * undefined, and iter will point to where the key should go if inserted.
162  */
163 #define btree_find_last(btree, key, iter) btree_find_lr(btree, key, iter, 1)
164
165 /* btree_find is an alias of btree_find_first. */
166 #define btree_find(btree, key, iter) btree_find_first(btree, key, iter)
167
168 /*
169  * If iter points to an item, btree_deref returns 1 and sets iter->item to the
170  * item it points to.
171  *
172  * Otherwise (if iter points to the end of the btree), btree_deref returns 0
173  * and leaves iter untouched.
174  */
175 int btree_deref(btree_iterator iter);
176
177 /*
178  * Inserts the item before the one pointed to by iter.
179  *
180  * Insertion invalidates all iterators to the btree, including the one
181  * passed to btree_insert_at.  Nevertheless, iter->item will be set to
182  * the item inserted.
183  */
184 void btree_insert_at(btree_iterator iter, const void *item);
185
186 /*
187  * Removes the item pointed to by iter.  Returns 1 if iter pointed
188  * to an item.  Returns 0 if iter pointed to the end, in which case
189  * it leaves iter intact.
190  *
191  * Removal invalidates all iterators to the btree, including the one
192  * passed to btree_remove_at.  Nevertheless, iter->item will be set to
193  * the item removed.
194  */
195 int btree_remove_at(btree_iterator iter);
196
197 /*
198  * Compares positions of two iterators.
199  *
200  * Returns -1 if a is before b, 0 if a is at the same position as b,
201  * and +1 if a is after b.
202  */
203 int btree_cmp_iters(const btree_iterator iter_a, const btree_iterator iter_b);
204
205 #define btree_search_implement(name, type, setup, equals, lessthan) \
206 unsigned int name(const void *__key, \
207                 const void * const *__base, unsigned int __count, \
208                 int __lr, int *__found) \
209 { \
210         unsigned int __start = 0; \
211         while (__count) { \
212                 unsigned int __middle = __count >> 1; \
213                 type a = (type)__key; \
214                 type b = (type)__base[__start + __middle]; \
215                 { \
216                         setup; \
217                         if (equals) \
218                                 goto __equals; \
219                         if (lessthan) \
220                                 goto __lessthan; \
221                 } \
222         __greaterthan: \
223                 __start += __middle + 1; \
224                 __count -= __middle + 1; \
225                 continue; \
226         __equals: \
227                 *__found = 1; \
228                 if (__lr) \
229                         goto __greaterthan; \
230                 /* else, fall through to __lessthan */ \
231         __lessthan: \
232                 __count = __middle; \
233                 continue; \
234         } \
235         return __start; \
236 }
237
238 #endif /* #ifndef CCAN_BTREE_H */