2 * Copyright (C) 2010 Joseph Adams <joeyadams3.14159@gmail.com>
4 * Permission is hereby granted, free of charge, to any person obtaining a copy
5 * of this software and associated documentation files (the "Software"), to deal
6 * in the Software without restriction, including without limitation the rights
7 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8 * copies of the Software, and to permit persons to whom the Software is
9 * furnished to do so, subject to the following conditions:
11 * The above copyright notice and this permission notice shall be included in
12 * all copies or substantial portions of the Software.
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
27 Note: The following should work but are not well-tested yet:
41 * Maximum number of items per node.
42 * The maximum number of branches is BTREE_ITEM_MAX + 1.
44 #define BTREE_ITEM_MAX 20
47 struct btree_node *parent;
49 /* Number of items (rather than branches). */
52 /* 0 if node is a leaf, 1 if it has leaf children, etc. */
55 /* node->parent->branch[node->k] == this */
58 const void *item[BTREE_ITEM_MAX];
61 * Allocated to BTREE_ITEM_MAX+1 items if this is
62 * an internal node, 0 items if it is a leaf.
64 struct btree_node *branch[];
67 typedef struct btree_iterator_s {
69 struct btree_node *node;
73 * The relationship between item and (node, k) depends on what function
74 * set it. It is mainly for convenience.
80 * Instead of a compare function, this library accepts a binary search function
81 * to know how to order the items.
83 typedef unsigned int btree_search_proto(
85 const void * const *base,
90 typedef btree_search_proto *btree_search_t;
92 btree_search_proto btree_strcmp;
95 * Callback used by btree_delete() and btree_walk...().
97 * If it returns 0, it causes btree_walk...() to stop traversing and return 0.
98 * Thus, in normal circumstances, this callback should return 1.
100 * Callback shall not insert/remove items from the btree being traversed,
101 * nor shall anything modify it during a walk.
103 typedef int (*btree_action_t)(void *item, void *ctx);
106 struct btree_node *root;
107 size_t count; /* Total number of items in B-tree */
109 btree_search_t search;
113 * These are set to NULL by default.
115 * When destroy is not NULL, it is called on each item in order when
116 * btree_delete() is called.
118 * When destroy is NULL, btree_delete runs faster because it does not have
119 * to visit each and every item.
121 btree_action_t destroy;
125 struct btree *btree_new(btree_search_t search);
126 void btree_delete(struct btree *btree);
128 /* Inserts an item into the btree. If an item already exists that is equal
129 * to this one (as determined by the search function), behavior depends on the
130 * btree->multi setting.
131 * If btree->multi is false (default), returns false, and no item
132 * is inserted (because it would be a duplicate).
133 * If btree->multi is true, returns true, putting the item after
136 bool btree_insert(struct btree *btree, const void *item);
138 /* Removes an item from the btree. If an item exists that is equal to the
139 * key (as determined by the search function), it is removed.
141 * If btree->multi is set, all matching items are removed.
143 * Returns true if item was found and deleted, false if not found. */
144 bool btree_remove(struct btree *btree, const void *key);
146 /* Finds the requested item.
147 * Returns the item pointer on success, NULL on failure.
148 * Note that NULL is a valid item value. If you need to put
149 * NULLs in a btree, use btree_find instead. */
150 void *btree_lookup(struct btree *btree, const void *key);
153 /* lr must be 0 or 1, nothing else. */
154 int btree_begin_end_lr(const struct btree *btree, btree_iterator iter, int lr);
155 int btree_find_lr(const struct btree *btree, const void *key,
156 btree_iterator iter, int lr);
158 int btree_walk_backward(const struct btree *btree,
159 btree_action_t action, void *ctx);
160 int btree_walk_forward(const struct btree *btree,
161 btree_action_t action, void *ctx);
163 #define btree_begin(btree, iter) btree_begin_end_lr(btree, iter, 0)
164 #define btree_end(btree, iter) btree_begin_end_lr(btree, iter, 1)
166 int btree_prev(btree_iterator iter);
167 int btree_next(btree_iterator iter);
169 #define btree_walk(btree, action, ctx) btree_walk_forward(btree, action, ctx)
172 * If key was found, btree_find_first will return 1, iter->item will be the
173 * first matching item, and iter will point to the beginning of the matching
176 * If key was not found, btree_find_first will return 0, iter->item will be
177 * undefined, and iter will point to where the key should go if inserted.
179 #define btree_find_first(btree, key, iter) btree_find_lr(btree, key, iter, 0)
182 * If key was found, btree_find_last will return 1, iter->item will be the
183 * last matching item, and iter will point to the end of the matching
186 * If key was not found, btree_find_last will return 0, iter->item will be
187 * undefined, and iter will point to where the key should go if inserted.
189 #define btree_find_last(btree, key, iter) btree_find_lr(btree, key, iter, 1)
191 /* btree_find is an alias of btree_find_first. */
192 #define btree_find(btree, key, iter) btree_find_first(btree, key, iter)
195 * If iter points to an item, btree_deref returns 1 and sets iter->item to the
198 * Otherwise (if iter points to the end of the btree), btree_deref returns 0
199 * and leaves iter untouched.
201 int btree_deref(btree_iterator iter);
204 * Inserts the item before the one pointed to by iter.
206 * Insertion invalidates all iterators to the btree, including the one
207 * passed to btree_insert_at. Nevertheless, iter->item will be set to
210 void btree_insert_at(btree_iterator iter, const void *item);
213 * Removes the item pointed to by iter. Returns 1 if iter pointed
214 * to an item. Returns 0 if iter pointed to the end, in which case
215 * it leaves iter intact.
217 * Removal invalidates all iterators to the btree, including the one
218 * passed to btree_remove_at. Nevertheless, iter->item will be set to
221 int btree_remove_at(btree_iterator iter);
224 * Compares positions of two iterators.
226 * Returns -1 if a is before b, 0 if a is at the same position as b,
227 * and +1 if a is after b.
229 int btree_cmp_iters(const btree_iterator iter_a, const btree_iterator iter_b);
231 #define btree_search_implement(name, type, setup, equals, lessthan) \
232 unsigned int name(const void *__key, \
233 const void * const *__base, unsigned int __count, \
234 int __lr, int *__found) \
236 unsigned int __start = 0; \
238 unsigned int __middle = __count >> 1; \
239 type a = (type)__key; \
240 type b = (type)__base[__start + __middle]; \
249 __start += __middle + 1; \
250 __count -= __middle + 1; \
255 goto __greaterthan; \
256 /* else, fall through to __lessthan */ \
258 __count = __middle; \
264 #endif /* #ifndef CCAN_BTREE_H */