The List Library  0.2.1
Data Structures | Defines
list.h File Reference

Documentation for List Library (CDSL) More...

#include <stddef.h>
Include dependency graph for list.h:
This graph shows which files directly or indirectly include this file:

Data Structures

struct  list_t
 represents a node in a list. More...

Defines

#define LIST_FOREACH(pos, list)   for ((pos) = (list); (pos); (pos)=(pos)->next)
 iterates for each node of a list

Functions

list creating functions:
list_tlist_list (void *,...)
 constructs a new list using a sequence of data.
list_tlist_append (list_t *, list_t *)
 appends a list to another.
list_tlist_push (list_t *, void *)
 pushes a new node to a list.
list_tlist_copy (const list_t *)
 duplicates a list.
data/information retrieving functions:
list_tlist_pop (list_t *, void **)
 pops a node from a list and save its data (pointer) into a pointer object.
void ** list_toarray (const list_t *, void *)
 converts a list to an array.
size_t list_length (const list_t *)
 counts the length of a list.
list destroying functions:
void list_free (list_t **)
 destroys a list.
list handling functions:
void list_map (list_t *, void(void **, void *), void *)
list_tlist_reverse (list_t *)
 reverses a list.

Detailed Description

Documentation for List Library (CDSL)

Header for List Library (CDSL)


Define Documentation

#define LIST_FOREACH (   pos,
  list 
)    for ((pos) = (list); (pos); (pos)=(pos)->next)

iterates for each node of a list

LIST_FOREACH() macro is useful when doing some task for every node of a list. For example, the following example deallocates storages for data of each node in a list named list and destroy list itself using list_free():

      list_t *t;

      LIST_FOREACH(t, list)
      {
          MEM_FREE(t->data);
      }
      list_free(list);

The braces enclosing the call to MEM_FREE are optional in this case as you may omit them in ordinary iterative statements. After the loop, list is untouched and t becomes indeterminate (if the loop finishes without jumping out of it, it should be a null pointer). There are cases where LIST_FOREACH() is more convenient than list_map() but the latter is recommended.

Warning:
Be wraned that modification to a list like pushing and popping a node before finishing the loop must be done very carefully and highly discouraged. For example, pushing a new node with t may invalidate the internal state of the list, popping a node with list may invalidate t thus subsequent tasks depending on which node t points to and so on. It is possible to provide a safer version of LIST_FOREACH() as done by Linux kernel's list implementation, but not done by this implementation for such an operation is not regarded as appropriate to the list.

Function Documentation

list_t* list_append ( list_t list,
list_t tail 
)

appends a list to another.

list_append() combines two lists by appending tail to list, which makes the next pointer of the last node in list point to the first node of tail.

Possible exceptions: mem_exceptfail

Unchecked errors: foreign data structure given for list and tail

Warning:
Do not forget that a null pointer is considered an empty list, not an error.
Parameters:
[in,out]listlist to which tail appended
[in]taillist to append to list
Returns:
appended list whose (pointer) value should be the same as list
Todo:
Improvements are possible and planned:
  • the time complexity of the current implementation is O(N) where N indicates the number of nodes in a list. With a circular list, where the next node of the last node set to the head, it is possible for both pushing and appending to be done in a constant time.
list_t* list_copy ( const list_t list)

duplicates a list.

list_copy() creates a new list by copying nodes of list.

Possible exceptions: mem_exceptfail

Unchecked errors: foreign data structure given for list

Warning:
Note that the data pointed by nodes in list are not duplicated. An empty list results in returning a null pointer, which means an empty list.
Parameters:
[in]listlist to duplicate
Returns:
duplicated list
void list_free ( list_t **  plist)

destroys a list.

list_free() destroys a list by deallocating storages for each node. After the call, the list is empty, which means that it makes a null pointer. If plist points to a null pointer, list_free() does nothing since it is already empty.

Possible exceptions: none

Unchecked errors: pointer to foreign data structure given for plist

Warning:
Note that the type of plist is a double pointer to list_t.
Parameters:
[in,out]plistpointer to list to destroy
Returns:
nothing
size_t list_length ( const list_t list)

counts the length of a list.

list_length() counts the number of nodes in list.

Possible exceptions: none

Unchecked errors: foreign data structure given for list

Parameters:
[in]listlist whose nodes counted
Returns:
length of list

Here is the caller graph for this function:

list_t* list_list ( void *  data,
  ... 
)

constructs a new list using a sequence of data.

list_list() constructs a 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 list_list() with one argument, a null pointer, is not treated as an error. Such a call requests an empty list, so returned; note that a null pointer is an empty list.
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
list_t* list_pop ( list_t list,
void **  pdata 
)

pops a node from a list and save its data (pointer) into a pointer object.

list_pop() copies a pointer value stored in the head node of list to a pointer object pointed to by pdata and pops the node. If the list is empty, list_pop() does nothing and just returns list. If pdata is a null pointer list_pop() just pops without saving any data.

Possible exceptions: none

Unchecked errors: foreign data structure given for list

Parameters:
[in]listlist from which head node popped
[out]pdatapoints to pointer into which data (pointer value) stored
Warning:
The return value of list_pop() has to be used to update the variable for the list passed. list_pop() takes a list and returns a modified list.
Returns:
list with its head node popped
list_t* list_push ( list_t list,
void *  data 
)

pushes a new node to a list.

list_push() pushes a pointer value data to a list list with creating a new node. A null pointer given for list is considered to indicate an empty list, thus not treated as an error.

Possible exceptions: mem_exceptfail

Unchecked errors: foreign data structure given for list

Parameters:
[in]listlist to which data pushed
[in]datadata to push into list
Warning:
The return value of list_push() has to be used to update the variable for the list passed. list_push() takes a list and returns a modified list.
Returns:
modified list
list_t* list_reverse ( list_t list)

reverses a list.

list_reverse() reverses a list, which eventually makes its first node the last and vice versa.

Possible exceptions: none

Unchecked errors: foreign data structure given for list

Parameters:
[in]listlist to reverse
Warning:
The return value of list_reverse() has to be used to update the variable for the list passed. list_reverse() takes a list and returns a reversed list.
Returns:
reversed list
void** list_toarray ( const list_t list,
void *  end 
)

converts a list to an array.

list_toarray() converts a list to an array whose elements correspond to the data stored in nodes of the list. This is useful when, say, sorting a list. A function like array_tolist() is not necessary because it is easy to construct a list scanning elements of an array, for example:

      for (i = 0; i < ARRAY_SIZE; i++)
          list = list_push(list, array[i]);

The last element of the constructed array is assigned by end, which is a null pointer in most cases. Do not forget to deallocate the array when it is unnecessary.

Possible exceptions: mem_exceptfail

Unchecked errors: foreign data structure given for list

Warning:
The size of an array generated for an empty list is not zero, since there is always an end-mark value.
Parameters:
[in]listlist to convert to array
[in]endend-mark to save in last element of array
Returns:
array converted from list

Here is the call graph for this function:

 All Data Structures Files Functions Variables Defines