2 Copyright (c) 2010 Joseph A. Adams
5 Redistribution and use in source and binary forms, with or without
6 modification, are permitted provided that the following conditions
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.
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.
32 Note: The following should work but are not well-tested yet:
42 * Maximum number of items per node.
43 * The maximum number of branches is BTREE_ITEM_MAX + 1.
45 #define BTREE_ITEM_MAX 20
48 struct btree_node *parent;
50 /* Number of items (rather than branches). */
53 /* 0 if node is a leaf, 1 if it has leaf children, etc. */
56 /* node->parent->branch[node->k] == this */
59 const void *item[BTREE_ITEM_MAX];
62 * Allocated to BTREE_ITEM_MAX+1 items if this is
63 * an internal node, 0 items if it is a leaf.
65 struct btree_node *branch[];
68 typedef struct btree_iterator_s {
70 struct btree_node *node;
74 * The relationship between item and (node, k) depends on what function
75 * set it. It is mainly for convenience.
81 * Instead of a compare function, this library accepts a binary search function
82 * to know how to order the items.
84 typedef unsigned int btree_search_proto(
86 const void * const *base,
91 typedef btree_search_proto *btree_search_t;
94 * Callback used by btree_delete() and btree_walk...().
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.
99 * Callback shall not insert/remove items from the btree being traversed,
100 * nor shall anything modify it during a walk.
102 typedef int (*btree_action_t)(void *item, void *ctx);
105 struct btree_node *root;
106 size_t count; /* Total number of items in B-tree */
108 btree_search_t search;
111 * These are set to NULL by default.
113 * When destroy is not NULL, it is called on each item in order when
114 * btree_delete() is called.
116 * When destroy is NULL, btree_delete runs faster because it does not have
117 * to visit each and every item.
119 btree_action_t destroy;
123 struct btree *btree_new(btree_search_t search);
124 void btree_delete(struct btree *btree);
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);
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);
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)
140 int btree_prev(btree_iterator iter);
141 int btree_next(btree_iterator iter);
143 #define btree_walk(btree, action, ctx) btree_walk_forward(btree, action, ctx)
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
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.
153 #define btree_find_first(btree, key, iter) btree_find_lr(btree, key, iter, 0)
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
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.
163 #define btree_find_last(btree, key, iter) btree_find_lr(btree, key, iter, 1)
165 /* btree_find is an alias of btree_find_first. */
166 #define btree_find(btree, key, iter) btree_find_first(btree, key, iter)
169 * If iter points to an item, btree_deref returns 1 and sets iter->item to the
172 * Otherwise (if iter points to the end of the btree), btree_deref returns 0
173 * and leaves iter untouched.
175 int btree_deref(btree_iterator iter);
178 * Inserts the item before the one pointed to by iter.
180 * Insertion invalidates all iterators to the btree, including the one
181 * passed to btree_insert_at. Nevertheless, iter->item will be set to
184 void btree_insert_at(btree_iterator iter, const void *item);
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.
191 * Removal invalidates all iterators to the btree, including the one
192 * passed to btree_remove_at. Nevertheless, iter->item will be set to
195 int btree_remove_at(btree_iterator iter);
198 * Compares positions of two iterators.
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.
203 int btree_cmp_iters(const btree_iterator iter_a, const btree_iterator iter_b);
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) \
210 unsigned int __start = 0; \
212 unsigned int __middle = __count >> 1; \
213 type a = (type)__key; \
214 type b = (type)__base[__start + __middle]; \
223 __start += __middle + 1; \
224 __count -= __middle + 1; \
229 goto __greaterthan; \
230 /* else, fall through to __lessthan */ \
232 __count = __middle; \
238 #endif /* #ifndef CCAN_BTREE_H */