git.ozlabs.org Git - ccan/blob - ccan/btree/btree.h

   1 /*
   2         Copyright (c) 2010  Joseph A. Adams
   3         All rights reserved.
   4
   5         Redistribution and use in source and binary forms, with or without
   6         modification, are permitted provided that the following conditions
   7         are met:
   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.
  15
  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.
  26 */
  27
  28 #ifndef CCAN_BTREE_H
  29 #define CCAN_BTREE_H
  30
  31 /*
  32 Note:  The following should work but are not well-tested yet:
  33
  34 btree_walk...
  35 btree_cmp_iters
  36 */
  37
  38 #include <stdint.h>
  39 #include <stddef.h>
  40
  41 /*
  42  * Maximum number of items per node.
  43  * The maximum number of branches is BTREE_ITEM_MAX + 1.
  44  */
  45 #define BTREE_ITEM_MAX 20
  46
  47 struct btree_node {
  48         struct btree_node *parent;
  49
  50         /* Number of items (rather than branches). */
  51         unsigned char count;
  52
  53         /* 0 if node is a leaf, 1 if it has leaf children, etc. */
  54         unsigned char depth;
  55
  56         /* node->parent->branch[node->k] == this */
  57         unsigned char k;
  58
  59         const void *item[BTREE_ITEM_MAX];
  60
  61         /*
  62          * Allocated to BTREE_ITEM_MAX+1 items if this is
  63          * an internal node, 0 items if it is a leaf.
  64          */
  65         struct btree_node *branch[];
  66 };
  67
  68 typedef struct btree_iterator_s {
  69         struct btree *btree;
  70         struct btree_node *node;
  71         unsigned int k;
  72
  73         /*
  74          * The relationship between item and (node, k) depends on what function
  75          * set it.  It is mainly for convenience.
  76          */
  77         void *item;
  78 } btree_iterator[1];
  79
  80 /*
  81  * Instead of a compare function, this library accepts a binary search function
  82  * to know how to order the items.
  83  */
  84 typedef unsigned int btree_search_proto(
  85         const void *key,
  86         const void * const *base,
  87         unsigned int count,
  88         int lr,
  89         int *found
  90 );
  91 typedef btree_search_proto *btree_search_t;
  92
  93 /*
  94  * Callback used by btree_delete() and btree_walk...().
  95  *
  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.
  98  *
  99  * Callback shall not insert/remove items from the btree being traversed,
 100  * nor shall anything modify it during a walk.
 101  */
 102 typedef int (*btree_action_t)(void *item, void *ctx);
 103
 104 struct btree {
 105         struct btree_node *root;
 106         size_t count; /* Total number of items in B-tree */
 107
 108         btree_search_t search;
 109
 110         /*
 111          * These are set to NULL by default.
 112          *
 113          * When destroy is not NULL, it is called on each item in order when
 114          * btree_delete() is called.
 115          *
 116          * When destroy is NULL, btree_delete runs faster because it does not have
 117          * to visit each and every item.
 118          */
 119         btree_action_t destroy;
 120         void *destroy_ctx;
 121 };
 122
 123 struct btree *btree_new(btree_search_t search);
 124 void btree_delete(struct btree *btree);
 125
 126
 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);
 131
 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);
 136
 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)
 139
 140 int btree_prev(btree_iterator iter);
 141 int btree_next(btree_iterator iter);
 142
 143 #define btree_walk(btree, action, ctx) btree_walk_forward(btree, action, ctx)
 144
 145 /*
 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
 148  * items.
 149  *
 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.
 152  */
 153 #define btree_find_first(btree, key, iter) btree_find_lr(btree, key, iter, 0)
 154
 155 /*
 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
 158  * items.
 159  *
 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.
 162  */
 163 #define btree_find_last(btree, key, iter) btree_find_lr(btree, key, iter, 1)
 164
 165 /* btree_find is an alias of btree_find_first. */
 166 #define btree_find(btree, key, iter) btree_find_first(btree, key, iter)
 167
 168 /*
 169  * If iter points to an item, btree_deref returns 1 and sets iter->item to the
 170  * item it points to.
 171  *
 172  * Otherwise (if iter points to the end of the btree), btree_deref returns 0
 173  * and leaves iter untouched.
 174  */
 175 int btree_deref(btree_iterator iter);
 176
 177 /*
 178  * Inserts the item before the one pointed to by iter.
 179  *
 180  * Insertion invalidates all iterators to the btree, including the one
 181  * passed to btree_insert_at.  Nevertheless, iter->item will be set to
 182  * the item inserted.
 183  */
 184 void btree_insert_at(btree_iterator iter, const void *item);
 185
 186 /*
 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.
 190  *
 191  * Removal invalidates all iterators to the btree, including the one
 192  * passed to btree_remove_at.  Nevertheless, iter->item will be set to
 193  * the item removed.
 194  */
 195 int btree_remove_at(btree_iterator iter);
 196
 197 /*
 198  * Compares positions of two iterators.
 199  *
 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.
 202  */
 203 int btree_cmp_iters(const btree_iterator iter_a, const btree_iterator iter_b);
 204
 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) \
 209 { \
 210         unsigned int __start = 0; \
 211         while (__count) { \
 212                 unsigned int __middle = __count >> 1; \
 213                 type a = (type)__key; \
 214                 type b = (type)__base[__start + __middle]; \
 215                 { \
 216                         setup; \
 217                         if (equals) \
 218                                 goto __equals; \
 219                         if (lessthan) \
 220                                 goto __lessthan; \
 221                 } \
 222         __greaterthan: \
 223                 __start += __middle + 1; \
 224                 __count -= __middle + 1; \
 225                 continue; \
 226         __equals: \
 227                 *__found = 1; \
 228                 if (__lr) \
 229                         goto __greaterthan; \
 230                 /* else, fall through to __lessthan */ \
 231         __lessthan: \
 232                 __count = __middle; \
 233                 continue; \
 234         } \
 235         return __start; \
 236 }
 237
 238 #endif /* #ifndef CCAN_BTREE_H */