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()
207 void *btree_last(struct btree_head *head, struct btree_geo *geo, in btree_last() argument
217 node = bval(geo, node, 0); in btree_last()
219 longcpy(key, bkey(geo, node, 0), geo->keylen); in btree_last()
220 return bval(geo, node, 0); in btree_last()
224 static int keycmp(struct btree_geo *geo, unsigned long *node, int pos, in keycmp() argument
227 return longcmp(bkey(geo, node, pos), key, geo->keylen); in keycmp()
230 static int keyzero(struct btree_geo *geo, unsigned long *key) in keyzero() argument
234 for (i = 0; i < geo->keylen; i++) in keyzero()
241 void *btree_lookup(struct btree_head *head, struct btree_geo *geo, in btree_lookup() argument
251 for (i = 0; i < geo->no_pairs; i++) in btree_lookup()
252 if (keycmp(geo, node, i, key) <= 0) in btree_lookup()
254 if (i == geo->no_pairs) in btree_lookup()
256 node = bval(geo, node, i); in btree_lookup()
264 for (i = 0; i < geo->no_pairs; i++) in btree_lookup()
265 if (keycmp(geo, node, i, key) == 0) in btree_lookup()
266 return bval(geo, node, i); in btree_lookup()
271 int btree_update(struct btree_head *head, struct btree_geo *geo, in btree_update() argument
281 for (i = 0; i < geo->no_pairs; i++) in btree_update()
282 if (keycmp(geo, node, i, key) <= 0) in btree_update()
284 if (i == geo->no_pairs) in btree_update()
286 node = bval(geo, node, i); in btree_update()
294 for (i = 0; i < geo->no_pairs; i++) in btree_update()
295 if (keycmp(geo, node, i, key) == 0) { in btree_update()
296 setval(geo, node, i, val); in btree_update()
311 void *btree_get_prev(struct btree_head *head, struct btree_geo *geo, in btree_get_prev() argument
316 unsigned long *retry_key = NULL, key[geo->keylen]; in btree_get_prev()
318 if (keyzero(geo, __key)) in btree_get_prev()
323 longcpy(key, __key, geo->keylen); in btree_get_prev()
325 dec_key(geo, key); in btree_get_prev()
329 for (i = 0; i < geo->no_pairs; i++) in btree_get_prev()
330 if (keycmp(geo, node, i, key) <= 0) in btree_get_prev()
332 if (i == geo->no_pairs) in btree_get_prev()
335 node = bval(geo, node, i); in btree_get_prev()
338 retry_key = bkey(geo, oldnode, i); in btree_get_prev()
344 for (i = 0; i < geo->no_pairs; i++) { in btree_get_prev()
345 if (keycmp(geo, node, i, key) <= 0) { in btree_get_prev()
346 if (bval(geo, node, i)) { in btree_get_prev()
347 longcpy(__key, bkey(geo, node, i), geo->keylen); in btree_get_prev()
348 return bval(geo, node, i); in btree_get_prev()
355 longcpy(key, retry_key, geo->keylen); in btree_get_prev()
363 static int getpos(struct btree_geo *geo, unsigned long *node, in getpos() argument
368 for (i = 0; i < geo->no_pairs; i++) { in getpos()
369 if (keycmp(geo, node, i, key) <= 0) in getpos()
375 static int getfill(struct btree_geo *geo, unsigned long *node, int start) in getfill() argument
379 for (i = start; i < geo->no_pairs; i++) in getfill()
380 if (!bval(geo, node, i)) in getfill()
388 static unsigned long *find_level(struct btree_head *head, struct btree_geo *geo, in find_level() argument
395 for (i = 0; i < geo->no_pairs; i++) in find_level()
396 if (keycmp(geo, node, i, key) <= 0) in find_level()
399 if ((i == geo->no_pairs) || !bval(geo, node, i)) { in find_level()
404 setkey(geo, node, i, key); in find_level()
407 node = bval(geo, node, i); in find_level()
413 static int btree_grow(struct btree_head *head, struct btree_geo *geo, in btree_grow() argument
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()
432 static void btree_shrink(struct btree_head *head, struct btree_geo *geo) in btree_shrink() argument
441 fill = getfill(geo, node, 0); in btree_shrink()
443 head->node = bval(geo, node, 0); in btree_shrink()
448 static int btree_insert_level(struct btree_head *head, struct btree_geo *geo, in btree_insert_level() argument
457 err = btree_grow(head, geo, gfp); in btree_insert_level()
463 node = find_level(head, geo, key, level); in btree_insert_level()
464 pos = getpos(geo, node, key); in btree_insert_level()
465 fill = getfill(geo, node, pos); in btree_insert_level()
467 BUG_ON(pos < fill && keycmp(geo, node, pos, key) == 0); in btree_insert_level()
469 if (fill == geo->no_pairs) { in btree_insert_level()
476 err = btree_insert_level(head, geo, in btree_insert_level()
477 bkey(geo, node, fill / 2 - 1), in btree_insert_level()
484 setkey(geo, new, i, bkey(geo, node, i)); in btree_insert_level()
485 setval(geo, new, i, bval(geo, node, i)); in btree_insert_level()
486 setkey(geo, node, i, bkey(geo, node, i + fill / 2)); in btree_insert_level()
487 setval(geo, node, i, bval(geo, node, i + fill / 2)); in btree_insert_level()
488 clearpair(geo, node, i + fill / 2); 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()
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()
504 setkey(geo, node, pos, key); in btree_insert_level()
505 setval(geo, node, pos, val); in btree_insert_level()
510 int btree_insert(struct btree_head *head, struct btree_geo *geo, in btree_insert() argument
514 return btree_insert_level(head, geo, key, val, 1, gfp); in btree_insert()
518 static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo,
520 static void merge(struct btree_head *head, struct btree_geo *geo, int level, in merge() argument
529 setkey(geo, left, lfill + i, bkey(geo, right, i)); in merge()
530 setval(geo, left, lfill + i, bval(geo, right, i)); in merge()
533 setval(geo, parent, lpos, right); in merge()
534 setval(geo, parent, lpos + 1, left); in merge()
536 btree_remove_level(head, geo, bkey(geo, parent, lpos), level + 1); in merge()
540 static void rebalance(struct btree_head *head, struct btree_geo *geo, in rebalance() argument
551 btree_remove_level(head, geo, key, level + 1); in rebalance()
556 parent = find_level(head, geo, key, level + 1); in rebalance()
557 i = getpos(geo, parent, key); in rebalance()
558 BUG_ON(bval(geo, parent, i) != child); 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()
564 merge(head, geo, level, in rebalance()
571 if (i + 1 < getfill(geo, parent, i)) { in rebalance()
572 right = bval(geo, parent, i + 1); in rebalance()
573 no_right = getfill(geo, right, 0); in rebalance()
574 if (fill + no_right <= geo->no_pairs) { in rebalance()
575 merge(head, geo, level, in rebalance()
591 static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo, in btree_remove_level() argument
605 node = find_level(head, geo, key, level); in btree_remove_level()
606 pos = getpos(geo, node, key); in btree_remove_level()
607 fill = getfill(geo, node, pos); in btree_remove_level()
608 if ((level == 1) && (keycmp(geo, node, pos, key) != 0)) in btree_remove_level()
610 ret = bval(geo, node, pos); in btree_remove_level()
614 setkey(geo, node, i, bkey(geo, node, i + 1)); in btree_remove_level()
615 setval(geo, node, i, bval(geo, node, i + 1)); 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()
621 rebalance(head, geo, key, level, node, fill - 1); in btree_remove_level()
623 btree_shrink(head, geo); in btree_remove_level()
629 void *btree_remove(struct btree_head *head, struct btree_geo *geo, in btree_remove() argument
635 return btree_remove_level(head, geo, key, 1); in btree_remove()
640 struct btree_geo *geo, gfp_t gfp) in btree_merge() argument
642 unsigned long key[geo->keylen]; in btree_merge()
643 unsigned long dup[geo->keylen]; in btree_merge()
661 if (!btree_last(victim, geo, key)) in btree_merge()
663 val = btree_lookup(victim, geo, key); in btree_merge()
664 err = btree_insert(target, geo, key, val, gfp); in btree_merge()
669 longcpy(dup, key, geo->keylen); in btree_merge()
670 btree_remove(victim, geo, dup); in btree_merge()
676 static size_t __btree_for_each(struct btree_head *head, struct btree_geo *geo, in __btree_for_each() argument
686 for (i = 0; i < geo->no_pairs; i++) { in __btree_for_each()
687 child = bval(geo, node, i); in __btree_for_each()
691 count = __btree_for_each(head, geo, child, opaque, in __btree_for_each()
694 func(child, opaque, bkey(geo, node, i), count++, in __btree_for_each()
746 size_t btree_visitor(struct btree_head *head, struct btree_geo *geo, in btree_visitor() argument
758 count = __btree_for_each(head, geo, head->node, opaque, func, in btree_visitor()
764 size_t btree_grim_visitor(struct btree_head *head, struct btree_geo *geo, in btree_grim_visitor() argument
776 count = __btree_for_each(head, geo, head->node, opaque, func, in btree_grim_visitor()