Lines Matching refs:root
83 static inline gfp_t root_gfp_mask(struct radix_tree_root *root) in root_gfp_mask() argument
85 return root->gfp_mask & __GFP_BITS_MASK; in root_gfp_mask()
106 static inline void root_tag_set(struct radix_tree_root *root, unsigned int tag) in root_tag_set() argument
108 root->gfp_mask |= (__force gfp_t)(1 << (tag + __GFP_BITS_SHIFT)); in root_tag_set()
111 static inline void root_tag_clear(struct radix_tree_root *root, unsigned int tag) in root_tag_clear() argument
113 root->gfp_mask &= (__force gfp_t)~(1 << (tag + __GFP_BITS_SHIFT)); in root_tag_clear()
116 static inline void root_tag_clear_all(struct radix_tree_root *root) in root_tag_clear_all() argument
118 root->gfp_mask &= __GFP_BITS_MASK; in root_tag_clear_all()
121 static inline int root_tag_get(struct radix_tree_root *root, unsigned int tag) in root_tag_get() argument
123 return (__force unsigned)root->gfp_mask & (1 << (tag + __GFP_BITS_SHIFT)); in root_tag_get()
181 radix_tree_node_alloc(struct radix_tree_root *root) in radix_tree_node_alloc() argument
184 gfp_t gfp_mask = root_gfp_mask(root); in radix_tree_node_alloc()
326 static int radix_tree_extend(struct radix_tree_root *root, unsigned long index) in radix_tree_extend() argument
334 height = root->height + 1; in radix_tree_extend()
338 if (root->rnode == NULL) { in radix_tree_extend()
339 root->height = height; in radix_tree_extend()
345 if (!(node = radix_tree_node_alloc(root))) in radix_tree_extend()
350 if (root_tag_get(root, tag)) in radix_tree_extend()
355 newheight = root->height+1; in radix_tree_extend()
360 slot = root->rnode; in radix_tree_extend()
367 rcu_assign_pointer(root->rnode, node); in radix_tree_extend()
368 root->height = newheight; in radix_tree_extend()
369 } while (height > root->height); in radix_tree_extend()
390 int __radix_tree_create(struct radix_tree_root *root, unsigned long index, in __radix_tree_create() argument
398 if (index > radix_tree_maxindex(root->height)) { in __radix_tree_create()
399 error = radix_tree_extend(root, index); in __radix_tree_create()
404 slot = indirect_to_ptr(root->rnode); in __radix_tree_create()
406 height = root->height; in __radix_tree_create()
413 if (!(slot = radix_tree_node_alloc(root))) in __radix_tree_create()
422 rcu_assign_pointer(root->rnode, ptr_to_indirect(slot)); in __radix_tree_create()
436 *slotp = node ? node->slots + offset : (void **)&root->rnode; in __radix_tree_create()
448 int radix_tree_insert(struct radix_tree_root *root, in radix_tree_insert() argument
457 error = __radix_tree_create(root, index, &node, &slot); in radix_tree_insert()
469 BUG_ON(root_tag_get(root, 0)); in radix_tree_insert()
470 BUG_ON(root_tag_get(root, 1)); in radix_tree_insert()
491 void *__radix_tree_lookup(struct radix_tree_root *root, unsigned long index, in __radix_tree_lookup() argument
498 node = rcu_dereference_raw(root->rnode); in __radix_tree_lookup()
509 *slotp = (void **)&root->rnode; in __radix_tree_lookup()
551 void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index) in radix_tree_lookup_slot() argument
555 if (!__radix_tree_lookup(root, index, NULL, &slot)) in radix_tree_lookup_slot()
573 void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index) in radix_tree_lookup() argument
575 return __radix_tree_lookup(root, index, NULL, NULL); in radix_tree_lookup()
592 void *radix_tree_tag_set(struct radix_tree_root *root, in radix_tree_tag_set() argument
598 height = root->height; in radix_tree_tag_set()
601 slot = indirect_to_ptr(root->rnode); in radix_tree_tag_set()
617 if (slot && !root_tag_get(root, tag)) in radix_tree_tag_set()
618 root_tag_set(root, tag); in radix_tree_tag_set()
638 void *radix_tree_tag_clear(struct radix_tree_root *root, in radix_tree_tag_clear() argument
646 height = root->height; in radix_tree_tag_clear()
651 slot = indirect_to_ptr(root->rnode); in radix_tree_tag_clear()
679 if (root_tag_get(root, tag)) in radix_tree_tag_clear()
680 root_tag_clear(root, tag); in radix_tree_tag_clear()
702 int radix_tree_tag_get(struct radix_tree_root *root, in radix_tree_tag_get() argument
709 if (!root_tag_get(root, tag)) in radix_tree_tag_get()
712 node = rcu_dereference_raw(root->rnode); in radix_tree_tag_get()
752 void **radix_tree_next_chunk(struct radix_tree_root *root, in radix_tree_next_chunk() argument
759 if ((flags & RADIX_TREE_ITER_TAGGED) && !root_tag_get(root, tag)) in radix_tree_next_chunk()
775 rnode = rcu_dereference_raw(root->rnode); in radix_tree_next_chunk()
783 return (void **)&root->rnode; in radix_tree_next_chunk()
888 unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root, in radix_tree_range_tag_if_tagged() argument
893 unsigned int height = root->height; in radix_tree_range_tag_if_tagged()
905 if (!root_tag_get(root, iftag)) { in radix_tree_range_tag_if_tagged()
911 root_tag_set(root, settag); in radix_tree_range_tag_if_tagged()
916 slot = indirect_to_ptr(root->rnode); in radix_tree_range_tag_if_tagged()
984 root_tag_set(root, settag); in radix_tree_range_tag_if_tagged()
1011 radix_tree_gang_lookup(struct radix_tree_root *root, void **results, in radix_tree_gang_lookup() argument
1021 radix_tree_for_each_slot(slot, root, &iter, first_index) { in radix_tree_gang_lookup()
1056 radix_tree_gang_lookup_slot(struct radix_tree_root *root, in radix_tree_gang_lookup_slot() argument
1067 radix_tree_for_each_slot(slot, root, &iter, first_index) { in radix_tree_gang_lookup_slot()
1093 radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results, in radix_tree_gang_lookup_tag() argument
1104 radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) { in radix_tree_gang_lookup_tag()
1134 radix_tree_gang_lookup_tag_slot(struct radix_tree_root *root, void ***results, in radix_tree_gang_lookup_tag_slot() argument
1145 radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) { in radix_tree_gang_lookup_tag_slot()
1212 unsigned long radix_tree_locate_item(struct radix_tree_root *root, void *item) in radix_tree_locate_item() argument
1221 node = rcu_dereference_raw(root->rnode); in radix_tree_locate_item()
1245 unsigned long radix_tree_locate_item(struct radix_tree_root *root, void *item) in radix_tree_locate_item() argument
1255 static inline void radix_tree_shrink(struct radix_tree_root *root) in radix_tree_shrink() argument
1258 while (root->height > 0) { in radix_tree_shrink()
1259 struct radix_tree_node *to_free = root->rnode; in radix_tree_shrink()
1282 if (root->height > 1) { in radix_tree_shrink()
1286 root->rnode = slot; in radix_tree_shrink()
1287 root->height--; in radix_tree_shrink()
1307 if (root->height == 0) in radix_tree_shrink()
1326 bool __radix_tree_delete_node(struct radix_tree_root *root, in __radix_tree_delete_node() argument
1335 if (node == indirect_to_ptr(root->rnode)) { in __radix_tree_delete_node()
1336 radix_tree_shrink(root); in __radix_tree_delete_node()
1337 if (root->height == 0) in __radix_tree_delete_node()
1351 root_tag_clear_all(root); in __radix_tree_delete_node()
1352 root->height = 0; in __radix_tree_delete_node()
1353 root->rnode = NULL; in __radix_tree_delete_node()
1376 void *radix_tree_delete_item(struct radix_tree_root *root, in radix_tree_delete_item() argument
1385 entry = __radix_tree_lookup(root, index, &node, &slot); in radix_tree_delete_item()
1393 root_tag_clear_all(root); in radix_tree_delete_item()
1394 root->rnode = NULL; in radix_tree_delete_item()
1406 radix_tree_tag_clear(root, index, tag); in radix_tree_delete_item()
1412 __radix_tree_delete_node(root, node); in radix_tree_delete_item()
1427 void *radix_tree_delete(struct radix_tree_root *root, unsigned long index) in radix_tree_delete() argument
1429 return radix_tree_delete_item(root, index, NULL); in radix_tree_delete()
1438 int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag) in radix_tree_tagged() argument
1440 return root_tag_get(root, tag); in radix_tree_tagged()