include/linux/btree.h

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