list

Double linked list embedded in a static array. More...

Data Structures
struct	util_list
	Structure for list, see also list. More...

Macros
#define	UTIL_LIST_NIL   -1
	Identifier for an invalid index.
#define	util_list_foreach(i, list)   for (i = util_list_first(list); i != -1; i = util_list_next(list, i))
	Foreach loop for iterating over a list.

Functions
int	util_list_size (int num_elements)
	Computes the size in bytes for num_elements list entries. More...
void	util_list_init (struct util_list *l, void *data, int size)
	Initializes a linked list which is embedded in a preallocated array. More...
void *	util_list_clear (struct util_list *l)
	Clear a list l. More...
int	util_list_insert (struct util_list *l, const void *x)
	Inserts the given element x into the list l. More...
int	util_list_insert_end (struct util_list *l, const void *x)
	Inserts the given element x into the list l. More...
void *	util_list_get (struct util_list *l, int index)
	Returns the element at the given index. More...
const void *	util_list_get_const (struct util_list *l, int index)
	Like util_list_get but returns pointer with const qualifier.
void *	util_list_remove (struct util_list *l, int index, int *new_index)
	Removes the element at the given index from the list l. More...
void *	util_list_pop_front (struct util_list *l)
	Remove the first element in list. More...
void *	util_list_pop_end (struct util_list *l)
	Remove the last element in list. More...
int	util_list_first (struct util_list *l)
	Returns the index of the first element in list. More...
int	util_list_last (struct util_list *l)
	Returns the index of the last element in list. More...
int	util_list_next (struct util_list *l, int index)
	Returns the index of the next element in list. More...
int	util_list_length (struct util_list *l)
	Returns the length of the given list. More...

Detailed Description

Double linked list embedded in a static array.

This way this list is very fast and doesn't need dynamic memory allocation. Unused array members are stored in a single linked list as these are always accessed at the front. It also supports index based access for known indeces, returned by insert (Note: index n is NOT the n-th element, it is just a handle for accessing the element).

Function Documentation

void* util_list_clear

(

struct util_list *

l

)

Clear a list l.

No furhter operations may be performed on this list after clearing.

Returns

The data pointer that was given in util_list_init(), as it might need to be freed.

int util_list_first

(

struct util_list *

l

)

Returns the index of the first element in list.

This function returns -1 with the list is empty.

void* util_list_get	(	struct util_list *	l,
		int	index
	)

Returns the element at the given index.

This operation works in O(1).

Returns

The value added using list_insert, or NULL to indicate an error. So you should not store NULL pointers in this list, because you cannot distinguish these from errors.

void util_list_init	(	struct util_list *	l,
		void *	data,
		int	size
	)

Initializes a linked list which is embedded in a preallocated array.

Parameters

l	The list context.
data	Pointer to preallocated memory to use for the list.
size	Size of data in bytes. See util_list_size.

int util_list_insert	(	struct util_list *	l,
		const void *	x
	)

Inserts the given element x into the list l.

This operation works in O(1).

Returns

index of element in array on succes, or -1 if the operation fails.

int util_list_insert_end	(	struct util_list *	l,
		const void *	x
	)

Inserts the given element x into the list l.

This operation works in O(1).

Returns

index of element in array on succes, or -1 if the operation fails.

int util_list_last

(

struct util_list *

l

)

Returns the index of the last element in list.

This function returns -1 when the list is empty.

int util_list_length

(

struct util_list *

l

)

Returns the length of the given list.

int util_list_next	(	struct util_list *	l,
		int	index
	)

Returns the index of the next element in list.

Parameters

l	list
index	current element index. This index must be a valid index.

Returns

index of next element if one exists, -1 otherwise.

void* util_list_pop_end

(

struct util_list *

l

)

Remove the last element in list.

Returns

value of removed element, or NULL to indicate an error. So you should not store NULL pointers in this list, because you cannot distinguish these from errors.

void* util_list_pop_front

(

struct util_list *

l

)

Remove the first element in list.

Returns

value of removed element, or NULL to indicate an error. So you should not store NULL pointers in this list, because you cannot distinguish these from errors.

void* util_list_remove	(	struct util_list *	l,
		int	index,
		int *	new_index
	)

Removes the element at the given index from the list l.

This operation works in O(1).

Parameters

l	List context.
index	Index of the element to remove.
new_index	Pointer to index, if remove is used in foreach loop.

Returns

value of removed element, or NULL to indicate an error. So you should not store NULL pointers in this list, because you cannot distinguish these from errors.

int util_list_size

(

int

num_elements

)

Computes the size in bytes for num_elements list entries.

This can be used by the called to allocate the correct amount of memory for util_list_init.