Skip to content
This repository

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Fetching contributors…

Cannot retrieve contributors at this time

file 105 lines (79 sloc) 3.706 kb
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105
#ifndef RANGESORT_H
#define RANGESORT_H

/* This implements a simple sorted list of non-overlapping ranges. */

#include <debug.h>
#include <common.h>
#include <gelf.h>

typedef enum range_error_t {
    ERROR_CONTAINS,
    ERROR_OVERLAPS
} range_error_t;

typedef struct range_t range_t;
struct range_t {
    GElf_Off start;
    GElf_Off length;
    void *user;
    void (*err_fn)(range_error_t, range_t *, range_t *);
    void (*user_dtor)(void *);
};

typedef struct range_list_t range_list_t;

range_list_t* init_range_list();
void destroy_range_list(range_list_t *);

/* Just adds a range to the list. We won't detect whether the range overlaps
other ranges or contains them, or is contained by them, till we call
sort_ranges(). */
void add_unique_range_nosort(range_list_t *ranges,
                             GElf_Off start, GElf_Off length,
                             void *user,
                             void (*err_fn)(range_error_t, range_t *, range_t *),
                             void (*user_dtor)(void * ));

/* Sorts the ranges. If there are overlapping ranges or ranges that contain
other ranges, it will cause the program to exit with a FAIL. */
range_list_t* sort_ranges(range_list_t *ranges);
/* Find which range value falls in. Return that range or NULL if value does
not fall within any range. */
range_t *find_range(range_list_t *ranges, GElf_Off value);
int get_num_ranges(const range_list_t *ranges);
range_t *get_sorted_ranges(const range_list_t *ranges, int *num_ranges);
GElf_Off get_last_address(const range_list_t *ranges);

/* This returns a range_list_t handle that contains ranges composed of the
adjacent ranges of the input range list. The user data of each range in
the range list is a structure of the type contiguous_range_info_t.
This structure contains an array of pointers to copies of the original
range_t structures comprising each new contiguous range, as well as the
length of that array.

NOTE: The input range must be sorted!

NOTE: destroy_range_list() will take care of releasing the data that it
allocates as a result of calling get_contiguous_ranges(). Do not free that
data yourself.

NOTE: the user data of the original range_t structures is simply copied, so
be careful handling it. You can destroy the range_list_t with
destroy_range_list() as usual. On error, the function does not return--the
program terminates.

NOTE: The returned range is not sorted. You must call sort_ranges() if you
need to.
*/

typedef struct {
    int num_ranges;
    range_t *ranges;
} contiguous_range_info_t;

range_list_t* get_contiguous_ranges(const range_list_t *);

/* The function below takes in two range lists: r and s, and subtracts the
ranges in s from those in r. For example, if r and s are as follows:

r = { [0, 10) }
s = { [3, 5), [7, 9) }

Then r - s is { [0, 3), [5, 7), [9, 10) }

NOTE: Both range lists must be sorted on input. This is guarded by an
assertion.

NOTE: Range s must contain ranges, which are fully contained by the span of
range r (the span being the interval between the start of the lowest
range in r, inclusive, and the end of the highest range in r,
exclusive).

NOTE: In addition to the requirement above, range s must contain ranges,
each of which is a subrange of one of the ranges of r.

NOTE: There is no user info associated with the resulting range.

NOTE: The resulting range is not sorted.

Ther returned list must be destroyed with destroy_range_list().
*/

range_list_t* subtract_ranges(const range_list_t *r, const range_list_t *s);

#endif/*RANGESORT_H*/
Something went wrong with that request. Please try again.