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 245