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