137 static void dec_key(struct btree_geo *geo, unsigned long *key)  in dec_key()  argument
142 	for (i = geo->keylen - 1; i >= 0; i--) {  in dec_key()
150 static unsigned long *bkey(struct btree_geo *geo, unsigned long *node, int n)  in bkey()  argument
152 	return &node[n * geo->keylen];  in bkey()
155 static void *bval(struct btree_geo *geo, unsigned long *node, int n)  in bval()  argument
157 	return (void *)node[geo->no_longs + n];  in bval()
160 static void setkey(struct btree_geo *geo, unsigned long *node, int n,  in setkey()  argument
163 	longcpy(bkey(geo, node, n), key, geo->keylen);  in setkey()
166 static void setval(struct btree_geo *geo, unsigned long *node, int n,  in setval()  argument
169 	node[geo->no_longs + n] = (unsigned long) val;  in setval()
172 static void clearpair(struct btree_geo *geo, unsigned long *node, int n)  in clearpair()  argument
174 	longset(bkey(geo, node, n), 0, geo->keylen);  in clearpair()
175 	node[geo->no_longs + n] = 0;  in clearpair()
209 void *btree_last(struct btree_head *head, struct btree_geo *geo,  in btree_last()  argument
219 		node = bval(geo, node, 0);  in btree_last()
221 	longcpy(key, bkey(geo, node, 0), geo->keylen);  in btree_last()
222 	return bval(geo, node, 0);  in btree_last()
226 static int keycmp(struct btree_geo *geo, unsigned long *node, int pos,  in keycmp()  argument
229 	return longcmp(bkey(geo, node, pos), key, geo->keylen);  in keycmp()
232 static int keyzero(struct btree_geo *geo, unsigned long *key)  in keyzero()  argument
236 	for (i = 0; i < geo->keylen; i++)  in keyzero()
243 void *btree_lookup(struct btree_head *head, struct btree_geo *geo,  in btree_lookup()  argument
253 		for (i = 0; i < geo->no_pairs; i++)  in btree_lookup()
254 			if (keycmp(geo, node, i, key) <= 0)  in btree_lookup()
256 		if (i == geo->no_pairs)  in btree_lookup()
258 		node = bval(geo, node, i);  in btree_lookup()
266 	for (i = 0; i < geo->no_pairs; i++)  in btree_lookup()
267 		if (keycmp(geo, node, i, key) == 0)  in btree_lookup()
268 			return bval(geo, node, i);  in btree_lookup()
273 int btree_update(struct btree_head *head, struct btree_geo *geo,  in btree_update()  argument
283 		for (i = 0; i < geo->no_pairs; i++)  in btree_update()
284 			if (keycmp(geo, node, i, key) <= 0)  in btree_update()
286 		if (i == geo->no_pairs)  in btree_update()
288 		node = bval(geo, node, i);  in btree_update()
296 	for (i = 0; i < geo->no_pairs; i++)  in btree_update()
297 		if (keycmp(geo, node, i, key) == 0) {  in btree_update()
298 			setval(geo, node, i, val);  in btree_update()
313 void *btree_get_prev(struct btree_head *head, struct btree_geo *geo,  in btree_get_prev()  argument
320 	if (keyzero(geo, __key))  in btree_get_prev()
325 	longcpy(key, __key, geo->keylen);  in btree_get_prev()
327 	dec_key(geo, key);  in btree_get_prev()
331 		for (i = 0; i < geo->no_pairs; i++)  in btree_get_prev()
332 			if (keycmp(geo, node, i, key) <= 0)  in btree_get_prev()
334 		if (i == geo->no_pairs)  in btree_get_prev()
337 		node = bval(geo, node, i);  in btree_get_prev()
340 		retry_key = bkey(geo, oldnode, i);  in btree_get_prev()
346 	for (i = 0; i < geo->no_pairs; i++) {  in btree_get_prev()
347 		if (keycmp(geo, node, i, key) <= 0) {  in btree_get_prev()
348 			if (bval(geo, node, i)) {  in btree_get_prev()
349 				longcpy(__key, bkey(geo, node, i), geo->keylen);  in btree_get_prev()
350 				return bval(geo, node, i);  in btree_get_prev()
357 		longcpy(key, retry_key, geo->keylen);  in btree_get_prev()
365 static int getpos(struct btree_geo *geo, unsigned long *node,  in getpos()  argument
370 	for (i = 0; i < geo->no_pairs; i++) {  in getpos()
371 		if (keycmp(geo, node, i, key) <= 0)  in getpos()
377 static int getfill(struct btree_geo *geo, unsigned long *node, int start)  in getfill()  argument
381 	for (i = start; i < geo->no_pairs; i++)  in getfill()
382 		if (!bval(geo, node, i))  in getfill()
390 static unsigned long *find_level(struct btree_head *head, struct btree_geo *geo,  in find_level()  argument
397 		for (i = 0; i < geo->no_pairs; i++)  in find_level()
398 			if (keycmp(geo, node, i, key) <= 0)  in find_level()
401 		if ((i == geo->no_pairs) || !bval(geo, node, i)) {  in find_level()
406 			setkey(geo, node, i, key);  in find_level()
409 		node = bval(geo, node, i);  in find_level()
415 static int btree_grow(struct btree_head *head, struct btree_geo *geo,  in btree_grow()  argument
425 		fill = getfill(geo, head->node, 0);  in btree_grow()
426 		setkey(geo, node, 0, bkey(geo, head->node, fill - 1));  in btree_grow()
427 		setval(geo, node, 0, head->node);  in btree_grow()
434 static void btree_shrink(struct btree_head *head, struct btree_geo *geo)  in btree_shrink()  argument
443 	fill = getfill(geo, node, 0);  in btree_shrink()
445 	head->node = bval(geo, node, 0);  in btree_shrink()
450 static int btree_insert_level(struct btree_head *head, struct btree_geo *geo,  in btree_insert_level()  argument
459 		err = btree_grow(head, geo, gfp);  in btree_insert_level()
465 	node = find_level(head, geo, key, level);  in btree_insert_level()
466 	pos = getpos(geo, node, key);  in btree_insert_level()
467 	fill = getfill(geo, node, pos);  in btree_insert_level()
469 	BUG_ON(pos < fill && keycmp(geo, node, pos, key) == 0);  in btree_insert_level()
471 	if (fill == geo->no_pairs) {  in btree_insert_level()
478 		err = btree_insert_level(head, geo,  in btree_insert_level()
479 				bkey(geo, node, fill / 2 - 1),  in btree_insert_level()
486 			setkey(geo, new, i, bkey(geo, node, i));  in btree_insert_level()
487 			setval(geo, new, i, bval(geo, node, i));  in btree_insert_level()
488 			setkey(geo, node, i, bkey(geo, node, i + fill / 2));  in btree_insert_level()
489 			setval(geo, node, i, bval(geo, node, i + fill / 2));  in btree_insert_level()
490 			clearpair(geo, node, i + fill / 2);  in btree_insert_level()
493 			setkey(geo, node, i, bkey(geo, node, fill - 1));  in btree_insert_level()
494 			setval(geo, node, i, bval(geo, node, fill - 1));  in btree_insert_level()
495 			clearpair(geo, node, fill - 1);  in btree_insert_level()
499 	BUG_ON(fill >= geo->no_pairs);  in btree_insert_level()
503 		setkey(geo, node, i, bkey(geo, node, i - 1));  in btree_insert_level()
504 		setval(geo, node, i, bval(geo, node, i - 1));  in btree_insert_level()
506 	setkey(geo, node, pos, key);  in btree_insert_level()
507 	setval(geo, node, pos, val);  in btree_insert_level()
512 int btree_insert(struct btree_head *head, struct btree_geo *geo,  in btree_insert()  argument
516 	return btree_insert_level(head, geo, key, val, 1, gfp);  in btree_insert()
520 static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo,
522 static void merge(struct btree_head *head, struct btree_geo *geo, int level,  in merge()  argument
531 		setkey(geo, left, lfill + i, bkey(geo, right, i));  in merge()
532 		setval(geo, left, lfill + i, bval(geo, right, i));  in merge()
535 	setval(geo, parent, lpos, right);  in merge()
536 	setval(geo, parent, lpos + 1, left);  in merge()
538 	btree_remove_level(head, geo, bkey(geo, parent, lpos), level + 1);  in merge()
542 static void rebalance(struct btree_head *head, struct btree_geo *geo,  in rebalance()  argument
553 		btree_remove_level(head, geo, key, level + 1);  in rebalance()
558 	parent = find_level(head, geo, key, level + 1);  in rebalance()
559 	i = getpos(geo, parent, key);  in rebalance()
560 	BUG_ON(bval(geo, parent, i) != child);  in rebalance()
563 		left = bval(geo, parent, i - 1);  in rebalance()
564 		no_left = getfill(geo, left, 0);  in rebalance()
565 		if (fill + no_left <= geo->no_pairs) {  in rebalance()
566 			merge(head, geo, level,  in rebalance()
573 	if (i + 1 < getfill(geo, parent, i)) {  in rebalance()
574 		right = bval(geo, parent, i + 1);  in rebalance()
575 		no_right = getfill(geo, right, 0);  in rebalance()
576 		if (fill + no_right <= geo->no_pairs) {  in rebalance()
577 			merge(head, geo, level,  in rebalance()
593 static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo,  in btree_remove_level()  argument
607 	node = find_level(head, geo, key, level);  in btree_remove_level()
608 	pos = getpos(geo, node, key);  in btree_remove_level()
609 	fill = getfill(geo, node, pos);  in btree_remove_level()
610 	if ((level == 1) && (keycmp(geo, node, pos, key) != 0))  in btree_remove_level()
612 	ret = bval(geo, node, pos);  in btree_remove_level()
616 		setkey(geo, node, i, bkey(geo, node, i + 1));  in btree_remove_level()
617 		setval(geo, node, i, bval(geo, node, i + 1));  in btree_remove_level()
619 	clearpair(geo, node, fill - 1);  in btree_remove_level()
621 	if (fill - 1 < geo->no_pairs / 2) {  in btree_remove_level()
623 			rebalance(head, geo, key, level, node, fill - 1);  in btree_remove_level()
625 			btree_shrink(head, geo);  in btree_remove_level()
631 void *btree_remove(struct btree_head *head, struct btree_geo *geo,  in btree_remove()  argument
637 	return btree_remove_level(head, geo, key, 1);  in btree_remove()
642 		struct btree_geo *geo, gfp_t gfp)  in btree_merge()  argument
663 		if (!btree_last(victim, geo, key))  in btree_merge()
665 		val = btree_lookup(victim, geo, key);  in btree_merge()
666 		err = btree_insert(target, geo, key, val, gfp);  in btree_merge()
671 		longcpy(dup, key, geo->keylen);  in btree_merge()
672 		btree_remove(victim, geo, dup);  in btree_merge()
678 static size_t __btree_for_each(struct btree_head *head, struct btree_geo *geo,  in __btree_for_each()  argument
688 	for (i = 0; i < geo->no_pairs; i++) {  in __btree_for_each()
689 		child = bval(geo, node, i);  in __btree_for_each()
693 			count = __btree_for_each(head, geo, child, opaque,  in __btree_for_each()
696 			func(child, opaque, bkey(geo, node, i), count++,  in __btree_for_each()
748 size_t btree_visitor(struct btree_head *head, struct btree_geo *geo,  in btree_visitor()  argument
760 		count = __btree_for_each(head, geo, head->node, opaque, func,  in btree_visitor()
766 size_t btree_grim_visitor(struct btree_head *head, struct btree_geo *geo,  in btree_grim_visitor()  argument
778 		count = __btree_for_each(head, geo, head->node, opaque, func,  in btree_grim_visitor()