diff options
Diffstat (limited to 'lib')
-rw-r--r-- | lib/radix-tree.c | 75 |
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 | } |
947 | EXPORT_SYMBOL(radix_tree_range_tag_if_tagged); | 947 | EXPORT_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 | */ | ||
970 | unsigned 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 | } | ||
985 | EXPORT_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 | */ | ||
1007 | unsigned 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 | } | ||
1022 | EXPORT_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 |