git.ozlabs.org Git - ccan/blob - 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 */