regfi
Data Structures | Functions
range_list.h File Reference

A data structure which stores a list of address ranges. More...

Include dependency graph for range_list.h:

Go to the source code of this file.

Data Structures

struct  range_list_element
 
struct  range_list
 XXX: document this. More...
 

Functions

range_listrange_list_new ()
 Allocates a new range_list. More...
 
void range_list_free (range_list *rl)
 Frees the memory associated with a range_list, including the elements, but not any data parameters referenced by those elements. More...
 
uint32_t range_list_size (const range_list *rl)
 Query the current number of elements on a range_list. More...
 
bool range_list_add (range_list *rl, uint32_t offset, uint32_t length, void *data)
 Adds an element to the range_list. More...
 
bool range_list_remove (range_list *rl, uint32_t index)
 Removes an element from the list. More...
 
const range_list_elementrange_list_get (const range_list *rl, uint32_t index)
 Retrieves the element for a given index. More...
 
int32_t range_list_find (const range_list *rl, uint32_t offset)
 Attempts to find the unique element whose range encompasses offset. More...
 
void * range_list_find_data (const range_list *rl, uint32_t offset)
 Same as range_list_find(), but returns the data associated with an element. More...
 
bool range_list_split_element (range_list *rl, uint32_t index, uint32_t offset)
 Splits an existing element into two elements in place. More...
 
bool range_list_has_range (range_list *rl, uint32_t start, uint32_t length)
 Determines whether or not a specified range exists contiguously within the range_list. More...
 

Detailed Description

A data structure which stores a list of address ranges.

range_lists support basic in-place modifications and maintain the address space in sorted order. Looking up a range_list_element is implemented through binary search.

Function Documentation

◆ range_list_new()

range_list* range_list_new ( )

Allocates a new range_list.

Returns
A newly allocated range_list, or NULL if an error occurred.

Referenced by regfi_parse_unalloc_cells().

◆ range_list_free()

void range_list_free ( range_list rl)

Frees the memory associated with a range_list, including the elements, but not any data parameters referenced by those elements.


If rl is NULL, does nothing.

Parameters
rlthe range_list to be free()d.

◆ range_list_size()

uint32_t range_list_size ( const range_list rl)

Query the current number of elements on a range_list.

Parameters
rlthe range_list to query
Returns
The number of elements currently in the list.

◆ range_list_add()

bool range_list_add ( range_list rl,
uint32_t  offset,
uint32_t  length,
void *  data 
)

Adds an element to the range_list.


The new element must not overlap with others. NOTE: this is a slow operation.

Parameters
rlthe range list to update
offsetthe starting point for the range
lengththe length of the range
datamisc data associated with this range element
Returns
true on success, false on failure.

Failures can occur due to memory limitations, max_size limitations, or if the submitted range overlaps with an existing element. Other errors may also be possible.

◆ range_list_remove()

bool range_list_remove ( range_list rl,
uint32_t  index 
)

Removes an element from the list.


The element data structure will be freed, but the data property will not be.

Parameters
rlthe range_list to modify
indexthe element index to remove
Returns
true if the element was successfully removed, false otherwise.

◆ range_list_get()

const range_list_element* range_list_get ( const range_list rl,
uint32_t  index 
)

Retrieves the element for a given index.

Parameters
rlthe range_list being queried.
indexthe element index desired.
Returns
The element for a given index, or NULL if the element is not available.

◆ range_list_find()

int32_t range_list_find ( const range_list rl,
uint32_t  offset 
)

Attempts to find the unique element whose range encompasses offset.

Parameters
rlthe range_list being queried.
offsetthe location for which an element is desired.
Returns
A matching element index or a negative value if none could be found.

Referenced by range_list_find_data(), and range_list_has_range().

◆ range_list_find_data()

void* range_list_find_data ( const range_list rl,
uint32_t  offset 
)

Same as range_list_find(), but returns the data associated with an element.

Parameters
rlthe range_list being queried.
offsetthe address to search for in the ranges
Returns
The data element of the matching element index or NULL if none could be found.

NOTE: May also return NULL if an element matched but the data element was never set.

References range_list_find().

Referenced by regfi_lookup_hbin().

◆ range_list_split_element()

bool range_list_split_element ( range_list rl,
uint32_t  index,
uint32_t  offset 
)

Splits an existing element into two elements in place.

The resulting list will contain an additional element whose offset is the one provided and whose length extends to the end of the old element (the one identified by the index). The original element's offset will remain the same while it's length is shortened such that it is contiguous with the newly created element. The newly created element will have an index of one more than the current element.

Both the original element and the newly created element will reference the original element's data.

Parameters
rlthe range_list to modify
indexthe index of the element to be split
offsetthe at which the element will be split
Returns
true if the element was successfully split, false otherwise.

◆ range_list_has_range()

bool range_list_has_range ( range_list rl,
uint32_t  start,
uint32_t  length 
)

Determines whether or not a specified range exists contiguously within the range_list.

Parameters
rlthe range_list to search
startthe offset at the beginning of the range
lengththe length of the range
Returns
true if the specified range exists and is complete, false otherwise.

References range_list_find().