Lines Matching +full:child +full:- +full:node
1 // SPDX-License-Identifier: GPL-2.0-only
3 * lib/btree.c - Simple In-memory B+Tree
5 * Copyright (c) 2007-2008 Joern Engel <joern@purestorage.com>
9 * see http://programming.kicks-ass.net/kernel-patches/vma_lookup/btree.patch
16 * well is that access to a random tree node is much faster than a large number
17 * of operations within each node.
27 * ~98% pointers - hard to beat. Very sparse radix trees contain only ~2%
35 * values are to the right, not to the left. All used slots within a node
94 unsigned long *node; in btree_node_alloc() local
96 node = mempool_alloc(head->mempool, gfp); in btree_node_alloc()
97 if (likely(node)) in btree_node_alloc()
98 memset(node, 0, NODESIZE); in btree_node_alloc()
99 return node; in btree_node_alloc()
108 return -1; in longcmp()
139 for (i = geo->keylen - 1; i >= 0; i--) { in dec_key()
141 key[i] = val - 1; in dec_key()
147 static unsigned long *bkey(struct btree_geo *geo, unsigned long *node, int n) in bkey() argument
149 return &node[n * geo->keylen]; in bkey()
152 static void *bval(struct btree_geo *geo, unsigned long *node, int n) in bval() argument
154 return (void *)node[geo->no_longs + n]; in bval()
157 static void setkey(struct btree_geo *geo, unsigned long *node, int n, in setkey() argument
160 longcpy(bkey(geo, node, n), key, geo->keylen); in setkey()
163 static void setval(struct btree_geo *geo, unsigned long *node, int n, in setval() argument
166 node[geo->no_longs + n] = (unsigned long) val; in setval()
169 static void clearpair(struct btree_geo *geo, unsigned long *node, int n) in clearpair() argument
171 longset(bkey(geo, node, n), 0, geo->keylen); in clearpair()
172 node[geo->no_longs + n] = 0; in clearpair()
177 head->node = NULL; in __btree_init()
178 head->height = 0; in __btree_init()
184 head->mempool = mempool; in btree_init_mempool()
191 head->mempool = mempool_create(0, btree_alloc, btree_free, NULL); in btree_init()
192 if (!head->mempool) in btree_init()
193 return -ENOMEM; in btree_init()
200 mempool_free(head->node, head->mempool); in btree_destroy()
201 mempool_destroy(head->mempool); in btree_destroy()
202 head->mempool = NULL; in btree_destroy()
209 int height = head->height; in btree_last()
210 unsigned long *node = head->node; in btree_last() local
215 for ( ; height > 1; height--) in btree_last()
216 node = bval(geo, node, 0); in btree_last()
218 longcpy(key, bkey(geo, node, 0), geo->keylen); in btree_last()
219 return bval(geo, node, 0); in btree_last()
223 static int keycmp(struct btree_geo *geo, unsigned long *node, int pos, in keycmp() argument
226 return longcmp(bkey(geo, node, pos), key, geo->keylen); in keycmp()
233 for (i = 0; i < geo->keylen; i++) in keyzero()
243 int i, height = head->height; in btree_lookup_node()
244 unsigned long *node = head->node; in btree_lookup_node() local
249 for ( ; height > 1; height--) { in btree_lookup_node()
250 for (i = 0; i < geo->no_pairs; i++) in btree_lookup_node()
251 if (keycmp(geo, node, i, key) <= 0) in btree_lookup_node()
253 if (i == geo->no_pairs) in btree_lookup_node()
255 node = bval(geo, node, i); in btree_lookup_node()
256 if (!node) in btree_lookup_node()
259 return node; in btree_lookup_node()
266 unsigned long *node; in btree_lookup() local
268 node = btree_lookup_node(head, geo, key); in btree_lookup()
269 if (!node) in btree_lookup()
272 for (i = 0; i < geo->no_pairs; i++) in btree_lookup()
273 if (keycmp(geo, node, i, key) == 0) in btree_lookup()
274 return bval(geo, node, i); in btree_lookup()
283 unsigned long *node; in btree_update() local
285 node = btree_lookup_node(head, geo, key); in btree_update()
286 if (!node) in btree_update()
287 return -ENOENT; in btree_update()
289 for (i = 0; i < geo->no_pairs; i++) in btree_update()
290 if (keycmp(geo, node, i, key) == 0) { in btree_update()
291 setval(geo, node, i, val); in btree_update()
294 return -ENOENT; in btree_update()
300 * a parent node may be smaller than the smallest key of all its siblings.
310 unsigned long *node, *oldnode; in btree_get_prev() local
316 if (head->height == 0) in btree_get_prev()
318 longcpy(key, __key, geo->keylen); in btree_get_prev()
322 node = head->node; in btree_get_prev()
323 for (height = head->height ; height > 1; height--) { in btree_get_prev()
324 for (i = 0; i < geo->no_pairs; i++) in btree_get_prev()
325 if (keycmp(geo, node, i, key) <= 0) in btree_get_prev()
327 if (i == geo->no_pairs) in btree_get_prev()
329 oldnode = node; in btree_get_prev()
330 node = bval(geo, node, i); in btree_get_prev()
331 if (!node) in btree_get_prev()
336 if (!node) in btree_get_prev()
339 for (i = 0; i < geo->no_pairs; i++) { in btree_get_prev()
340 if (keycmp(geo, node, i, key) <= 0) { in btree_get_prev()
341 if (bval(geo, node, i)) { in btree_get_prev()
342 longcpy(__key, bkey(geo, node, i), geo->keylen); in btree_get_prev()
343 return bval(geo, node, i); in btree_get_prev()
350 longcpy(key, retry_key, geo->keylen); in btree_get_prev()
358 static int getpos(struct btree_geo *geo, unsigned long *node, in getpos() argument
363 for (i = 0; i < geo->no_pairs; i++) { in getpos()
364 if (keycmp(geo, node, i, key) <= 0) in getpos()
370 static int getfill(struct btree_geo *geo, unsigned long *node, int start) in getfill() argument
374 for (i = start; i < geo->no_pairs; i++) in getfill()
375 if (!bval(geo, node, i)) in getfill()
381 * locate the correct leaf node in the btree
386 unsigned long *node = head->node; in find_level() local
389 for (height = head->height; height > level; height--) { in find_level()
390 for (i = 0; i < geo->no_pairs; i++) in find_level()
391 if (keycmp(geo, node, i, key) <= 0) in find_level()
394 if ((i == geo->no_pairs) || !bval(geo, node, i)) { in find_level()
395 /* right-most key is too large, update it */ in find_level()
396 /* FIXME: If the right-most key on higher levels is in find_level()
398 i--; in find_level()
399 setkey(geo, node, i, key); in find_level()
402 node = bval(geo, node, i); in find_level()
404 BUG_ON(!node); in find_level()
405 return node; in find_level()
411 unsigned long *node; in btree_grow() local
414 node = btree_node_alloc(head, gfp); in btree_grow()
415 if (!node) in btree_grow()
416 return -ENOMEM; in btree_grow()
417 if (head->node) { in btree_grow()
418 fill = getfill(geo, head->node, 0); in btree_grow()
419 setkey(geo, node, 0, bkey(geo, head->node, fill - 1)); in btree_grow()
420 setval(geo, node, 0, head->node); in btree_grow()
422 head->node = node; in btree_grow()
423 head->height++; in btree_grow()
429 unsigned long *node; in btree_shrink() local
432 if (head->height <= 1) in btree_shrink()
435 node = head->node; in btree_shrink()
436 fill = getfill(geo, node, 0); in btree_shrink()
438 head->node = bval(geo, node, 0); in btree_shrink()
439 head->height--; in btree_shrink()
440 mempool_free(node, head->mempool); in btree_shrink()
447 unsigned long *node; in btree_insert_level() local
451 if (head->height < level) { in btree_insert_level()
458 node = find_level(head, geo, key, level); in btree_insert_level()
459 pos = getpos(geo, node, key); in btree_insert_level()
460 fill = getfill(geo, node, pos); in btree_insert_level()
462 BUG_ON(pos < fill && keycmp(geo, node, pos, key) == 0); in btree_insert_level()
464 if (fill == geo->no_pairs) { in btree_insert_level()
465 /* need to split node */ in btree_insert_level()
470 return -ENOMEM; in btree_insert_level()
472 bkey(geo, node, fill / 2 - 1), in btree_insert_level()
475 mempool_free(new, head->mempool); in btree_insert_level()
479 setkey(geo, new, i, bkey(geo, node, i)); in btree_insert_level()
480 setval(geo, new, i, bval(geo, node, i)); in btree_insert_level()
481 setkey(geo, node, i, bkey(geo, node, i + fill / 2)); in btree_insert_level()
482 setval(geo, node, i, bval(geo, node, i + fill / 2)); in btree_insert_level()
483 clearpair(geo, node, i + fill / 2); in btree_insert_level()
486 setkey(geo, node, i, bkey(geo, node, fill - 1)); in btree_insert_level()
487 setval(geo, node, i, bval(geo, node, fill - 1)); in btree_insert_level()
488 clearpair(geo, node, fill - 1); in btree_insert_level()
492 BUG_ON(fill >= geo->no_pairs); in btree_insert_level()
495 for (i = fill; i > pos; i--) { in btree_insert_level()
496 setkey(geo, node, i, bkey(geo, node, i - 1)); in btree_insert_level()
497 setval(geo, node, i, bval(geo, node, i - 1)); in btree_insert_level()
499 setkey(geo, node, pos, key); in btree_insert_level()
500 setval(geo, node, pos, val); in btree_insert_level()
527 /* Exchange left and right child in parent */ in merge()
530 /* Remove left (formerly right) child from parent */ in merge()
532 mempool_free(right, head->mempool); in merge()
536 unsigned long *key, int level, unsigned long *child, int fill) in rebalance() argument
543 * can happen. Parent node contains a single child, this in rebalance()
544 * node, so merging with a sibling never happens. in rebalance()
547 mempool_free(child, head->mempool); in rebalance()
553 BUG_ON(bval(geo, parent, i) != child); in rebalance()
556 left = bval(geo, parent, i - 1); in rebalance()
558 if (fill + no_left <= geo->no_pairs) { in rebalance()
561 child, fill, in rebalance()
562 parent, i - 1); in rebalance()
569 if (fill + no_right <= geo->no_pairs) { in rebalance()
571 child, fill, in rebalance()
589 unsigned long *node; in btree_remove_level() local
593 if (level > head->height) { in btree_remove_level()
595 head->height = 0; in btree_remove_level()
596 head->node = NULL; in btree_remove_level()
600 node = find_level(head, geo, key, level); in btree_remove_level()
601 pos = getpos(geo, node, key); in btree_remove_level()
602 fill = getfill(geo, node, pos); in btree_remove_level()
603 if ((level == 1) && (keycmp(geo, node, pos, key) != 0)) in btree_remove_level()
605 ret = bval(geo, node, pos); in btree_remove_level()
608 for (i = pos; i < fill - 1; i++) { in btree_remove_level()
609 setkey(geo, node, i, bkey(geo, node, i + 1)); in btree_remove_level()
610 setval(geo, node, i, bval(geo, node, i + 1)); in btree_remove_level()
612 clearpair(geo, node, fill - 1); in btree_remove_level()
614 if (fill - 1 < geo->no_pairs / 2) { in btree_remove_level()
615 if (level < head->height) in btree_remove_level()
616 rebalance(head, geo, key, level, node, fill - 1); in btree_remove_level()
617 else if (fill - 1 == 1) in btree_remove_level()
627 if (head->height == 0) in btree_remove()
644 if (!(target->node)) { in btree_merge()
646 target->node = victim->node; in btree_merge()
647 target->height = victim->height; in btree_merge()
664 longcpy(dup, key, geo->keylen); in btree_merge()
672 unsigned long *node, unsigned long opaque, in __btree_for_each() argument
679 unsigned long *child; in __btree_for_each() local
681 for (i = 0; i < geo->no_pairs; i++) { in __btree_for_each()
682 child = bval(geo, node, i); in __btree_for_each()
683 if (!child) in __btree_for_each()
686 count = __btree_for_each(head, geo, child, opaque, in __btree_for_each()
687 func, func2, reap, height - 1, count); in __btree_for_each()
689 func(child, opaque, bkey(geo, node, i), count++, in __btree_for_each()
693 mempool_free(node, head->mempool); in __btree_for_each()
752 if (head->node) in btree_visitor()
753 count = __btree_for_each(head, geo, head->node, opaque, func, in btree_visitor()
754 func2, 0, head->height, 0); in btree_visitor()
770 if (head->node) in btree_grim_visitor()
771 count = __btree_for_each(head, geo, head->node, opaque, func, in btree_grim_visitor()
772 func2, 1, head->height, 0); in btree_grim_visitor()