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 given list.
list_t *() list_list (void *data,...)
 constructs a new list using a given 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 given 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] list list to which tail appended
[in] tail list 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 node, 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] list list 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 means an empty list.

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] plist pointer 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] list list 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 given 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] 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

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 because such an operation is not regarded as appropriate to the list.
Parameters:
[in,out] list list with which apply called
[in] apply user-provided function (callback)
[in] cl passing-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 given 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 given 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] list list from which head node popped
[out] pdata points 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 given list.

list_push() pushes a pointer value data to a given list list with creating a new node. The 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] list list to which data pushed
[in] data data 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 given 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] list list 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 given 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] list list to convert to array
[in] end end-mark to save in last element of array
Returns:
array converted from list

Here is the call graph for this function:


Generated on Mon Jan 24 01:12:57 2011 for The List Library by  doxygen 1.5.8