include/linux/btree.h

   1 #ifndef BTREE_H
   2 #define BTREE_H
   3
   4 #include <linux/kernel.h>
   5 #include <linux/mempool.h>
   6
   7 /**
   8  * DOC: B+Tree basics
   9  *
  10  * A B+Tree is a data structure for looking up arbitrary (currently allowing
  11  * unsigned long, u32, u64 and 2 * u64) keys into pointers. The data structure
  12  * is described at http://en.wikipedia.org/wiki/B-tree, we currently do not
  13  * use binary search to find the key on lookups.
  14  *
  15  * Each B+Tree consists of a head, that contains bookkeeping information and
  16  * a variable number (starting with zero) nodes. Each node contains the keys
  17  * and pointers to sub-nodes, or, for leaf nodes, the keys and values for the
  18  * tree entries.
  19  *
  20  * Each node in this implementation has the following layout:
  21  * [key1, key2, ..., keyN] [val1, val2, ..., valN]
  22  *
  23  * Each key here is an array of unsigned longs, geo->no_longs in total. The
  24  * number of keys and values (N) is geo->no_pairs.
  25  */
  26
  27 /**
  28  * struct btree_head - btree head
  29  *
  30  * @node: the first node in the tree
  31  * @mempool: mempool used for node allocations
  32  * @height: current of the tree
  33  */
  34 struct btree_head {
  35         unsigned long *node;
  36         mempool_t *mempool;
  37         int height;
  38 };
  39
  40 /* btree geometry */
  41 struct btree_geo;
  42
  43 /**
  44  * btree_alloc - allocate function for the mempool
  45  * @gfp_mask: gfp mask for the allocation
  46  * @pool_data: unused
  47  */
  48 void *btree_alloc(gfp_t gfp_mask, void *pool_data);
  49
  50 /**
  51  * btree_free - free function for the mempool
  52  * @element: the element to free
  53  * @pool_data: unused
  54  */
  55 void btree_free(void *element, void *pool_data);
  56
  57 /**
  58  * btree_init_mempool - initialise a btree with given mempool
  59  *
  60  * @head: the btree head to initialise
  61  * @mempool: the mempool to use
  62  *
  63  * When this function is used, there is no need to destroy
  64  * the mempool.
  65  */
  66 void btree_init_mempool(struct btree_head *head, mempool_t *mempool);
  67
  68 /**
  69  * btree_init - initialise a btree
  70  *
  71  * @head: the btree head to initialise
  72  *
  73  * This function allocates the memory pool that the
  74  * btree needs. Returns zero or a negative error code
  75  * (-%ENOMEM) when memory allocation fails.
  76  *
  77  */
  78 int __must_check btree_init(struct btree_head *head);
  79
  80 /**
  81  * btree_destroy - destroy mempool
  82  *
  83  * @head: the btree head to destroy
  84  *
  85  * This function destroys the internal memory pool, use only
  86  * when using btree_init(), not with btree_init_mempool().
  87  */
  88 void btree_destroy(struct btree_head *head);
  89
  90 /**
  91  * btree_lookup - look up a key in the btree
  92  *
  93  * @head: the btree to look in
  94  * @geo: the btree geometry
  95  * @key: the key to look up
  96  *
  97  * This function returns the value for the given key, or %NULL.
  98  */
  99 void *btree_lookup(struct btree_head *head, struct btree_geo *geo,
 100                    unsigned long *key);
 101
 102 /**
 103  * btree_insert - insert an entry into the btree
 104  *
 105  * @head: the btree to add to
 106  * @geo: the btree geometry
 107  * @key: the key to add (must not already be present)
 108  * @val: the value to add (must not be %NULL)
 109  * @gfp: allocation flags for node allocations
 110  *
 111  * This function returns 0 if the item could be added, or an
 112  * error code if it failed (may fail due to memory pressure).
 113  */
 114 int __must_check btree_insert(struct btree_head *head, struct btree_geo *geo,
 115                               unsigned long *key, void *val, gfp_t gfp);
 116 /**
 117  * btree_update - update an entry in the btree
 118  *
 119  * @head: the btree to update
 120  * @geo: the btree geometry
 121  * @key: the key to update
 122  * @val: the value to change it to (must not be %NULL)
 123  *
 124  * This function returns 0 if the update was successful, or
 125  * -%ENOENT if the key could not be found.
 126  */
 127 int btree_update(struct btree_head *head, struct btree_geo *geo,
 128                  unsigned long *key, void *val);
 129 /**
 130  * btree_remove - remove an entry from the btree
 131  *
 132  * @head: the btree to update
 133  * @geo: the btree geometry
 134  * @key: the key to remove
 135  *
 136  * This function returns the removed entry, or %NULL if the key
 137  * could not be found.
 138  */
 139 void *btree_remove(struct btree_head *head, struct btree_geo *geo,
 140                    unsigned long *key);
 141
 142 /**
 143  * btree_merge - merge two btrees
 144  *
 145  * @target: the tree that gets all the entries
 146  * @victim: the tree that gets merged into @target
 147  * @geo: the btree geometry
 148  * @gfp: allocation flags
 149  *
 150  * The two trees @target and @victim may not contain the same keys,
 151  * that is a bug and triggers a BUG(). This function returns zero
 152  * if the trees were merged successfully, and may return a failure
 153  * when memory allocation fails, in which case both trees might have
 154  * been partially merged, i.e. some entries have been moved from
 155  * @victim to @target.
 156  */
 157 int btree_merge(struct btree_head *target, struct btree_head *victim,
 158                 struct btree_geo *geo, gfp_t gfp);
 159
 160 /**
 161  * btree_last - get last entry in btree
 162  *
 163  * @head: btree head
 164  * @geo: btree geometry
 165  * @key: last key
 166  *
 167  * Returns the last entry in the btree, and sets @key to the key
 168  * of that entry; returns NULL if the tree is empty, in that case
 169  * key is not changed.
 170  */
 171 void *btree_last(struct btree_head *head, struct btree_geo *geo,
 172                  unsigned long *key);
 173
 174 /**
 175  * btree_get_prev - get previous entry
 176  *
 177  * @head: btree head
 178  * @geo: btree geometry
 179  * @key: pointer to key
 180  *
 181  * The function returns the next item right before the value pointed to by
 182  * @key, and updates @key with its key, or returns %NULL when there is no
 183  * entry with a key smaller than the given key.
 184  */
 185 void *btree_get_prev(struct btree_head *head, struct btree_geo *geo,
 186                      unsigned long *key);
 187
 188
 189 /* internal use, use btree_visitor{l,32,64,128} */
 190 size_t btree_visitor(struct btree_head *head, struct btree_geo *geo,
 191                      unsigned long opaque,
 192                      void (*func)(void *elem, unsigned long opaque,
 193                                   unsigned long *key, size_t index,
 194                                   void *func2),
 195                      void *func2);
 196
 197 /* internal use, use btree_grim_visitor{l,32,64,128} */
 198 size_t btree_grim_visitor(struct btree_head *head, struct btree_geo *geo,
 199                           unsigned long opaque,
 200                           void (*func)(void *elem, unsigned long opaque,
 201                                        unsigned long *key,
 202                                        size_t index, void *func2),
 203                           void *func2);
 204
 205
 206 #include <linux/btree-128.h>
 207
 208 extern struct btree_geo btree_geo32;
 209 #define BTREE_TYPE_SUFFIX l
 210 #define BTREE_TYPE_BITS BITS_PER_LONG
 211 #define BTREE_TYPE_GEO &btree_geo32
 212 #define BTREE_KEYTYPE unsigned long
 213 #include <linux/btree-type.h>
 214
 215 #define btree_for_each_safel(head, key, val)    \
 216         for (val = btree_lastl(head, &key);     \
 217              val;                               \
 218              val = btree_get_prevl(head, &key))
 219
 220 #define BTREE_TYPE_SUFFIX 32
 221 #define BTREE_TYPE_BITS 32
 222 #define BTREE_TYPE_GEO &btree_geo32
 223 #define BTREE_KEYTYPE u32
 224 #include <linux/btree-type.h>
 225
 226 #define btree_for_each_safe32(head, key, val)   \
 227         for (val = btree_last32(head, &key);    \
 228              val;                               \
 229              val = btree_get_prev32(head, &key))
 230
 231 extern struct btree_geo btree_geo64;
 232 #define BTREE_TYPE_SUFFIX 64
 233 #define BTREE_TYPE_BITS 64
 234 #define BTREE_TYPE_GEO &btree_geo64
 235 #define BTREE_KEYTYPE u64
 236 #include <linux/btree-type.h>
 237
 238 #define btree_for_each_safe64(head, key, val)   \
 239         for (val = btree_last64(head, &key);    \
 240              val;                               \
 241              val = btree_get_prev64(head, &key))
 242
 243 #endif