linux/include/linux/btree.h
<<
>>
Prefs
   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 http://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 */
  35struct btree_head {
  36        unsigned long *node;
  37        mempool_t *mempool;
  38        int height;
  39};
  40
  41/* btree geometry */
  42struct 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 */
  49void *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 */
  56void 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 */
  67void 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 */
  79int __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 */
  89void 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 */
 100void *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 */
 115int __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 */
 128int 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 */
 140void *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 */
 158int 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 */
 172void *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 */
 186void *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} */
 191size_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} */
 199size_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
 209extern 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
 232extern 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
 245