Lines Matching full:root
43 * of RADIX_TREE_MAX_PATH size to be created, with only the root node shared.
93 static inline gfp_t root_gfp_mask(const struct radix_tree_root *root) in root_gfp_mask() argument
95 return root->xa_flags & (__GFP_BITS_MASK & ~GFP_ZONEMASK); in root_gfp_mask()
116 static inline void root_tag_set(struct radix_tree_root *root, unsigned tag) in root_tag_set() argument
118 root->xa_flags |= (__force gfp_t)(1 << (tag + ROOT_TAG_SHIFT)); in root_tag_set()
121 static inline void root_tag_clear(struct radix_tree_root *root, unsigned tag) in root_tag_clear() argument
123 root->xa_flags &= (__force gfp_t)~(1 << (tag + ROOT_TAG_SHIFT)); in root_tag_clear()
126 static inline void root_tag_clear_all(struct radix_tree_root *root) in root_tag_clear_all() argument
128 root->xa_flags &= (__force gfp_t)((1 << ROOT_TAG_SHIFT) - 1); in root_tag_clear_all()
131 static inline int root_tag_get(const struct radix_tree_root *root, unsigned tag) in root_tag_get() argument
133 return (__force int)root->xa_flags & (1 << (tag + ROOT_TAG_SHIFT)); in root_tag_get()
136 static inline unsigned root_tags_get(const struct radix_tree_root *root) in root_tags_get() argument
138 return (__force unsigned)root->xa_flags >> ROOT_TAG_SHIFT; in root_tags_get()
141 static inline bool is_idr(const struct radix_tree_root *root) in is_idr() argument
143 return !!(root->xa_flags & ROOT_IS_IDR); in is_idr()
232 struct radix_tree_root *root, in radix_tree_node_alloc() argument
283 ret->array = root; in radix_tree_node_alloc()
386 static unsigned radix_tree_load_root(const struct radix_tree_root *root, in radix_tree_load_root() argument
389 struct radix_tree_node *node = rcu_dereference_raw(root->xa_head); in radix_tree_load_root()
406 static int radix_tree_extend(struct radix_tree_root *root, gfp_t gfp, in radix_tree_extend() argument
418 entry = rcu_dereference_raw(root->xa_head); in radix_tree_extend()
419 if (!entry && (!is_idr(root) || root_tag_get(root, IDR_FREE))) in radix_tree_extend()
424 root, shift, 0, 1, 0); in radix_tree_extend()
428 if (is_idr(root)) { in radix_tree_extend()
430 if (!root_tag_get(root, IDR_FREE)) { in radix_tree_extend()
432 root_tag_set(root, IDR_FREE); in radix_tree_extend()
437 if (root_tag_get(root, tag)) in radix_tree_extend()
446 /* Moving a value entry root->xa_head to a node */ in radix_tree_extend()
455 rcu_assign_pointer(root->xa_head, entry); in radix_tree_extend()
464 * @root: radix tree root
466 static inline bool radix_tree_shrink(struct radix_tree_root *root) in radix_tree_shrink() argument
471 struct radix_tree_node *node = rcu_dereference_raw(root->xa_head); in radix_tree_shrink()
489 * For an IDR, we must not shrink entry 0 into the root in in radix_tree_shrink()
493 if (!node->shift && is_idr(root)) in radix_tree_shrink()
504 * one (root->xa_head) as far as dependent read barriers go. in radix_tree_shrink()
506 root->xa_head = (void __rcu *)child; in radix_tree_shrink()
507 if (is_idr(root) && !tag_get(node, IDR_FREE, 0)) in radix_tree_shrink()
508 root_tag_clear(root, IDR_FREE); in radix_tree_shrink()
524 * problem (replacing direct root node with an indirect pointer in radix_tree_shrink()
541 static bool delete_node(struct radix_tree_root *root, in delete_node() argument
551 rcu_dereference_raw(root->xa_head)) in delete_node()
552 deleted |= radix_tree_shrink(root); in delete_node()
565 if (!is_idr(root)) in delete_node()
566 root_tag_clear_all(root); in delete_node()
567 root->xa_head = NULL; in delete_node()
582 * @root: radix tree root
588 * at position @index in the radix tree @root.
591 * allocated and @root->xa_head is used as a direct slot instead of
596 static int __radix_tree_create(struct radix_tree_root *root, in __radix_tree_create() argument
601 void __rcu **slot = (void __rcu **)&root->xa_head; in __radix_tree_create()
605 gfp_t gfp = root_gfp_mask(root); in __radix_tree_create()
607 shift = radix_tree_load_root(root, &child, &maxindex); in __radix_tree_create()
611 int error = radix_tree_extend(root, gfp, max, shift); in __radix_tree_create()
615 child = rcu_dereference_raw(root->xa_head); in __radix_tree_create()
622 child = radix_tree_node_alloc(gfp, node, root, shift, in __radix_tree_create()
695 * @root: radix tree root
701 int radix_tree_insert(struct radix_tree_root *root, unsigned long index, in radix_tree_insert() argument
710 error = __radix_tree_create(root, index, &node, &slot); in radix_tree_insert()
724 BUG_ON(root_tags_get(root)); in radix_tree_insert()
733 * @root: radix tree root
739 * tree @root.
742 * allocated and @root->xa_head is used as a direct slot instead of
745 void *__radix_tree_lookup(const struct radix_tree_root *root, in __radix_tree_lookup() argument
755 slot = (void __rcu **)&root->xa_head; in __radix_tree_lookup()
756 radix_tree_load_root(root, &node, &maxindex); in __radix_tree_lookup()
781 * @root: radix tree root
785 * radix tree @root. This is useful for update-if-exists operations.
792 void __rcu **radix_tree_lookup_slot(const struct radix_tree_root *root, in radix_tree_lookup_slot() argument
797 if (!__radix_tree_lookup(root, index, NULL, &slot)) in radix_tree_lookup_slot()
805 * @root: radix tree root
808 * Lookup the item at the position @index in the radix tree @root.
815 void *radix_tree_lookup(const struct radix_tree_root *root, unsigned long index) in radix_tree_lookup() argument
817 return __radix_tree_lookup(root, index, NULL, NULL); in radix_tree_lookup()
832 static bool node_tag_get(const struct radix_tree_root *root, in node_tag_get() argument
838 return root_tag_get(root, tag); in node_tag_get()
848 static int calculate_count(struct radix_tree_root *root, in calculate_count() argument
852 if (is_idr(root)) { in calculate_count()
854 bool free = node_tag_get(root, node, IDR_FREE, offset); in calculate_count()
865 * @root: radix tree root
873 void __radix_tree_replace(struct radix_tree_root *root, in __radix_tree_replace() argument
879 int count = calculate_count(root, node, slot, item, old); in __radix_tree_replace()
884 * node unless the slot is root->xa_head. in __radix_tree_replace()
886 WARN_ON_ONCE(!node && (slot != (void __rcu **)&root->xa_head) && in __radix_tree_replace()
893 delete_node(root, node); in __radix_tree_replace()
898 * @root: radix tree root
912 void radix_tree_replace_slot(struct radix_tree_root *root, in radix_tree_replace_slot() argument
915 __radix_tree_replace(root, NULL, slot, item); in radix_tree_replace_slot()
921 * @root: radix tree root
929 void radix_tree_iter_replace(struct radix_tree_root *root, in radix_tree_iter_replace() argument
933 __radix_tree_replace(root, iter->node, slot, item); in radix_tree_iter_replace()
936 static void node_tag_set(struct radix_tree_root *root, in node_tag_set() argument
948 if (!root_tag_get(root, tag)) in node_tag_set()
949 root_tag_set(root, tag); in node_tag_set()
954 * @root: radix tree root
960 * the root all the way down to the leaf node.
965 void *radix_tree_tag_set(struct radix_tree_root *root, in radix_tree_tag_set() argument
971 radix_tree_load_root(root, &node, &maxindex); in radix_tree_tag_set()
985 /* set the root's tag bit */ in radix_tree_tag_set()
986 if (!root_tag_get(root, tag)) in radix_tree_tag_set()
987 root_tag_set(root, tag); in radix_tree_tag_set()
993 static void node_tag_clear(struct radix_tree_root *root, in node_tag_clear() argument
1008 /* clear the root's tag bit */ in node_tag_clear()
1009 if (root_tag_get(root, tag)) in node_tag_clear()
1010 root_tag_clear(root, tag); in node_tag_clear()
1015 * @root: radix tree root
1027 void *radix_tree_tag_clear(struct radix_tree_root *root, in radix_tree_tag_clear() argument
1034 radix_tree_load_root(root, &node, &maxindex); in radix_tree_tag_clear()
1046 node_tag_clear(root, parent, tag, offset); in radix_tree_tag_clear()
1054 * @root: radix tree root
1058 void radix_tree_iter_tag_clear(struct radix_tree_root *root, in radix_tree_iter_tag_clear() argument
1061 node_tag_clear(root, iter->node, tag, iter_offset(iter)); in radix_tree_iter_tag_clear()
1066 * @root: radix tree root
1079 int radix_tree_tag_get(const struct radix_tree_root *root, in radix_tree_tag_get() argument
1085 if (!root_tag_get(root, tag)) in radix_tree_tag_get()
1088 radix_tree_load_root(root, &node, &maxindex); in radix_tree_tag_get()
1148 * @root: radix tree root
1153 void __rcu **radix_tree_next_chunk(const struct radix_tree_root *root, in radix_tree_next_chunk() argument
1160 if ((flags & RADIX_TREE_ITER_TAGGED) && !root_tag_get(root, tag)) in radix_tree_next_chunk()
1177 radix_tree_load_root(root, &child, &maxindex); in radix_tree_next_chunk()
1189 return (void __rcu **)&root->xa_head; in radix_tree_next_chunk()
1242 * @root: radix tree root
1261 radix_tree_gang_lookup(const struct radix_tree_root *root, void **results, in radix_tree_gang_lookup() argument
1271 radix_tree_for_each_slot(slot, root, &iter, first_index) { in radix_tree_gang_lookup()
1290 * @root: radix tree root
1301 radix_tree_gang_lookup_tag(const struct radix_tree_root *root, void **results, in radix_tree_gang_lookup_tag() argument
1312 radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) { in radix_tree_gang_lookup_tag()
1331 * @root: radix tree root
1342 radix_tree_gang_lookup_tag_slot(const struct radix_tree_root *root, in radix_tree_gang_lookup_tag_slot() argument
1353 radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) { in radix_tree_gang_lookup_tag_slot()
1363 static bool __radix_tree_delete(struct radix_tree_root *root, in __radix_tree_delete() argument
1371 if (is_idr(root)) in __radix_tree_delete()
1372 node_tag_set(root, node, IDR_FREE, offset); in __radix_tree_delete()
1375 node_tag_clear(root, node, tag, offset); in __radix_tree_delete()
1378 return node && delete_node(root, node); in __radix_tree_delete()
1383 * @root: radix tree root
1393 void radix_tree_iter_delete(struct radix_tree_root *root, in radix_tree_iter_delete() argument
1396 if (__radix_tree_delete(root, iter->node, slot)) in radix_tree_iter_delete()
1403 * @root: radix tree root
1407 * Remove @item at @index from the radix tree rooted at @root.
1412 void *radix_tree_delete_item(struct radix_tree_root *root, in radix_tree_delete_item() argument
1419 entry = __radix_tree_lookup(root, index, &node, &slot); in radix_tree_delete_item()
1422 if (!entry && (!is_idr(root) || node_tag_get(root, node, IDR_FREE, in radix_tree_delete_item()
1429 __radix_tree_delete(root, node, slot); in radix_tree_delete_item()
1437 * @root: radix tree root
1440 * Remove the entry at @index from the radix tree rooted at @root.
1444 void *radix_tree_delete(struct radix_tree_root *root, unsigned long index) in radix_tree_delete() argument
1446 return radix_tree_delete_item(root, index, NULL); in radix_tree_delete()
1452 * @root: radix tree root
1455 int radix_tree_tagged(const struct radix_tree_root *root, unsigned int tag) in radix_tree_tagged() argument
1457 return root_tag_get(root, tag); in radix_tree_tagged()
1475 void __rcu **idr_get_free(struct radix_tree_root *root, in idr_get_free() argument
1480 void __rcu **slot = (void __rcu **)&root->xa_head; in idr_get_free()
1485 shift = radix_tree_load_root(root, &child, &maxindex); in idr_get_free()
1486 if (!radix_tree_tagged(root, IDR_FREE)) in idr_get_free()
1492 int error = radix_tree_extend(root, gfp, start, shift); in idr_get_free()
1496 child = rcu_dereference_raw(root->xa_head); in idr_get_free()
1505 child = radix_tree_node_alloc(gfp, node, root, shift, in idr_get_free()