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 static void *btree_lookup_node(struct btree_head *head, struct btree_geo *geo, in btree_lookup_node() argument
244 int i, height = head->height; in btree_lookup_node()
245 unsigned long *node = head->node; in btree_lookup_node()
263 void *btree_lookup(struct btree_head *head, struct btree_geo *geo, in btree_lookup() argument
269 node = btree_lookup_node(head, geo, key); in btree_lookup()
280 int btree_update(struct btree_head *head, struct btree_geo *geo, in btree_update() argument
286 node = btree_lookup_node(head, geo, key); in btree_update()
307 void *btree_get_prev(struct btree_head *head, struct btree_geo *geo, in btree_get_prev() argument
317 if (head->height == 0) in btree_get_prev()
323 node = head->node; in btree_get_prev()
324 for (height = head->height ; height > 1; height--) { in btree_get_prev()
384 static unsigned long *find_level(struct btree_head *head, struct btree_geo *geo, in find_level() argument
387 unsigned long *node = head->node; in find_level()
390 for (height = head->height; height > level; height--) { in find_level()
409 static int btree_grow(struct btree_head *head, struct btree_geo *geo, in btree_grow() argument
415 node = btree_node_alloc(head, gfp); in btree_grow()
418 if (head->node) { in btree_grow()
419 fill = getfill(geo, head->node, 0); in btree_grow()
420 setkey(geo, node, 0, bkey(geo, head->node, fill - 1)); in btree_grow()
421 setval(geo, node, 0, head->node); in btree_grow()
423 head->node = node; in btree_grow()
424 head->height++; in btree_grow()
428 static void btree_shrink(struct btree_head *head, struct btree_geo *geo) in btree_shrink() argument
433 if (head->height <= 1) in btree_shrink()
436 node = head->node; in btree_shrink()
439 head->node = bval(geo, node, 0); in btree_shrink()
440 head->height--; in btree_shrink()
441 mempool_free(node, head->mempool); in btree_shrink()
444 static int btree_insert_level(struct btree_head *head, struct btree_geo *geo, in btree_insert_level() argument
452 if (head->height < level) { in btree_insert_level()
453 err = btree_grow(head, geo, gfp); in btree_insert_level()
459 node = find_level(head, geo, key, level); in btree_insert_level()
469 new = btree_node_alloc(head, gfp); in btree_insert_level()
472 err = btree_insert_level(head, geo, in btree_insert_level()
476 mempool_free(new, head->mempool); in btree_insert_level()
506 int btree_insert(struct btree_head *head, struct btree_geo *geo, in btree_insert() argument
510 return btree_insert_level(head, geo, key, val, 1, gfp); in btree_insert()
514 static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo,
516 static void merge(struct btree_head *head, struct btree_geo *geo, int level, in merge() argument
532 btree_remove_level(head, geo, bkey(geo, parent, lpos), level + 1); in merge()
533 mempool_free(right, head->mempool); in merge()
536 static void rebalance(struct btree_head *head, struct btree_geo *geo, in rebalance() argument
547 btree_remove_level(head, geo, key, level + 1); in rebalance()
548 mempool_free(child, head->mempool); in rebalance()
552 parent = find_level(head, geo, key, level + 1); in rebalance()
560 merge(head, geo, level, in rebalance()
571 merge(head, geo, level, in rebalance()
587 static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo, in btree_remove_level() argument
594 if (level > head->height) { in btree_remove_level()
596 head->height = 0; in btree_remove_level()
597 head->node = NULL; in btree_remove_level()
601 node = find_level(head, geo, key, level); in btree_remove_level()
616 if (level < head->height) in btree_remove_level()
617 rebalance(head, geo, key, level, node, fill - 1); in btree_remove_level()
619 btree_shrink(head, geo); in btree_remove_level()
625 void *btree_remove(struct btree_head *head, struct btree_geo *geo, in btree_remove() argument
628 if (head->height == 0) in btree_remove()
631 return btree_remove_level(head, geo, key, 1); in btree_remove()
672 static size_t __btree_for_each(struct btree_head *head, struct btree_geo *geo, in __btree_for_each() argument
687 count = __btree_for_each(head, geo, child, opaque, in __btree_for_each()
694 mempool_free(node, head->mempool); in __btree_for_each()
742 size_t btree_visitor(struct btree_head *head, struct btree_geo *geo, in btree_visitor() argument
753 if (head->node) in btree_visitor()
754 count = __btree_for_each(head, geo, head->node, opaque, func, in btree_visitor()
755 func2, 0, head->height, 0); in btree_visitor()
760 size_t btree_grim_visitor(struct btree_head *head, struct btree_geo *geo, in btree_grim_visitor() argument
771 if (head->node) in btree_grim_visitor()
772 count = __btree_for_each(head, geo, head->node, opaque, func, in btree_grim_visitor()
773 func2, 1, head->height, 0); in btree_grim_visitor()
774 __btree_init(head); in btree_grim_visitor()