Lines Matching refs:root
75 struct radix_tree_root *root) in radix_tree_node_alloc() argument
78 ret = root->node_alloc(root->node_alloc_free_arg); in radix_tree_node_alloc()
85 struct radix_tree_root *root, struct radix_tree_node *node) in radix_tree_node_free() argument
87 root->node_free(node, root->node_alloc_free_arg); in radix_tree_node_free()
102 static int radix_tree_extend(struct radix_tree_root *root, unsigned long index) in radix_tree_extend() argument
108 height = root->height + 1; in radix_tree_extend()
112 if (root->rnode == NULL) { in radix_tree_extend()
113 root->height = height; in radix_tree_extend()
119 if (!(node = radix_tree_node_alloc(root))) in radix_tree_extend()
123 node->slots[0] = indirect_to_ptr(root->rnode); in radix_tree_extend()
125 newheight = root->height+1; in radix_tree_extend()
129 rcu_assign_pointer(root->rnode, node); in radix_tree_extend()
130 root->height = newheight; in radix_tree_extend()
131 } while (height > root->height); in radix_tree_extend()
144 int radix_tree_insert(struct radix_tree_root *root, in radix_tree_insert() argument
155 if (index > radix_tree_maxindex(root->height)) { in radix_tree_insert()
156 error = radix_tree_extend(root, index); in radix_tree_insert()
161 slot = indirect_to_ptr(root->rnode); in radix_tree_insert()
163 height = root->height; in radix_tree_insert()
170 if (!(slot = radix_tree_node_alloc(root))) in radix_tree_insert()
177 rcu_assign_pointer(root->rnode, ptr_to_indirect(slot)); in radix_tree_insert()
195 rcu_assign_pointer(root->rnode, item); in radix_tree_insert()
206 static void *radix_tree_lookup_element(struct radix_tree_root *root, in radix_tree_lookup_element() argument
212 node = rcu_dereference(root->rnode); in radix_tree_lookup_element()
219 return is_slot ? (void *)&root->rnode : node; in radix_tree_lookup_element()
256 void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index) in radix_tree_lookup_slot() argument
258 return (void **)radix_tree_lookup_element(root, index, 1); in radix_tree_lookup_slot()
274 void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index) in radix_tree_lookup() argument
276 return radix_tree_lookup_element(root, index, 0); in radix_tree_lookup()
300 unsigned long radix_tree_next_hole(struct radix_tree_root *root, in radix_tree_next_hole() argument
306 if (!radix_tree_lookup(root, index)) in radix_tree_next_hole()
337 unsigned long radix_tree_prev_hole(struct radix_tree_root *root, in radix_tree_prev_hole() argument
343 if (!radix_tree_lookup(root, index)) in radix_tree_prev_hole()
421 radix_tree_gang_lookup(struct radix_tree_root *root, void **results, in radix_tree_gang_lookup() argument
429 node = rcu_dereference(root->rnode); in radix_tree_gang_lookup()
490 radix_tree_gang_lookup_slot(struct radix_tree_root *root, void ***results, in radix_tree_gang_lookup_slot() argument
498 node = rcu_dereference(root->rnode); in radix_tree_gang_lookup_slot()
505 results[0] = (void **)&root->rnode; in radix_tree_gang_lookup_slot()
535 static inline void radix_tree_shrink(struct radix_tree_root *root) in radix_tree_shrink() argument
538 while (root->height > 0) { in radix_tree_shrink()
539 struct radix_tree_node *to_free = root->rnode; in radix_tree_shrink()
562 if (root->height > 1) in radix_tree_shrink()
564 root->rnode = newptr; in radix_tree_shrink()
565 root->height--; in radix_tree_shrink()
585 if (root->height == 0) in radix_tree_shrink()
589 radix_tree_node_free(root, to_free); in radix_tree_shrink()
602 void *radix_tree_delete(struct radix_tree_root *root, unsigned long index) in radix_tree_delete() argument
614 height = root->height; in radix_tree_delete()
618 slot = root->rnode; in radix_tree_delete()
620 root->rnode = NULL; in radix_tree_delete()
654 radix_tree_node_free(root, to_free); in radix_tree_delete()
657 if (pathp->node == indirect_to_ptr(root->rnode)) in radix_tree_delete()
658 radix_tree_shrink(root); in radix_tree_delete()
667 root->height = 0; in radix_tree_delete()
668 root->rnode = NULL; in radix_tree_delete()
670 radix_tree_node_free(root, to_free); in radix_tree_delete()
679 struct radix_tree_root *root, struct radix_tree_node *node, in radix_tree_node_destroy() argument
693 radix_tree_node_destroy(root, slot, slot_free); in radix_tree_node_destroy()
697 radix_tree_node_free(root, node); in radix_tree_node_destroy()
701 struct radix_tree_root *root, in radix_tree_destroy() argument
704 struct radix_tree_node *node = root->rnode; in radix_tree_destroy()
712 radix_tree_node_destroy(root, node, slot_free); in radix_tree_destroy()
714 radix_tree_init(root); in radix_tree_destroy()
717 void radix_tree_init(struct radix_tree_root *root) in radix_tree_init() argument
719 memset(root, 0, sizeof(*root)); in radix_tree_init()
720 root->node_alloc = rcu_node_alloc; in radix_tree_init()
721 root->node_free = rcu_node_free; in radix_tree_init()
725 struct radix_tree_root *root, in radix_tree_set_alloc_callbacks() argument
730 root->node_alloc = node_alloc; in radix_tree_set_alloc_callbacks()
731 root->node_free = node_free; in radix_tree_set_alloc_callbacks()
732 root->node_alloc_free_arg = node_alloc_free_arg; in radix_tree_set_alloc_callbacks()