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()
245 unsigned long *node = head->node; in btree_lookup()
250 for ( ; height > 1; height--) { in btree_lookup()
251 for (i = 0; i < geo->no_pairs; i++) in btree_lookup()
254 if (i == geo->no_pairs) in btree_lookup()
264 for (i = 0; i < geo->no_pairs; i++) in btree_lookup()
274 int i, height = head->height; in btree_update()
275 unsigned long *node = head->node; in btree_update()
278 return -ENOENT; in btree_update()
280 for ( ; height > 1; height--) { in btree_update()
281 for (i = 0; i < geo->no_pairs; i++) in btree_update()
284 if (i == geo->no_pairs) in btree_update()
285 return -ENOENT; in btree_update()
288 return -ENOENT; in btree_update()
292 return -ENOENT; in btree_update()
294 for (i = 0; i < geo->no_pairs; i++) in btree_update()
299 return -ENOENT; in btree_update()
321 if (head->height == 0) in btree_get_prev()
323 longcpy(key, __key, geo->keylen); in btree_get_prev()
327 node = head->node; in btree_get_prev()
328 for (height = head->height ; height > 1; height--) { in btree_get_prev()
329 for (i = 0; i < geo->no_pairs; i++) in btree_get_prev()
332 if (i == geo->no_pairs) in btree_get_prev()
344 for (i = 0; i < geo->no_pairs; i++) { in btree_get_prev()
347 longcpy(__key, bkey(geo, node, i), geo->keylen); in btree_get_prev()
355 longcpy(key, retry_key, geo->keylen); in btree_get_prev()
368 for (i = 0; i < geo->no_pairs; i++) { in getpos()
379 for (i = start; i < geo->no_pairs; i++) in getfill()
391 unsigned long *node = head->node; in find_level()
394 for (height = head->height; height > level; height--) { in find_level()
395 for (i = 0; i < geo->no_pairs; i++) in find_level()
399 if ((i == geo->no_pairs) || !bval(geo, node, i)) { in find_level()
400 /* right-most key is too large, update it */ in find_level()
401 /* FIXME: If the right-most key on higher levels is in find_level()
403 i--; in find_level()
421 return -ENOMEM; in btree_grow()
422 if (head->node) { in btree_grow()
423 fill = getfill(geo, head->node, 0); in btree_grow()
424 setkey(geo, node, 0, bkey(geo, head->node, fill - 1)); in btree_grow()
425 setval(geo, node, 0, head->node); in btree_grow()
427 head->node = node; in btree_grow()
428 head->height++; in btree_grow()
437 if (head->height <= 1) in btree_shrink()
440 node = head->node; in btree_shrink()
443 head->node = bval(geo, node, 0); in btree_shrink()
444 head->height--; in btree_shrink()
445 mempool_free(node, head->mempool); in btree_shrink()
456 if (head->height < level) { in btree_insert_level()
469 if (fill == geo->no_pairs) { in btree_insert_level()
475 return -ENOMEM; in btree_insert_level()
477 bkey(geo, node, fill / 2 - 1), in btree_insert_level()
480 mempool_free(new, head->mempool); in btree_insert_level()
491 setkey(geo, node, i, bkey(geo, node, fill - 1)); in btree_insert_level()
492 setval(geo, node, i, bval(geo, node, fill - 1)); in btree_insert_level()
493 clearpair(geo, node, fill - 1); in btree_insert_level()
497 BUG_ON(fill >= geo->no_pairs); in btree_insert_level()
500 for (i = fill; i > pos; i--) { in btree_insert_level()
501 setkey(geo, node, i, bkey(geo, node, i - 1)); in btree_insert_level()
502 setval(geo, node, i, bval(geo, node, i - 1)); in btree_insert_level()
521 unsigned long *left, int lfill, in merge() argument
528 /* Move all keys to the left */ in merge()
529 setkey(geo, left, lfill + i, bkey(geo, right, i)); in merge()
530 setval(geo, left, lfill + i, bval(geo, right, i)); in merge()
532 /* Exchange left and right child in parent */ in merge()
534 setval(geo, parent, lpos + 1, left); in merge()
535 /* Remove left (formerly right) child from parent */ in merge()
537 mempool_free(right, head->mempool); in merge()
543 unsigned long *parent, *left = NULL, *right = NULL; in rebalance() local
552 mempool_free(child, head->mempool); in rebalance()
561 left = bval(geo, parent, i - 1); in rebalance()
562 no_left = getfill(geo, left, 0); in rebalance()
563 if (fill + no_left <= geo->no_pairs) { in rebalance()
565 left, no_left, in rebalance()
567 parent, i - 1); in rebalance()
574 if (fill + no_right <= geo->no_pairs) { in rebalance()
583 * We could also try to steal one entry from the left or right in rebalance()
598 if (level > head->height) { in btree_remove_level()
600 head->height = 0; in btree_remove_level()
601 head->node = NULL; in btree_remove_level()
613 for (i = pos; i < fill - 1; i++) { in btree_remove_level()
617 clearpair(geo, node, fill - 1); in btree_remove_level()
619 if (fill - 1 < geo->no_pairs / 2) { in btree_remove_level()
620 if (level < head->height) in btree_remove_level()
621 rebalance(head, geo, key, level, node, fill - 1); in btree_remove_level()
622 else if (fill - 1 == 1) in btree_remove_level()
632 if (head->height == 0) in btree_remove()
649 if (!(target->node)) { in btree_merge()
651 target->node = victim->node; in btree_merge()
652 target->height = victim->height; in btree_merge()
669 longcpy(dup, key, geo->keylen); in btree_merge()
686 for (i = 0; i < geo->no_pairs; i++) { in __btree_for_each()
692 func, func2, reap, height - 1, count); in __btree_for_each()
698 mempool_free(node, head->mempool); in __btree_for_each()
757 if (head->node) in btree_visitor()
758 count = __btree_for_each(head, geo, head->node, opaque, func, in btree_visitor()
759 func2, 0, head->height, 0); in btree_visitor()
775 if (head->node) in btree_grim_visitor()
776 count = __btree_for_each(head, geo, head->node, opaque, func, in btree_grim_visitor()
777 func2, 1, head->height, 0); in btree_grim_visitor()