ucx
UAP Common Extensions
Data Structures | Macros | Typedefs | Functions
list.h File Reference

Doubly linked list implementation. More...

#include "ucx.h"
#include "allocator.h"

Go to the source code of this file.

Data Structures

struct  UcxList
 UCX list structure. More...
 

Macros

#define UCX_FOREACH(elem, list)   for (UcxList* elem = list ; elem != NULL ; elem = elem->next)
 Loop statement for UCX lists. More...
 

Typedefs

typedef struct UcxList UcxList
 UCX list type. More...
 

Functions

UcxListucx_list_clone (UcxList *list, copy_func cpyfnc, void *data)
 Creates an element-wise copy of a list. More...
 
UcxListucx_list_clone_a (UcxAllocator *allocator, UcxList *list, copy_func cpyfnc, void *data)
 Creates an element-wise copy of a list using a UcxAllocator. More...
 
int ucx_list_equals (const UcxList *list1, const UcxList *list2, cmp_func cmpfnc, void *data)
 Compares two UCX lists element-wise by using a compare function. More...
 
void ucx_list_free (UcxList *list)
 Destroys the entire list. More...
 
void ucx_list_free_a (UcxAllocator *allocator, UcxList *list)
 Destroys the entire list using a UcxAllocator. More...
 
void ucx_list_free_content (UcxList *list, ucx_destructor destr)
 Destroys the contents of the specified list by calling the specified destructor on each of them. More...
 
UcxListucx_list_append (UcxList *list, void *data)
 Inserts an element at the end of the list. More...
 
UcxListucx_list_append_a (UcxAllocator *allocator, UcxList *list, void *data)
 Inserts an element at the end of the list using a UcxAllocator. More...
 
UcxListucx_list_append_once (UcxList *list, void *data, cmp_func cmpfnc, void *cmpdata)
 Inserts an element at the end of the list, if it is not present in the list. More...
 
UcxListucx_list_append_once_a (UcxAllocator *allocator, UcxList *list, void *data, cmp_func cmpfnc, void *cmpdata)
 Inserts an element at the end of the list, if it is not present in the list, using a UcxAllocator. More...
 
UcxListucx_list_prepend (UcxList *list, void *data)
 Inserts an element at the beginning of the list. More...
 
UcxListucx_list_prepend_a (UcxAllocator *allocator, UcxList *list, void *data)
 Inserts an element at the beginning of the list using a UcxAllocator. More...
 
UcxListucx_list_concat (UcxList *list1, UcxList *list2)
 Concatenates two lists. More...
 
UcxListucx_list_first (const UcxList *elem)
 Returns the first element of a list. More...
 
UcxListucx_list_last (const UcxList *elem)
 Returns the last element of a list. More...
 
UcxListucx_list_get (const UcxList *list, size_t index)
 Returns the list element at the specified index. More...
 
ssize_t ucx_list_indexof (const UcxList *list, const UcxList *elem)
 Returns the index of an element. More...
 
size_t ucx_list_size (const UcxList *list)
 Returns the element count of the list. More...
 
ssize_t ucx_list_find (UcxList *list, void *elem, cmp_func cmpfnc, void *data)
 Returns the index of an element containing the specified data. More...
 
int ucx_list_contains (UcxList *list, void *elem, cmp_func cmpfnc, void *data)
 Checks, if a list contains a specific element. More...
 
UcxListucx_list_sort (UcxList *list, cmp_func cmpfnc, void *data)
 Sorts a UcxList with natural merge sort. More...
 
UcxListucx_list_remove (UcxList *list, UcxList *element)
 Removes an element from the list. More...
 
UcxListucx_list_remove_a (UcxAllocator *allocator, UcxList *list, UcxList *element)
 Removes an element from the list using a UcxAllocator. More...
 

Detailed Description

Doubly linked list implementation.

Author
Mike Becker
Olaf Wintermann

Macro Definition Documentation

#define UCX_FOREACH (   elem,
  list 
)    for (UcxList* elem = list ; elem != NULL ; elem = elem->next)

Loop statement for UCX lists.

The first argument is the name of the iteration variable. The scope of this variable is limited to the UCX_FOREACH statement.

The second argument is a pointer to the list. In most cases this will be the pointer to the first element of the list, but it may also be an arbitrary element of the list. The iteration will then start with that element.

Parameters
listThe first element of the list
elemThe variable name of the element

Typedef Documentation

typedef struct UcxList UcxList

UCX list type.

See also
UcxList

Function Documentation

UcxList* ucx_list_append ( UcxList list,
void *  data 
)

Inserts an element at the end of the list.

This is generally an O(n) operation, as the end of the list is retrieved with ucx_list_last().

Parameters
listthe list where to append the data, or NULL to create a new list
datathe data to insert
Returns
list, if it is not NULL or a pointer to the newly created list otherwise
UcxList* ucx_list_append_a ( UcxAllocator allocator,
UcxList list,
void *  data 
)

Inserts an element at the end of the list using a UcxAllocator.

See ucx_list_append() for details.

Parameters
allocatorthe allocator to use
listthe list where to append the data, or NULL to create a new list
datathe data to insert
Returns
list, if it is not NULL or a pointer to the newly created list otherwise
See also
ucx_list_append()
UcxList* ucx_list_append_once ( UcxList list,
void *  data,
cmp_func  cmpfnc,
void *  cmpdata 
)

Inserts an element at the end of the list, if it is not present in the list.

Parameters
listthe list where to append the data, or NULL to create a new list
datathe data to insert
cmpfncthe compare function
cmpdataadditional data for the compare function
Returns
list, if it is not NULL or a pointer to the newly created list otherwise
See also
ucx_list_append()
UcxList* ucx_list_append_once_a ( UcxAllocator allocator,
UcxList list,
void *  data,
cmp_func  cmpfnc,
void *  cmpdata 
)

Inserts an element at the end of the list, if it is not present in the list, using a UcxAllocator.

See ucx_list_append() for details.

Parameters
allocatorthe allocator to use
listthe list where to append the data, or NULL to create a new list
datathe data to insert
cmpfncthe compare function
cmpdataadditional data for the compare function
Returns
list, if it is not NULL or a pointer to the newly created list otherwise
See also
ucx_list_append_a()
UcxList* ucx_list_clone ( UcxList list,
copy_func  cpyfnc,
void *  data 
)

Creates an element-wise copy of a list.

This function clones the specified list by creating new list elements and copying the data with the specified copy_func(). If no copy_func() is specified, a shallow copy is created and the new list will reference the same data as the source list.

Parameters
listthe list to copy
cpyfnca pointer to the function that shall copy an element (may be NULL)
dataadditional data for the copy_func()
Returns
a pointer to the copy
UcxList* ucx_list_clone_a ( UcxAllocator allocator,
UcxList list,
copy_func  cpyfnc,
void *  data 
)

Creates an element-wise copy of a list using a UcxAllocator.

See ucx_list_clone() for details.

You might want to pass the allocator via the data parameter, to access it within the copy function for making deep copies.

Parameters
allocatorthe allocator to use
listthe list to copy
cpyfnca pointer to the function that shall copy an element (may be NULL)
dataadditional data for the copy_func()
Returns
a pointer to the copy
See also
ucx_list_clone()
UcxList* ucx_list_concat ( UcxList list1,
UcxList list2 
)

Concatenates two lists.

Either of the two arguments may be NULL.

This function modifies the references to the next/previous element of the last/first element of list1/ list2.

Parameters
list1first list
list2second list
Returns
if list1 is NULL, list2 is returned, otherwise list1 is returned
int ucx_list_contains ( UcxList list,
void *  elem,
cmp_func  cmpfnc,
void *  data 
)

Checks, if a list contains a specific element.

An element is found, if ucx_list_find() returns a value greater than -1.

Parameters
listthe list where to search for the data
elemthe element data
cmpfncthe compare function
dataadditional data for the compare function
Returns
1, if and only if the list contains the specified element data
See also
ucx_list_find()
int ucx_list_equals ( const UcxList list1,
const UcxList list2,
cmp_func  cmpfnc,
void *  data 
)

Compares two UCX lists element-wise by using a compare function.

Each element of the two specified lists are compared by using the specified compare function and the additional data. The type and content of this additional data depends on the cmp_func() used.

If the list pointers denote elements within a list, the lists are compared starting with the denoted elements. Thus any previous elements are not taken into account. This might be useful to check, if certain list tails match each other.

Parameters
list1the first list
list2the second list
cmpfncthe compare function
dataadditional data for the compare function
Returns
1, if and only if the two lists equal element-wise, 0 otherwise
ssize_t ucx_list_find ( UcxList list,
void *  elem,
cmp_func  cmpfnc,
void *  data 
)

Returns the index of an element containing the specified data.

This function uses a cmp_func() to compare the data of each list element with the specified data. If no cmp_func is provided, the pointers are compared.

If the list contains the data more than once, the index of the first occurrence is returned.

Parameters
listthe list where to search for the data
elemthe element data
cmpfncthe compare function
dataadditional data for the compare function
Returns
the index of the element containing the specified data or -1 if the data is not found in this list
UcxList* ucx_list_first ( const UcxList elem)

Returns the first element of a list.

If the argument is the list pointer, it is directly returned. Otherwise this function traverses to the first element of the list and returns the list pointer.

Parameters
elemone element of the list
Returns
the first element of the list, the specified element is a member of
void ucx_list_free ( UcxList list)

Destroys the entire list.

The members of the list are not automatically freed, so ensure they are otherwise referenced or destroyed by ucx_list_free_contents(). Otherwise, a memory leak is likely to occur.

Caution: the argument MUST denote an entire list (i.e. a call to ucx_list_first() on the argument must return the argument itself)

Parameters
listthe list to free
See also
ucx_list_free_contents()
void ucx_list_free_a ( UcxAllocator allocator,
UcxList list 
)

Destroys the entire list using a UcxAllocator.

See ucx_list_free() for details.

Parameters
allocatorthe allocator to use
listthe list to free
See also
ucx_list_free()
void ucx_list_free_content ( UcxList list,
ucx_destructor  destr 
)

Destroys the contents of the specified list by calling the specified destructor on each of them.

Note, that the contents are not usable afterwards and the list should be destroyed with ucx_list_free().

Parameters
listthe list for which the contents shall be freed
destrthe destructor function (e.g. stdlib free())
See also
ucx_list_free()
UcxList* ucx_list_get ( const UcxList list,
size_t  index 
)

Returns the list element at the specified index.

Parameters
listthe list to retrieve the element from
indexindex of the element to return
Returns
the element at the specified index or NULL, if the index is greater than the list size
ssize_t ucx_list_indexof ( const UcxList list,
const UcxList elem 
)

Returns the index of an element.

Parameters
listthe list where to search for the element
elemthe element to find
Returns
the index of the element or -1 if the list does not contain the element
UcxList* ucx_list_last ( const UcxList elem)

Returns the last element of a list.

If the argument has no successor, it is the last element and therefore directly returned. Otherwise this function traverses to the last element of the list and returns it.

Parameters
elemone element of the list
Returns
the last element of the list, the specified element is a member of
UcxList* ucx_list_prepend ( UcxList list,
void *  data 
)

Inserts an element at the beginning of the list.

You should overwrite the old list pointer by calling mylist = ucx_list_prepend(mylist, mydata);. However, you may also perform successive calls of ucx_list_prepend() on the same list pointer, as this function always searchs for the head of the list with ucx_list_first().

Parameters
listthe list where to insert the data or NULL to create a new list
datathe data to insert
Returns
a pointer to the new list head
UcxList* ucx_list_prepend_a ( UcxAllocator allocator,
UcxList list,
void *  data 
)

Inserts an element at the beginning of the list using a UcxAllocator.

See ucx_list_prepend() for details.

Parameters
allocatorthe allocator to use
listthe list where to insert the data or NULL to create a new list
datathe data to insert
Returns
a pointer to the new list head
See also
ucx_list_prepend()
UcxList* ucx_list_remove ( UcxList list,
UcxList element 
)

Removes an element from the list.

If the first element is removed, the list pointer changes. So it is highly recommended to always update the pointer by calling mylist = ucx_list_remove(mylist, myelem);.

Parameters
listthe list from which the element shall be removed
elementthe element to remove
Returns
returns the updated list pointer or NULL, if the list is now empty
UcxList* ucx_list_remove_a ( UcxAllocator allocator,
UcxList list,
UcxList element 
)

Removes an element from the list using a UcxAllocator.

See ucx_list_remove() for details.

Parameters
allocatorthe allocator to use
listthe list from which the element shall be removed
elementthe element to remove
Returns
returns the updated list pointer or NULL, if the list
See also
ucx_list_remove()
size_t ucx_list_size ( const UcxList list)

Returns the element count of the list.

Parameters
listthe list whose elements are counted
Returns
the element count
UcxList* ucx_list_sort ( UcxList list,
cmp_func  cmpfnc,
void *  data 
)

Sorts a UcxList with natural merge sort.

This function uses O(n) additional temporary memory for merge operations that is automatically freed after each merge.

As the head of the list might change, you MUST call this function as follows: mylist = ucx_list_sort(mylist, mycmpfnc, mydata);.

Parameters
listthe list to sort
cmpfncthe function that shall be used to compare the element data
dataadditional data for the cmp_func()
Returns
the sorted list