dlist.h File Reference

Header for Doubly-Linked List Library (CDSL). More...

This graph shows which files directly or indirectly include this file:


Typedefs

typedef struct dlist_t dlist_t
 represents a doubly-linked list.

Functions

list creating functions:
dlist_tdlist_new (void)
 creates an empty new list.
dlist_tdlist_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.

Detailed Description

Header for Doubly-Linked List Library (CDSL).

Documentation for Doubly-Linked List Library (CDSL).


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)

       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

Parameters:
[in,out] dlist list to which new node inserted
[in] pos position for new node
[in] data data 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] dlist list to which new node to be inserted
[in] data data 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] dlist list to which new node to be inserted
[in] data data 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] pdlist pointer 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] dlist list from which data is to be retrieved
[in] i index 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] dlist list 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 the 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] data data 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] dlist list whose data to be replaced
[in] i index for noded
[in] data new 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] dlist list 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] dlist list from which node to be removed
[in] i index 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] dlist list 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) does not have any effect as dlist_shift(..., 0) does not.

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] dlist list to shift
[in] n direction and distance of shift
Returns:
nothing


Generated on Mon Jan 24 01:12:50 2011 for The Doubly-Linked List Library by  doxygen 1.5.8