Lines Matching refs:root
81 static inline gfp_t root_gfp_mask(struct radix_tree_root *root)
83 return root->gfp_mask & __GFP_BITS_MASK;
91 radix_tree_node_alloc(struct radix_tree_root *root)
94 gfp_t gfp_mask = root_gfp_mask(root);
173 static inline void root_tag_set(struct radix_tree_root *root, unsigned int tag)
175 root->gfp_mask |= (__force gfp_t)(1 << (tag + __GFP_BITS_SHIFT));
179 static inline void root_tag_clear(struct radix_tree_root *root, unsigned int tag)
181 root->gfp_mask &= (__force gfp_t)~(1 << (tag + __GFP_BITS_SHIFT));
184 static inline void root_tag_clear_all(struct radix_tree_root *root)
186 root->gfp_mask &= __GFP_BITS_MASK;
189 static inline int root_tag_get(struct radix_tree_root *root, unsigned int tag)
191 return (__force unsigned)root->gfp_mask & (1 << (tag + __GFP_BITS_SHIFT));
220 static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
227 height = root->height + 1;
231 if (root->rnode == NULL) {
232 root->height = height;
238 if (!(node = radix_tree_node_alloc(root)))
242 node->slots[0] = radix_tree_direct_to_ptr(root->rnode);
244 /* Propagate the aggregated tag info into the new root */
246 if (root_tag_get(root, tag))
250 newheight = root->height+1;
253 rcu_assign_pointer(root->rnode, node);
254 root->height = newheight;
255 } while (height > root->height);
262 * @root: radix tree root
268 int radix_tree_insert(struct radix_tree_root *root,
279 if (index > radix_tree_maxindex(root->height)) {
280 error = radix_tree_extend(root, index);
285 slot = root->rnode;
286 height = root->height;
293 if (!(slot = radix_tree_node_alloc(root)))
300 rcu_assign_pointer(root->rnode, slot);
320 rcu_assign_pointer(root->rnode, radix_tree_ptr_to_direct(item));
321 BUG_ON(root_tag_get(root, 0));
322 BUG_ON(root_tag_get(root, 1));
331 * @root: radix tree root
335 * radix tree @root. This is useful for update-if-exists operations.
343 void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index)
348 node = root->rnode;
355 return (void **)&root->rnode;
381 * @root: radix tree root
384 * Lookup the item at the position @index in the radix tree @root.
391 void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
396 node = rcu_dereference(root->rnode);
429 * @root: radix tree root
435 * the root all the way down to the leaf node.
440 void *radix_tree_tag_set(struct radix_tree_root *root,
446 height = root->height;
449 slot = root->rnode;
464 /* set the root's tag bit */
465 if (slot && !root_tag_get(root, tag))
466 root_tag_set(root, tag);
474 * @root: radix tree root
486 void *radix_tree_tag_clear(struct radix_tree_root *root,
493 height = root->height;
499 slot = root->rnode;
528 /* clear the root's tag bit */
529 if (root_tag_get(root, tag))
530 root_tag_clear(root, tag);
540 * @root: radix tree root
549 int radix_tree_tag_get(struct radix_tree_root *root,
556 /* check the root's tag bit */
557 if (!root_tag_get(root, tag))
560 node = rcu_dereference(root->rnode);
652 * @root: radix tree root
670 radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
678 node = rcu_dereference(root->rnode);
778 * @root: radix tree root
789 radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
798 /* check the root's tag bit */
799 if (!root_tag_get(root, tag))
802 node = rcu_dereference(root->rnode);
837 * @root radix tree root
839 static inline void radix_tree_shrink(struct radix_tree_root *root)
842 while (root->height > 0 &&
843 root->rnode->count == 1 &&
844 root->rnode->slots[0]) {
845 struct radix_tree_node *to_free = root->rnode;
853 * one (root->rnode).
856 if (root->height == 1)
858 root->rnode = newptr;
859 root->height--;
871 * @root: radix tree root
874 * Remove the item at @index from the radix tree rooted at @root.
878 void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
887 height = root->height;
891 slot = root->rnode;
892 if (height == 0 && root->rnode) {
894 root_tag_clear_all(root);
895 root->rnode = NULL;
923 radix_tree_tag_clear(root, index, tag);
939 if (pathp->node == root->rnode)
940 radix_tree_shrink(root);
949 root_tag_clear_all(root);
950 root->height = 0;
951 root->rnode = NULL;
962 * @root: radix tree root
965 int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag)
967 return root_tag_get(root, tag);