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_list *	range_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_element *	range_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

rl	the 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

rl	the 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

rl	the range list to update
offset	the starting point for the range
length	the length of the range
data	misc 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

rl	the range_list to modify
index	the 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

rl	the range_list being queried.
index	the 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

rl	the range_list being queried.
offset	the 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

rl	the range_list being queried.
offset	the 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

rl	the range_list to modify
index	the index of the element to be split
offset	the 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

rl	the range_list to search
start	the offset at the beginning of the range
length	the length of the range

Returns

true if the specified range exists and is complete, false otherwise.

References range_list_find().