list.h File Reference

Robust, reentrant linked list structure. More...

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

Go to the source code of this file.

## Macros

#define | LIST_ITERATE(list, item)
| Macro to iterate over a list in the most common case.

## Functions

struct list * | list_create (void)
| Create an empty linked list.
bool | list_destroy (struct list *list)
| Delete an empty list.
unsigned | list_length (struct list *list)
| Get the number of items in a list.
struct list_cursor * | list_cursor_create (struct list *list)
| Create a new cursor on a list.
void | list_cursor_destroy (struct list_cursor *cur)
| Delete a previously created cursor.
struct list_cursor * | list_cursor_clone (struct list_cursor *cur)
| Get a copy of an existing cursor.
void | list_reset (struct list_cursor *cur)
| Reset the position of a cursor.
bool | list_seek (struct list_cursor *cur, int index)
| Move a cursor to an item by index.
bool | list_tell (struct list_cursor *cur, unsigned *index)
| Get the position of a cursor within a list.
bool | list_next (struct list_cursor *cur)
| Move a cursor to the next item.
bool | list_prev (struct list_cursor *cur)
| Move a cursor to the previous item.
bool | list_get (struct list_cursor *cur, void **item)
| Get the item under a cursor.
bool | list_set (struct list_cursor *cur, void *item)
| Set the value under the cursor.
bool | list_drop (struct list_cursor *cur)
| Remove the item under the cursor.
void | list_insert (struct list_cursor *cur, void *item)
| Insert an item to the left of the cursor.
int | list_size (struct list *list)
| Count the elements in a list.
struct list * | list_duplicate (struct list *list)
| Duplicate a linked list Returns a copy of the linked list.
void | list_delete (struct list *list)
| Delete a linked list.
void | list_free (struct list *list)
| Free every item referred to by the list.
void | list_clear (struct list *list, void(*delete_func)(void *item))
| Delete every item contained within this list, using the provided function.
struct list * | list_splice (struct list *top, struct list *bottom)
| Splice two lists together.
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.
int | list_push_head (struct list *list, void *item)
| Push an item onto the list head.
void * | list_pop_head (struct list *list)
| Pop an item off of the list head.
void * | list_peek_head (struct list *list)
| Peek at the list head.
int | list_push_tail (struct list *list, void *item)
| Push an item onto the list tail.
void * | list_pop_tail (struct list *list)
| Pop an item off of the list tail.
void * | list_rotate (struct list *list)
| Move the list head to the tail.
void * | list_peek_tail (struct list *list)
| Peek at the list tail.
void * | list_peek_current (struct list *list)
| Peek at the current element in the iteration.
void | list_push_priority (struct list *list, list_priority_t p, void *item)
| Push an item onto of a list 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.
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.
void | list_first_item (struct list *list)
| Begin traversing a list.
void * | list_next_item (struct list *list)
| Continue traversing a list.
int | list_iterate (struct list *list, list_op_t op, const void *arg)
| Apply a function to a list.
int | list_iterate_reverse (struct list *list, list_op_t op, const void *arg)
| Apply a function to a list in reverse.
struct list * | list_sort (struct list *list, int(*comparator)(const void *, const void *))
| Sort a list using a comparator function.

## 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.

## Macro Definition Documentation

## LIST_ITERATE

#define LIST_ITERATE | ( |  | list,
|  |  | item )

Value:
list_first_item(list); while((item=list_next_item(list)))
list_next_item
void * list_next_item(struct list *list)
Continue traversing a list.
list_first_item
void list_first_item(struct list *list)
Begin traversing a list.

Macro to iterate over a list in the most common case.

Note that a statement or code block must follow the macro, like this:

    char *s;

    LIST_ITERATE( list, s ) {
            printf("%s\n",s);
    }

## Function Documentation

## list_create()

struct list * list_create | ( | void |  | ) |

Create an empty linked list.

Returns
  A pointer to the newly created list.

## list_destroy()

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.

## list_length()

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.

## list_cursor_create()

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.

## list_cursor_destroy()

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.

## list_cursor_clone()

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.

## list_reset()

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.

## list_seek()

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.

## list_tell()

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.

## list_next()

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.

## list_prev()

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.

## list_get()

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.

## list_set()

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.

## list_drop()

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.

## list_insert()

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.

## list_size()

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.

## list_duplicate()

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

## list_delete()

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.

## list_free()

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.

## list_clear()

void list_clear | ( | struct list * | list,
|  | void(* | delete_func )(void *item) )

Delete every item contained within this list, using the provided function.

Note that this function does not delete the list itself.

Parameters

  list | The list to free.
  delete_func | The function to delete items with.

## list_splice()

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.

## list_split()

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.

## list_push_head()

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.)

## list_pop_head()

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.

## list_peek_head()

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.

## list_push_tail()

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.)

## list_pop_tail()

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.

## list_rotate()

void * list_rotate | ( | struct list * | list | ) |

Move the list head to the tail.

Parameters

  list | The list to rotate

Returns
  The old list head, new tail

## list_peek_tail()

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.

## list_peek_current()

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 current internal iterator, or null if list is empty.

## list_push_priority()

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.

## list_find()

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.

## list_remove()

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.

## list_first_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.

## list_next_item()

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, NULL if end of list.

## list_iterate()

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.

## list_iterate_reverse()

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.

## list_sort()

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

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.