Files | |
| file | list.c |
| Linked lists implementation. | |
| file | list.h |
| Linked lists header. | |
Functions | |
| int | list_push (node_l **_x, void *_data) |
| Adds a new node to the list. | |
| int | cmp (void *_a, void *_b) |
| Auxiliary function for examples. | |
| void * | list_pop (node_l **_x) |
| Removes the first node from the list and returns its node data. | |
| int | list_move (node_l **_dest, node_l **_src) |
Moves a node from _src to _dest. | |
| int | list_reverse (node_l **_x) |
| Reverses the order of a list. | |
| node_l * | list_sub (const node_l *_x, int _pos) |
Returns a sub-list of _x. | |
| int | list_insert (node_l **_x, int _pos, void *_data) |
| Inserts a new node at the specified position. | |
| void * | list_remove (node_l **_x, int _pos) |
Removes element at position _pos+1 from the list, returning its data. | |
| void * | list_get (const node_l *_x, int _pos) |
| Get data item of a list element. | |
| size_t | list_size (const node_l *_x) |
| Computes the size of a list. | |
| node_l * | list_join (node_l *_dest, node_l *_src) |
Appends the list _src to the list _dest. | |
| void | list_print (const node_l *_a) |
| Prints list elements. | |
| int | list_split (node_l **_src, node_l **_front, node_l **_back) |
| Splits a list in two equal-sized sublists. | |
| int | list_merge (node_l **_dest, node_l **_a, node_l **_b, int _cmp(void *, void *)) |
Merges two lists using _cmp to compare nodes. | |
| int | list_sort (node_l **_x, int _cmp(void *, void *)) |
| Sorts a list. | |
| int | list_copy (const node_l *_src, node_l **_dest) |
| Makes a copy of a list, not including its data items (see list_dup()). | |
| int | list_realloc (node_l *_x, size_t _sz) |
| Re-allocates storage for a list. | |
| int | list_dup (node_l *_src, node_l **_dest, size_t _sz) |
| Duplicates a list, including its data items (see list_copy()). | |
| void | list_delete (node_l **_x) |
| Deletes a list, not including its data items. | |
| void | list_destroy (node_l **_x) |
| Destroys a list, including its data items. | |
| node_l * | list_create123 () |
| Auxiliary function for examples. | |
| int | list_foreach (node_l *_x, int _func(void *)) |
| Calls a function for each list element. | |
See the following pages for detailed information about linked lists:
| int list_push | ( | node_l ** | _x, | |
| void * | _data | |||
| ) |
Adds a new node to the list.
Creates a new node with the given data and pushes it onto the front of the list. The list is not passed in by its head pointer. Instead the list is passed in as a "reference" pointer to the head pointer -- this allows as to modify the caller's memory.
This is a constant time operation.
| _x | reference to a list (adress might change) | |
| _data | the data item for the new node |
Definition at line 56 of file dlist.c.
References node_l::data, and node_l::next.
Referenced by list_copy(), list_create123(), list_insert(), and stack_push().
| int cmp | ( | void * | _a, | |
| void * | _b | |||
| ) |
Auxiliary function for examples.
This function compares to data items and returns -1, 0 or 1 if the first argument is less than, equal to or greater than the second argument respectively.
| _a | data item | |
| _b | data item |
Definition at line 312 of file dlist.c.
References _data::n.
| void* list_pop | ( | node_l ** | _x | ) |
Removes the first node from the list and returns its node data.
Note that NULL is a valid node data. Also note that the function will return NULL also for the empty list.
This is a constant time operation.
| _x | reference to a list (adress might change) |
Definition at line 80 of file list.c.
References node_l::data, and node_l::next.
Referenced by list_delete(), list_destroy(), list_remove(), and stack_pop().
Moves a node from _src to _dest.
The function removes the first node of _src, making it the first node of _dest. If _src and _dest are equal, the current implementation swaps the first two nodes. This behaviour may change in future releases, so don't rely on it.
| _dest | the destination list | |
| _src | the source list |
_src is the empty list), 0 on success Definition at line 109 of file list.c.
References node_l::next.
Referenced by list_merge(), and list_reverse().
| int list_reverse | ( | node_l ** | _x | ) |
Reverses the order of a list.
This function reverses the order of a list, making the last element the first, the second-last the second-first and so on... This is useful when creating a list with a few list_push() operations, because elements will then appear in reverse order.
| _x | reference to a list (adress might change) |
Definition at line 136 of file list.c.
References list_move().
Referenced by list_copy().
Returns a sub-list of _x.
This function returns the sub-list of _x starting at position _pos+1.
| _x | pointer to a list | |
| _pos | sub-list position |
_pos+1 Definition at line 157 of file list.c.
References node_l::next.
Referenced by list_insert().
| int list_insert | ( | node_l ** | _x, | |
| int | _pos, | |||
| void * | _data | |||
| ) |
Inserts a new node at the specified position.
This function creates a new node with the supplied _data and inserts it at position _pos+1 of _x. This is a linear time operation, for obvious reasons.
| _x | reference to a list (address might change) | |
| _pos | position of new list node | |
| _data | data item of new list node |
Definition at line 186 of file list.c.
References list_push(), list_sub(), and node_l::next.
| void* list_remove | ( | node_l ** | _x, | |
| int | _pos | |||
| ) |
Removes element at position _pos+1 from the list, returning its data.
This function removes the element at position _pos+1 from the list. If _pos is 0, its semantics are equivalent to list_pop().
| _x | reference to a list (address might change) | |
| _pos | position of element to be removed |
Definition at line 214 of file list.c.
References node_l::data, list_pop(), and node_l::next.
| void* list_get | ( | const node_l * | _x, | |
| int | _pos | |||
| ) |
Get data item of a list element.
This function returns a pointer to the data item of the list element at position _pos+1. It will return NULL on error. Note that NULL is also a valid data item.
| _x | pointer to a list | |
| _pos | position of a list element |
NULL on error, pointer to a data item on success Definition at line 255 of file list.c.
References node_l::data, and node_l::next.
| size_t list_size | ( | const node_l * | _x | ) |
Computes the size of a list.
This function computes the size of a list. The code should be relatively self-explanatory.
| _x | pointer to a list |
Definition at line 279 of file list.c.
References node_l::next.
Appends the list _src to the list _dest.
If _dest is empty, it simply returns _src, else it makes the last element of _dest point to the first element of _src, modifying _dest.
| _dest | the destination list | |
| _src | the source list |
_dest, with _src appended Definition at line 297 of file list.c.
References node_l::next.
| void list_print | ( | const node_l * | _a | ) |
Prints list elements.
This function will change or vanish in future releases, so don't use it. It will be replaced by list_foreach(), which shall execute a user-supplied function for each list element.
| _a | pointer to a list |
Definition at line 324 of file list.c.
References node_l::data, _data::n, node_l::next, and _data::str.
Splits a list in two equal-sized sublists.
This function uses the hare-and-tortoise approach, also known as the Classic Floyd's Cycle Finding Algorithm to split a list in two rougly equal-sized sublists (see http://en.wikipedia.org/wiki/Floyd's_cycle-finding_algorithm for details). You should make sure that the list doesn't contain cycles using list_cyclic() (to be implemented).
| _src | reference to a list (will be replaced by NULL) | |
| _front | reference to a list (will be replaced by the first sublist) | |
| _back | reference to a list (will be replaced by the second sublist) |
Definition at line 351 of file list.c.
References node_l::next.
Referenced by list_sort().
Merges two lists using _cmp to compare nodes.
This function merges the two lists _a and _b into the new list _dest using the function _cmp to decide which element to choose next, the first element of _a or the first element of _b. _cmp is a comparison function and shall return -1, 0 or 1 if _a->data is less than, equal to or greater than _b->data.
This function is mainly used in list_sort() to merge two already sorted sublists together.
| _dest | a reference to the resulting list | |
| _a | reference to list A | |
| _b | reference to list B | |
| _cmp | comparison function, takes two data items and returns int |
Definition at line 396 of file list.c.
References list_move().
Referenced by list_sort().
| int list_sort | ( | node_l ** | _x, | |
| int | _cmp(void *, void *) | |||
| ) |
Sorts a list.
This function sorts a list using mergesort (see http://en.wikipedia.org/wiki/Merge_sort for details). The comparison function _cmp determines the sort order: _cmp takes two data items A and B and returns -1, 0 or 1 if A is less than, equal to or greater than B respectively.
| _x | reference to a list (address might change) | |
| _cmp | comparison function |
Definition at line 438 of file list.c.
References list_merge(), list_sort(), list_split(), and node_l::next.
Referenced by list_sort().
Makes a copy of a list, not including its data items (see list_dup()).
This function creates a copy of a list, NOT duplicating the list's data items. The resulting list uses the same data items as the original list. If you want to duplicate the data items too, use list_dup().
On error, -1 is returned and _dest is the copy of _src up to the point where no more memory was available. In all cases, you have to list_free() _dest.
| _src | pointer to a list | |
| _dest | reference to the list copy |
Definition at line 473 of file list.c.
References node_l::data, list_push(), list_reverse(), and node_l::next.
Referenced by list_dup().
| int list_realloc | ( | node_l * | _x, | |
| size_t | _sz | |||
| ) |
Re-allocates storage for a list.
This function re-allocates all data items in _x, assigning the new address to its nodes.
This function is mainly used in list_dup().
| _x | pointer to a list | |
| _sz | size of the list's data items |
Definition at line 500 of file list.c.
References node_l::data, and node_l::next.
Referenced by list_dup().
Duplicates a list, including its data items (see list_copy()).
Makes a copy of _src, saving a pointer to the result in _dest.
This function merely calls list_copy(), followed by list_realloc().
| _src | pointer to a list | |
| _dest | reference to a list (address might change) | |
| _sz | size of the list's data items |
Definition at line 529 of file list.c.
References list_copy(), and list_realloc().
| void list_delete | ( | node_l ** | _x | ) |
Deletes a list, not including its data items.
This function deletes a list, not including its data items. This will result in memory leaks if you don't have a copy of the list, because all references to the data items are lost.
| _x | reference to a list (address might change) |
Definition at line 552 of file list.c.
References list_pop().
Referenced by stack_delete(), and stack_reset().
| void list_destroy | ( | node_l ** | _x | ) |
Destroys a list, including its data items.
This function deletes a list, including its data items. After a call to list_destroy(), the list and its data items will be lost. If you have a copy of the list, it will be invalid (use list_delete() on it).
| _x | reference to a list (address might change) |
Definition at line 571 of file list.c.
References list_pop().
Referenced by stack_destroy().
| node_l* list_create123 | ( | ) |
Auxiliary function for examples.
This function creates a short list, see examples for details.
FIXME: add examples
Definition at line 589 of file list.c.
References list_push(), _data::n, and _data::str.
| int list_foreach | ( | node_l * | _x, | |
| int | _func(void *) | |||
| ) |
Calls a function for each list element.
list_foreach() executes the user-supplied function _func for each element of the list pointed to by _x, passing the element's data to _func. list_foreach() returns the sum of all return values of _func. This is useful if you want to count all list elements that match to certain criteria, but you may also use list_foreach() for much simpler operations, e.g. print functions.
| _x | a list | |
| _func | a function |
_func return values Definition at line 643 of file list.c.
References node_l::data, and node_l::next.
1.5.1-p1. Thank you,