The Doubly-Linked List Library  0.2.1
Functions
dlist.c File Reference

Source for Doubly-Linked List Library. More...

#include <limits.h>
#include <stddef.h>
#include <stdarg.h>
#include "cbl/assert.h"
#include "cbl/memory.h"
#include "dlist.h"
Include dependency graph for dlist.c:

Functions

dlist_t *() dlist_new (void)
 creates an empty new list.
dlist_t *() dlist_list (void *data,...)
 constructs a new list using a given sequence of data.
void() dlist_free (dlist_t **pdlist)
 destroys a list.
long() dlist_length (const dlist_t *dlist)
 returns the length of a list.
void *() dlist_get (dlist_t *dlist, long i)
 retrieves data stored in the i-th node in a list.
void *() dlist_put (dlist_t *dlist, long i, void *data)
 replaces data stored in a node with new given data.
void *() dlist_addtail (dlist_t *dlist, void *data)
 adds a node after the last node.
void *() dlist_addhead (dlist_t *dlist, void *data)
 adds a new node before the head node.
void *() dlist_add (dlist_t *dlist, long pos, void *data)
 adds a new node to a specified position in a list.
void *() dlist_remove (dlist_t *dlist, long i)
 removes a node with a specific index from a list.
void *() dlist_remtail (dlist_t *dlist)
 removes the last node of a list.
void *() dlist_remhead (dlist_t *dlist)
 removes the first node from a list.
void() dlist_shift (dlist_t *dlist, long n)
 shifts a list to right or left.

Detailed Description

Source for Doubly-Linked List Library.


Function Documentation

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 to be in a list)

       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 pos - (dlist_length()+1) gives a non-negative value for a positive pos, and pos + (dlist_length()+1) gives a positive value for a negative pos.

Possible exceptions: mem_exceptfail, assert_exceptfail

Unchecked errors: foreign data structure given for dlist

Parameters:
[in,out]dlistlist to which new node inserted
[in]posposition for new node
[in]datadata for new node
Returns:
data for new node

Here is the call graph for this function:

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

Parameters:
[in,out]dlistlist to which new node to be inserted
[in]datadata for new node
Returns:
data for new node

Here is the call graph for this function:

Here is the caller graph for this function:

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

Parameters:
[in,out]dlistlist to which new node to be inserted
[in]datadata for new node
Returns:
data for new node

Here is the caller graph for this function:

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

Parameters:
[in,out]pdlistpointer to list to destroy
Returns:
nothing
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

Parameters:
[in,out]dlistlist from which data is to be retrieved
[in]iindex for node
Returns:
data retrieved
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

Parameters:
[in]dlistlist whose length to be returned
Returns:
length of list (non-negative)
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 a null pointer is for. Any argument following a null pointer argument is not invalid, but ignored.

Possible exceptions: mem_exceptfail

Unchecked errors: none

Warning:
Calling dlist_list() with one argument, a null pointer, is not treated as an error. Such a call request an empty list as calling dlist_new().
Parameters:
[in]datadata to store in head node of new list
[in]...other data to store in new list
Returns:
new list containing given sequence of data

Here is the call graph for this function:

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

Returns:
empty new list

Here is the caller graph for this function:

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

Parameters:
[in,out]dlistlist whose data to be replaced
[in]iindex for noded
[in]datanew data for substitution
Returns:
old data
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

Parameters:
[in,out]dlistlist from which first node to be removed
Returns:
data of deleted node

Here is the call graph for this function:

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

Parameters:
[in,out]dlistlist from which node to be removed
[in]iindex for node to remove
Returns:
data of removed node
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

Parameters:
[in,out]dlistlist from which last node to be removed
Returns:
data of deleted node

Here is the caller graph for this function:

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) has no effect as dlist_shift(..., 0) has none.

Possible exceptions: assert_exceptfail

Unchecked errors: foreign data structure given for dlist

Warning:
Note that it is a list itself that dlist_shift() shifts, not the head pointer of a list.
Parameters:
[in,out]dlistlist to shift
[in]ndirection and distance of shift
Returns:
nothing
 All Files Functions Typedefs