X-Git-Url: https://git.ozlabs.org/?p=ccan;a=blobdiff_plain;f=ccan%2Fbtree%2Fbtree.h;fp=ccan%2Fbtree%2Fbtree.h;h=babfea763f14fda65794866c2699c65800deb030;hp=0000000000000000000000000000000000000000;hb=8f7447e48f6405a083919f3d6b591eb7dfbc6a9f;hpb=5008de765e1c1550aad1b3697713f7549774a9c9 diff --git a/ccan/btree/btree.h b/ccan/btree/btree.h new file mode 100644 index 00000000..babfea76 --- /dev/null +++ b/ccan/btree/btree.h @@ -0,0 +1,238 @@ +/* + Copyright (c) 2010 Joseph A. Adams + All rights reserved. + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions + are met: + 1. Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + 2. Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + 3. The name of the author may not be used to endorse or promote products + derived from this software without specific prior written permission. + + THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +#ifndef CCAN_BTREE_H +#define CCAN_BTREE_H + +/* +Note: The following should work but are not well-tested yet: + +btree_walk... +btree_cmp_iters +*/ + +#include +#include + +/* + * Maximum number of items per node. + * The maximum number of branches is BTREE_ITEM_MAX + 1. + */ +#define BTREE_ITEM_MAX 20 + +struct btree_node { + struct btree_node *parent; + + /* Number of items (rather than branches). */ + unsigned char count; + + /* 0 if node is a leaf, 1 if it has leaf children, etc. */ + unsigned char depth; + + /* node->parent->branch[node->k] == this */ + unsigned char k; + + const void *item[BTREE_ITEM_MAX]; + + /* + * Allocated to BTREE_ITEM_MAX+1 items if this is + * an internal node, 0 items if it is a leaf. + */ + struct btree_node *branch[]; +}; + +typedef struct btree_iterator_s { + struct btree *btree; + struct btree_node *node; + unsigned int k; + + /* + * The relationship between item and (node, k) depends on what function + * set it. It is mainly for convenience. + */ + void *item; +} btree_iterator[1]; + +/* + * Instead of a compare function, this library accepts a binary search function + * to know how to order the items. + */ +typedef unsigned int btree_search_proto( + const void *key, + const void * const *base, + unsigned int count, + int lr, + int *found +); +typedef btree_search_proto *btree_search_t; + +/* + * Callback used by btree_delete() and btree_walk...(). + * + * If it returns 0, it causes btree_walk...() to stop traversing and return 0. + * Thus, in normal circumstances, this callback should return 1. + * + * Callback shall not insert/remove items from the btree being traversed, + * nor shall anything modify it during a walk. + */ +typedef int (*btree_action_t)(void *item, void *ctx); + +struct btree { + struct btree_node *root; + size_t count; /* Total number of items in B-tree */ + + btree_search_t search; + + /* + * These are set to NULL by default. + * + * When destroy is not NULL, it is called on each item in order when + * btree_delete() is called. + * + * When destroy is NULL, btree_delete runs faster because it does not have + * to visit each and every item. + */ + btree_action_t destroy; + void *destroy_ctx; +}; + +struct btree *btree_new(btree_search_t search); +void btree_delete(struct btree *btree); + + +/* lr must be 0 or 1, nothing else. */ +int btree_begin_end_lr(const struct btree *btree, btree_iterator iter, int lr); +int btree_find_lr(const struct btree *btree, const void *key, + btree_iterator iter, int lr); + +int btree_walk_backward(const struct btree *btree, + btree_action_t action, void *ctx); +int btree_walk_forward(const struct btree *btree, + btree_action_t action, void *ctx); + +#define btree_begin(btree, iter) btree_begin_end_lr(btree, iter, 0) +#define btree_end(btree, iter) btree_begin_end_lr(btree, iter, 1) + +int btree_prev(btree_iterator iter); +int btree_next(btree_iterator iter); + +#define btree_walk(btree, action, ctx) btree_walk_forward(btree, action, ctx) + +/* + * If key was found, btree_find_first will return 1, iter->item will be the + * first matching item, and iter will point to the beginning of the matching + * items. + * + * If key was not found, btree_find_first will return 0, iter->item will be + * undefined, and iter will point to where the key should go if inserted. + */ +#define btree_find_first(btree, key, iter) btree_find_lr(btree, key, iter, 0) + +/* + * If key was found, btree_find_last will return 1, iter->item will be the + * last matching item, and iter will point to the end of the matching + * items. + * + * If key was not found, btree_find_last will return 0, iter->item will be + * undefined, and iter will point to where the key should go if inserted. + */ +#define btree_find_last(btree, key, iter) btree_find_lr(btree, key, iter, 1) + +/* btree_find is an alias of btree_find_first. */ +#define btree_find(btree, key, iter) btree_find_first(btree, key, iter) + +/* + * If iter points to an item, btree_deref returns 1 and sets iter->item to the + * item it points to. + * + * Otherwise (if iter points to the end of the btree), btree_deref returns 0 + * and leaves iter untouched. + */ +int btree_deref(btree_iterator iter); + +/* + * Inserts the item before the one pointed to by iter. + * + * Insertion invalidates all iterators to the btree, including the one + * passed to btree_insert_at. Nevertheless, iter->item will be set to + * the item inserted. + */ +void btree_insert_at(btree_iterator iter, const void *item); + +/* + * Removes the item pointed to by iter. Returns 1 if iter pointed + * to an item. Returns 0 if iter pointed to the end, in which case + * it leaves iter intact. + * + * Removal invalidates all iterators to the btree, including the one + * passed to btree_remove_at. Nevertheless, iter->item will be set to + * the item removed. + */ +int btree_remove_at(btree_iterator iter); + +/* + * Compares positions of two iterators. + * + * Returns -1 if a is before b, 0 if a is at the same position as b, + * and +1 if a is after b. + */ +int btree_cmp_iters(const btree_iterator iter_a, const btree_iterator iter_b); + +#define btree_search_implement(name, type, setup, equals, lessthan) \ +unsigned int name(const void *__key, \ + const void * const *__base, unsigned int __count, \ + int __lr, int *__found) \ +{ \ + unsigned int __start = 0; \ + while (__count) { \ + unsigned int __middle = __count >> 1; \ + type a = (type)__key; \ + type b = (type)__base[__start + __middle]; \ + { \ + setup; \ + if (equals) \ + goto __equals; \ + if (lessthan) \ + goto __lessthan; \ + } \ + __greaterthan: \ + __start += __middle + 1; \ + __count -= __middle + 1; \ + continue; \ + __equals: \ + *__found = 1; \ + if (__lr) \ + goto __greaterthan; \ + /* else, fall through to __lessthan */ \ + __lessthan: \ + __count = __middle; \ + continue; \ + } \ + return __start; \ +} + +#endif /* #ifndef CCAN_BTREE_H */