134 static void dec_key(struct btree_geo *geo, unsigned long *key)  in dec_key()  argument
139 	for (i = geo->keylen - 1; i >= 0; i--) {  in dec_key()
147 static unsigned long *bkey(struct btree_geo *geo, unsigned long *node, int n)  in bkey()  argument
149 	return &node[n * geo->keylen];  in bkey()
152 static void *bval(struct btree_geo *geo, unsigned long *node, int n)  in bval()  argument
154 	return (void *)node[geo->no_longs + n];  in bval()
157 static void setkey(struct btree_geo *geo, unsigned long *node, int n,  in setkey()  argument
160 	longcpy(bkey(geo, node, n), key, geo->keylen);  in setkey()
163 static void setval(struct btree_geo *geo, unsigned long *node, int n,  in setval()  argument
166 	node[geo->no_longs + n] = (unsigned long) val;  in setval()
169 static void clearpair(struct btree_geo *geo, unsigned long *node, int n)  in clearpair()  argument
171 	longset(bkey(geo, node, n), 0, geo->keylen);  in clearpair()
172 	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 static void *btree_lookup_node(struct btree_head *head, struct btree_geo *geo,  in btree_lookup_node()  argument
250 		for (i = 0; i < geo->no_pairs; i++)  in btree_lookup_node()
251 			if (keycmp(geo, node, i, key) <= 0)  in btree_lookup_node()
253 		if (i == geo->no_pairs)  in btree_lookup_node()
255 		node = bval(geo, node, i);  in btree_lookup_node()
262 void *btree_lookup(struct btree_head *head, struct btree_geo *geo,  in btree_lookup()  argument
268 	node = btree_lookup_node(head, geo, key);  in btree_lookup()
272 	for (i = 0; i < geo->no_pairs; i++)  in btree_lookup()
273 		if (keycmp(geo, node, i, key) == 0)  in btree_lookup()
274 			return bval(geo, node, i);  in btree_lookup()
279 int btree_update(struct btree_head *head, struct btree_geo *geo,  in btree_update()  argument
285 	node = btree_lookup_node(head, geo, key);  in btree_update()
289 	for (i = 0; i < geo->no_pairs; i++)  in btree_update()
290 		if (keycmp(geo, node, i, key) == 0) {  in btree_update()
291 			setval(geo, node, i, val);  in btree_update()
306 void *btree_get_prev(struct btree_head *head, struct btree_geo *geo,  in btree_get_prev()  argument
313 	if (keyzero(geo, __key))  in btree_get_prev()
318 	longcpy(key, __key, geo->keylen);  in btree_get_prev()
320 	dec_key(geo, key);  in btree_get_prev()
324 		for (i = 0; i < geo->no_pairs; i++)  in btree_get_prev()
325 			if (keycmp(geo, node, i, key) <= 0)  in btree_get_prev()
327 		if (i == geo->no_pairs)  in btree_get_prev()
330 		node = bval(geo, node, i);  in btree_get_prev()
333 		retry_key = bkey(geo, oldnode, i);  in btree_get_prev()
339 	for (i = 0; i < geo->no_pairs; i++) {  in btree_get_prev()
340 		if (keycmp(geo, node, i, key) <= 0) {  in btree_get_prev()
341 			if (bval(geo, node, i)) {  in btree_get_prev()
342 				longcpy(__key, bkey(geo, node, i), geo->keylen);  in btree_get_prev()
343 				return bval(geo, node, i);  in btree_get_prev()
350 		longcpy(key, retry_key, geo->keylen);  in btree_get_prev()
358 static int getpos(struct btree_geo *geo, unsigned long *node,  in getpos()  argument
363 	for (i = 0; i < geo->no_pairs; i++) {  in getpos()
364 		if (keycmp(geo, node, i, key) <= 0)  in getpos()
370 static int getfill(struct btree_geo *geo, unsigned long *node, int start)  in getfill()  argument
374 	for (i = start; i < geo->no_pairs; i++)  in getfill()
375 		if (!bval(geo, node, i))  in getfill()
383 static unsigned long *find_level(struct btree_head *head, struct btree_geo *geo,  in find_level()  argument
390 		for (i = 0; i < geo->no_pairs; i++)  in find_level()
391 			if (keycmp(geo, node, i, key) <= 0)  in find_level()
394 		if ((i == geo->no_pairs) || !bval(geo, node, i)) {  in find_level()
399 			setkey(geo, node, i, key);  in find_level()
402 		node = bval(geo, node, i);  in find_level()
408 static int btree_grow(struct btree_head *head, struct btree_geo *geo,  in btree_grow()  argument
418 		fill = getfill(geo, head->node, 0);  in btree_grow()
419 		setkey(geo, node, 0, bkey(geo, head->node, fill - 1));  in btree_grow()
420 		setval(geo, node, 0, head->node);  in btree_grow()
427 static void btree_shrink(struct btree_head *head, struct btree_geo *geo)  in btree_shrink()  argument
436 	fill = getfill(geo, node, 0);  in btree_shrink()
438 	head->node = bval(geo, node, 0);  in btree_shrink()
443 static int btree_insert_level(struct btree_head *head, struct btree_geo *geo,  in btree_insert_level()  argument
452 		err = btree_grow(head, geo, gfp);  in btree_insert_level()
458 	node = find_level(head, geo, key, level);  in btree_insert_level()
459 	pos = getpos(geo, node, key);  in btree_insert_level()
460 	fill = getfill(geo, node, pos);  in btree_insert_level()
462 	BUG_ON(pos < fill && keycmp(geo, node, pos, key) == 0);  in btree_insert_level()
464 	if (fill == geo->no_pairs) {  in btree_insert_level()
471 		err = btree_insert_level(head, geo,  in btree_insert_level()
472 				bkey(geo, node, fill / 2 - 1),  in btree_insert_level()
479 			setkey(geo, new, i, bkey(geo, node, i));  in btree_insert_level()
480 			setval(geo, new, i, bval(geo, node, i));  in btree_insert_level()
481 			setkey(geo, node, i, bkey(geo, node, i + fill / 2));  in btree_insert_level()
482 			setval(geo, node, i, bval(geo, node, i + fill / 2));  in btree_insert_level()
483 			clearpair(geo, node, i + fill / 2);  in btree_insert_level()
486 			setkey(geo, node, i, bkey(geo, node, fill - 1));  in btree_insert_level()
487 			setval(geo, node, i, bval(geo, node, fill - 1));  in btree_insert_level()
488 			clearpair(geo, node, fill - 1);  in btree_insert_level()
492 	BUG_ON(fill >= geo->no_pairs);  in btree_insert_level()
496 		setkey(geo, node, i, bkey(geo, node, i - 1));  in btree_insert_level()
497 		setval(geo, node, i, bval(geo, node, i - 1));  in btree_insert_level()
499 	setkey(geo, node, pos, key);  in btree_insert_level()
500 	setval(geo, node, pos, val);  in btree_insert_level()
505 int btree_insert(struct btree_head *head, struct btree_geo *geo,  in btree_insert()  argument
509 	return btree_insert_level(head, geo, key, val, 1, gfp);  in btree_insert()
513 static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo,
515 static void merge(struct btree_head *head, struct btree_geo *geo, int level,  in merge()  argument
524 		setkey(geo, left, lfill + i, bkey(geo, right, i));  in merge()
525 		setval(geo, left, lfill + i, bval(geo, right, i));  in merge()
528 	setval(geo, parent, lpos, right);  in merge()
529 	setval(geo, parent, lpos + 1, left);  in merge()
531 	btree_remove_level(head, geo, bkey(geo, parent, lpos), level + 1);  in merge()
535 static void rebalance(struct btree_head *head, struct btree_geo *geo,  in rebalance()  argument
546 		btree_remove_level(head, geo, key, level + 1);  in rebalance()
551 	parent = find_level(head, geo, key, level + 1);  in rebalance()
552 	i = getpos(geo, parent, key);  in rebalance()
553 	BUG_ON(bval(geo, parent, i) != child);  in rebalance()
556 		left = bval(geo, parent, i - 1);  in rebalance()
557 		no_left = getfill(geo, left, 0);  in rebalance()
558 		if (fill + no_left <= geo->no_pairs) {  in rebalance()
559 			merge(head, geo, level,  in rebalance()
566 	if (i + 1 < getfill(geo, parent, i)) {  in rebalance()
567 		right = bval(geo, parent, i + 1);  in rebalance()
568 		no_right = getfill(geo, right, 0);  in rebalance()
569 		if (fill + no_right <= geo->no_pairs) {  in rebalance()
570 			merge(head, geo, level,  in rebalance()
586 static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo,  in btree_remove_level()  argument
600 	node = find_level(head, geo, key, level);  in btree_remove_level()
601 	pos = getpos(geo, node, key);  in btree_remove_level()
602 	fill = getfill(geo, node, pos);  in btree_remove_level()
603 	if ((level == 1) && (keycmp(geo, node, pos, key) != 0))  in btree_remove_level()
605 	ret = bval(geo, node, pos);  in btree_remove_level()
609 		setkey(geo, node, i, bkey(geo, node, i + 1));  in btree_remove_level()
610 		setval(geo, node, i, bval(geo, node, i + 1));  in btree_remove_level()
612 	clearpair(geo, node, fill - 1);  in btree_remove_level()
614 	if (fill - 1 < geo->no_pairs / 2) {  in btree_remove_level()
616 			rebalance(head, geo, key, level, node, fill - 1);  in btree_remove_level()
618 			btree_shrink(head, geo);  in btree_remove_level()
624 void *btree_remove(struct btree_head *head, struct btree_geo *geo,  in btree_remove()  argument
630 	return btree_remove_level(head, geo, key, 1);  in btree_remove()
635 		struct btree_geo *geo, gfp_t gfp)  in btree_merge()  argument
656 		if (!btree_last(victim, geo, key))  in btree_merge()
658 		val = btree_lookup(victim, geo, key);  in btree_merge()
659 		err = btree_insert(target, geo, key, val, gfp);  in btree_merge()
664 		longcpy(dup, key, geo->keylen);  in btree_merge()
665 		btree_remove(victim, geo, dup);  in btree_merge()
671 static size_t __btree_for_each(struct btree_head *head, struct btree_geo *geo,  in __btree_for_each()  argument
681 	for (i = 0; i < geo->no_pairs; i++) {  in __btree_for_each()
682 		child = bval(geo, node, i);  in __btree_for_each()
686 			count = __btree_for_each(head, geo, child, opaque,  in __btree_for_each()
689 			func(child, opaque, bkey(geo, node, i), count++,  in __btree_for_each()
741 size_t btree_visitor(struct btree_head *head, struct btree_geo *geo,  in btree_visitor()  argument
753 		count = __btree_for_each(head, geo, head->node, opaque, func,  in btree_visitor()
759 size_t btree_grim_visitor(struct btree_head *head, struct btree_geo *geo,  in btree_grim_visitor()  argument
771 		count = __btree_for_each(head, geo, head->node, opaque, func,  in btree_grim_visitor()