linux/lib/btree.c

92 static unsigned long *btree_node_alloc(struct btree_head *head, gfp_t gfp)
96 	node = mempool_alloc(head->mempool, gfp);
175 static inline void __btree_init(struct btree_head *head)
177 	head->node = NULL;
178 	head->height = 0;
181 void btree_init_mempool(struct btree_head *head, mempool_t *mempool)
183 	__btree_init(head);
184 	head->mempool = mempool;
188 int btree_init(struct btree_head *head)
190 	__btree_init(head);
191 	head->mempool = mempool_create(0, btree_alloc, btree_free, NULL);
192 	if (!head->mempool)
198 void btree_destroy(struct btree_head *head)
200 	mempool_free(head->node, head->mempool);
201 	mempool_destroy(head->mempool);
202 	head->mempool = NULL;
206 void *btree_last(struct btree_head *head, struct btree_geo *geo,
209 	int height = head->height;
210 	unsigned long *node = head->node;
240 static void *btree_lookup_node(struct btree_head *head, struct btree_geo *geo,
243 	int i, height = head->height;
244 	unsigned long *node = head->node;
262 void *btree_lookup(struct btree_head *head, struct btree_geo *geo,
268 	node = btree_lookup_node(head, geo, key);
279 int btree_update(struct btree_head *head, struct btree_geo *geo,
285 	node = btree_lookup_node(head, geo, key);
306 void *btree_get_prev(struct btree_head *head, struct btree_geo *geo,
316 	if (head->height == 0)
322 	node = head->node;
323 	for (height = head->height ; height > 1; height--) {
383 static unsigned long *find_level(struct btree_head *head, struct btree_geo *geo,
386 	unsigned long *node = head->node;
389 	for (height = head->height; height > level; height--) {
408 static int btree_grow(struct btree_head *head, struct btree_geo *geo,
414 	node = btree_node_alloc(head, gfp);
417 	if (head->node) {
418 		fill = getfill(geo, head->node, 0);
419 		setkey(geo, node, 0, bkey(geo, head->node, fill - 1));
420 		setval(geo, node, 0, head->node);
422 	head->node = node;
423 	head->height++;
427 static void btree_shrink(struct btree_head *head, struct btree_geo *geo)
432 	if (head->height <= 1)
435 	node = head->node;
438 	head->node = bval(geo, node, 0);
439 	head->height--;
440 	mempool_free(node, head->mempool);
443 static int btree_insert_level(struct btree_head *head, struct btree_geo *geo,
451 	if (head->height < level) {
452 		err = btree_grow(head, geo, gfp);
458 	node = find_level(head, geo, key, level);
468 		new = btree_node_alloc(head, gfp);
471 		err = btree_insert_level(head, geo,
475 			mempool_free(new, head->mempool);
505 int btree_insert(struct btree_head *head, struct btree_geo *geo,
509 	return btree_insert_level(head, geo, key, val, 1, gfp);
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,
531 	btree_remove_level(head, geo, bkey(geo, parent, lpos), level + 1);
532 	mempool_free(right, head->mempool);
535 static void rebalance(struct btree_head *head, struct btree_geo *geo,
546 		btree_remove_level(head, geo, key, level + 1);
547 		mempool_free(child, head->mempool);
551 	parent = find_level(head, geo, key, level + 1);
559 			merge(head, geo, level,
570 			merge(head, geo, level,
586 static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo,
593 	if (level > head->height) {
595 		head->height = 0;
596 		head->node = NULL;
600 	node = find_level(head, geo, key, level);
615 		if (level < head->height)
616 			rebalance(head, geo, key, level, node, fill - 1);
618 			btree_shrink(head, geo);
624 void *btree_remove(struct btree_head *head, struct btree_geo *geo,
627 	if (head->height == 0)
630 	return btree_remove_level(head, geo, key, 1);
671 static size_t __btree_for_each(struct btree_head *head, struct btree_geo *geo,
686 			count = __btree_for_each(head, geo, child, opaque,
693 		mempool_free(node, head->mempool);
741 size_t btree_visitor(struct btree_head *head, struct btree_geo *geo,
752 	if (head->node)
753 		count = __btree_for_each(head, geo, head->node, opaque, func,
754 				func2, 0, head->height, 0);
759 size_t btree_grim_visitor(struct btree_head *head, struct btree_geo *geo,
770 	if (head->node)
771 		count = __btree_for_each(head, geo, head->node, opaque, func,
772 				func2, 1, head->height, 0);
773 	__btree_init(head);