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 */ 34 struct btree_head { 35 unsigned long *node; 36 mempool_t *mempool; 37 int height; 38 }; 39 40 /* btree geometry */ 41 struct 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 */ 48 void *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 */ 55 void 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 */ 66 void 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 */ 78 int __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 */ 88 void 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 */ 99 void *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 */ 114 int __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 */ 127 int 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 */ 139 void *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 */ 157 int 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 */ 171 void *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 */ 185 void *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} */ 190 size_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} */ 198 size_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 208 extern 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 231 extern 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