aboutsummaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/radix-tree.c75
1 files changed, 0 insertions, 75 deletions
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index d832117e7d94..7e30d2a7f346 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -946,81 +946,6 @@ next:
946} 946}
947EXPORT_SYMBOL(radix_tree_range_tag_if_tagged); 947EXPORT_SYMBOL(radix_tree_range_tag_if_tagged);
948 948
949
950/**
951 * radix_tree_next_hole - find the next hole (not-present entry)
952 * @root: tree root
953 * @index: index key
954 * @max_scan: maximum range to search
955 *
956 * Search the set [index, min(index+max_scan-1, MAX_INDEX)] for the lowest
957 * indexed hole.
958 *
959 * Returns: the index of the hole if found, otherwise returns an index
960 * outside of the set specified (in which case 'return - index >= max_scan'
961 * will be true). In rare cases of index wrap-around, 0 will be returned.
962 *
963 * radix_tree_next_hole may be called under rcu_read_lock. However, like
964 * radix_tree_gang_lookup, this will not atomically search a snapshot of
965 * the tree at a single point in time. For example, if a hole is created
966 * at index 5, then subsequently a hole is created at index 10,
967 * radix_tree_next_hole covering both indexes may return 10 if called
968 * under rcu_read_lock.
969 */
970unsigned long radix_tree_next_hole(struct radix_tree_root *root,
971 unsigned long index, unsigned long max_scan)
972{
973 unsigned long i;
974
975 for (i = 0; i < max_scan; i++) {
976 if (!radix_tree_lookup(root, index))
977 break;
978 index++;
979 if (index == 0)
980 break;
981 }
982
983 return index;
984}
985EXPORT_SYMBOL(radix_tree_next_hole);
986
987/**
988 * radix_tree_prev_hole - find the prev hole (not-present entry)
989 * @root: tree root
990 * @index: index key
991 * @max_scan: maximum range to search
992 *
993 * Search backwards in the range [max(index-max_scan+1, 0), index]
994 * for the first hole.
995 *
996 * Returns: the index of the hole if found, otherwise returns an index
997 * outside of the set specified (in which case 'index - return >= max_scan'
998 * will be true). In rare cases of wrap-around, ULONG_MAX will be returned.
999 *
1000 * radix_tree_next_hole may be called under rcu_read_lock. However, like
1001 * radix_tree_gang_lookup, this will not atomically search a snapshot of
1002 * the tree at a single point in time. For example, if a hole is created
1003 * at index 10, then subsequently a hole is created at index 5,
1004 * radix_tree_prev_hole covering both indexes may return 5 if called under
1005 * rcu_read_lock.
1006 */
1007unsigned long radix_tree_prev_hole(struct radix_tree_root *root,
1008 unsigned long index, unsigned long max_scan)
1009{
1010 unsigned long i;
1011
1012 for (i = 0; i < max_scan; i++) {
1013 if (!radix_tree_lookup(root, index))
1014 break;
1015 index--;
1016 if (index == ULONG_MAX)
1017 break;
1018 }
1019
1020 return index;
1021}
1022EXPORT_SYMBOL(radix_tree_prev_hole);
1023
1024/** 949/**
1025 * radix_tree_gang_lookup - perform multiple lookup on a radix tree 950 * radix_tree_gang_lookup - perform multiple lookup on a radix tree
1026 * @root: radix tree root 951 * @root: radix tree root