245 lines · c
1/* SPDX-License-Identifier: GPL-2.0 */2#ifndef BTREE_H3#define BTREE_H4 5#include <linux/kernel.h>6#include <linux/mempool.h>7 8/**9 * DOC: B+Tree basics10 *11 * A B+Tree is a data structure for looking up arbitrary (currently allowing12 * unsigned long, u32, u64 and 2 * u64) keys into pointers. The data structure13 * is described at https://en.wikipedia.org/wiki/B-tree, we currently do not14 * use binary search to find the key on lookups.15 *16 * Each B+Tree consists of a head, that contains bookkeeping information and17 * a variable number (starting with zero) nodes. Each node contains the keys18 * and pointers to sub-nodes, or, for leaf nodes, the keys and values for the19 * 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. The25 * number of keys and values (N) is geo->no_pairs.26 */27 28/**29 * struct btree_head - btree head30 *31 * @node: the first node in the tree32 * @mempool: mempool used for node allocations33 * @height: current of the tree34 */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 mempool46 * @gfp_mask: gfp mask for the allocation47 * @pool_data: unused48 */49void *btree_alloc(gfp_t gfp_mask, void *pool_data);50 51/**52 * btree_free - free function for the mempool53 * @element: the element to free54 * @pool_data: unused55 */56void btree_free(void *element, void *pool_data);57 58/**59 * btree_init_mempool - initialise a btree with given mempool60 *61 * @head: the btree head to initialise62 * @mempool: the mempool to use63 *64 * When this function is used, there is no need to destroy65 * the mempool.66 */67void btree_init_mempool(struct btree_head *head, mempool_t *mempool);68 69/**70 * btree_init - initialise a btree71 *72 * @head: the btree head to initialise73 *74 * This function allocates the memory pool that the75 * btree needs. Returns zero or a negative error code76 * (-%ENOMEM) when memory allocation fails.77 *78 */79int __must_check btree_init(struct btree_head *head);80 81/**82 * btree_destroy - destroy mempool83 *84 * @head: the btree head to destroy85 *86 * This function destroys the internal memory pool, use only87 * 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 btree93 *94 * @head: the btree to look in95 * @geo: the btree geometry96 * @key: the key to look up97 *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 btree105 *106 * @head: the btree to add to107 * @geo: the btree geometry108 * @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 allocations111 *112 * This function returns 0 if the item could be added, or an113 * 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 btree119 *120 * @head: the btree to update121 * @geo: the btree geometry122 * @key: the key to update123 * @val: the value to change it to (must not be %NULL)124 *125 * This function returns 0 if the update was successful, or126 * -%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 btree132 *133 * @head: the btree to update134 * @geo: the btree geometry135 * @key: the key to remove136 *137 * This function returns the removed entry, or %NULL if the key138 * 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 btrees145 *146 * @target: the tree that gets all the entries147 * @victim: the tree that gets merged into @target148 * @geo: the btree geometry149 * @gfp: allocation flags150 *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 zero153 * if the trees were merged successfully, and may return a failure154 * when memory allocation fails, in which case both trees might have155 * been partially merged, i.e. some entries have been moved from156 * @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 btree163 *164 * @head: btree head165 * @geo: btree geometry166 * @key: last key167 *168 * Returns the last entry in the btree, and sets @key to the key169 * of that entry; returns NULL if the tree is empty, in that case170 * 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 entry177 *178 * @head: btree head179 * @geo: btree geometry180 * @key: pointer to key181 *182 * The function returns the next item right before the value pointed to by183 * @key, and updates @key with its key, or returns %NULL when there is no184 * 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 l211#define BTREE_TYPE_BITS BITS_PER_LONG212#define BTREE_TYPE_GEO &btree_geo32213#define BTREE_KEYTYPE unsigned long214#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 32222#define BTREE_TYPE_BITS 32223#define BTREE_TYPE_GEO &btree_geo32224#define BTREE_KEYTYPE u32225#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 64234#define BTREE_TYPE_BITS 64235#define BTREE_TYPE_GEO &btree_geo64236#define BTREE_KEYTYPE u64237#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#endif245