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