Lines Matching +full:left +full:- +full:most
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
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
36 * are on the left, all unused slots contain NUL values. Most operations
96 node = mempool_alloc(head->mempool, gfp); 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()
149 return &node[n * geo->keylen]; in bkey()
154 return (void *)node[geo->no_longs + n]; in bval()
160 longcpy(bkey(geo, node, n), key, geo->keylen); in setkey()
166 node[geo->no_longs + n] = (unsigned long) val; in setval()
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()
215 for ( ; height > 1; height--) in btree_last()
218 longcpy(key, bkey(geo, node, 0), geo->keylen); in btree_last()
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()
249 for ( ; height > 1; height--) { in btree_lookup_node()
250 for (i = 0; i < geo->no_pairs; i++) in btree_lookup_node()
253 if (i == geo->no_pairs) in btree_lookup_node()
272 for (i = 0; i < geo->no_pairs; i++) in btree_lookup()
287 return -ENOENT; in btree_update()
289 for (i = 0; i < geo->no_pairs; i++) in btree_update()
294 return -ENOENT; in btree_update()
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()
327 if (i == geo->no_pairs) in btree_get_prev()
339 for (i = 0; i < geo->no_pairs; i++) { in btree_get_prev()
342 longcpy(__key, bkey(geo, node, i), geo->keylen); in btree_get_prev()
350 longcpy(key, retry_key, geo->keylen); in btree_get_prev()
363 for (i = 0; i < geo->no_pairs; i++) { in getpos()
374 for (i = start; i < geo->no_pairs; i++) in getfill()
386 unsigned long *node = head->node; in find_level()
389 for (height = head->height; height > level; height--) { in find_level()
390 for (i = 0; i < geo->no_pairs; i++) 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()
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()
432 if (head->height <= 1) in btree_shrink()
435 node = head->node; 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()
451 if (head->height < level) { in btree_insert_level()
464 if (fill == geo->no_pairs) { 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()
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()
516 unsigned long *left, int lfill, in merge() argument
523 /* Move all keys to the left */ in merge()
524 setkey(geo, left, lfill + i, bkey(geo, right, i)); in merge()
525 setval(geo, left, lfill + i, bval(geo, right, i)); in merge()
527 /* Exchange left and right child in parent */ in merge()
529 setval(geo, parent, lpos + 1, left); in merge()
530 /* Remove left (formerly right) child from parent */ in merge()
532 mempool_free(right, head->mempool); in merge()
538 unsigned long *parent, *left = NULL, *right = NULL; in rebalance() local
547 mempool_free(child, head->mempool); in rebalance()
556 left = bval(geo, parent, i - 1); in rebalance()
557 no_left = getfill(geo, left, 0); in rebalance()
558 if (fill + no_left <= geo->no_pairs) { in rebalance()
560 left, no_left, in rebalance()
562 parent, i - 1); in rebalance()
569 if (fill + no_right <= geo->no_pairs) { in rebalance()
578 * We could also try to steal one entry from the left or right in rebalance()
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()
608 for (i = pos; i < fill - 1; i++) { 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()
681 for (i = 0; i < geo->no_pairs; i++) { in __btree_for_each()
687 func, func2, reap, height - 1, 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()