+/*
+ 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 <stdint.h>
+#include <stddef.h>
+
+/*
+ * 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 */
projects / ccan / blobdiff