95 static unsigned long *btree_node_alloc(struct btree_head *head, gfp_t gfp)  in btree_node_alloc()  argument
99 	node = mempool_alloc(head->mempool, gfp);  in btree_node_alloc()
178 static inline void __btree_init(struct btree_head *head)  in __btree_init()  argument
180 	head->node = NULL;  in __btree_init()
181 	head->height = 0;  in __btree_init()
184 void btree_init_mempool(struct btree_head *head, mempool_t *mempool)  in btree_init_mempool()  argument
186 	__btree_init(head);  in btree_init_mempool()
187 	head->mempool = mempool;  in btree_init_mempool()
191 int btree_init(struct btree_head *head)  in btree_init()  argument
193 	__btree_init(head);  in btree_init()
194 	head->mempool = mempool_create(0, btree_alloc, btree_free, NULL);  in btree_init()
195 	if (!head->mempool)  in btree_init()
201 void btree_destroy(struct btree_head *head)  in btree_destroy()  argument
203 	mempool_free(head->node, head->mempool);  in btree_destroy()
204 	mempool_destroy(head->mempool);  in btree_destroy()
205 	head->mempool = NULL;  in btree_destroy()
209 void *btree_last(struct btree_head *head, struct btree_geo *geo,  in btree_last()  argument
212 	int height = head->height;  in btree_last()
213 	unsigned long *node = head->node;  in btree_last()
243 void *btree_lookup(struct btree_head *head, struct btree_geo *geo,  in btree_lookup()  argument
246 	int i, height = head->height;  in btree_lookup()
247 	unsigned long *node = head->node;  in btree_lookup()
273 int btree_update(struct btree_head *head, struct btree_geo *geo,  in btree_update()  argument
276 	int i, height = head->height;  in btree_update()
277 	unsigned long *node = head->node;  in btree_update()
313 void *btree_get_prev(struct btree_head *head, struct btree_geo *geo,  in btree_get_prev()  argument
323 	if (head->height == 0)  in btree_get_prev()
329 	node = head->node;  in btree_get_prev()
330 	for (height = head->height ; height > 1; height--) {  in btree_get_prev()
390 static unsigned long *find_level(struct btree_head *head, struct btree_geo *geo,  in find_level()  argument
393 	unsigned long *node = head->node;  in find_level()
396 	for (height = head->height; height > level; height--) {  in find_level()
415 static int btree_grow(struct btree_head *head, struct btree_geo *geo,  in btree_grow()  argument
421 	node = btree_node_alloc(head, gfp);  in btree_grow()
424 	if (head->node) {  in btree_grow()
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()
429 	head->node = node;  in btree_grow()
430 	head->height++;  in btree_grow()
434 static void btree_shrink(struct btree_head *head, struct btree_geo *geo)  in btree_shrink()  argument
439 	if (head->height <= 1)  in btree_shrink()
442 	node = head->node;  in btree_shrink()
445 	head->node = bval(geo, node, 0);  in btree_shrink()
446 	head->height--;  in btree_shrink()
447 	mempool_free(node, head->mempool);  in btree_shrink()
450 static int btree_insert_level(struct btree_head *head, struct btree_geo *geo,  in btree_insert_level()  argument
458 	if (head->height < level) {  in btree_insert_level()
459 		err = btree_grow(head, geo, gfp);  in btree_insert_level()
465 	node = find_level(head, geo, key, level);  in btree_insert_level()
475 		new = btree_node_alloc(head, gfp);  in btree_insert_level()
478 		err = btree_insert_level(head, geo,  in btree_insert_level()
482 			mempool_free(new, head->mempool);  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
538 	btree_remove_level(head, geo, bkey(geo, parent, lpos), level + 1);  in merge()
539 	mempool_free(right, head->mempool);  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()
554 		mempool_free(child, head->mempool);  in rebalance()
558 	parent = find_level(head, geo, key, level + 1);  in rebalance()
566 			merge(head, geo, level,  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
600 	if (level > head->height) {  in btree_remove_level()
602 		head->height = 0;  in btree_remove_level()
603 		head->node = NULL;  in btree_remove_level()
607 	node = find_level(head, geo, key, level);  in btree_remove_level()
622 		if (level < head->height)  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
634 	if (head->height == 0)  in btree_remove()
637 	return btree_remove_level(head, geo, key, 1);  in btree_remove()
678 static size_t __btree_for_each(struct btree_head *head, struct btree_geo *geo,  in __btree_for_each()  argument
693 			count = __btree_for_each(head, geo, child, opaque,  in __btree_for_each()
700 		mempool_free(node, head->mempool);  in __btree_for_each()
748 size_t btree_visitor(struct btree_head *head, struct btree_geo *geo,  in btree_visitor()  argument
759 	if (head->node)  in btree_visitor()
760 		count = __btree_for_each(head, geo, head->node, opaque, func,  in btree_visitor()
761 				func2, 0, head->height, 0);  in btree_visitor()
766 size_t btree_grim_visitor(struct btree_head *head, struct btree_geo *geo,  in btree_grim_visitor()  argument
777 	if (head->node)  in btree_grim_visitor()
778 		count = __btree_for_each(head, geo, head->node, opaque, func,  in btree_grim_visitor()
779 				func2, 1, head->height, 0);  in btree_grim_visitor()
780 	__btree_init(head);  in btree_grim_visitor()