Robust, reentrant linked list structure. More...

#include <limits.h>
#include <stdbool.h>

Functions
struct list *	list_create (void)
	Create an empty linked list. More...

bool	list_destroy (struct list *list)
	Delete an empty list. More...

unsigned	list_length (struct list *list)
	Get the number of items in a list. More...

struct list_cursor *	list_cursor_create (struct list *list)
	Create a new cursor on a list. More...

void	list_cursor_destroy (struct list_cursor *cur)
	Delete a previously created cursor. More...

struct list_cursor *	list_cursor_clone (struct list_cursor *cur)
	Get a copy of an existing cursor. More...

void	list_reset (struct list_cursor *cur)
	Reset the position of a cursor. More...

bool	list_seek (struct list_cursor *cur, int index)
	Move a cursor to an item by index. More...

bool	list_tell (struct list_cursor cur, unsigned index)
	Get the position of a cursor within a list. More...

bool	list_next (struct list_cursor *cur)
	Move a cursor to the next item. More...

bool	list_prev (struct list_cursor *cur)
	Move a cursor to the previous item. More...

bool	list_get (struct list_cursor cur, void *item)
	Get the item under a cursor. More...

bool	list_set (struct list_cursor cur, void item)
	Set the value under the cursor. More...

bool	list_drop (struct list_cursor *cur)
	Remove the item under the cursor. More...

void	list_insert (struct list_cursor cur, void item)
	Insert an item to the left of the cursor. More...

int	list_size (struct list *list)
	Count the elements in a list. More...

struct list *	list_duplicate (struct list *list)
	Duplicate a linked list Returns a copy of the linked list. More...

void	list_delete (struct list *list)
	Delete a linked list. More...

void	list_free (struct list *list)
	Free every item referred to by the list. More...

struct list *	list_splice (struct list top, struct list bottom)
	Splice two lists together. More...

struct list *	list_split (struct list src, list_op_t cmp, const void arg)
	Split a list into two at the given item If arg is NULL or not found, list_split returns NULL and the list is unaffected. More...

int	list_push_head (struct list list, void item)
	Push an item onto the list head. More...

void *	list_pop_head (struct list *list)
	Pop an item off of the list head. More...

void *	list_peek_head (struct list *list)
	Peek at the list head. More...

int	list_push_tail (struct list list, void item)
	Push an item onto the list tail. More...

void *	list_pop_tail (struct list *list)
	Pop an item off of the list tail. More...

void *	list_peek_tail (struct list *list)
	Peek at the list tail. More...

void *	list_peek_current (struct list *list)
	Peek at the current element in the iteration. More...

void	list_push_priority (struct list list, list_priority_t p, void item)
	Push an item onto of a list in priority order. More...

void *	list_find (struct list list, list_op_t cmp, const void arg)
	Find an element within a list This function searches the list, comparing each element in the list to arg, and returns a pointer to the first matching element. More...

void *	list_remove (struct list list, const void value)
	Remove an item from the list This function searches the list for the item pointed to by value and removes it. More...

void	list_first_item (struct list *list)
	Begin traversing a list. More...

void *	list_next_item (struct list *list)
	Continue traversing a list. More...

int	list_iterate (struct list list, list_op_t op, const void arg)
	Apply a function to a list. More...

int	list_iterate_reverse (struct list list, list_op_t op, const void arg)
	Apply a function to a list in reverse. More...

struct list *	list_sort (struct list list, int(comparator)(const void , const void ))
	Sort a list using a comparator function. More...

Detailed Description

Robust, reentrant linked list structure.

Aside from list create and delete operations, most functionality is based on cursors on a list. A cursor is a logical position within a list. Due to insertions and deletions, a simple numeric index is not sufficient to define a constant position. Cursors are unaffected by changes in other parts of the list. Lookups, insertions, deletions, etc. all happen at the current location of a cursor. Cursors also support iteration, by moving forward and backward in the list.

After creation, a cursor's position is undefined. It could be thought of as sitting at index ∞. Insertions in this state always place the item at the tail of the list, and the cursor's position is unaffected. Calls that examine the value under a cursor fail if the position is undefined.

To interact with the contents of a list, a cursor must be placed on a list item by moving forward/backward or by seeking to a specific index. Negative indices are interpreted relative to the tail of the list, so index 0 is the head, and index -1 is the tail.

After an item is dropped, it will not be reachable by seeking or moving. If a cursor is on an item that is deleted, it will no longer be able to interact with that item. The cursor can only move off the item. Once all cursors have moved off the item, it is finally free()d.

Function Documentation

struct list* list_create ( void )

Create an empty linked list.

Returns: A pointer to the newly created list.

bool list_destroy ( struct list * list )

Delete an empty list.

The caller is responsible for removing all the items in the list before deleting. If the list is non-empty or there are any living cursors on the list, this call fails and the list is not modified.

Parameters

list	The list to delete.

Returns: true if the list was deleted.; false if the list is non-empty or there are live cursors.

unsigned list_length ( struct list * list )

Get the number of items in a list.

Parameters

list	The list to look at.

Returns: The number of items in the list.

struct list_cursor* list_cursor_create ( struct list * list )

Create a new cursor on a list.

The cursor's position is initially undefined. The cursor must be deleted with list_cursor_destroy.

Parameters

list	The list to use.

Returns: A pointer to a new cursor.

void list_cursor_destroy ( struct list_cursor * cur )

Delete a previously created cursor.

All cursors must be deleted to avoid leaking memory and references. This does not modify the underlying list.

Parameters

cur	The cursor to free.

struct list_cursor* list_cursor_clone ( struct list_cursor * cur )

Get a copy of an existing cursor.

The returned cursor is independent from the original, but initially sits at the same position.

Parameters

cur	The cursor to clone.

Returns: A new cursor, which must also be deleted.

void list_reset ( struct list_cursor * cur )

Reset the position of a cursor.

After calling, the cursor's position will be undefined, just like a newly-created cursor. This function always succeeds.

Parameters

cur	The cursor to reset.

bool list_seek	(	struct list_cursor *	cur,
		int	index
	)

Move a cursor to an item by index.

The index specifies the item the cursor will move to. The first item (i.e. the head of the list) is at index zero. Negative indices are taken from the back of the list, so index -1 is the list tail.

Parameters

cur	The cursor to move.
index	The position of the cursor.

Returns: true if the cursor moved.; false if the index is out of bounds, leaving the cursor unchanged.

bool list_tell	(	struct list_cursor *	cur,
		unsigned *	index
	)

Get the position of a cursor within a list.

Due to insertions and deletions, an item's index within a list is subject to change. This function walks from the beginning of the list to determine the cursor's current index. If the cursor's position is undefined, or sitting on a dropped item, this function returns false and does not modify the passed in index.

Parameters

cur	The cursor to check.
index	The location to store the index.

Returns: true if the cursor's index was written.; false if the cursor position is undefined or the item was dropped.

bool list_next ( struct list_cursor * cur )

Move a cursor to the next item.

Parameters

cur	The cursor to move.

Returns: true if the cursor moved to the next item.; false if the cursor moved off the end of the list, making the cursor's position undefined.

bool list_prev ( struct list_cursor * cur )

Move a cursor to the previous item.

Parameters

cur	The cursor to move.

Returns: true if the cursor moved to the previous item.; false if the cursor moved off the end of the list, making the cursor's position undefined.

bool list_get	(	struct list_cursor *	cur,
		void **	item
	)

Get the item under a cursor.

If cursor position is undefined, the passed pointer will not be modified. Note that there are no restrictions on the stored pointer, so it is perfectly possible to receive a null pointer from a list.

Parameters

cur	The cursor to look at.
item	The location at which to store the value under the cursor.

Returns: true if the value of the list item was stored.; false if the cursor position is undefined.

bool list_set	(	struct list_cursor *	cur,
		void *	item
	)

Set the value under the cursor.

If the cursor position is undefined, this function simply returns false. Any pointer value (including NULL) is allowed.

Parameters

cur	The cursor position to set.
item	The value to set to.

Returns: true on success.; false if the cursor position is undefined.

bool list_drop ( struct list_cursor * cur )

Remove the item under the cursor.

This function is safe to use while iterating over a list, and in the presence of other cursors. Any cursors on the same item will be advanced to the next item.

Parameters

cur	The cursor to use.

Returns: true if an item was successfully removed.; false if the cursor position is undefined.

void list_insert	(	struct list_cursor *	cur,
		void *	item
	)

Insert an item to the left of the cursor.

If the cursor position is undefined, insert at the list tail. There are no restrictions on the pointer value, so inserting a null pointer is perfectly valid. The cursor position is unchanged.

Parameters

cur	The cursor to use.
item	The pointer to insert.

int list_size ( struct list * list )

Count the elements in a list.

Parameters

list	The list to count.

Returns: The number of items stored in the list.

struct list* list_duplicate ( struct list * list )

Duplicate a linked list

Returns a copy of the linked list.

Note that the pointers in both lists point to the same places.

Parameters

list	The list to be duplicated

Returns: A pointer to the duplicate list

void list_delete ( struct list * list )

Delete a linked list.

Note that this function only deletes the list itself, it does not delete the items referred to by the list.

Parameters

list	The list to delete.

void list_free ( struct list * list )

Free every item referred to by the list.

Note that this function does not delete the list itself.

Parameters

list	The list to free.

struct list* list_splice	(	struct list *	top,
		struct list *	bottom
	)

Splice two lists together.

Parameters

top	A linked list that will be destroyed in the process.
bottom	A linked list that will be destroyed in the process.

Returns: A new linked list with elements from top at the head and bottom at the tail.

struct list* list_split	(	struct list *	src,
		list_op_t	cmp,
		const void *	arg
	)

Split a list into two at the given item

If arg is NULL or not found, list_split returns NULL and the list is unaffected.

Otherwise src will contain all elements [src->head, arg) and a new list will be created with all elements [arg, src->tail].

Parameters

src	The linked list to be split
cmp	The comparison function. Should return non-zero on a match.
arg	The data element to split on.

Returns: A new linked list with arg as the head and all elements after arg as elements of the new list.

int list_push_head	(	struct list *	list,
		void *	item
	)

Push an item onto the list head.

Parameters

list	The list to push onto.
item	The item to push onto the list.

Returns: True on success, false on failure (due to out of memory.)

void* list_pop_head ( struct list * list )

Pop an item off of the list head.

Parameters

list	The list to pop.

Returns: The item popped, or null if list is empty.

void* list_peek_head ( struct list * list )

Peek at the list head.

Parameters

list	The list to peek.

Returns: The item at the list head, or null if list is empty.

int list_push_tail	(	struct list *	list,
		void *	item
	)

Push an item onto the list tail.

Parameters

list	The list to push onto.
item	The item to push onto the list.

Returns: True on success, false on failure (due to out of memory.)

void* list_pop_tail ( struct list * list )

Pop an item off of the list tail.

Parameters

list	The list to pop.

Returns: The item popped, or null if list is empty.

void* list_peek_tail ( struct list * list )

Peek at the list tail.

Parameters

list	The list to peek.

Returns: The item at the list tail, or null if list is empty.

void* list_peek_current ( struct list * list )

Peek at the current element in the iteration.

Parameters

list	The list to peek.

Returns: The item at the list head, or null if list is empty.

void list_push_priority	(	struct list *	list,
		list_priority_t	p,
		void *	item
	)

Push an item onto of a list in priority order.

The passed-in function is used to determine the priority of each item. The new item is inserted at the leftmost position such that p(n) >= p(item) > p(n + 1) in the general position. If a list is built using list_push_priority() with the same priority function, it will always be sorted. Note that each insertion takes O(n) time, where n is the number of list items. See list_sort() for a more efficient way to sort an entire list.

Parameters

list	The list to modify.
p	The priority function to apply to list items.
item	The new item to insert in priority order.

void* list_find	(	struct list *	list,
		list_op_t	cmp,
		const void *	arg
	)

Find an element within a list

This function searches the list, comparing each element in the list to arg, and returns a pointer to the first matching element.

Parameters

list	The list to search
cmp	The comparison function. Should return non-zero on a match.
arg	The element to compare against

Returns: A pointer to the first matched element, or NULL if no elements match.

void* list_remove	(	struct list *	list,
		const void *	value
	)

Remove an item from the list

This function searches the list for the item pointed to by value and removes it.

Parameters

list	The list to search
value	The item to remove

Returns: The removed item.

void list_first_item ( struct list * list )

Begin traversing a list.

This function sets the internal list iterator to the first item. Call list_next_item to begin returning the items.

Parameters

list	The list to traverse.

void* list_next_item ( struct list * list )

Continue traversing a list.

This function returns the current list item, and advances the internal iterator to the next item.

Parameters

list	The list to traverse.

Returns: The current item in the list.

int list_iterate	(	struct list *	list,
		list_op_t	op,
		const void *	arg
	)

Apply a function to a list.

Invokes op on every member of the list.

Parameters

list	The list to operate on.
op	The operator to apply.
arg	An optional parameter to send to op.

int list_iterate_reverse	(	struct list *	list,
		list_op_t	op,
		const void *	arg
	)

Apply a function to a list in reverse.

Invokes op on every member of the list in reverse.

Parameters

list	The list to operate on.
op	The operator to apply.
arg	An optional parameter to send to op.

struct list* list_sort	(	struct list *	list,
		int()(const void , const void *)	comparator
	)

Sort a list using a comparator function.

Parameters

list	The list to sort.
comparator	The comparison function used in the sort. The function should take in pointers to two objects casted as void* and return an integer indicating whether the first is less than (negative), equal to (0), or greater than (positive) the second.

Returns: A pointer to the list passed in. Identical to the list parameter.

Functions

Detailed Description

Function Documentation