Lines Matching refs: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)
95 return root->xa_flags & (__GFP_BITS_MASK & ~GFP_ZONEMASK);
116 static inline void root_tag_set(struct radix_tree_root *root, unsigned tag)
118 root->xa_flags |= (__force gfp_t)(1 << (tag + ROOT_TAG_SHIFT));
121 static inline void root_tag_clear(struct radix_tree_root *root, unsigned tag)
123 root->xa_flags &= (__force gfp_t)~(1 << (tag + ROOT_TAG_SHIFT));
126 static inline void root_tag_clear_all(struct radix_tree_root *root)
128 root->xa_flags &= (__force gfp_t)((1 << ROOT_TAG_SHIFT) - 1);
131 static inline int root_tag_get(const struct radix_tree_root *root, unsigned tag)
133 return (__force int)root->xa_flags & (1 << (tag + ROOT_TAG_SHIFT));
136 static inline unsigned root_tags_get(const struct radix_tree_root *root)
138 return (__force unsigned)root->xa_flags >> ROOT_TAG_SHIFT;
141 static inline bool is_idr(const struct radix_tree_root *root)
143 return !!(root->xa_flags & ROOT_IS_IDR);
232 struct radix_tree_root *root,
283 ret->array = root;
386 static unsigned radix_tree_load_root(const struct radix_tree_root *root,
389 struct radix_tree_node *node = rcu_dereference_raw(root->xa_head);
406 static int radix_tree_extend(struct radix_tree_root *root, gfp_t gfp,
418 entry = rcu_dereference_raw(root->xa_head);
419 if (!entry && (!is_idr(root) || root_tag_get(root, IDR_FREE)))
424 root, shift, 0, 1, 0);
428 if (is_idr(root)) {
430 if (!root_tag_get(root, IDR_FREE)) {
432 root_tag_set(root, IDR_FREE);
437 if (root_tag_get(root, tag))
446 /* Moving a value entry root->xa_head to a node */
455 rcu_assign_pointer(root->xa_head, entry);
464 * @root radix tree root
466 static inline bool radix_tree_shrink(struct radix_tree_root *root)
471 struct radix_tree_node *node = rcu_dereference_raw(root->xa_head);
489 * For an IDR, we must not shrink entry 0 into the root in
493 if (!node->shift && is_idr(root))
504 * one (root->xa_head) as far as dependent read barriers go.
506 root->xa_head = (void __rcu *)child;
507 if (is_idr(root) && !tag_get(node, IDR_FREE, 0))
508 root_tag_clear(root, IDR_FREE);
524 * problem (replacing direct root node with an indirect pointer
541 static bool delete_node(struct radix_tree_root *root,
551 rcu_dereference_raw(root->xa_head))
552 deleted |= radix_tree_shrink(root);
565 if (!is_idr(root))
566 root_tag_clear_all(root);
567 root->xa_head = NULL;
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,
601 void __rcu **slot = (void __rcu **)&root->xa_head;
605 gfp_t gfp = root_gfp_mask(root);
607 shift = radix_tree_load_root(root, &child, &maxindex);
611 int error = radix_tree_extend(root, gfp, max, shift);
615 child = rcu_dereference_raw(root->xa_head);
622 child = radix_tree_node_alloc(gfp, node, root, shift,
695 * @root: radix tree root
701 int radix_tree_insert(struct radix_tree_root *root, unsigned long index,
710 error = __radix_tree_create(root, index, &node, &slot);
724 BUG_ON(root_tags_get(root));
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,
755 slot = (void __rcu **)&root->xa_head;
756 radix_tree_load_root(root, &node, &maxindex);
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,
797 if (!__radix_tree_lookup(root, index, NULL, &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)
817 return __radix_tree_lookup(root, index, NULL, NULL);
832 static bool node_tag_get(const struct radix_tree_root *root,
838 return root_tag_get(root, tag);
848 static int calculate_count(struct radix_tree_root *root,
852 if (is_idr(root)) {
854 bool free = node_tag_get(root, node, IDR_FREE, offset);
865 * @root: radix tree root
873 void __radix_tree_replace(struct radix_tree_root *root,
879 int count = calculate_count(root, node, slot, item, old);
884 * node unless the slot is root->xa_head.
886 WARN_ON_ONCE(!node && (slot != (void __rcu **)&root->xa_head) &&
893 delete_node(root, node);
898 * @root: radix tree root
912 void radix_tree_replace_slot(struct radix_tree_root *root,
915 __radix_tree_replace(root, NULL, slot, item);
921 * @root: radix tree root
928 void radix_tree_iter_replace(struct radix_tree_root *root,
932 __radix_tree_replace(root, iter->node, slot, item);
935 static void node_tag_set(struct radix_tree_root *root,
947 if (!root_tag_get(root, tag))
948 root_tag_set(root, tag);
953 * @root: radix tree root
959 * the root all the way down to the leaf node.
964 void *radix_tree_tag_set(struct radix_tree_root *root,
970 radix_tree_load_root(root, &node, &maxindex);
984 /* set the root's tag bit */
985 if (!root_tag_get(root, tag))
986 root_tag_set(root, tag);
992 static void node_tag_clear(struct radix_tree_root *root,
1007 /* clear the root's tag bit */
1008 if (root_tag_get(root, tag))
1009 root_tag_clear(root, tag);
1014 * @root: radix tree root
1026 void *radix_tree_tag_clear(struct radix_tree_root *root,
1033 radix_tree_load_root(root, &node, &maxindex);
1045 node_tag_clear(root, parent, tag, offset);
1053 * @root: radix tree root
1057 void radix_tree_iter_tag_clear(struct radix_tree_root *root,
1060 node_tag_clear(root, iter->node, tag, iter_offset(iter));
1065 * @root: radix tree root
1078 int radix_tree_tag_get(const struct radix_tree_root *root,
1084 if (!root_tag_get(root, tag))
1087 radix_tree_load_root(root, &node, &maxindex);
1146 * @root: radix tree root
1151 void __rcu **radix_tree_next_chunk(const struct radix_tree_root *root,
1158 if ((flags & RADIX_TREE_ITER_TAGGED) && !root_tag_get(root, tag))
1175 radix_tree_load_root(root, &child, &maxindex);
1187 return (void __rcu **)&root->xa_head;
1240 * @root: radix tree root
1259 radix_tree_gang_lookup(const struct radix_tree_root *root, void **results,
1269 radix_tree_for_each_slot(slot, root, &iter, first_index) {
1288 * @root: radix tree root
1299 radix_tree_gang_lookup_tag(const struct radix_tree_root *root, void **results,
1310 radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) {
1329 * @root: radix tree root
1340 radix_tree_gang_lookup_tag_slot(const struct radix_tree_root *root,
1351 radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) {
1361 static bool __radix_tree_delete(struct radix_tree_root *root,
1369 if (is_idr(root))
1370 node_tag_set(root, node, IDR_FREE, offset);
1373 node_tag_clear(root, node, tag, offset);
1376 return node && delete_node(root, node);
1381 * @root: radix tree root
1391 void radix_tree_iter_delete(struct radix_tree_root *root,
1394 if (__radix_tree_delete(root, iter->node, slot))
1401 * @root: radix tree root
1405 * Remove @item at @index from the radix tree rooted at @root.
1410 void *radix_tree_delete_item(struct radix_tree_root *root,
1417 entry = __radix_tree_lookup(root, index, &node, &slot);
1420 if (!entry && (!is_idr(root) || node_tag_get(root, node, IDR_FREE,
1427 __radix_tree_delete(root, node, slot);
1435 * @root: radix tree root
1438 * Remove the entry at @index from the radix tree rooted at @root.
1442 void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
1444 return radix_tree_delete_item(root, index, NULL);
1450 * @root: radix tree root
1453 int radix_tree_tagged(const struct radix_tree_root *root, unsigned int tag)
1455 return root_tag_get(root, tag);
1473 void __rcu **idr_get_free(struct radix_tree_root *root,
1478 void __rcu **slot = (void __rcu **)&root->xa_head;
1483 shift = radix_tree_load_root(root, &child, &maxindex);
1484 if (!radix_tree_tagged(root, IDR_FREE))
1490 int error = radix_tree_extend(root, gfp, start, shift);
1494 child = rcu_dereference_raw(root->xa_head);
1503 child = radix_tree_node_alloc(gfp, node, root, shift,