check_type: fix incorrect documentation.
[ccan] / ccan / btree / btree.h
1 /*
2  * Copyright (C) 2010 Joseph Adams <joeyadams3.14159@gmail.com>
3  *
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:
10  *
11  * The above copyright notice and this permission notice shall be included in
12  * all copies or substantial portions of the Software.
13  *
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
20  * THE SOFTWARE.
21  */
22
23 #ifndef CCAN_BTREE_H
24 #define CCAN_BTREE_H
25
26 /*
27 Note:  The following should work but are not well-tested yet:
28
29 btree_walk...
30 btree_cmp_iters
31 btree_insert
32 btree_remove
33 btree_lookup
34 */
35
36 #include <stdbool.h>
37 #include <stdint.h>
38 #include <string.h>
39
40 /*
41  * Maximum number of items per node.
42  * The maximum number of branches is BTREE_ITEM_MAX + 1.
43  */
44 #define BTREE_ITEM_MAX 20
45
46 struct btree_node {
47         struct btree_node *parent;
48         
49         /* Number of items (rather than branches). */
50         unsigned char count;
51         
52         /* 0 if node is a leaf, 1 if it has leaf children, etc. */
53         unsigned char depth;
54         
55         /* node->parent->branch[node->k] == this */
56         unsigned char k;
57         
58         const void *item[BTREE_ITEM_MAX];
59         
60         /*
61          * Allocated to BTREE_ITEM_MAX+1 items if this is
62          * an internal node, 0 items if it is a leaf.
63          */
64         struct btree_node *branch[];
65 };
66
67 typedef struct btree_iterator_s {
68         struct btree *btree;
69         struct btree_node *node;
70         unsigned int k;
71         
72         /*
73          * The relationship between item and (node, k) depends on what function
74          * set it.  It is mainly for convenience.
75          */
76         void *item;
77 } btree_iterator[1];
78
79 /*
80  * Instead of a compare function, this library accepts a binary search function
81  * to know how to order the items.
82  */
83 typedef unsigned int btree_search_proto(
84         const void *key,
85         const void * const *base,
86         unsigned int count,
87         int lr,
88         int *found
89 );
90 typedef btree_search_proto *btree_search_t;
91
92 btree_search_proto btree_strcmp;
93
94 /*
95  * Callback used by btree_delete() and btree_walk...().
96  *
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.
99  *
100  * Callback shall not insert/remove items from the btree being traversed,
101  * nor shall anything modify it during a walk.
102  */
103 typedef int (*btree_action_t)(void *item, void *ctx);
104
105 struct btree {
106         struct btree_node *root;
107         size_t count; /* Total number of items in B-tree */
108         
109         btree_search_t search;
110         bool multi;
111         
112         /*
113          * These are set to NULL by default.
114          *
115          * When destroy is not NULL, it is called on each item in order when
116          * btree_delete() is called.
117          *
118          * When destroy is NULL, btree_delete runs faster because it does not have
119          * to visit each and every item.
120          */
121         btree_action_t destroy;
122         void *destroy_ctx;
123 };
124
125 struct btree *btree_new(btree_search_t search);
126 void btree_delete(struct btree *btree);
127
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
134  *      its duplicates.
135  */
136 bool btree_insert(struct btree *btree, const void *item);
137
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.
140  *
141  * If btree->multi is set, all matching items are removed.
142  *
143  * Returns true if item was found and deleted, false if not found. */
144 bool btree_remove(struct btree *btree, const void *key);
145
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);
151
152
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);
157
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);
162
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)
165
166 int btree_prev(btree_iterator iter);
167 int btree_next(btree_iterator iter);
168
169 #define btree_walk(btree, action, ctx) btree_walk_forward(btree, action, ctx)
170
171 /*
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
174  * items.
175  *
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.
178  */
179 #define btree_find_first(btree, key, iter) btree_find_lr(btree, key, iter, 0)
180
181 /*
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
184  * items.
185  *
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.
188  */
189 #define btree_find_last(btree, key, iter) btree_find_lr(btree, key, iter, 1)
190
191 /* btree_find is an alias of btree_find_first. */
192 #define btree_find(btree, key, iter) btree_find_first(btree, key, iter)
193
194 /*
195  * If iter points to an item, btree_deref returns 1 and sets iter->item to the
196  * item it points to.
197  *
198  * Otherwise (if iter points to the end of the btree), btree_deref returns 0
199  * and leaves iter untouched.
200  */
201 int btree_deref(btree_iterator iter);
202
203 /*
204  * Inserts the item before the one pointed to by iter.
205  *
206  * Insertion invalidates all iterators to the btree, including the one
207  * passed to btree_insert_at.  Nevertheless, iter->item will be set to
208  * the item inserted.
209  */
210 void btree_insert_at(btree_iterator iter, const void *item);
211
212 /*
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.
216  *
217  * Removal invalidates all iterators to the btree, including the one
218  * passed to btree_remove_at.  Nevertheless, iter->item will be set to
219  * the item removed.
220  */
221 int btree_remove_at(btree_iterator iter);
222
223 /*
224  * Compares positions of two iterators.
225  *
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.
228  */
229 int btree_cmp_iters(const btree_iterator iter_a, const btree_iterator iter_b);
230
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) \
235 { \
236         unsigned int __start = 0; \
237         while (__count) { \
238                 unsigned int __middle = __count >> 1; \
239                 type a = (type)__key; \
240                 type b = (type)__base[__start + __middle]; \
241                 { \
242                         setup; \
243                         if (equals) \
244                                 goto __equals; \
245                         if (lessthan) \
246                                 goto __lessthan; \
247                 } \
248         __greaterthan: \
249                 __start += __middle + 1; \
250                 __count -= __middle + 1; \
251                 continue; \
252         __equals: \
253                 *__found = 1; \
254                 if (__lr) \
255                         goto __greaterthan; \
256                 /* else, fall through to __lessthan */ \
257         __lessthan: \
258                 __count = __middle; \
259                 continue; \
260         } \
261         return __start; \
262 }
263
264 #endif /* #ifndef CCAN_BTREE_H */