Branch data Line data Source code
1 : : // SPDX-License-Identifier: GPL-2.0-only
2 : : /*
3 : : * lib/btree.c - Simple In-memory B+Tree
4 : : *
5 : : * Copyright (c) 2007-2008 Joern Engel <joern@purestorage.com>
6 : : * Bits and pieces stolen from Peter Zijlstra's code, which is
7 : : * Copyright 2007, Red Hat Inc. Peter Zijlstra
8 : : *
9 : : * see http://programming.kicks-ass.net/kernel-patches/vma_lookup/btree.patch
10 : : *
11 : : * A relatively simple B+Tree implementation. I have written it as a learning
12 : : * exercise to understand how B+Trees work. Turned out to be useful as well.
13 : : *
14 : : * B+Trees can be used similar to Linux radix trees (which don't have anything
15 : : * in common with textbook radix trees, beware). Prerequisite for them working
16 : : * well is that access to a random tree node is much faster than a large number
17 : : * of operations within each node.
18 : : *
19 : : * Disks have fulfilled the prerequisite for a long time. More recently DRAM
20 : : * has gained similar properties, as memory access times, when measured in cpu
21 : : * cycles, have increased. Cacheline sizes have increased as well, which also
22 : : * helps B+Trees.
23 : : *
24 : : * Compared to radix trees, B+Trees are more efficient when dealing with a
25 : : * sparsely populated address space. Between 25% and 50% of the memory is
26 : : * occupied with valid pointers. When densely populated, radix trees contain
27 : : * ~98% pointers - hard to beat. Very sparse radix trees contain only ~2%
28 : : * pointers.
29 : : *
30 : : * This particular implementation stores pointers identified by a long value.
31 : : * Storing NULL pointers is illegal, lookup will return NULL when no entry
32 : : * was found.
33 : : *
34 : : * A tricks was used that is not commonly found in textbooks. The lowest
35 : : * values are to the right, not to the left. All used slots within a node
36 : : * are on the left, all unused slots contain NUL values. Most operations
37 : : * simply loop once over all slots and terminate on the first NUL.
38 : : */
39 : :
40 : : #include <linux/btree.h>
41 : : #include <linux/cache.h>
42 : : #include <linux/kernel.h>
43 : : #include <linux/slab.h>
44 : : #include <linux/module.h>
45 : :
46 : : #define MAX(a, b) ((a) > (b) ? (a) : (b))
47 : : #define NODESIZE MAX(L1_CACHE_BYTES, 128)
48 : :
49 : : struct btree_geo {
50 : : int keylen;
51 : : int no_pairs;
52 : : int no_longs;
53 : : };
54 : :
55 : : struct btree_geo btree_geo32 = {
56 : : .keylen = 1,
57 : : .no_pairs = NODESIZE / sizeof(long) / 2,
58 : : .no_longs = NODESIZE / sizeof(long) / 2,
59 : : };
60 : : EXPORT_SYMBOL_GPL(btree_geo32);
61 : :
62 : : #define LONG_PER_U64 (64 / BITS_PER_LONG)
63 : : struct btree_geo btree_geo64 = {
64 : : .keylen = LONG_PER_U64,
65 : : .no_pairs = NODESIZE / sizeof(long) / (1 + LONG_PER_U64),
66 : : .no_longs = LONG_PER_U64 * (NODESIZE / sizeof(long) / (1 + LONG_PER_U64)),
67 : : };
68 : : EXPORT_SYMBOL_GPL(btree_geo64);
69 : :
70 : : struct btree_geo btree_geo128 = {
71 : : .keylen = 2 * LONG_PER_U64,
72 : : .no_pairs = NODESIZE / sizeof(long) / (1 + 2 * LONG_PER_U64),
73 : : .no_longs = 2 * LONG_PER_U64 * (NODESIZE / sizeof(long) / (1 + 2 * LONG_PER_U64)),
74 : : };
75 : : EXPORT_SYMBOL_GPL(btree_geo128);
76 : :
77 : : #define MAX_KEYLEN (2 * LONG_PER_U64)
78 : :
79 : : static struct kmem_cache *btree_cachep;
80 : :
81 : 0 : void *btree_alloc(gfp_t gfp_mask, void *pool_data)
82 : : {
83 : 0 : return kmem_cache_alloc(btree_cachep, gfp_mask);
84 : : }
85 : : EXPORT_SYMBOL_GPL(btree_alloc);
86 : :
87 : 0 : void btree_free(void *element, void *pool_data)
88 : : {
89 : 0 : kmem_cache_free(btree_cachep, element);
90 : 0 : }
91 : : EXPORT_SYMBOL_GPL(btree_free);
92 : :
93 : 0 : static unsigned long *btree_node_alloc(struct btree_head *head, gfp_t gfp)
94 : : {
95 : : unsigned long *node;
96 : :
97 : 0 : node = mempool_alloc(head->mempool, gfp);
98 [ # # ]: 0 : if (likely(node))
99 : 0 : memset(node, 0, NODESIZE);
100 : 0 : return node;
101 : : }
102 : :
103 : : static int longcmp(const unsigned long *l1, const unsigned long *l2, size_t n)
104 : : {
105 : : size_t i;
106 : :
107 [ # # # # : 0 : for (i = 0; i < n; i++) {
# # # # #
# # # # #
# # # # #
# ]
108 [ # # # # : 0 : if (l1[i] < l2[i])
# # # # #
# # # # #
# # # # #
# ]
109 : : return -1;
110 [ # # # # : 0 : if (l1[i] > l2[i])
# # # # #
# # # # #
# # # # #
# ]
111 : : return 1;
112 : : }
113 : : return 0;
114 : : }
115 : :
116 : : static unsigned long *longcpy(unsigned long *dest, const unsigned long *src,
117 : : size_t n)
118 : : {
119 : : size_t i;
120 : :
121 [ # # # # : 0 : for (i = 0; i < n; i++)
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
122 : 0 : dest[i] = src[i];
123 : : return dest;
124 : : }
125 : :
126 : : static unsigned long *longset(unsigned long *s, unsigned long c, size_t n)
127 : : {
128 : : size_t i;
129 : :
130 [ # # # # : 0 : for (i = 0; i < n; i++)
# # ]
131 : 0 : s[i] = c;
132 : : return s;
133 : : }
134 : :
135 : : static void dec_key(struct btree_geo *geo, unsigned long *key)
136 : : {
137 : : unsigned long val;
138 : : int i;
139 : :
140 [ # # ]: 0 : for (i = geo->keylen - 1; i >= 0; i--) {
141 : 0 : val = key[i];
142 : 0 : key[i] = val - 1;
143 [ # # ]: 0 : if (val)
144 : : break;
145 : : }
146 : : }
147 : :
148 : : static unsigned long *bkey(struct btree_geo *geo, unsigned long *node, int n)
149 : : {
150 : 0 : return &node[n * geo->keylen];
151 : : }
152 : :
153 : : static void *bval(struct btree_geo *geo, unsigned long *node, int n)
154 : : {
155 : 0 : return (void *)node[geo->no_longs + n];
156 : : }
157 : :
158 : : static void setkey(struct btree_geo *geo, unsigned long *node, int n,
159 : : unsigned long *key)
160 : : {
161 : 0 : longcpy(bkey(geo, node, n), key, geo->keylen);
162 : : }
163 : :
164 : : static void setval(struct btree_geo *geo, unsigned long *node, int n,
165 : : void *val)
166 : : {
167 : 0 : node[geo->no_longs + n] = (unsigned long) val;
168 : : }
169 : :
170 : : static void clearpair(struct btree_geo *geo, unsigned long *node, int n)
171 : : {
172 : 0 : longset(bkey(geo, node, n), 0, geo->keylen);
173 : 0 : node[geo->no_longs + n] = 0;
174 : : }
175 : :
176 : : static inline void __btree_init(struct btree_head *head)
177 : : {
178 : 0 : head->node = NULL;
179 : 0 : head->height = 0;
180 : : }
181 : :
182 : 0 : void btree_init_mempool(struct btree_head *head, mempool_t *mempool)
183 : : {
184 : : __btree_init(head);
185 : 0 : head->mempool = mempool;
186 : 0 : }
187 : : EXPORT_SYMBOL_GPL(btree_init_mempool);
188 : :
189 : 0 : int btree_init(struct btree_head *head)
190 : : {
191 : : __btree_init(head);
192 : 0 : head->mempool = mempool_create(0, btree_alloc, btree_free, NULL);
193 [ # # ]: 0 : if (!head->mempool)
194 : : return -ENOMEM;
195 : 0 : return 0;
196 : : }
197 : : EXPORT_SYMBOL_GPL(btree_init);
198 : :
199 : 0 : void btree_destroy(struct btree_head *head)
200 : : {
201 : 0 : mempool_free(head->node, head->mempool);
202 : 0 : mempool_destroy(head->mempool);
203 : 0 : head->mempool = NULL;
204 : 0 : }
205 : : EXPORT_SYMBOL_GPL(btree_destroy);
206 : :
207 : 0 : void *btree_last(struct btree_head *head, struct btree_geo *geo,
208 : : unsigned long *key)
209 : : {
210 : 0 : int height = head->height;
211 : 0 : unsigned long *node = head->node;
212 : :
213 [ # # ]: 0 : if (height == 0)
214 : : return NULL;
215 : :
216 [ # # ]: 0 : for ( ; height > 1; height--)
217 : : node = bval(geo, node, 0);
218 : :
219 : 0 : longcpy(key, bkey(geo, node, 0), geo->keylen);
220 : 0 : return bval(geo, node, 0);
221 : : }
222 : : EXPORT_SYMBOL_GPL(btree_last);
223 : :
224 : : static int keycmp(struct btree_geo *geo, unsigned long *node, int pos,
225 : : unsigned long *key)
226 : : {
227 : 0 : return longcmp(bkey(geo, node, pos), key, geo->keylen);
228 : : }
229 : :
230 : : static int keyzero(struct btree_geo *geo, unsigned long *key)
231 : : {
232 : : int i;
233 : :
234 [ # # ]: 0 : for (i = 0; i < geo->keylen; i++)
235 [ # # ]: 0 : if (key[i])
236 : : return 0;
237 : :
238 : : return 1;
239 : : }
240 : :
241 : 0 : void *btree_lookup(struct btree_head *head, struct btree_geo *geo,
242 : : unsigned long *key)
243 : : {
244 : 0 : int i, height = head->height;
245 : 0 : unsigned long *node = head->node;
246 : :
247 [ # # ]: 0 : if (height == 0)
248 : : return NULL;
249 : :
250 [ # # ]: 0 : for ( ; height > 1; height--) {
251 [ # # ]: 0 : for (i = 0; i < geo->no_pairs; i++)
252 [ # # ]: 0 : if (keycmp(geo, node, i, key) <= 0)
253 : : break;
254 [ # # ]: 0 : if (i == geo->no_pairs)
255 : : return NULL;
256 : : node = bval(geo, node, i);
257 [ # # ]: 0 : if (!node)
258 : : return NULL;
259 : : }
260 : :
261 [ # # ]: 0 : if (!node)
262 : : return NULL;
263 : :
264 [ # # ]: 0 : for (i = 0; i < geo->no_pairs; i++)
265 [ # # ]: 0 : if (keycmp(geo, node, i, key) == 0)
266 : 0 : return bval(geo, node, i);
267 : : return NULL;
268 : : }
269 : : EXPORT_SYMBOL_GPL(btree_lookup);
270 : :
271 : 0 : int btree_update(struct btree_head *head, struct btree_geo *geo,
272 : : unsigned long *key, void *val)
273 : : {
274 : 0 : int i, height = head->height;
275 : 0 : unsigned long *node = head->node;
276 : :
277 [ # # ]: 0 : if (height == 0)
278 : : return -ENOENT;
279 : :
280 [ # # ]: 0 : for ( ; height > 1; height--) {
281 [ # # ]: 0 : for (i = 0; i < geo->no_pairs; i++)
282 [ # # ]: 0 : if (keycmp(geo, node, i, key) <= 0)
283 : : break;
284 [ # # ]: 0 : if (i == geo->no_pairs)
285 : : return -ENOENT;
286 : : node = bval(geo, node, i);
287 [ # # ]: 0 : if (!node)
288 : : return -ENOENT;
289 : : }
290 : :
291 [ # # ]: 0 : if (!node)
292 : : return -ENOENT;
293 : :
294 [ # # ]: 0 : for (i = 0; i < geo->no_pairs; i++)
295 [ # # ]: 0 : if (keycmp(geo, node, i, key) == 0) {
296 : : setval(geo, node, i, val);
297 : 0 : return 0;
298 : : }
299 : : return -ENOENT;
300 : : }
301 : : EXPORT_SYMBOL_GPL(btree_update);
302 : :
303 : : /*
304 : : * Usually this function is quite similar to normal lookup. But the key of
305 : : * a parent node may be smaller than the smallest key of all its siblings.
306 : : * In such a case we cannot just return NULL, as we have only proven that no
307 : : * key smaller than __key, but larger than this parent key exists.
308 : : * So we set __key to the parent key and retry. We have to use the smallest
309 : : * such parent key, which is the last parent key we encountered.
310 : : */
311 : 0 : void *btree_get_prev(struct btree_head *head, struct btree_geo *geo,
312 : : unsigned long *__key)
313 : : {
314 : : int i, height;
315 : : unsigned long *node, *oldnode;
316 : : unsigned long *retry_key = NULL, key[MAX_KEYLEN];
317 : :
318 [ # # ]: 0 : if (keyzero(geo, __key))
319 : : return NULL;
320 : :
321 [ # # ]: 0 : if (head->height == 0)
322 : : return NULL;
323 : 0 : longcpy(key, __key, geo->keylen);
324 : : retry:
325 : : dec_key(geo, key);
326 : :
327 : 0 : node = head->node;
328 [ # # ]: 0 : for (height = head->height ; height > 1; height--) {
329 [ # # ]: 0 : for (i = 0; i < geo->no_pairs; i++)
330 [ # # ]: 0 : if (keycmp(geo, node, i, key) <= 0)
331 : : break;
332 [ # # ]: 0 : if (i == geo->no_pairs)
333 : : goto miss;
334 : : oldnode = node;
335 : : node = bval(geo, node, i);
336 [ # # ]: 0 : if (!node)
337 : : goto miss;
338 : : retry_key = bkey(geo, oldnode, i);
339 : : }
340 : :
341 [ # # ]: 0 : if (!node)
342 : : goto miss;
343 : :
344 [ # # ]: 0 : for (i = 0; i < geo->no_pairs; i++) {
345 [ # # ]: 0 : if (keycmp(geo, node, i, key) <= 0) {
346 [ # # ]: 0 : if (bval(geo, node, i)) {
347 : : longcpy(__key, bkey(geo, node, i), geo->keylen);
348 : 0 : return bval(geo, node, i);
349 : : } else
350 : : goto miss;
351 : : }
352 : : }
353 : : miss:
354 [ # # ]: 0 : if (retry_key) {
355 : : longcpy(key, retry_key, geo->keylen);
356 : : retry_key = NULL;
357 : : goto retry;
358 : : }
359 : : return NULL;
360 : : }
361 : : EXPORT_SYMBOL_GPL(btree_get_prev);
362 : :
363 : 0 : static int getpos(struct btree_geo *geo, unsigned long *node,
364 : : unsigned long *key)
365 : : {
366 : : int i;
367 : :
368 [ # # ]: 0 : for (i = 0; i < geo->no_pairs; i++) {
369 [ # # ]: 0 : if (keycmp(geo, node, i, key) <= 0)
370 : : break;
371 : : }
372 : 0 : return i;
373 : : }
374 : :
375 : : static int getfill(struct btree_geo *geo, unsigned long *node, int start)
376 : : {
377 : : int i;
378 : :
379 [ # # # # : 0 : for (i = start; i < geo->no_pairs; i++)
# # # # #
# # # #
# ]
380 [ # # # # : 0 : if (!bval(geo, node, i))
# # # # #
# # # #
# ]
381 : : break;
382 : 0 : return i;
383 : : }
384 : :
385 : : /*
386 : : * locate the correct leaf node in the btree
387 : : */
388 : 0 : static unsigned long *find_level(struct btree_head *head, struct btree_geo *geo,
389 : : unsigned long *key, int level)
390 : : {
391 : 0 : unsigned long *node = head->node;
392 : : int i, height;
393 : :
394 [ # # ]: 0 : for (height = head->height; height > level; height--) {
395 [ # # ]: 0 : for (i = 0; i < geo->no_pairs; i++)
396 [ # # ]: 0 : if (keycmp(geo, node, i, key) <= 0)
397 : : break;
398 : :
399 [ # # # # ]: 0 : if ((i == geo->no_pairs) || !bval(geo, node, i)) {
400 : : /* right-most key is too large, update it */
401 : : /* FIXME: If the right-most key on higher levels is
402 : : * always zero, this wouldn't be necessary. */
403 : 0 : i--;
404 : : setkey(geo, node, i, key);
405 : : }
406 [ # # ]: 0 : BUG_ON(i < 0);
407 : : node = bval(geo, node, i);
408 : : }
409 [ # # ]: 0 : BUG_ON(!node);
410 : 0 : return node;
411 : : }
412 : :
413 : 0 : static int btree_grow(struct btree_head *head, struct btree_geo *geo,
414 : : gfp_t gfp)
415 : : {
416 : : unsigned long *node;
417 : : int fill;
418 : :
419 : 0 : node = btree_node_alloc(head, gfp);
420 [ # # ]: 0 : if (!node)
421 : : return -ENOMEM;
422 [ # # ]: 0 : if (head->node) {
423 : : fill = getfill(geo, head->node, 0);
424 : 0 : setkey(geo, node, 0, bkey(geo, head->node, fill - 1));
425 : 0 : setval(geo, node, 0, head->node);
426 : : }
427 : 0 : head->node = node;
428 : 0 : head->height++;
429 : 0 : return 0;
430 : : }
431 : :
432 : 0 : static void btree_shrink(struct btree_head *head, struct btree_geo *geo)
433 : : {
434 : : unsigned long *node;
435 : : int fill;
436 : :
437 [ # # ]: 0 : if (head->height <= 1)
438 : 0 : return;
439 : :
440 : 0 : node = head->node;
441 : : fill = getfill(geo, node, 0);
442 [ # # ]: 0 : BUG_ON(fill > 1);
443 : 0 : head->node = bval(geo, node, 0);
444 : 0 : head->height--;
445 : 0 : mempool_free(node, head->mempool);
446 : : }
447 : :
448 : 0 : static int btree_insert_level(struct btree_head *head, struct btree_geo *geo,
449 : : unsigned long *key, void *val, int level,
450 : : gfp_t gfp)
451 : : {
452 : : unsigned long *node;
453 : : int i, pos, fill, err;
454 : :
455 [ # # ]: 0 : BUG_ON(!val);
456 [ # # ]: 0 : if (head->height < level) {
457 : 0 : err = btree_grow(head, geo, gfp);
458 [ # # ]: 0 : if (err)
459 : : return err;
460 : : }
461 : :
462 : : retry:
463 : 0 : node = find_level(head, geo, key, level);
464 : 0 : pos = getpos(geo, node, key);
465 : : fill = getfill(geo, node, pos);
466 : : /* two identical keys are not allowed */
467 [ # # # # ]: 0 : BUG_ON(pos < fill && keycmp(geo, node, pos, key) == 0);
468 : :
469 [ # # ]: 0 : if (fill == geo->no_pairs) {
470 : : /* need to split node */
471 : : unsigned long *new;
472 : :
473 : 0 : new = btree_node_alloc(head, gfp);
474 [ # # ]: 0 : if (!new)
475 : : return -ENOMEM;
476 : 0 : err = btree_insert_level(head, geo,
477 : 0 : bkey(geo, node, fill / 2 - 1),
478 : : new, level + 1, gfp);
479 [ # # ]: 0 : if (err) {
480 : 0 : mempool_free(new, head->mempool);
481 : 0 : return err;
482 : : }
483 [ # # ]: 0 : for (i = 0; i < fill / 2; i++) {
484 : : setkey(geo, new, i, bkey(geo, node, i));
485 : : setval(geo, new, i, bval(geo, node, i));
486 : 0 : setkey(geo, node, i, bkey(geo, node, i + fill / 2));
487 : : setval(geo, node, i, bval(geo, node, i + fill / 2));
488 : : clearpair(geo, node, i + fill / 2);
489 : : }
490 [ # # ]: 0 : if (fill & 1) {
491 : 0 : setkey(geo, node, i, bkey(geo, node, fill - 1));
492 : : setval(geo, node, i, bval(geo, node, fill - 1));
493 : : clearpair(geo, node, fill - 1);
494 : : }
495 : : goto retry;
496 : : }
497 [ # # ]: 0 : BUG_ON(fill >= geo->no_pairs);
498 : :
499 : : /* shift and insert */
500 [ # # ]: 0 : for (i = fill; i > pos; i--) {
501 : 0 : setkey(geo, node, i, bkey(geo, node, i - 1));
502 : : setval(geo, node, i, bval(geo, node, i - 1));
503 : : }
504 : : setkey(geo, node, pos, key);
505 : : setval(geo, node, pos, val);
506 : :
507 : 0 : return 0;
508 : : }
509 : :
510 : 0 : int btree_insert(struct btree_head *head, struct btree_geo *geo,
511 : : unsigned long *key, void *val, gfp_t gfp)
512 : : {
513 [ # # ]: 0 : BUG_ON(!val);
514 : 0 : return btree_insert_level(head, geo, key, val, 1, gfp);
515 : : }
516 : : EXPORT_SYMBOL_GPL(btree_insert);
517 : :
518 : : static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo,
519 : : unsigned long *key, int level);
520 : 0 : static void merge(struct btree_head *head, struct btree_geo *geo, int level,
521 : : unsigned long *left, int lfill,
522 : : unsigned long *right, int rfill,
523 : : unsigned long *parent, int lpos)
524 : : {
525 : : int i;
526 : :
527 [ # # ]: 0 : for (i = 0; i < rfill; i++) {
528 : : /* Move all keys to the left */
529 : 0 : setkey(geo, left, lfill + i, bkey(geo, right, i));
530 : : setval(geo, left, lfill + i, bval(geo, right, i));
531 : : }
532 : : /* Exchange left and right child in parent */
533 : : setval(geo, parent, lpos, right);
534 : 0 : setval(geo, parent, lpos + 1, left);
535 : : /* Remove left (formerly right) child from parent */
536 : 0 : btree_remove_level(head, geo, bkey(geo, parent, lpos), level + 1);
537 : 0 : mempool_free(right, head->mempool);
538 : 0 : }
539 : :
540 : 0 : static void rebalance(struct btree_head *head, struct btree_geo *geo,
541 : : unsigned long *key, int level, unsigned long *child, int fill)
542 : : {
543 : : unsigned long *parent, *left = NULL, *right = NULL;
544 : : int i, no_left, no_right;
545 : :
546 [ # # ]: 0 : if (fill == 0) {
547 : : /* Because we don't steal entries from a neighbour, this case
548 : : * can happen. Parent node contains a single child, this
549 : : * node, so merging with a sibling never happens.
550 : : */
551 : 0 : btree_remove_level(head, geo, key, level + 1);
552 : 0 : mempool_free(child, head->mempool);
553 : 0 : return;
554 : : }
555 : :
556 : 0 : parent = find_level(head, geo, key, level + 1);
557 : 0 : i = getpos(geo, parent, key);
558 [ # # ]: 0 : BUG_ON(bval(geo, parent, i) != child);
559 : :
560 [ # # ]: 0 : if (i > 0) {
561 : 0 : left = bval(geo, parent, i - 1);
562 : : no_left = getfill(geo, left, 0);
563 [ # # ]: 0 : if (fill + no_left <= geo->no_pairs) {
564 : 0 : merge(head, geo, level,
565 : : left, no_left,
566 : : child, fill,
567 : : parent, i - 1);
568 : 0 : return;
569 : : }
570 : : }
571 [ # # ]: 0 : if (i + 1 < getfill(geo, parent, i)) {
572 : : right = bval(geo, parent, i + 1);
573 : : no_right = getfill(geo, right, 0);
574 [ # # ]: 0 : if (fill + no_right <= geo->no_pairs) {
575 : 0 : merge(head, geo, level,
576 : : child, fill,
577 : : right, no_right,
578 : : parent, i);
579 : 0 : return;
580 : : }
581 : : }
582 : : /*
583 : : * We could also try to steal one entry from the left or right
584 : : * neighbor. By not doing so we changed the invariant from
585 : : * "all nodes are at least half full" to "no two neighboring
586 : : * nodes can be merged". Which means that the average fill of
587 : : * all nodes is still half or better.
588 : : */
589 : : }
590 : :
591 : 0 : static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo,
592 : : unsigned long *key, int level)
593 : : {
594 : : unsigned long *node;
595 : : int i, pos, fill;
596 : : void *ret;
597 : :
598 [ # # ]: 0 : if (level > head->height) {
599 : : /* we recursed all the way up */
600 : 0 : head->height = 0;
601 : 0 : head->node = NULL;
602 : 0 : return NULL;
603 : : }
604 : :
605 : 0 : node = find_level(head, geo, key, level);
606 : 0 : pos = getpos(geo, node, key);
607 : : fill = getfill(geo, node, pos);
608 [ # # # # ]: 0 : if ((level == 1) && (keycmp(geo, node, pos, key) != 0))
609 : : return NULL;
610 : : ret = bval(geo, node, pos);
611 : :
612 : : /* remove and shift */
613 [ # # ]: 0 : for (i = pos; i < fill - 1; i++) {
614 : 0 : setkey(geo, node, i, bkey(geo, node, i + 1));
615 : : setval(geo, node, i, bval(geo, node, i + 1));
616 : : }
617 : 0 : clearpair(geo, node, fill - 1);
618 : :
619 [ # # ]: 0 : if (fill - 1 < geo->no_pairs / 2) {
620 [ # # ]: 0 : if (level < head->height)
621 : 0 : rebalance(head, geo, key, level, node, fill - 1);
622 [ # # ]: 0 : else if (fill - 1 == 1)
623 : 0 : btree_shrink(head, geo);
624 : : }
625 : :
626 : 0 : return ret;
627 : : }
628 : :
629 : 0 : void *btree_remove(struct btree_head *head, struct btree_geo *geo,
630 : : unsigned long *key)
631 : : {
632 [ # # # # ]: 0 : if (head->height == 0)
633 : : return NULL;
634 : :
635 : 0 : return btree_remove_level(head, geo, key, 1);
636 : : }
637 : : EXPORT_SYMBOL_GPL(btree_remove);
638 : :
639 : 0 : int btree_merge(struct btree_head *target, struct btree_head *victim,
640 : : struct btree_geo *geo, gfp_t gfp)
641 : : {
642 : : unsigned long key[MAX_KEYLEN];
643 : : unsigned long dup[MAX_KEYLEN];
644 : : void *val;
645 : : int err;
646 : :
647 [ # # ]: 0 : BUG_ON(target == victim);
648 : :
649 [ # # ]: 0 : if (!(target->node)) {
650 : : /* target is empty, just copy fields over */
651 : 0 : target->node = victim->node;
652 : 0 : target->height = victim->height;
653 : : __btree_init(victim);
654 : 0 : return 0;
655 : : }
656 : :
657 : : /* TODO: This needs some optimizations. Currently we do three tree
658 : : * walks to remove a single object from the victim.
659 : : */
660 : : for (;;) {
661 [ # # ]: 0 : if (!btree_last(victim, geo, key))
662 : : break;
663 : 0 : val = btree_lookup(victim, geo, key);
664 : 0 : err = btree_insert(target, geo, key, val, gfp);
665 [ # # ]: 0 : if (err)
666 : 0 : return err;
667 : : /* We must make a copy of the key, as the original will get
668 : : * mangled inside btree_remove. */
669 : 0 : longcpy(dup, key, geo->keylen);
670 : : btree_remove(victim, geo, dup);
671 : : }
672 : : return 0;
673 : : }
674 : : EXPORT_SYMBOL_GPL(btree_merge);
675 : :
676 : 0 : static size_t __btree_for_each(struct btree_head *head, struct btree_geo *geo,
677 : : unsigned long *node, unsigned long opaque,
678 : : void (*func)(void *elem, unsigned long opaque,
679 : : unsigned long *key, size_t index,
680 : : void *func2),
681 : : void *func2, int reap, int height, size_t count)
682 : : {
683 : : int i;
684 : : unsigned long *child;
685 : :
686 [ # # ]: 0 : for (i = 0; i < geo->no_pairs; i++) {
687 : : child = bval(geo, node, i);
688 [ # # ]: 0 : if (!child)
689 : : break;
690 [ # # ]: 0 : if (height > 1)
691 : 0 : count = __btree_for_each(head, geo, child, opaque,
692 : : func, func2, reap, height - 1, count);
693 : : else
694 : 0 : func(child, opaque, bkey(geo, node, i), count++,
695 : : func2);
696 : : }
697 [ # # ]: 0 : if (reap)
698 : 0 : mempool_free(node, head->mempool);
699 : 0 : return count;
700 : : }
701 : :
702 : 0 : static void empty(void *elem, unsigned long opaque, unsigned long *key,
703 : : size_t index, void *func2)
704 : : {
705 : 0 : }
706 : :
707 : 0 : void visitorl(void *elem, unsigned long opaque, unsigned long *key,
708 : : size_t index, void *__func)
709 : : {
710 : 0 : visitorl_t func = __func;
711 : :
712 : 0 : func(elem, opaque, *key, index);
713 : 0 : }
714 : : EXPORT_SYMBOL_GPL(visitorl);
715 : :
716 : 0 : void visitor32(void *elem, unsigned long opaque, unsigned long *__key,
717 : : size_t index, void *__func)
718 : : {
719 : 0 : visitor32_t func = __func;
720 : : u32 *key = (void *)__key;
721 : :
722 : 0 : func(elem, opaque, *key, index);
723 : 0 : }
724 : : EXPORT_SYMBOL_GPL(visitor32);
725 : :
726 : 0 : void visitor64(void *elem, unsigned long opaque, unsigned long *__key,
727 : : size_t index, void *__func)
728 : : {
729 : 0 : visitor64_t func = __func;
730 : : u64 *key = (void *)__key;
731 : :
732 : 0 : func(elem, opaque, *key, index);
733 : 0 : }
734 : : EXPORT_SYMBOL_GPL(visitor64);
735 : :
736 : 0 : void visitor128(void *elem, unsigned long opaque, unsigned long *__key,
737 : : size_t index, void *__func)
738 : : {
739 : 0 : visitor128_t func = __func;
740 : : u64 *key = (void *)__key;
741 : :
742 : 0 : func(elem, opaque, key[0], key[1], index);
743 : 0 : }
744 : : EXPORT_SYMBOL_GPL(visitor128);
745 : :
746 : 0 : size_t btree_visitor(struct btree_head *head, struct btree_geo *geo,
747 : : unsigned long opaque,
748 : : void (*func)(void *elem, unsigned long opaque,
749 : : unsigned long *key,
750 : : size_t index, void *func2),
751 : : void *func2)
752 : : {
753 : : size_t count = 0;
754 : :
755 [ # # ]: 0 : if (!func2)
756 : : func = empty;
757 [ # # ]: 0 : if (head->node)
758 : 0 : count = __btree_for_each(head, geo, head->node, opaque, func,
759 : : func2, 0, head->height, 0);
760 : 0 : return count;
761 : : }
762 : : EXPORT_SYMBOL_GPL(btree_visitor);
763 : :
764 : 0 : size_t btree_grim_visitor(struct btree_head *head, struct btree_geo *geo,
765 : : unsigned long opaque,
766 : : void (*func)(void *elem, unsigned long opaque,
767 : : unsigned long *key,
768 : : size_t index, void *func2),
769 : : void *func2)
770 : : {
771 : : size_t count = 0;
772 : :
773 [ # # ]: 0 : if (!func2)
774 : : func = empty;
775 [ # # ]: 0 : if (head->node)
776 : 0 : count = __btree_for_each(head, geo, head->node, opaque, func,
777 : : func2, 1, head->height, 0);
778 : : __btree_init(head);
779 : 0 : return count;
780 : : }
781 : : EXPORT_SYMBOL_GPL(btree_grim_visitor);
782 : :
783 : 207 : static int __init btree_module_init(void)
784 : : {
785 : 207 : btree_cachep = kmem_cache_create("btree_node", NODESIZE, 0,
786 : : SLAB_HWCACHE_ALIGN, NULL);
787 : 207 : return 0;
788 : : }
789 : :
790 : 0 : static void __exit btree_module_exit(void)
791 : : {
792 : 0 : kmem_cache_destroy(btree_cachep);
793 : 0 : }
794 : :
795 : : /* If core code starts using btree, initialization should happen even earlier */
796 : : module_init(btree_module_init);
797 : : module_exit(btree_module_exit);
798 : :
799 : : MODULE_AUTHOR("Joern Engel <joern@logfs.org>");
800 : : MODULE_AUTHOR("Johannes Berg <johannes@sipsolutions.net>");
801 : : MODULE_LICENSE("GPL");
|
