1 #ifndef RANGESORT_H 2 #define RANGESORT_H 3 4 /* This implements a simple sorted list of non-overlapping ranges. */ 5 6 #include <debug.h> 7 #include <common.h> 8 #include <gelf.h> 9 10 typedef enum range_error_t { 11 ERROR_CONTAINS, 12 ERROR_OVERLAPS 13 } range_error_t; 14 15 typedef struct range_t range_t; 16 struct range_t { 17 GElf_Off start; 18 GElf_Off length; 19 void *user; 20 void (*err_fn)(range_error_t, range_t *, range_t *); 21 void (*user_dtor)(void *); 22 }; 23 24 typedef struct range_list_t range_list_t; 25 26 range_list_t* init_range_list(); 27 void destroy_range_list(range_list_t *); 28 29 /* Just adds a range to the list. We won't detect whether the range overlaps 30 other ranges or contains them, or is contained by them, till we call 31 sort_ranges(). */ 32 void add_unique_range_nosort(range_list_t *ranges, 33 GElf_Off start, GElf_Off length, 34 void *user, 35 void (*err_fn)(range_error_t, range_t *, range_t *), 36 void (*user_dtor)(void * )); 37 38 /* Sorts the ranges. If there are overlapping ranges or ranges that contain 39 other ranges, it will cause the program to exit with a FAIL. */ 40 range_list_t* sort_ranges(range_list_t *ranges); 41 /* Find which range value falls in. Return that range or NULL if value does 42 not fall within any range. */ 43 range_t *find_range(range_list_t *ranges, GElf_Off value); 44 int get_num_ranges(const range_list_t *ranges); 45 range_t *get_sorted_ranges(const range_list_t *ranges, int *num_ranges); 46 GElf_Off get_last_address(const range_list_t *ranges); 47 48 /* This returns a range_list_t handle that contains ranges composed of the 49 adjacent ranges of the input range list. The user data of each range in 50 the range list is a structure of the type contiguous_range_info_t. 51 This structure contains an array of pointers to copies of the original 52 range_t structures comprising each new contiguous range, as well as the 53 length of that array. 54 55 NOTE: The input range must be sorted! 56 57 NOTE: destroy_range_list() will take care of releasing the data that it 58 allocates as a result of calling get_contiguous_ranges(). Do not free that 59 data yourself. 60 61 NOTE: the user data of the original range_t structures is simply copied, so 62 be careful handling it. You can destroy the range_list_t with 63 destroy_range_list() as usual. On error, the function does not return--the 64 program terminates. 65 66 NOTE: The returned range is not sorted. You must call sort_ranges() if you 67 need to. 68 */ 69 70 typedef struct { 71 int num_ranges; 72 range_t *ranges; 73 } contiguous_range_info_t; 74 75 range_list_t* get_contiguous_ranges(const range_list_t *); 76 77 /* The function below takes in two range lists: r and s, and subtracts the 78 ranges in s from those in r. For example, if r and s are as follows: 79 80 r = { [0, 10) } 81 s = { [3, 5), [7, 9) } 82 83 Then r - s is { [0, 3), [5, 7), [9, 10) } 84 85 NOTE: Both range lists must be sorted on input. This is guarded by an 86 assertion. 87 88 NOTE: Range s must contain ranges, which are fully contained by the span of 89 range r (the span being the interval between the start of the lowest 90 range in r, inclusive, and the end of the highest range in r, 91 exclusive). 92 93 NOTE: In addition to the requirement above, range s must contain ranges, 94 each of which is a subrange of one of the ranges of r. 95 96 NOTE: There is no user info associated with the resulting range. 97 98 NOTE: The resulting range is not sorted. 99 100 Ther returned list must be destroyed with destroy_range_list(). 101 */ 102 103 range_list_t* subtract_ranges(const range_list_t *r, const range_list_t *s); 104 105 #endif/*RANGESORT_H*/ 106