Lines Matching full:tree
24 #include <linux/radix-tree.h>
30 #include "radix-tree.h"
33 * Radix tree node cache.
38 * The radix tree is variable-height, so an insert operation not only has
43 * The worst case is a zero height tree with just a single item at index 0,
51 * The IDR does not have to be as high as the radix tree since it uses
209 * The maximum index which can be stored in a radix tree
315 * ensure that the addition of a single element in the tree cannot fail. On
319 * To make use of this facility, the radix tree must be initialised without
358 * ensure that the addition of a single element in the tree cannot fail. On
362 * To make use of this facility, the radix tree must be initialised without
406 * Extend a radix tree so it can store key @index.
452 * entry was already in the radix tree, so we do not need in radix_tree_extend()
465 * radix_tree_shrink - shrink radix tree to minimum height
466 * @root: radix tree root
503 * moving the node from one part of the tree to another: if it in radix_tree_shrink()
583 * __radix_tree_create - create a slot in a radix tree
584 * @root: radix tree root
590 * at position @index in the radix tree @root.
592 * Until there is more than one item in the tree, no nodes are
611 /* Make sure the tree is high enough. */ in __radix_tree_create()
648 * Free any nodes below this node. The tree is presumed to not need
649 * shrinking, and any user data in the tree is presumed to not need a
652 * slots from the tree as an RCU walker may still have a pointer into
696 * radix_tree_insert - insert into a radix tree
697 * @root: radix tree root
701 * Insert an item into the radix tree at position @index.
734 * __radix_tree_lookup - lookup an item in a radix tree
735 * @root: radix tree root
741 * tree @root.
743 * Until there is more than one item in the tree, no nodes are
782 * radix_tree_lookup_slot - lookup a slot in a radix tree
783 * @root: radix tree root
787 * radix tree @root. This is useful for update-if-exists operations.
806 * radix_tree_lookup - perform lookup operation on a radix tree
807 * @root: radix tree root
810 * Lookup the item at the position @index in the radix tree @root.
844 * IDR users want to be able to store NULL in the tree, so if the slot isn't
867 * @root: radix tree root
868 * @node: pointer to tree node
872 * For use with __radix_tree_lookup(). Caller must hold tree write locked
900 * @root: radix tree root
905 * radix_tree_gang_lookup_tag_slot(). Caller must hold tree write locked
910 * inside the radix tree node. When switching from one type of entry or
923 * @root: radix tree root
929 * Caller must hold tree write locked.
955 * radix_tree_tag_set - set a tag on a radix tree node
956 * @root: radix tree root
961 * corresponding to @index in the radix tree. From
1016 * radix_tree_tag_clear - clear a tag on a radix tree node
1017 * @root: radix tree root
1022 * corresponding to @index in the radix tree. If this causes
1056 * @root: radix tree root
1067 * radix_tree_tag_get - get a tag on a radix tree node
1068 * @root: radix tree root
1149 * @root: radix tree root
1185 /* Single-slot tree */ in radix_tree_next_chunk()
1242 * radix_tree_gang_lookup - perform multiple lookup on a radix tree
1243 * @root: radix tree root
1248 * Performs an index-ascending scan of the tree for present items. Places
1256 * an atomic snapshot of the tree at a single point in time, the
1289 * radix_tree_gang_lookup_tag - perform multiple lookup on a radix tree
1291 * @root: radix tree root
1297 * Performs an index-ascending scan of the tree for present items which
1331 * radix tree based on a tag
1332 * @root: radix tree root
1338 * Performs an index-ascending scan of the tree for present items which
1384 * @root: radix tree root
1392 * which can access this tree.
1403 * radix_tree_delete_item - delete an item from a radix tree
1404 * @root: radix tree root
1408 * Remove @item at @index from the radix tree rooted at @root.
1437 * radix_tree_delete - delete an entry from a radix tree
1438 * @root: radix tree root
1441 * Remove the entry at @index from the radix tree rooted at @root.
1452 * radix_tree_tagged - test whether any items in the tree are tagged
1453 * @root: radix tree root
1555 * A typical clean-up sequence for objects stored in an idr tree will use