The List Library  0.2.1
Functions
list.c File Reference

Source for List Library (CDSL) More...

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

Functions

list_t *() list_push (list_t *list, void *data)
 pushes a new node to a list.
list_t *() list_list (void *data,...)
 constructs a new list using a sequence of data.
list_t *() list_append (list_t *list, list_t *tail)
 appends a list to another.
list_t *() list_copy (const list_t *list)
 duplicates a list.
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_t *() list_reverse (list_t *list)
 reverses a list.
size_t() list_length (const list_t *list)
 counts the length of a list.
void() list_free (list_t **plist)
 destroys a list.
void() list_map (list_t *list, void apply(void **, void *), void *cl)
 calls a user-provided function for each node in a list.
void **() list_toarray (const list_t *list, void *end)
 converts a list to an array.

Detailed Description

Source for List Library (CDSL)


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
void() list_map ( list_t list,
void   applyvoid **, void *,
void *  cl 
)

calls a user-provided function for each node in a list.

For each node in a list, list_map() calls a user-provided callback function; it is useful when doing some common task for each node. The pointer given in cl is passed to the second parameter of a user callback function, so can be used as a communication channel between the caller of list_map() and the callback. Since the callback has the address of data (as opposed to the value of data) through the first parameter, it is free to change its content. One of cases where list_map() is useful is to deallocate storages given for data of each node. Differently from the original implementation, this library also provides a marco named LIST_FOREACH() that can be used in the similar situation.

Possible exceptions: none (user-provided function may raise some)

Unchecked errors: foreign data structure given for list, user callback function doing something wrong (see the warning below)

Warning:
Be wraned that modification to a list like pushing and popping a node before finishing list_map() must be done very carefully and highly discouraged. For example, in a callback function popping a node from the same list list_map() is applying to may spoil subsequent tasks depending on which node list_map() is dealing with. It is possible to provide a safer version, but not done because such an operation is not regarded as appropriate to the list.
Parameters:
[in,out]listlist with which apply called
[in]applyuser-provided function (callback)
[in]clpassing-by argument to apply
Returns:
nothing
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