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
97 node = mempool_alloc(head->mempool, gfp); in btree_node_alloc()
109 return -1; in longcmp()
140 for (i = geo->keylen - 1; i >= 0; i--) { in dec_key()
142 key[i] = val - 1; in dec_key()
150 return &node[n * geo->keylen]; in bkey()
155 return (void *)node[geo->no_longs + n]; in bval()
161 longcpy(bkey(geo, node, n), key, geo->keylen); in setkey()
167 node[geo->no_longs + n] = (unsigned long) val; in setval()
172 longset(bkey(geo, node, n), 0, geo->keylen); in clearpair()
173 node[geo->no_longs + n] = 0; in clearpair()
178 head->node = NULL; in __btree_init()
179 head->height = 0; in __btree_init()
185 head->mempool = mempool; in btree_init_mempool()
192 head->mempool = mempool_create(0, btree_alloc, btree_free, NULL); in btree_init()
193 if (!head->mempool) in btree_init()
194 return -ENOMEM; in btree_init()
201 mempool_free(head->node, head->mempool); in btree_destroy()
202 mempool_destroy(head->mempool); in btree_destroy()
203 head->mempool = NULL; in btree_destroy()
210 int height = head->height; in btree_last()
211 unsigned long *node = head->node; in btree_last()
216 for ( ; height > 1; height--) in btree_last()
219 longcpy(key, bkey(geo, node, 0), geo->keylen); in btree_last()
227 return longcmp(bkey(geo, node, pos), key, geo->keylen); in keycmp()
234 for (i = 0; i < geo->keylen; i++) in keyzero()
244 int i, height = head->height; in btree_lookup_node()
245 unsigned long *node = head->node; in btree_lookup_node()
250 for ( ; height > 1; height--) { in btree_lookup_node()
251 for (i = 0; i < geo->no_pairs; i++) in btree_lookup_node()
254 if (i == geo->no_pairs) in btree_lookup_node()
273 for (i = 0; i < geo->no_pairs; i++) in btree_lookup()
288 return -ENOENT; in btree_update()
290 for (i = 0; i < geo->no_pairs; i++) in btree_update()
295 return -ENOENT; in btree_update()
317 if (head->height == 0) in btree_get_prev()
319 longcpy(key, __key, geo->keylen); in btree_get_prev()
323 node = head->node; in btree_get_prev()
324 for (height = head->height ; height > 1; height--) { in btree_get_prev()
325 for (i = 0; i < geo->no_pairs; i++) in btree_get_prev()
328 if (i == geo->no_pairs) in btree_get_prev()
340 for (i = 0; i < geo->no_pairs; i++) { in btree_get_prev()
343 longcpy(__key, bkey(geo, node, i), geo->keylen); in btree_get_prev()
351 longcpy(key, retry_key, geo->keylen); in btree_get_prev()
364 for (i = 0; i < geo->no_pairs; i++) { in getpos()
375 for (i = start; i < geo->no_pairs; i++) in getfill()
387 unsigned long *node = head->node; in find_level()
390 for (height = head->height; height > level; height--) { in find_level()
391 for (i = 0; i < geo->no_pairs; i++) in find_level()
395 if ((i == geo->no_pairs) || !bval(geo, node, i)) { in find_level()
396 /* right-most key is too large, update it */ in find_level()
397 /* FIXME: If the right-most key on higher levels is in find_level()
399 i--; in find_level()
417 return -ENOMEM; in btree_grow()
418 if (head->node) { in btree_grow()
419 fill = getfill(geo, head->node, 0); in btree_grow()
420 setkey(geo, node, 0, bkey(geo, head->node, fill - 1)); in btree_grow()
421 setval(geo, node, 0, head->node); in btree_grow()
423 head->node = node; in btree_grow()
424 head->height++; in btree_grow()
433 if (head->height <= 1) in btree_shrink()
436 node = head->node; in btree_shrink()
439 head->node = bval(geo, node, 0); in btree_shrink()
440 head->height--; in btree_shrink()
441 mempool_free(node, head->mempool); in btree_shrink()
452 if (head->height < level) { in btree_insert_level()
465 if (fill == geo->no_pairs) { in btree_insert_level()
471 return -ENOMEM; in btree_insert_level()
473 bkey(geo, node, fill / 2 - 1), in btree_insert_level()
476 mempool_free(new, head->mempool); in btree_insert_level()
487 setkey(geo, node, i, bkey(geo, node, fill - 1)); in btree_insert_level()
488 setval(geo, node, i, bval(geo, node, fill - 1)); in btree_insert_level()
489 clearpair(geo, node, fill - 1); in btree_insert_level()
493 BUG_ON(fill >= geo->no_pairs); in btree_insert_level()
496 for (i = fill; i > pos; i--) { in btree_insert_level()
497 setkey(geo, node, i, bkey(geo, node, i - 1)); in btree_insert_level()
498 setval(geo, node, i, bval(geo, node, i - 1)); in btree_insert_level()
517 unsigned long *left, int lfill, in merge() argument
524 /* Move all keys to the left */ in merge()
525 setkey(geo, left, lfill + i, bkey(geo, right, i)); in merge()
526 setval(geo, left, lfill + i, bval(geo, right, i)); in merge()
528 /* Exchange left and right child in parent */ in merge()
530 setval(geo, parent, lpos + 1, left); in merge()
531 /* Remove left (formerly right) child from parent */ in merge()
533 mempool_free(right, head->mempool); in merge()
539 unsigned long *parent, *left = NULL, *right = NULL; in rebalance() local
548 mempool_free(child, head->mempool); in rebalance()
557 left = bval(geo, parent, i - 1); in rebalance()
558 no_left = getfill(geo, left, 0); in rebalance()
559 if (fill + no_left <= geo->no_pairs) { in rebalance()
561 left, no_left, in rebalance()
563 parent, i - 1); in rebalance()
570 if (fill + no_right <= geo->no_pairs) { in rebalance()
579 * We could also try to steal one entry from the left or right in rebalance()
594 if (level > head->height) { in btree_remove_level()
596 head->height = 0; in btree_remove_level()
597 head->node = NULL; in btree_remove_level()
609 for (i = pos; i < fill - 1; i++) { in btree_remove_level()
613 clearpair(geo, node, fill - 1); in btree_remove_level()
615 if (fill - 1 < geo->no_pairs / 2) { in btree_remove_level()
616 if (level < head->height) in btree_remove_level()
617 rebalance(head, geo, key, level, node, fill - 1); in btree_remove_level()
618 else if (fill - 1 == 1) in btree_remove_level()
628 if (head->height == 0) in btree_remove()
645 if (!(target->node)) { in btree_merge()
647 target->node = victim->node; in btree_merge()
648 target->height = victim->height; in btree_merge()
665 longcpy(dup, key, geo->keylen); in btree_merge()
682 for (i = 0; i < geo->no_pairs; i++) { in __btree_for_each()
688 func, func2, reap, height - 1, count); in __btree_for_each()
694 mempool_free(node, head->mempool); in __btree_for_each()
753 if (head->node) in btree_visitor()
754 count = __btree_for_each(head, geo, head->node, opaque, func, in btree_visitor()
755 func2, 0, head->height, 0); in btree_visitor()
771 if (head->node) in btree_grim_visitor()
772 count = __btree_for_each(head, geo, head->node, opaque, func, in btree_grim_visitor()
773 func2, 1, head->height, 0); in btree_grim_visitor()