linux/include/linux/btree.h
<<
>>
Prefs
   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 */
  34struct btree_head {
  35        unsigned long *node;
  36        mempool_t *mempool;
  37        int height;
  38};
  39
  40/* btree geometry */
  41struct 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 */
  48void *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 */
  55void 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 */
  66void 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 */
  78int __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 */
  88void 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 */
  99void *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 */
 114int __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 */
 127int 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 */
 139void *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 */
 157int 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 */
 171void *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 */
 185void *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} */
 190size_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} */
 198size_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
 208extern 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
 231extern 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
 244
lxr.linux.no kindly hosted by Redpill Linpro AS, provider of Linux consulting and operations services since 1995.