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 static void *btree_lookup_node(struct btree_head *head, struct btree_geo *geo,  in btree_lookup_node()  argument
251 		for (i = 0; i < geo->no_pairs; i++)  in btree_lookup_node()
252 			if (keycmp(geo, node, i, key) <= 0)  in btree_lookup_node()
254 		if (i == geo->no_pairs)  in btree_lookup_node()
256 		node = bval(geo, node, i);  in btree_lookup_node()
263 void *btree_lookup(struct btree_head *head, struct btree_geo *geo,  in btree_lookup()  argument
269 	node = btree_lookup_node(head, geo, key);  in btree_lookup()
273 	for (i = 0; i < geo->no_pairs; i++)  in btree_lookup()
274 		if (keycmp(geo, node, i, key) == 0)  in btree_lookup()
275 			return bval(geo, node, i);  in btree_lookup()
280 int btree_update(struct btree_head *head, struct btree_geo *geo,  in btree_update()  argument
286 	node = btree_lookup_node(head, geo, key);  in btree_update()
290 	for (i = 0; i < geo->no_pairs; i++)  in btree_update()
291 		if (keycmp(geo, node, i, key) == 0) {  in btree_update()
292 			setval(geo, node, i, val);  in btree_update()
307 void *btree_get_prev(struct btree_head *head, struct btree_geo *geo,  in btree_get_prev()  argument
314 	if (keyzero(geo, __key))  in btree_get_prev()
319 	longcpy(key, __key, geo->keylen);  in btree_get_prev()
321 	dec_key(geo, key);  in btree_get_prev()
325 		for (i = 0; i < geo->no_pairs; i++)  in btree_get_prev()
326 			if (keycmp(geo, node, i, key) <= 0)  in btree_get_prev()
328 		if (i == geo->no_pairs)  in btree_get_prev()
331 		node = bval(geo, node, i);  in btree_get_prev()
334 		retry_key = bkey(geo, oldnode, i);  in btree_get_prev()
340 	for (i = 0; i < geo->no_pairs; i++) {  in btree_get_prev()
341 		if (keycmp(geo, node, i, key) <= 0) {  in btree_get_prev()
342 			if (bval(geo, node, i)) {  in btree_get_prev()
343 				longcpy(__key, bkey(geo, node, i), geo->keylen);  in btree_get_prev()
344 				return bval(geo, node, i);  in btree_get_prev()
351 		longcpy(key, retry_key, geo->keylen);  in btree_get_prev()
359 static int getpos(struct btree_geo *geo, unsigned long *node,  in getpos()  argument
364 	for (i = 0; i < geo->no_pairs; i++) {  in getpos()
365 		if (keycmp(geo, node, i, key) <= 0)  in getpos()
371 static int getfill(struct btree_geo *geo, unsigned long *node, int start)  in getfill()  argument
375 	for (i = start; i < geo->no_pairs; i++)  in getfill()
376 		if (!bval(geo, node, i))  in getfill()
384 static unsigned long *find_level(struct btree_head *head, struct btree_geo *geo,  in find_level()  argument
391 		for (i = 0; i < geo->no_pairs; i++)  in find_level()
392 			if (keycmp(geo, node, i, key) <= 0)  in find_level()
395 		if ((i == geo->no_pairs) || !bval(geo, node, i)) {  in find_level()
400 			setkey(geo, node, i, key);  in find_level()
403 		node = bval(geo, node, i);  in find_level()
409 static int btree_grow(struct btree_head *head, struct btree_geo *geo,  in btree_grow()  argument
419 		fill = getfill(geo, head->node, 0);  in btree_grow()
420 		setkey(geo, node, 0, bkey(geo, head->node, fill - 1));  in btree_grow()
421 		setval(geo, node, 0, head->node);  in btree_grow()
428 static void btree_shrink(struct btree_head *head, struct btree_geo *geo)  in btree_shrink()  argument
437 	fill = getfill(geo, node, 0);  in btree_shrink()
439 	head->node = bval(geo, node, 0);  in btree_shrink()
444 static int btree_insert_level(struct btree_head *head, struct btree_geo *geo,  in btree_insert_level()  argument
453 		err = btree_grow(head, geo, gfp);  in btree_insert_level()
459 	node = find_level(head, geo, key, level);  in btree_insert_level()
460 	pos = getpos(geo, node, key);  in btree_insert_level()
461 	fill = getfill(geo, node, pos);  in btree_insert_level()
463 	BUG_ON(pos < fill && keycmp(geo, node, pos, key) == 0);  in btree_insert_level()
465 	if (fill == geo->no_pairs) {  in btree_insert_level()
472 		err = btree_insert_level(head, geo,  in btree_insert_level()
473 				bkey(geo, node, fill / 2 - 1),  in btree_insert_level()
480 			setkey(geo, new, i, bkey(geo, node, i));  in btree_insert_level()
481 			setval(geo, new, i, bval(geo, node, i));  in btree_insert_level()
482 			setkey(geo, node, i, bkey(geo, node, i + fill / 2));  in btree_insert_level()
483 			setval(geo, node, i, bval(geo, node, i + fill / 2));  in btree_insert_level()
484 			clearpair(geo, node, i + fill / 2);  in btree_insert_level()
487 			setkey(geo, node, i, bkey(geo, node, fill - 1));  in btree_insert_level()
488 			setval(geo, node, i, bval(geo, node, fill - 1));  in btree_insert_level()
489 			clearpair(geo, node, fill - 1);  in btree_insert_level()
493 	BUG_ON(fill >= geo->no_pairs);  in btree_insert_level()
497 		setkey(geo, node, i, bkey(geo, node, i - 1));  in btree_insert_level()
498 		setval(geo, node, i, bval(geo, node, i - 1));  in btree_insert_level()
500 	setkey(geo, node, pos, key);  in btree_insert_level()
501 	setval(geo, node, pos, val);  in btree_insert_level()
506 int btree_insert(struct btree_head *head, struct btree_geo *geo,  in btree_insert()  argument
510 	return btree_insert_level(head, geo, key, val, 1, gfp);  in btree_insert()
514 static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo,
516 static void merge(struct btree_head *head, struct btree_geo *geo, int level,  in merge()  argument
525 		setkey(geo, left, lfill + i, bkey(geo, right, i));  in merge()
526 		setval(geo, left, lfill + i, bval(geo, right, i));  in merge()
529 	setval(geo, parent, lpos, right);  in merge()
530 	setval(geo, parent, lpos + 1, left);  in merge()
532 	btree_remove_level(head, geo, bkey(geo, parent, lpos), level + 1);  in merge()
536 static void rebalance(struct btree_head *head, struct btree_geo *geo,  in rebalance()  argument
547 		btree_remove_level(head, geo, key, level + 1);  in rebalance()
552 	parent = find_level(head, geo, key, level + 1);  in rebalance()
553 	i = getpos(geo, parent, key);  in rebalance()
554 	BUG_ON(bval(geo, parent, i) != child);  in rebalance()
557 		left = bval(geo, parent, i - 1);  in rebalance()
558 		no_left = getfill(geo, left, 0);  in rebalance()
559 		if (fill + no_left <= geo->no_pairs) {  in rebalance()
560 			merge(head, geo, level,  in rebalance()
567 	if (i + 1 < getfill(geo, parent, i)) {  in rebalance()
568 		right = bval(geo, parent, i + 1);  in rebalance()
569 		no_right = getfill(geo, right, 0);  in rebalance()
570 		if (fill + no_right <= geo->no_pairs) {  in rebalance()
571 			merge(head, geo, level,  in rebalance()
587 static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo,  in btree_remove_level()  argument
601 	node = find_level(head, geo, key, level);  in btree_remove_level()
602 	pos = getpos(geo, node, key);  in btree_remove_level()
603 	fill = getfill(geo, node, pos);  in btree_remove_level()
604 	if ((level == 1) && (keycmp(geo, node, pos, key) != 0))  in btree_remove_level()
606 	ret = bval(geo, node, pos);  in btree_remove_level()
610 		setkey(geo, node, i, bkey(geo, node, i + 1));  in btree_remove_level()
611 		setval(geo, node, i, bval(geo, node, i + 1));  in btree_remove_level()
613 	clearpair(geo, node, fill - 1);  in btree_remove_level()
615 	if (fill - 1 < geo->no_pairs / 2) {  in btree_remove_level()
617 			rebalance(head, geo, key, level, node, fill - 1);  in btree_remove_level()
619 			btree_shrink(head, geo);  in btree_remove_level()
625 void *btree_remove(struct btree_head *head, struct btree_geo *geo,  in btree_remove()  argument
631 	return btree_remove_level(head, geo, key, 1);  in btree_remove()
636 		struct btree_geo *geo, gfp_t gfp)  in btree_merge()  argument
657 		if (!btree_last(victim, geo, key))  in btree_merge()
659 		val = btree_lookup(victim, geo, key);  in btree_merge()
660 		err = btree_insert(target, geo, key, val, gfp);  in btree_merge()
665 		longcpy(dup, key, geo->keylen);  in btree_merge()
666 		btree_remove(victim, geo, dup);  in btree_merge()
672 static size_t __btree_for_each(struct btree_head *head, struct btree_geo *geo,  in __btree_for_each()  argument
682 	for (i = 0; i < geo->no_pairs; i++) {  in __btree_for_each()
683 		child = bval(geo, node, i);  in __btree_for_each()
687 			count = __btree_for_each(head, geo, child, opaque,  in __btree_for_each()
690 			func(child, opaque, bkey(geo, node, i), count++,  in __btree_for_each()
742 size_t btree_visitor(struct btree_head *head, struct btree_geo *geo,  in btree_visitor()  argument
754 		count = __btree_for_each(head, geo, head->node, opaque, func,  in btree_visitor()
760 size_t btree_grim_visitor(struct btree_head *head, struct btree_geo *geo,  in btree_grim_visitor()  argument
772 		count = __btree_for_each(head, geo, head->node, opaque, func,  in btree_grim_visitor()