Lines Matching refs:geo
135 static void dec_key(struct btree_geo *geo, unsigned long *key) in dec_key() argument
140 for (i = geo->keylen - 1; i >= 0; i--) { in dec_key()
148 static unsigned long *bkey(struct btree_geo *geo, unsigned long *node, int n) in bkey() argument
150 return &node[n * geo->keylen]; in bkey()
153 static void *bval(struct btree_geo *geo, unsigned long *node, int n) in bval() argument
155 return (void *)node[geo->no_longs + n]; in bval()
158 static void setkey(struct btree_geo *geo, unsigned long *node, int n, in setkey() argument
161 longcpy(bkey(geo, node, n), key, geo->keylen); in setkey()
164 static void setval(struct btree_geo *geo, unsigned long *node, int n, in setval() argument
167 node[geo->no_longs + n] = (unsigned long) val; in setval()
170 static void clearpair(struct btree_geo *geo, unsigned long *node, int n) in clearpair() argument
172 longset(bkey(geo, node, n), 0, geo->keylen); in clearpair()
173 node[geo->no_longs + n] = 0; in clearpair()
206 void *btree_last(struct btree_head *head, struct btree_geo *geo, in btree_last() argument
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()
229 static int keyzero(struct btree_geo *geo, unsigned long *key) in keyzero() argument
233 for (i = 0; i < geo->keylen; i++) in keyzero()
240 void *btree_lookup(struct btree_head *head, struct btree_geo *geo, in btree_lookup() argument
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()
270 int btree_update(struct btree_head *head, struct btree_geo *geo, in btree_update() argument
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()
285 node = bval(geo, node, i); 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()
310 void *btree_get_prev(struct btree_head *head, struct btree_geo *geo, in btree_get_prev() argument
315 unsigned long *retry_key = NULL, key[geo->keylen]; in btree_get_prev()
317 if (keyzero(geo, __key)) in btree_get_prev()
322 longcpy(key, __key, geo->keylen); in btree_get_prev()
324 dec_key(geo, key); 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()
354 longcpy(key, retry_key, geo->keylen); in btree_get_prev()
362 static int getpos(struct btree_geo *geo, unsigned long *node, in getpos() argument
367 for (i = 0; i < geo->no_pairs; i++) { in getpos()
368 if (keycmp(geo, node, i, key) <= 0) in getpos()
374 static int getfill(struct btree_geo *geo, unsigned long *node, int start) in getfill() argument
378 for (i = start; i < geo->no_pairs; i++) in getfill()
379 if (!bval(geo, node, i)) in getfill()
387 static unsigned long *find_level(struct btree_head *head, struct btree_geo *geo, in find_level() argument
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()
403 setkey(geo, node, i, key); in find_level()
406 node = bval(geo, node, i); in find_level()
412 static int btree_grow(struct btree_head *head, struct btree_geo *geo, in btree_grow() argument
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()
431 static void btree_shrink(struct btree_head *head, struct btree_geo *geo) in btree_shrink() argument
440 fill = getfill(geo, node, 0); in btree_shrink()
442 head->node = bval(geo, node, 0); in btree_shrink()
447 static int btree_insert_level(struct btree_head *head, struct btree_geo *geo, in btree_insert_level() argument
456 err = btree_grow(head, geo, gfp); in btree_insert_level()
462 node = find_level(head, geo, key, level); in btree_insert_level()
463 pos = getpos(geo, node, key); in btree_insert_level()
464 fill = getfill(geo, node, pos); in btree_insert_level()
466 BUG_ON(pos < fill && keycmp(geo, node, pos, key) == 0); in btree_insert_level()
468 if (fill == geo->no_pairs) { in btree_insert_level()
475 err = btree_insert_level(head, geo, in btree_insert_level()
476 bkey(geo, node, fill / 2 - 1), 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()
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()
503 setkey(geo, node, pos, key); in btree_insert_level()
504 setval(geo, node, pos, val); in btree_insert_level()
509 int btree_insert(struct btree_head *head, struct btree_geo *geo, in btree_insert() argument
513 return btree_insert_level(head, geo, key, val, 1, gfp); in btree_insert()
517 static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo,
519 static void merge(struct btree_head *head, struct btree_geo *geo, int level, in merge() argument
528 setkey(geo, left, lfill + i, bkey(geo, right, i)); in merge()
529 setval(geo, left, lfill + i, bval(geo, right, i)); in merge()
532 setval(geo, parent, lpos, right); in merge()
533 setval(geo, parent, lpos + 1, left); in merge()
535 btree_remove_level(head, geo, bkey(geo, parent, lpos), level + 1); in merge()
539 static void rebalance(struct btree_head *head, struct btree_geo *geo, in rebalance() argument
550 btree_remove_level(head, geo, key, level + 1); in rebalance()
555 parent = find_level(head, geo, key, level + 1); in rebalance()
556 i = getpos(geo, parent, key); in rebalance()
557 BUG_ON(bval(geo, parent, i) != child); in rebalance()
560 left = bval(geo, parent, i - 1); in rebalance()
561 no_left = getfill(geo, left, 0); in rebalance()
562 if (fill + no_left <= geo->no_pairs) { in rebalance()
563 merge(head, geo, level, in rebalance()
570 if (i + 1 < getfill(geo, parent, i)) { in rebalance()
571 right = bval(geo, parent, i + 1); in rebalance()
572 no_right = getfill(geo, right, 0); in rebalance()
573 if (fill + no_right <= geo->no_pairs) { in rebalance()
574 merge(head, geo, level, in rebalance()
590 static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo, in btree_remove_level() argument
604 node = find_level(head, geo, key, level); in btree_remove_level()
605 pos = getpos(geo, node, key); in btree_remove_level()
606 fill = getfill(geo, node, pos); in btree_remove_level()
607 if ((level == 1) && (keycmp(geo, node, pos, key) != 0)) in btree_remove_level()
609 ret = bval(geo, node, pos); in btree_remove_level()
613 setkey(geo, node, i, bkey(geo, node, i + 1)); in btree_remove_level()
614 setval(geo, node, i, bval(geo, node, i + 1)); in btree_remove_level()
616 clearpair(geo, node, fill - 1); in btree_remove_level()
618 if (fill - 1 < geo->no_pairs / 2) { in btree_remove_level()
620 rebalance(head, geo, key, level, node, fill - 1); in btree_remove_level()
622 btree_shrink(head, geo); in btree_remove_level()
628 void *btree_remove(struct btree_head *head, struct btree_geo *geo, in btree_remove() argument
634 return btree_remove_level(head, geo, key, 1); in btree_remove()
639 struct btree_geo *geo, gfp_t gfp) in btree_merge() argument
641 unsigned long key[geo->keylen]; in btree_merge()
642 unsigned long dup[geo->keylen]; in btree_merge()
660 if (!btree_last(victim, geo, key)) in btree_merge()
662 val = btree_lookup(victim, geo, key); in btree_merge()
663 err = btree_insert(target, geo, key, val, gfp); in btree_merge()
668 longcpy(dup, key, geo->keylen); in btree_merge()
669 btree_remove(victim, geo, dup); in btree_merge()
675 static size_t __btree_for_each(struct btree_head *head, struct btree_geo *geo, in __btree_for_each() argument
685 for (i = 0; i < geo->no_pairs; i++) { in __btree_for_each()
686 child = bval(geo, node, i); in __btree_for_each()
690 count = __btree_for_each(head, geo, child, opaque, in __btree_for_each()
693 func(child, opaque, bkey(geo, node, i), count++, in __btree_for_each()
745 size_t btree_visitor(struct btree_head *head, struct btree_geo *geo, in btree_visitor() argument
757 count = __btree_for_each(head, geo, head->node, opaque, func, in btree_visitor()
763 size_t btree_grim_visitor(struct btree_head *head, struct btree_geo *geo, in btree_grim_visitor() argument
775 count = __btree_for_each(head, geo, head->node, opaque, func, in btree_grim_visitor()