Lines Matching refs:root
82 static inline gfp_t root_gfp_mask(struct radix_tree_root *root) in root_gfp_mask() argument
84 return root->gfp_mask & __GFP_BITS_MASK; in root_gfp_mask()
105 static inline void root_tag_set(struct radix_tree_root *root, unsigned int tag) in root_tag_set() argument
107 root->gfp_mask |= (__force gfp_t)(1 << (tag + __GFP_BITS_SHIFT)); in root_tag_set()
110 static inline void root_tag_clear(struct radix_tree_root *root, unsigned int tag) in root_tag_clear() argument
112 root->gfp_mask &= (__force gfp_t)~(1 << (tag + __GFP_BITS_SHIFT)); in root_tag_clear()
115 static inline void root_tag_clear_all(struct radix_tree_root *root) in root_tag_clear_all() argument
117 root->gfp_mask &= __GFP_BITS_MASK; in root_tag_clear_all()
120 static inline int root_tag_get(struct radix_tree_root *root, unsigned int tag) in root_tag_get() argument
122 return (__force unsigned)root->gfp_mask & (1 << (tag + __GFP_BITS_SHIFT)); in root_tag_get()
180 radix_tree_node_alloc(struct radix_tree_root *root) in radix_tree_node_alloc() argument
183 gfp_t gfp_mask = root_gfp_mask(root); in radix_tree_node_alloc()
321 static int radix_tree_extend(struct radix_tree_root *root, unsigned long index) in radix_tree_extend() argument
329 height = root->height + 1; in radix_tree_extend()
333 if (root->rnode == NULL) { in radix_tree_extend()
334 root->height = height; in radix_tree_extend()
340 if (!(node = radix_tree_node_alloc(root))) in radix_tree_extend()
345 if (root_tag_get(root, tag)) in radix_tree_extend()
350 newheight = root->height+1; in radix_tree_extend()
355 slot = root->rnode; in radix_tree_extend()
362 rcu_assign_pointer(root->rnode, node); in radix_tree_extend()
363 root->height = newheight; in radix_tree_extend()
364 } while (height > root->height); in radix_tree_extend()
385 int __radix_tree_create(struct radix_tree_root *root, unsigned long index, in __radix_tree_create() argument
393 if (index > radix_tree_maxindex(root->height)) { in __radix_tree_create()
394 error = radix_tree_extend(root, index); in __radix_tree_create()
399 slot = indirect_to_ptr(root->rnode); in __radix_tree_create()
401 height = root->height; in __radix_tree_create()
408 if (!(slot = radix_tree_node_alloc(root))) in __radix_tree_create()
417 rcu_assign_pointer(root->rnode, ptr_to_indirect(slot)); in __radix_tree_create()
431 *slotp = node ? node->slots + offset : (void **)&root->rnode; in __radix_tree_create()
443 int radix_tree_insert(struct radix_tree_root *root, in radix_tree_insert() argument
452 error = __radix_tree_create(root, index, &node, &slot); in radix_tree_insert()
464 BUG_ON(root_tag_get(root, 0)); in radix_tree_insert()
465 BUG_ON(root_tag_get(root, 1)); in radix_tree_insert()
486 void *__radix_tree_lookup(struct radix_tree_root *root, unsigned long index, in __radix_tree_lookup() argument
493 node = rcu_dereference_raw(root->rnode); in __radix_tree_lookup()
504 *slotp = (void **)&root->rnode; in __radix_tree_lookup()
546 void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index) in radix_tree_lookup_slot() argument
550 if (!__radix_tree_lookup(root, index, NULL, &slot)) in radix_tree_lookup_slot()
568 void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index) in radix_tree_lookup() argument
570 return __radix_tree_lookup(root, index, NULL, NULL); in radix_tree_lookup()
587 void *radix_tree_tag_set(struct radix_tree_root *root, in radix_tree_tag_set() argument
593 height = root->height; in radix_tree_tag_set()
596 slot = indirect_to_ptr(root->rnode); in radix_tree_tag_set()
612 if (slot && !root_tag_get(root, tag)) in radix_tree_tag_set()
613 root_tag_set(root, tag); in radix_tree_tag_set()
633 void *radix_tree_tag_clear(struct radix_tree_root *root, in radix_tree_tag_clear() argument
641 height = root->height; in radix_tree_tag_clear()
646 slot = indirect_to_ptr(root->rnode); in radix_tree_tag_clear()
674 if (root_tag_get(root, tag)) in radix_tree_tag_clear()
675 root_tag_clear(root, tag); in radix_tree_tag_clear()
697 int radix_tree_tag_get(struct radix_tree_root *root, in radix_tree_tag_get() argument
704 if (!root_tag_get(root, tag)) in radix_tree_tag_get()
707 node = rcu_dereference_raw(root->rnode); in radix_tree_tag_get()
747 void **radix_tree_next_chunk(struct radix_tree_root *root, in radix_tree_next_chunk() argument
754 if ((flags & RADIX_TREE_ITER_TAGGED) && !root_tag_get(root, tag)) in radix_tree_next_chunk()
770 rnode = rcu_dereference_raw(root->rnode); in radix_tree_next_chunk()
778 return (void **)&root->rnode; in radix_tree_next_chunk()
883 unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root, in radix_tree_range_tag_if_tagged() argument
888 unsigned int height = root->height; in radix_tree_range_tag_if_tagged()
900 if (!root_tag_get(root, iftag)) { in radix_tree_range_tag_if_tagged()
906 root_tag_set(root, settag); in radix_tree_range_tag_if_tagged()
911 slot = indirect_to_ptr(root->rnode); in radix_tree_range_tag_if_tagged()
979 root_tag_set(root, settag); in radix_tree_range_tag_if_tagged()
1006 radix_tree_gang_lookup(struct radix_tree_root *root, void **results, in radix_tree_gang_lookup() argument
1016 radix_tree_for_each_slot(slot, root, &iter, first_index) { in radix_tree_gang_lookup()
1051 radix_tree_gang_lookup_slot(struct radix_tree_root *root, in radix_tree_gang_lookup_slot() argument
1062 radix_tree_for_each_slot(slot, root, &iter, first_index) { in radix_tree_gang_lookup_slot()
1088 radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results, in radix_tree_gang_lookup_tag() argument
1099 radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) { in radix_tree_gang_lookup_tag()
1129 radix_tree_gang_lookup_tag_slot(struct radix_tree_root *root, void ***results, in radix_tree_gang_lookup_tag_slot() argument
1140 radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) { in radix_tree_gang_lookup_tag_slot()
1207 unsigned long radix_tree_locate_item(struct radix_tree_root *root, void *item) in radix_tree_locate_item() argument
1216 node = rcu_dereference_raw(root->rnode); in radix_tree_locate_item()
1240 unsigned long radix_tree_locate_item(struct radix_tree_root *root, void *item) in radix_tree_locate_item() argument
1250 static inline void radix_tree_shrink(struct radix_tree_root *root) in radix_tree_shrink() argument
1253 while (root->height > 0) { in radix_tree_shrink()
1254 struct radix_tree_node *to_free = root->rnode; in radix_tree_shrink()
1277 if (root->height > 1) { in radix_tree_shrink()
1281 root->rnode = slot; in radix_tree_shrink()
1282 root->height--; in radix_tree_shrink()
1302 if (root->height == 0) in radix_tree_shrink()
1321 bool __radix_tree_delete_node(struct radix_tree_root *root, in __radix_tree_delete_node() argument
1330 if (node == indirect_to_ptr(root->rnode)) { in __radix_tree_delete_node()
1331 radix_tree_shrink(root); in __radix_tree_delete_node()
1332 if (root->height == 0) in __radix_tree_delete_node()
1346 root_tag_clear_all(root); in __radix_tree_delete_node()
1347 root->height = 0; in __radix_tree_delete_node()
1348 root->rnode = NULL; in __radix_tree_delete_node()
1371 void *radix_tree_delete_item(struct radix_tree_root *root, in radix_tree_delete_item() argument
1380 entry = __radix_tree_lookup(root, index, &node, &slot); in radix_tree_delete_item()
1388 root_tag_clear_all(root); in radix_tree_delete_item()
1389 root->rnode = NULL; in radix_tree_delete_item()
1401 radix_tree_tag_clear(root, index, tag); in radix_tree_delete_item()
1407 __radix_tree_delete_node(root, node); in radix_tree_delete_item()
1422 void *radix_tree_delete(struct radix_tree_root *root, unsigned long index) in radix_tree_delete() argument
1424 return radix_tree_delete_item(root, index, NULL); in radix_tree_delete()
1433 int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag) in radix_tree_tagged() argument
1435 return root_tag_get(root, tag); in radix_tree_tagged()