Typedefs | |
typedef struct dlist_t | dlist_t |
represents a doubly-linked list. | |
Functions | |
list creating functions: | |
dlist_t * | dlist_new (void) |
creates an empty new list. | |
dlist_t * | dlist_list (void *,...) |
constructs a new list using a given sequence of data. | |
list destroying functions: | |
void | dlist_free (dlist_t **) |
destroys a list. | |
node adding/deleting functions: | |
void * | dlist_add (dlist_t *, long, void *) |
adds a new node to a specified position in a list. | |
void * | dlist_addhead (dlist_t *, void *) |
adds a new node before the head node. | |
void * | dlist_addtail (dlist_t *, void *) |
adds a node after the last node. | |
void * | dlist_remove (dlist_t *, long) |
removes a node with a specific index from a list. | |
void * | dlist_remhead (dlist_t *) |
removes the first node from a list. | |
void * | dlist_remtail (dlist_t *) |
removes the last node of a list. | |
data/information retrieving functions: | |
long | dlist_length (const dlist_t *) |
returns the length of a list. | |
void * | dlist_get (dlist_t *, long) |
retrieves data stored in the i-th node in a list. | |
void * | dlist_put (dlist_t *, long, void *) |
replaces data stored in a node with new given data. | |
list handling functions: | |
void | dlist_shift (dlist_t *, long) |
shifts a list to right or left. |
Documentation for Doubly-Linked List Library (CDSL).
void* dlist_add | ( | dlist_t * | dlist, | |
long | pos, | |||
void * | data | |||
) |
adds a new node to a specified position in a list.
dlist_add() inserts a new node to a position specified by pos
. The position is interpreted as follows: (5 nodes assumed)
1 2 3 4 5 6 positive position values +-+ +-+ +-+ +-+ +-+ | |--| |--| |--| |--| | +-+ +-+ +-+ +-+ +-+ -5 -4 -3 -2 -1 0 non-positive position values
Non-positive positions are useful when to locate without knowing the length of a list. If a list is empty both 0 and 1 are the valid values for a new node. Note that for positive pos
pos
- (dlist_length()+1) gives a non-negative value for the same position, and for negative pos
pos
+ (dlist_length()+1) gives a positive value for the same position.
Possible exceptions: mem_exceptfail, assert_exceptfail
Unchecked errors: foreign data structure given for dlist
[in,out] | dlist | list to which new node inserted |
[in] | pos | position for new node |
[in] | data | data for new node |
void* dlist_addhead | ( | dlist_t * | dlist, | |
void * | data | |||
) |
adds a new node before the head node.
dlist_addhead() inserts a new node before the head node; the new node will be the head node. dlist_addhead() is equivalent to dlist_add() with 1 given for the position.
Possible exceptions: mem_exceptfail, assert_exceptfail
Unchecked errors: foreign data structure given for dlist
[in,out] | dlist | list to which new node to be inserted |
[in] | data | data for new node |
void* dlist_addtail | ( | dlist_t * | dlist, | |
void * | data | |||
) |
adds a node after the last node.
dlist_addtail() inserts a new node after the last node; the index for the new node will be N if there are N nodes before the insertion. If a list is empty, dlist_addtail() and dlist_addhead() do the same job. dlist_addtail() is equivalent to dlist_add() with 0 given for the position.
Possible exceptions: mem_exceptfail, assert_exceptfail
Unchecked errors: foreign data structure given for dlist
[in,out] | dlist | list to which new node to be inserted |
[in] | data | data for new node |
void dlist_free | ( | dlist_t ** | pdlist | ) |
destroys a list.
dlist_free() destroys a list by deallocating storages for each node and for the list itself. After the call the list does not exist (do not confuse this with an empty list). If pdlist
points to a null pointer, an assertion in dlist_free() fails; it's a checked error.
Possible exceptions: assert_exceptfail
Unchecked error: pointer to foreign data structure given for plist
[in,out] | pdlist | pointer to list to destroy |
void* dlist_get | ( | dlist_t * | dlist, | |
long | i | |||
) |
retrieves data stored in the i-th
node in a list.
dlist_get() brings and return data in the i-th
node in a list. The first node has the index 0 and the last has n-1 when there are n nodes in a list.
Possible exceptions: assert_exceptfail
Unchecked errors: foreign data structure given for dlist
[in,out] | dlist | list from which data is to be retrieved |
[in] | i | index for node |
long dlist_length | ( | const dlist_t * | dlist | ) |
returns the length of a list.
dlist_length() returns the length of a list, the number of nodes in it.
Possible exceptions: assert_exceptfail
Unchecked errors: foreign data structure given for dlist
[in] | dlist | list whose length to be returned |
dlist_t* dlist_list | ( | void * | data, | |
... | ||||
) |
constructs a new list using a given sequence of data.
dlist_list() constructs a doubly-linked list whose nodes contain a sequence of data given as arguments; the first argument is stored in the head (first) node, the second argument in the second node, and so on. There should be a way to mark the end of the argument list, which the null pointer is for. Any argument following a null pointer argument is not invalid, but ignored.
Possible exceptions: mem_exceptfail
Unchecked errors: none
[in] | data | data to store in head node of new list |
[in] | ... | other data to store in new list |
dlist_t* dlist_new | ( | void | ) |
creates an empty new list.
dlist_new() creates an empty list and returns it for further use.
Possible exceptions: mem_exceptfail
Unchecked errors: none
void* dlist_put | ( | dlist_t * | dlist, | |
long | i, | |||
void * | data | |||
) |
replaces data stored in a node with new given data.
dlist_put() replaces the data stored in the i-th
node with new given data and retrieves the old data. For indexing, see dlist_get().
Possible exceptions: assert_exceptfail
Unchecked errors: foreign data structure given for dlist
[in,out] | dlist | list whose data to be replaced |
[in] | i | index for noded |
[in] | data | new data for substitution |
void* dlist_remhead | ( | dlist_t * | dlist | ) |
removes the first node from a list.
dlist_remhead() removes the first (head) node from a list. dlist_remhead() is equivalent to dlist_remove() with 0 for the position.
Possible exceptions: assert_exceptfail
Unchecked errors: foreign data structure given for dlist
[in,out] | dlist | list from which first node to be removed |
void* dlist_remove | ( | dlist_t * | dlist, | |
long | i | |||
) |
removes a node with a specific index from a list.
dlist_remove() removes the i-th
node from a list. For indexing, see dlist_get().
Possible exceptions: assert_exceptfail
Unchecked errors: foreign data structure given for dlist
[in,out] | dlist | list from which node to be removed |
[in] | i | index for node to remove |
void* dlist_remtail | ( | dlist_t * | dlist | ) |
removes the last node of a list.
dlist_remtail() removes the last (tail) node of a list. dlist_remtail() is equivalent to dlist_remove() with dlist_length()-1 for the index.
Possible exceptions: assert_exceptfail
Unchecked errors: foreign data structure given for dlist
[in,out] | dlist | list from which last node to be removed |
void dlist_shift | ( | dlist_t * | dlist, | |
long | n | |||
) |
shifts a list to right or left.
dlist_shift() shifts a list to right or left according to the value of n
. A positive value indicates shift to right; for example shift by 1 means to make the tail node become the head node. Similarly, a negative value indicates shift to left; for example shift by -1 means to make the head node become the tail node.
The absolute value of the shift distance specified by n
should be equal to or less than the length of a list. For exmple, dlist_shift(..., 7) or dlist_shift(..., -7) is not allowed when there are only 6 nodes in a list. In such a case, dlist_shift(..., 6) or dlist_shift(..., -6) does not have any effect as dlist_shift(..., 0) does not.
Possible exceptions: assert_exceptfail
Unchecked errors: foreign data structure given for dlist
[in,out] | dlist | list to shift |
[in] | n | direction and distance of shift |