Lines Matching refs:head
93 static unsigned long *btree_node_alloc(struct btree_head *head, gfp_t gfp) in btree_node_alloc() argument
97 node = mempool_alloc(head->mempool, gfp); in btree_node_alloc()
176 static inline void __btree_init(struct btree_head *head) in __btree_init() argument
178 head->node = NULL; in __btree_init()
179 head->height = 0; in __btree_init()
182 void btree_init_mempool(struct btree_head *head, mempool_t *mempool) in btree_init_mempool() argument
184 __btree_init(head); in btree_init_mempool()
185 head->mempool = mempool; in btree_init_mempool()
189 int btree_init(struct btree_head *head) in btree_init() argument
191 __btree_init(head); in btree_init()
192 head->mempool = mempool_create(0, btree_alloc, btree_free, NULL); in btree_init()
193 if (!head->mempool) in btree_init()
199 void btree_destroy(struct btree_head *head) in btree_destroy() argument
201 mempool_free(head->node, head->mempool); in btree_destroy()
202 mempool_destroy(head->mempool); in btree_destroy()
203 head->mempool = NULL; in btree_destroy()
207 void *btree_last(struct btree_head *head, struct btree_geo *geo, in btree_last() argument
210 int height = head->height; in btree_last()
211 unsigned long *node = head->node; in btree_last()
241 void *btree_lookup(struct btree_head *head, struct btree_geo *geo, in btree_lookup() argument
244 int i, height = head->height; in btree_lookup()
245 unsigned long *node = head->node; in btree_lookup()
271 int btree_update(struct btree_head *head, struct btree_geo *geo, in btree_update() argument
274 int i, height = head->height; in btree_update()
275 unsigned long *node = head->node; in btree_update()
311 void *btree_get_prev(struct btree_head *head, struct btree_geo *geo, in btree_get_prev() argument
321 if (head->height == 0) in btree_get_prev()
327 node = head->node; in btree_get_prev()
328 for (height = head->height ; height > 1; height--) { in btree_get_prev()
388 static unsigned long *find_level(struct btree_head *head, struct btree_geo *geo, in find_level() argument
391 unsigned long *node = head->node; in find_level()
394 for (height = head->height; height > level; height--) { in find_level()
413 static int btree_grow(struct btree_head *head, struct btree_geo *geo, in btree_grow() argument
419 node = btree_node_alloc(head, gfp); in btree_grow()
422 if (head->node) { in btree_grow()
423 fill = getfill(geo, head->node, 0); in btree_grow()
424 setkey(geo, node, 0, bkey(geo, head->node, fill - 1)); in btree_grow()
425 setval(geo, node, 0, head->node); in btree_grow()
427 head->node = node; in btree_grow()
428 head->height++; in btree_grow()
432 static void btree_shrink(struct btree_head *head, struct btree_geo *geo) in btree_shrink() argument
437 if (head->height <= 1) in btree_shrink()
440 node = head->node; in btree_shrink()
443 head->node = bval(geo, node, 0); in btree_shrink()
444 head->height--; in btree_shrink()
445 mempool_free(node, head->mempool); in btree_shrink()
448 static int btree_insert_level(struct btree_head *head, struct btree_geo *geo, in btree_insert_level() argument
456 if (head->height < level) { in btree_insert_level()
457 err = btree_grow(head, geo, gfp); in btree_insert_level()
463 node = find_level(head, geo, key, level); in btree_insert_level()
473 new = btree_node_alloc(head, gfp); in btree_insert_level()
476 err = btree_insert_level(head, geo, in btree_insert_level()
480 mempool_free(new, head->mempool); in btree_insert_level()
510 int btree_insert(struct btree_head *head, struct btree_geo *geo, in btree_insert() argument
514 return btree_insert_level(head, geo, key, val, 1, gfp); in btree_insert()
518 static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo,
520 static void merge(struct btree_head *head, struct btree_geo *geo, int level, in merge() argument
536 btree_remove_level(head, geo, bkey(geo, parent, lpos), level + 1); in merge()
537 mempool_free(right, head->mempool); in merge()
540 static void rebalance(struct btree_head *head, struct btree_geo *geo, in rebalance() argument
551 btree_remove_level(head, geo, key, level + 1); in rebalance()
552 mempool_free(child, head->mempool); in rebalance()
556 parent = find_level(head, geo, key, level + 1); in rebalance()
564 merge(head, geo, level, in rebalance()
575 merge(head, geo, level, in rebalance()
591 static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo, in btree_remove_level() argument
598 if (level > head->height) { in btree_remove_level()
600 head->height = 0; in btree_remove_level()
601 head->node = NULL; in btree_remove_level()
605 node = find_level(head, geo, key, level); in btree_remove_level()
620 if (level < head->height) in btree_remove_level()
621 rebalance(head, geo, key, level, node, fill - 1); in btree_remove_level()
623 btree_shrink(head, geo); in btree_remove_level()
629 void *btree_remove(struct btree_head *head, struct btree_geo *geo, in btree_remove() argument
632 if (head->height == 0) in btree_remove()
635 return btree_remove_level(head, geo, key, 1); in btree_remove()
676 static size_t __btree_for_each(struct btree_head *head, struct btree_geo *geo, in __btree_for_each() argument
691 count = __btree_for_each(head, geo, child, opaque, in __btree_for_each()
698 mempool_free(node, head->mempool); in __btree_for_each()
746 size_t btree_visitor(struct btree_head *head, struct btree_geo *geo, in btree_visitor() argument
757 if (head->node) in btree_visitor()
758 count = __btree_for_each(head, geo, head->node, opaque, func, in btree_visitor()
759 func2, 0, head->height, 0); in btree_visitor()
764 size_t btree_grim_visitor(struct btree_head *head, struct btree_geo *geo, in btree_grim_visitor() argument
775 if (head->node) in btree_grim_visitor()
776 count = __btree_for_each(head, geo, head->node, opaque, func, in btree_grim_visitor()
777 func2, 1, head->height, 0); in btree_grim_visitor()
778 __btree_init(head); in btree_grim_visitor()