Lines Matching +full:- +full:i
2 * lib/btree.c - Simple In-memory B+Tree
6 * Copyright (c) 2007-2008 Joern Engel <joern@logfs.org>
11 * see http://programming.kicks-ass.net/kernel-patches/vma_lookup/btree.patch
13 * A relatively simple B+Tree implementation. I have written it as a learning
29 * ~98% pointers - hard to beat. Very sparse radix trees contain only ~2%
97 node = mempool_alloc(head->mempool, gfp); in btree_node_alloc()
105 size_t i; in longcmp() local
107 for (i = 0; i < n; i++) { in longcmp()
108 if (l1[i] < l2[i]) in longcmp()
109 return -1; in longcmp()
110 if (l1[i] > l2[i]) in longcmp()
119 size_t i; in longcpy() local
121 for (i = 0; i < n; i++) in longcpy()
122 dest[i] = src[i]; in longcpy()
128 size_t i; in longset() local
130 for (i = 0; i < n; i++) in longset()
131 s[i] = c; in longset()
138 int i; in dec_key() local
140 for (i = geo->keylen - 1; i >= 0; i--) { in dec_key()
141 val = key[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_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()
231 int i; in keyzero() local
233 for (i = 0; i < geo->keylen; i++) in keyzero()
234 if (key[i]) in keyzero()
243 int i, height = head->height; in btree_lookup() local
244 unsigned long *node = head->node; in btree_lookup()
249 for ( ; height > 1; height--) { in btree_lookup()
250 for (i = 0; i < geo->no_pairs; i++) in btree_lookup()
251 if (keycmp(geo, node, i, key) <= 0) in btree_lookup()
253 if (i == geo->no_pairs) in btree_lookup()
255 node = bval(geo, node, i); in btree_lookup()
263 for (i = 0; i < geo->no_pairs; i++) in btree_lookup()
264 if (keycmp(geo, node, i, key) == 0) in btree_lookup()
265 return bval(geo, node, i); in btree_lookup()
273 int i, height = head->height; in btree_update() local
274 unsigned long *node = head->node; in btree_update()
277 return -ENOENT; in btree_update()
279 for ( ; height > 1; height--) { in btree_update()
280 for (i = 0; i < geo->no_pairs; i++) in btree_update()
281 if (keycmp(geo, node, i, key) <= 0) in btree_update()
283 if (i == geo->no_pairs) in btree_update()
284 return -ENOENT; in btree_update()
285 node = bval(geo, node, i); in btree_update()
287 return -ENOENT; in btree_update()
291 return -ENOENT; in btree_update()
293 for (i = 0; i < geo->no_pairs; i++) in btree_update()
294 if (keycmp(geo, node, i, key) == 0) { in btree_update()
295 setval(geo, node, i, val); in btree_update()
298 return -ENOENT; in btree_update()
313 int i, height; in btree_get_prev() local
315 unsigned long *retry_key = NULL, key[geo->keylen]; in btree_get_prev()
320 if (head->height == 0) in btree_get_prev()
323 longcpy(key, __key, geo->keylen); in btree_get_prev()
326 node = head->node; in btree_get_prev()
327 for (height = head->height ; height > 1; height--) { in btree_get_prev()
328 for (i = 0; i < geo->no_pairs; i++) in btree_get_prev()
329 if (keycmp(geo, node, i, key) <= 0) in btree_get_prev()
331 if (i == geo->no_pairs) in btree_get_prev()
334 node = bval(geo, node, i); in btree_get_prev()
337 retry_key = bkey(geo, oldnode, i); in btree_get_prev()
343 for (i = 0; i < geo->no_pairs; i++) { in btree_get_prev()
344 if (keycmp(geo, node, i, key) <= 0) { in btree_get_prev()
345 if (bval(geo, node, i)) { in btree_get_prev()
346 longcpy(__key, bkey(geo, node, i), geo->keylen); in btree_get_prev()
347 return bval(geo, node, i); in btree_get_prev()
365 int i; in getpos() local
367 for (i = 0; i < geo->no_pairs; i++) { in getpos()
368 if (keycmp(geo, node, i, key) <= 0) in getpos()
371 return i; in getpos()
376 int i; in getfill() local
378 for (i = start; i < geo->no_pairs; i++) in getfill()
379 if (!bval(geo, node, i)) in getfill()
381 return i; in getfill()
390 unsigned long *node = head->node; in find_level()
391 int i, height; in find_level() local
393 for (height = head->height; height > level; height--) { in find_level()
394 for (i = 0; i < geo->no_pairs; i++) in find_level()
395 if (keycmp(geo, node, i, key) <= 0) in find_level()
398 if ((i == geo->no_pairs) || !bval(geo, node, i)) { in find_level()
399 /* right-most key is too large, update it */ in find_level()
400 /* FIXME: If the right-most key on higher levels is in find_level()
402 i--; in find_level()
403 setkey(geo, node, i, key); in find_level()
405 BUG_ON(i < 0); in find_level()
406 node = bval(geo, node, i); in find_level()
420 return -ENOMEM; in btree_grow()
421 if (head->node) { in btree_grow()
422 fill = getfill(geo, head->node, 0); in btree_grow()
423 setkey(geo, node, 0, bkey(geo, head->node, fill - 1)); in btree_grow()
424 setval(geo, node, 0, head->node); in btree_grow()
426 head->node = node; in btree_grow()
427 head->height++; in btree_grow()
436 if (head->height <= 1) in btree_shrink()
439 node = head->node; in btree_shrink()
442 head->node = bval(geo, node, 0); in btree_shrink()
443 head->height--; in btree_shrink()
444 mempool_free(node, head->mempool); in btree_shrink()
452 int i, pos, fill, err; in btree_insert_level() local
455 if (head->height < level) { in btree_insert_level()
468 if (fill == geo->no_pairs) { in btree_insert_level()
474 return -ENOMEM; in btree_insert_level()
476 bkey(geo, node, fill / 2 - 1), in btree_insert_level()
479 mempool_free(new, head->mempool); in btree_insert_level()
482 for (i = 0; i < fill / 2; i++) { in btree_insert_level()
483 setkey(geo, new, i, bkey(geo, node, i)); in btree_insert_level()
484 setval(geo, new, i, bval(geo, node, i)); in btree_insert_level()
485 setkey(geo, node, i, bkey(geo, node, i + fill / 2)); in btree_insert_level()
486 setval(geo, node, i, bval(geo, node, i + fill / 2)); in btree_insert_level()
487 clearpair(geo, node, i + fill / 2); in btree_insert_level()
490 setkey(geo, node, i, bkey(geo, node, fill - 1)); in btree_insert_level()
491 setval(geo, node, i, bval(geo, node, fill - 1)); in btree_insert_level()
492 clearpair(geo, node, fill - 1); in btree_insert_level()
496 BUG_ON(fill >= geo->no_pairs); in btree_insert_level()
499 for (i = fill; i > pos; i--) { in btree_insert_level()
500 setkey(geo, node, i, bkey(geo, node, i - 1)); in btree_insert_level()
501 setval(geo, node, i, bval(geo, node, i - 1)); in btree_insert_level()
523 int i; in merge() local
525 for (i = 0; i < rfill; i++) { in merge()
527 setkey(geo, left, lfill + i, bkey(geo, right, i)); in merge()
528 setval(geo, left, lfill + i, bval(geo, right, i)); in merge()
535 mempool_free(right, head->mempool); in merge()
542 int i, no_left, no_right; in rebalance() local
550 mempool_free(child, head->mempool); in rebalance()
555 i = getpos(geo, parent, key); in rebalance()
556 BUG_ON(bval(geo, parent, i) != child); in rebalance()
558 if (i > 0) { in rebalance()
559 left = bval(geo, parent, i - 1); in rebalance()
561 if (fill + no_left <= geo->no_pairs) { in rebalance()
565 parent, i - 1); in rebalance()
569 if (i + 1 < getfill(geo, parent, i)) { in rebalance()
570 right = bval(geo, parent, i + 1); in rebalance()
572 if (fill + no_right <= geo->no_pairs) { in rebalance()
576 parent, i); in rebalance()
593 int i, pos, fill; in btree_remove_level() local
596 if (level > head->height) { in btree_remove_level()
598 head->height = 0; in btree_remove_level()
599 head->node = NULL; in btree_remove_level()
611 for (i = pos; i < fill - 1; i++) { in btree_remove_level()
612 setkey(geo, node, i, bkey(geo, node, i + 1)); in btree_remove_level()
613 setval(geo, node, i, bval(geo, node, i + 1)); in btree_remove_level()
615 clearpair(geo, node, fill - 1); in btree_remove_level()
617 if (fill - 1 < geo->no_pairs / 2) { in btree_remove_level()
618 if (level < head->height) in btree_remove_level()
619 rebalance(head, geo, key, level, node, fill - 1); in btree_remove_level()
620 else if (fill - 1 == 1) in btree_remove_level()
630 if (head->height == 0) in btree_remove()
640 unsigned long key[geo->keylen]; in btree_merge()
641 unsigned long dup[geo->keylen]; in btree_merge()
647 if (!(target->node)) { in btree_merge()
649 target->node = victim->node; in btree_merge()
650 target->height = victim->height; in btree_merge()
667 longcpy(dup, key, geo->keylen); in btree_merge()
681 int i; in __btree_for_each() local
684 for (i = 0; i < geo->no_pairs; i++) { in __btree_for_each()
685 child = bval(geo, node, i); in __btree_for_each()
690 func, func2, reap, height - 1, count); in __btree_for_each()
692 func(child, opaque, bkey(geo, node, i), count++, in __btree_for_each()
696 mempool_free(node, head->mempool); in __btree_for_each()
755 if (head->node) in btree_visitor()
756 count = __btree_for_each(head, geo, head->node, opaque, func, in btree_visitor()
757 func2, 0, head->height, 0); in btree_visitor()
773 if (head->node) in btree_grim_visitor()
774 count = __btree_for_each(head, geo, head->node, opaque, func, in btree_grim_visitor()
775 func2, 1, head->height, 0); in btree_grim_visitor()