Lines Matching refs:root
45 * of RADIX_TREE_MAX_PATH size to be created, with only the root node shared.
95 static inline gfp_t root_gfp_mask(const struct radix_tree_root *root)
97 return root->xa_flags & (__GFP_BITS_MASK & ~GFP_ZONEMASK);
118 static inline void root_tag_set(struct radix_tree_root *root, unsigned tag)
120 root->xa_flags |= (__force gfp_t)(1 << (tag + ROOT_TAG_SHIFT));
123 static inline void root_tag_clear(struct radix_tree_root *root, unsigned tag)
125 root->xa_flags &= (__force gfp_t)~(1 << (tag + ROOT_TAG_SHIFT));
128 static inline void root_tag_clear_all(struct radix_tree_root *root)
130 root->xa_flags &= (__force gfp_t)((1 << ROOT_TAG_SHIFT) - 1);
133 static inline int root_tag_get(const struct radix_tree_root *root, unsigned tag)
135 return (__force int)root->xa_flags & (1 << (tag + ROOT_TAG_SHIFT));
138 static inline unsigned root_tags_get(const struct radix_tree_root *root)
140 return (__force unsigned)root->xa_flags >> ROOT_TAG_SHIFT;
143 static inline bool is_idr(const struct radix_tree_root *root)
145 return !!(root->xa_flags & ROOT_IS_IDR);
234 struct radix_tree_root *root,
285 ret->array = root;
388 static unsigned radix_tree_load_root(const struct radix_tree_root *root,
391 struct radix_tree_node *node = rcu_dereference_raw(root->xa_head);
408 static int radix_tree_extend(struct radix_tree_root *root, gfp_t gfp,
420 entry = rcu_dereference_raw(root->xa_head);
421 if (!entry && (!is_idr(root) || root_tag_get(root, IDR_FREE)))
426 root, shift, 0, 1, 0);
430 if (is_idr(root)) {
432 if (!root_tag_get(root, IDR_FREE)) {
434 root_tag_set(root, IDR_FREE);
439 if (root_tag_get(root, tag))
448 /* Moving a value entry root->xa_head to a node */
457 rcu_assign_pointer(root->xa_head, entry);
466 * @root: radix tree root
468 static inline bool radix_tree_shrink(struct radix_tree_root *root)
473 struct radix_tree_node *node = rcu_dereference_raw(root->xa_head);
491 * For an IDR, we must not shrink entry 0 into the root in
495 if (!node->shift && is_idr(root))
506 * one (root->xa_head) as far as dependent read barriers go.
508 root->xa_head = (void __rcu *)child;
509 if (is_idr(root) && !tag_get(node, IDR_FREE, 0))
510 root_tag_clear(root, IDR_FREE);
526 * problem (replacing direct root node with an indirect pointer
543 static bool delete_node(struct radix_tree_root *root,
553 rcu_dereference_raw(root->xa_head))
554 deleted |= radix_tree_shrink(root);
567 if (!is_idr(root))
568 root_tag_clear_all(root);
569 root->xa_head = NULL;
584 * @root: radix tree root
590 * at position @index in the radix tree @root.
593 * allocated and @root->xa_head is used as a direct slot instead of
598 static int __radix_tree_create(struct radix_tree_root *root,
603 void __rcu **slot = (void __rcu **)&root->xa_head;
607 gfp_t gfp = root_gfp_mask(root);
609 shift = radix_tree_load_root(root, &child, &maxindex);
613 int error = radix_tree_extend(root, gfp, max, shift);
617 child = rcu_dereference_raw(root->xa_head);
624 child = radix_tree_node_alloc(gfp, node, root, shift,
697 * @root: radix tree root
703 int radix_tree_insert(struct radix_tree_root *root, unsigned long index,
712 error = __radix_tree_create(root, index, &node, &slot);
726 BUG_ON(root_tags_get(root));
735 * @root: radix tree root
741 * tree @root.
744 * allocated and @root->xa_head is used as a direct slot instead of
747 void *__radix_tree_lookup(const struct radix_tree_root *root,
757 slot = (void __rcu **)&root->xa_head;
758 radix_tree_load_root(root, &node, &maxindex);
783 * @root: radix tree root
787 * radix tree @root. This is useful for update-if-exists operations.
794 void __rcu **radix_tree_lookup_slot(const struct radix_tree_root *root,
799 if (!__radix_tree_lookup(root, index, NULL, &slot))
807 * @root: radix tree root
810 * Lookup the item at the position @index in the radix tree @root.
817 void *radix_tree_lookup(const struct radix_tree_root *root, unsigned long index)
819 return __radix_tree_lookup(root, index, NULL, NULL);
834 static bool node_tag_get(const struct radix_tree_root *root,
840 return root_tag_get(root, tag);
850 static int calculate_count(struct radix_tree_root *root,
854 if (is_idr(root)) {
856 bool free = node_tag_get(root, node, IDR_FREE, offset);
867 * @root: radix tree root
875 void __radix_tree_replace(struct radix_tree_root *root,
881 int count = calculate_count(root, node, slot, item, old);
886 * node unless the slot is root->xa_head.
888 WARN_ON_ONCE(!node && (slot != (void __rcu **)&root->xa_head) &&
895 delete_node(root, node);
900 * @root: radix tree root
914 void radix_tree_replace_slot(struct radix_tree_root *root,
917 __radix_tree_replace(root, NULL, slot, item);
923 * @root: radix tree root
931 void radix_tree_iter_replace(struct radix_tree_root *root,
935 __radix_tree_replace(root, iter->node, slot, item);
938 static void node_tag_set(struct radix_tree_root *root,
950 if (!root_tag_get(root, tag))
951 root_tag_set(root, tag);
956 * @root: radix tree root
962 * the root all the way down to the leaf node.
967 void *radix_tree_tag_set(struct radix_tree_root *root,
973 radix_tree_load_root(root, &node, &maxindex);
987 /* set the root's tag bit */
988 if (!root_tag_get(root, tag))
989 root_tag_set(root, tag);
995 static void node_tag_clear(struct radix_tree_root *root,
1010 /* clear the root's tag bit */
1011 if (root_tag_get(root, tag))
1012 root_tag_clear(root, tag);
1017 * @root: radix tree root
1029 void *radix_tree_tag_clear(struct radix_tree_root *root,
1036 radix_tree_load_root(root, &node, &maxindex);
1048 node_tag_clear(root, parent, tag, offset);
1056 * @root: radix tree root
1060 void radix_tree_iter_tag_clear(struct radix_tree_root *root,
1063 node_tag_clear(root, iter->node, tag, iter_offset(iter));
1068 * @root: radix tree root
1081 int radix_tree_tag_get(const struct radix_tree_root *root,
1087 if (!root_tag_get(root, tag))
1090 radix_tree_load_root(root, &node, &maxindex);
1149 * @root: radix tree root
1154 void __rcu **radix_tree_next_chunk(const struct radix_tree_root *root,
1161 if ((flags & RADIX_TREE_ITER_TAGGED) && !root_tag_get(root, tag))
1178 radix_tree_load_root(root, &child, &maxindex);
1190 return (void __rcu **)&root->xa_head;
1243 * @root: radix tree root
1262 radix_tree_gang_lookup(const struct radix_tree_root *root, void **results,
1272 radix_tree_for_each_slot(slot, root, &iter, first_index) {
1291 * @root: radix tree root
1302 radix_tree_gang_lookup_tag(const struct radix_tree_root *root, void **results,
1313 radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) {
1332 * @root: radix tree root
1343 radix_tree_gang_lookup_tag_slot(const struct radix_tree_root *root,
1354 radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) {
1364 static bool __radix_tree_delete(struct radix_tree_root *root,
1372 if (is_idr(root))
1373 node_tag_set(root, node, IDR_FREE, offset);
1376 node_tag_clear(root, node, tag, offset);
1379 return node && delete_node(root, node);
1384 * @root: radix tree root
1394 void radix_tree_iter_delete(struct radix_tree_root *root,
1397 if (__radix_tree_delete(root, iter->node, slot))
1404 * @root: radix tree root
1408 * Remove @item at @index from the radix tree rooted at @root.
1413 void *radix_tree_delete_item(struct radix_tree_root *root,
1420 entry = __radix_tree_lookup(root, index, &node, &slot);
1423 if (!entry && (!is_idr(root) || node_tag_get(root, node, IDR_FREE,
1430 __radix_tree_delete(root, node, slot);
1438 * @root: radix tree root
1441 * Remove the entry at @index from the radix tree rooted at @root.
1445 void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
1447 return radix_tree_delete_item(root, index, NULL);
1453 * @root: radix tree root
1456 int radix_tree_tagged(const struct radix_tree_root *root, unsigned int tag)
1458 return root_tag_get(root, tag);
1476 void __rcu **idr_get_free(struct radix_tree_root *root,
1481 void __rcu **slot = (void __rcu **)&root->xa_head;
1486 shift = radix_tree_load_root(root, &child, &maxindex);
1487 if (!radix_tree_tagged(root, IDR_FREE))
1493 int error = radix_tree_extend(root, gfp, start, shift);
1497 child = rcu_dereference_raw(root->xa_head);
1506 child = radix_tree_node_alloc(gfp, node, root, shift,