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
928 void radix_tree_iter_replace(struct radix_tree_root *root, in radix_tree_iter_replace() argument
932 __radix_tree_replace(root, iter->node, slot, item); in radix_tree_iter_replace()
935 static void node_tag_set(struct radix_tree_root *root, in node_tag_set() argument
947 if (!root_tag_get(root, tag)) in node_tag_set()
948 root_tag_set(root, tag); in node_tag_set()
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, in radix_tree_tag_set() argument
970 radix_tree_load_root(root, &node, &maxindex); in radix_tree_tag_set()
984 /* set the root's tag bit */ in radix_tree_tag_set()
985 if (!root_tag_get(root, tag)) in radix_tree_tag_set()
986 root_tag_set(root, tag); in radix_tree_tag_set()
992 static void node_tag_clear(struct radix_tree_root *root, in node_tag_clear() argument
1007 /* clear the root's tag bit */ in node_tag_clear()
1008 if (root_tag_get(root, tag)) in node_tag_clear()
1009 root_tag_clear(root, tag); in node_tag_clear()
1014 * @root: radix tree root
1026 void *radix_tree_tag_clear(struct radix_tree_root *root, in radix_tree_tag_clear() argument
1033 radix_tree_load_root(root, &node, &maxindex); in radix_tree_tag_clear()
1045 node_tag_clear(root, parent, tag, offset); in radix_tree_tag_clear()
1053 * @root: radix tree root
1057 void radix_tree_iter_tag_clear(struct radix_tree_root *root, in radix_tree_iter_tag_clear() argument
1060 node_tag_clear(root, iter->node, tag, iter_offset(iter)); in radix_tree_iter_tag_clear()
1065 * @root: radix tree root
1078 int radix_tree_tag_get(const struct radix_tree_root *root, in radix_tree_tag_get() argument
1084 if (!root_tag_get(root, tag)) in radix_tree_tag_get()
1087 radix_tree_load_root(root, &node, &maxindex); in radix_tree_tag_get()
1147 * @root: radix tree root
1152 void __rcu **radix_tree_next_chunk(const struct radix_tree_root *root, in radix_tree_next_chunk() argument
1159 if ((flags & RADIX_TREE_ITER_TAGGED) && !root_tag_get(root, tag)) in radix_tree_next_chunk()
1176 radix_tree_load_root(root, &child, &maxindex); in radix_tree_next_chunk()
1188 return (void __rcu **)&root->xa_head; in radix_tree_next_chunk()
1241 * @root: radix tree root
1260 radix_tree_gang_lookup(const struct radix_tree_root *root, void **results, in radix_tree_gang_lookup() argument
1270 radix_tree_for_each_slot(slot, root, &iter, first_index) { in radix_tree_gang_lookup()
1289 * @root: radix tree root
1300 radix_tree_gang_lookup_tag(const struct radix_tree_root *root, void **results, in radix_tree_gang_lookup_tag() argument
1311 radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) { in radix_tree_gang_lookup_tag()
1330 * @root: radix tree root
1341 radix_tree_gang_lookup_tag_slot(const struct radix_tree_root *root, in radix_tree_gang_lookup_tag_slot() argument
1352 radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) { in radix_tree_gang_lookup_tag_slot()
1362 static bool __radix_tree_delete(struct radix_tree_root *root, in __radix_tree_delete() argument
1370 if (is_idr(root)) in __radix_tree_delete()
1371 node_tag_set(root, node, IDR_FREE, offset); in __radix_tree_delete()
1374 node_tag_clear(root, node, tag, offset); in __radix_tree_delete()
1377 return node && delete_node(root, node); in __radix_tree_delete()
1382 * @root: radix tree root
1392 void radix_tree_iter_delete(struct radix_tree_root *root, in radix_tree_iter_delete() argument
1395 if (__radix_tree_delete(root, iter->node, slot)) in radix_tree_iter_delete()
1402 * @root: radix tree root
1406 * Remove @item at @index from the radix tree rooted at @root.
1411 void *radix_tree_delete_item(struct radix_tree_root *root, in radix_tree_delete_item() argument
1418 entry = __radix_tree_lookup(root, index, &node, &slot); in radix_tree_delete_item()
1421 if (!entry && (!is_idr(root) || node_tag_get(root, node, IDR_FREE, in radix_tree_delete_item()
1428 __radix_tree_delete(root, node, slot); in radix_tree_delete_item()
1436 * @root: radix tree root
1439 * Remove the entry at @index from the radix tree rooted at @root.
1443 void *radix_tree_delete(struct radix_tree_root *root, unsigned long index) in radix_tree_delete() argument
1445 return radix_tree_delete_item(root, index, NULL); in radix_tree_delete()
1451 * @root: radix tree root
1454 int radix_tree_tagged(const struct radix_tree_root *root, unsigned int tag) in radix_tree_tagged() argument
1456 return root_tag_get(root, tag); in radix_tree_tagged()
1474 void __rcu **idr_get_free(struct radix_tree_root *root, in idr_get_free() argument
1479 void __rcu **slot = (void __rcu **)&root->xa_head; in idr_get_free()
1484 shift = radix_tree_load_root(root, &child, &maxindex); in idr_get_free()
1485 if (!radix_tree_tagged(root, IDR_FREE)) in idr_get_free()
1491 int error = radix_tree_extend(root, gfp, start, shift); in idr_get_free()
1495 child = rcu_dereference_raw(root->xa_head); in idr_get_free()
1504 child = radix_tree_node_alloc(gfp, node, root, shift, in idr_get_free()