Lines Matching refs:root
104 static inline gfp_t root_gfp_mask(const struct radix_tree_root *root) in root_gfp_mask() argument
106 return root->xa_flags & (__GFP_BITS_MASK & ~GFP_ZONEMASK); in root_gfp_mask()
127 static inline void root_tag_set(struct radix_tree_root *root, unsigned tag) in root_tag_set() argument
129 root->xa_flags |= (__force gfp_t)(1 << (tag + ROOT_TAG_SHIFT)); in root_tag_set()
132 static inline void root_tag_clear(struct radix_tree_root *root, unsigned tag) in root_tag_clear() argument
134 root->xa_flags &= (__force gfp_t)~(1 << (tag + ROOT_TAG_SHIFT)); in root_tag_clear()
137 static inline void root_tag_clear_all(struct radix_tree_root *root) in root_tag_clear_all() argument
139 root->xa_flags &= (__force gfp_t)((1 << ROOT_TAG_SHIFT) - 1); in root_tag_clear_all()
142 static inline int root_tag_get(const struct radix_tree_root *root, unsigned tag) in root_tag_get() argument
144 return (__force int)root->xa_flags & (1 << (tag + ROOT_TAG_SHIFT)); in root_tag_get()
147 static inline unsigned root_tags_get(const struct radix_tree_root *root) in root_tags_get() argument
149 return (__force unsigned)root->xa_flags >> ROOT_TAG_SHIFT; in root_tags_get()
152 static inline bool is_idr(const struct radix_tree_root *root) in is_idr() argument
154 return !!(root->xa_flags & ROOT_IS_IDR); in is_idr()
243 struct radix_tree_root *root, in radix_tree_node_alloc() argument
294 ret->array = root; in radix_tree_node_alloc()
397 static unsigned radix_tree_load_root(const struct radix_tree_root *root, in radix_tree_load_root() argument
400 struct radix_tree_node *node = rcu_dereference_raw(root->xa_head); in radix_tree_load_root()
417 static int radix_tree_extend(struct radix_tree_root *root, gfp_t gfp, in radix_tree_extend() argument
429 entry = rcu_dereference_raw(root->xa_head); in radix_tree_extend()
430 if (!entry && (!is_idr(root) || root_tag_get(root, IDR_FREE))) in radix_tree_extend()
435 root, shift, 0, 1, 0); in radix_tree_extend()
439 if (is_idr(root)) { in radix_tree_extend()
441 if (!root_tag_get(root, IDR_FREE)) { in radix_tree_extend()
443 root_tag_set(root, IDR_FREE); in radix_tree_extend()
448 if (root_tag_get(root, tag)) in radix_tree_extend()
466 rcu_assign_pointer(root->xa_head, entry); in radix_tree_extend()
477 static inline bool radix_tree_shrink(struct radix_tree_root *root) in radix_tree_shrink() argument
482 struct radix_tree_node *node = rcu_dereference_raw(root->xa_head); in radix_tree_shrink()
504 if (!node->shift && is_idr(root)) in radix_tree_shrink()
517 root->xa_head = (void __rcu *)child; in radix_tree_shrink()
518 if (is_idr(root) && !tag_get(node, IDR_FREE, 0)) in radix_tree_shrink()
519 root_tag_clear(root, IDR_FREE); in radix_tree_shrink()
552 static bool delete_node(struct radix_tree_root *root, in delete_node() argument
562 rcu_dereference_raw(root->xa_head)) in delete_node()
563 deleted |= radix_tree_shrink(root); in delete_node()
576 if (!is_idr(root)) in delete_node()
577 root_tag_clear_all(root); in delete_node()
578 root->xa_head = NULL; in delete_node()
607 static int __radix_tree_create(struct radix_tree_root *root, in __radix_tree_create() argument
612 void __rcu **slot = (void __rcu **)&root->xa_head; in __radix_tree_create()
616 gfp_t gfp = root_gfp_mask(root); in __radix_tree_create()
618 shift = radix_tree_load_root(root, &child, &maxindex); in __radix_tree_create()
622 int error = radix_tree_extend(root, gfp, max, shift); in __radix_tree_create()
626 child = rcu_dereference_raw(root->xa_head); in __radix_tree_create()
633 child = radix_tree_node_alloc(gfp, node, root, shift, in __radix_tree_create()
712 int radix_tree_insert(struct radix_tree_root *root, unsigned long index, in radix_tree_insert() argument
721 error = __radix_tree_create(root, index, &node, &slot); in radix_tree_insert()
735 BUG_ON(root_tags_get(root)); in radix_tree_insert()
756 void *__radix_tree_lookup(const struct radix_tree_root *root, in __radix_tree_lookup() argument
766 slot = (void __rcu **)&root->xa_head; in __radix_tree_lookup()
767 radix_tree_load_root(root, &node, &maxindex); in __radix_tree_lookup()
803 void __rcu **radix_tree_lookup_slot(const struct radix_tree_root *root, in radix_tree_lookup_slot() argument
808 if (!__radix_tree_lookup(root, index, NULL, &slot)) in radix_tree_lookup_slot()
826 void *radix_tree_lookup(const struct radix_tree_root *root, unsigned long index) in radix_tree_lookup() argument
828 return __radix_tree_lookup(root, index, NULL, NULL); in radix_tree_lookup()
843 static bool node_tag_get(const struct radix_tree_root *root, in node_tag_get() argument
849 return root_tag_get(root, tag); in node_tag_get()
859 static int calculate_count(struct radix_tree_root *root, in calculate_count() argument
863 if (is_idr(root)) { in calculate_count()
865 bool free = node_tag_get(root, node, IDR_FREE, offset); in calculate_count()
884 void __radix_tree_replace(struct radix_tree_root *root, in __radix_tree_replace() argument
890 int count = calculate_count(root, node, slot, item, old); in __radix_tree_replace()
897 WARN_ON_ONCE(!node && (slot != (void __rcu **)&root->xa_head) && in __radix_tree_replace()
904 delete_node(root, node); in __radix_tree_replace()
923 void radix_tree_replace_slot(struct radix_tree_root *root, in radix_tree_replace_slot() argument
926 __radix_tree_replace(root, NULL, slot, item); in radix_tree_replace_slot()
939 void radix_tree_iter_replace(struct radix_tree_root *root, in radix_tree_iter_replace() argument
943 __radix_tree_replace(root, iter->node, slot, item); in radix_tree_iter_replace()
946 static void node_tag_set(struct radix_tree_root *root, in node_tag_set() argument
958 if (!root_tag_get(root, tag)) in node_tag_set()
959 root_tag_set(root, tag); in node_tag_set()
975 void *radix_tree_tag_set(struct radix_tree_root *root, in radix_tree_tag_set() argument
981 radix_tree_load_root(root, &node, &maxindex); in radix_tree_tag_set()
996 if (!root_tag_get(root, tag)) in radix_tree_tag_set()
997 root_tag_set(root, tag); in radix_tree_tag_set()
1003 static void node_tag_clear(struct radix_tree_root *root, in node_tag_clear() argument
1019 if (root_tag_get(root, tag)) in node_tag_clear()
1020 root_tag_clear(root, tag); in node_tag_clear()
1037 void *radix_tree_tag_clear(struct radix_tree_root *root, in radix_tree_tag_clear() argument
1044 radix_tree_load_root(root, &node, &maxindex); in radix_tree_tag_clear()
1056 node_tag_clear(root, parent, tag, offset); in radix_tree_tag_clear()
1068 void radix_tree_iter_tag_clear(struct radix_tree_root *root, in radix_tree_iter_tag_clear() argument
1071 node_tag_clear(root, iter->node, tag, iter_offset(iter)); in radix_tree_iter_tag_clear()
1089 int radix_tree_tag_get(const struct radix_tree_root *root, in radix_tree_tag_get() argument
1095 if (!root_tag_get(root, tag)) in radix_tree_tag_get()
1098 radix_tree_load_root(root, &node, &maxindex); in radix_tree_tag_get()
1163 void __rcu **radix_tree_next_chunk(const struct radix_tree_root *root, in radix_tree_next_chunk() argument
1170 if ((flags & RADIX_TREE_ITER_TAGGED) && !root_tag_get(root, tag)) in radix_tree_next_chunk()
1187 radix_tree_load_root(root, &child, &maxindex); in radix_tree_next_chunk()
1199 return (void __rcu **)&root->xa_head; in radix_tree_next_chunk()
1271 radix_tree_gang_lookup(const struct radix_tree_root *root, void **results, in radix_tree_gang_lookup() argument
1281 radix_tree_for_each_slot(slot, root, &iter, first_index) { in radix_tree_gang_lookup()
1311 radix_tree_gang_lookup_tag(const struct radix_tree_root *root, void **results, in radix_tree_gang_lookup_tag() argument
1322 radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) { in radix_tree_gang_lookup_tag()
1352 radix_tree_gang_lookup_tag_slot(const struct radix_tree_root *root, in radix_tree_gang_lookup_tag_slot() argument
1363 radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) { in radix_tree_gang_lookup_tag_slot()
1373 static bool __radix_tree_delete(struct radix_tree_root *root, in __radix_tree_delete() argument
1381 if (is_idr(root)) in __radix_tree_delete()
1382 node_tag_set(root, node, IDR_FREE, offset); in __radix_tree_delete()
1385 node_tag_clear(root, node, tag, offset); in __radix_tree_delete()
1388 return node && delete_node(root, node); in __radix_tree_delete()
1403 void radix_tree_iter_delete(struct radix_tree_root *root, in radix_tree_iter_delete() argument
1406 if (__radix_tree_delete(root, iter->node, slot)) in radix_tree_iter_delete()
1422 void *radix_tree_delete_item(struct radix_tree_root *root, in radix_tree_delete_item() argument
1429 entry = __radix_tree_lookup(root, index, &node, &slot); in radix_tree_delete_item()
1432 if (!entry && (!is_idr(root) || node_tag_get(root, node, IDR_FREE, in radix_tree_delete_item()
1439 __radix_tree_delete(root, node, slot); in radix_tree_delete_item()
1454 void *radix_tree_delete(struct radix_tree_root *root, unsigned long index) in radix_tree_delete() argument
1456 return radix_tree_delete_item(root, index, NULL); in radix_tree_delete()
1465 int radix_tree_tagged(const struct radix_tree_root *root, unsigned int tag) in radix_tree_tagged() argument
1467 return root_tag_get(root, tag); in radix_tree_tagged()
1485 void __rcu **idr_get_free(struct radix_tree_root *root, in idr_get_free() argument
1490 void __rcu **slot = (void __rcu **)&root->xa_head; in idr_get_free()
1495 shift = radix_tree_load_root(root, &child, &maxindex); in idr_get_free()
1496 if (!radix_tree_tagged(root, IDR_FREE)) in idr_get_free()
1502 int error = radix_tree_extend(root, gfp, start, shift); in idr_get_free()
1506 child = rcu_dereference_raw(root->xa_head); in idr_get_free()
1515 child = radix_tree_node_alloc(gfp, node, root, shift, in idr_get_free()