Doubly linked list implementation. More...

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

Data Structures
struct	UcxList
	UCX list structure. More...

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

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

Functions
UcxList *	ucx_list_clone (const UcxList list, copy_func cpyfnc, void data)
	Creates an element-wise copy of a list. More...

UcxList *	ucx_list_clone_a (UcxAllocator allocator, const 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...

UcxList *	ucx_list_append (UcxList list, void data)
	Inserts an element at the end of the list. More...

UcxList *	ucx_list_append_a (UcxAllocator allocator, UcxList list, void *data)
	Inserts an element at the end of the list using a UcxAllocator. More...

UcxList *	ucx_list_prepend (UcxList list, void data)
	Inserts an element at the beginning of the list. More...

UcxList *	ucx_list_prepend_a (UcxAllocator allocator, UcxList list, void *data)
	Inserts an element at the beginning of the list using a UcxAllocator. More...

UcxList *	ucx_list_concat (UcxList list1, UcxList list2)
	Concatenates two lists. More...

UcxList *	ucx_list_first (const UcxList *elem)
	Returns the first element of a list. More...

UcxList *	ucx_list_last (const UcxList *elem)
	Returns the last element of a list. More...

UcxList *	ucx_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 (const UcxList list, void elem, cmp_func cmpfnc, void *data)
	Returns the index of an element containing the specified data. More...

int	ucx_list_contains (const UcxList list, void elem, cmp_func cmpfnc, void *data)
	Checks, if a list contains a specific element. More...

UcxList *	ucx_list_sort (UcxList list, cmp_func cmpfnc, void data)
	Sorts a UcxList with natural merge sort. More...

UcxList *	ucx_list_remove (UcxList list, UcxList element)
	Removes an element from the list. More...

UcxList *	ucx_list_remove_a (UcxAllocator allocator, UcxList list, UcxList *element)
	Removes an element from the list using a UcxAllocator. More...

UcxList *	ucx_list_union (const UcxList left, const UcxList right, cmp_func cmpfnc, void cmpdata, copy_func cpfnc, void cpdata)
	Returns the union of two lists. More...

UcxList *	ucx_list_union_a (UcxAllocator allocator, const UcxList left, const UcxList right, cmp_func cmpfnc, void cmpdata, copy_func cpfnc, void *cpdata)
	Returns the union of two lists. More...

UcxList *	ucx_list_intersection (const UcxList left, const UcxList right, cmp_func cmpfnc, void cmpdata, copy_func cpfnc, void cpdata)
	Returns the intersection of two lists. More...

UcxList *	ucx_list_intersection_a (UcxAllocator allocator, const UcxList left, const UcxList right, cmp_func cmpfnc, void cmpdata, copy_func cpfnc, void *cpdata)
	Returns the intersection of two lists. More...

UcxList *	ucx_list_difference (const UcxList left, const UcxList right, cmp_func cmpfnc, void cmpdata, copy_func cpfnc, void cpdata)
	Returns the difference of two lists. More...

UcxList *	ucx_list_difference_a (UcxAllocator allocator, const UcxList left, const UcxList right, cmp_func cmpfnc, void cmpdata, copy_func cpfnc, void *cpdata)
	Returns the difference of two lists. More...

Detailed Description

Doubly linked list implementation.

Author: Mike Becker; Olaf Wintermann

Macro Definition Documentation

◆ UCX_FOREACH

#define UCX_FOREACH	(	elem,
		list
	)	for (UcxList* elem = (UcxList*) 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

list	The first element of the list
elem	The variable name of the element

Typedef Documentation

◆ UcxList

typedef struct UcxList UcxList

UCX list type.

See also: UcxList

Function Documentation

◆ ucx_list_append()

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

list	the list where to append the data, or `NULL` to create a new list
data	the data to insert

Returns: list, if it is not NULL or a pointer to the newly created list otherwise

◆ ucx_list_append_a()

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

allocator	the allocator to use
list	the list where to append the data, or `NULL` to create a new list
data	the data to insert

Returns: list, if it is not NULL or a pointer to the newly created list otherwise

See also: ucx_list_append()

◆ ucx_list_clone()

UcxList* ucx_list_clone	(	const 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

list	the list to copy
cpyfnc	a pointer to the function that shall copy an element (may be `NULL`)
data	additional data for the copy_func()

Returns: a pointer to the copy

◆ ucx_list_clone_a()

UcxList* ucx_list_clone_a	(	UcxAllocator *	allocator,
		const 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

allocator	the allocator to use
list	the list to copy
cpyfnc	a pointer to the function that shall copy an element (may be `NULL`)
data	additional data for the copy_func()

Returns: a pointer to the copy

See also: ucx_list_clone()

◆ ucx_list_concat()

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

list1	first list
list2	second list

Returns: if list1 is NULL, list2 is returned, otherwise list1 is returned

◆ ucx_list_contains()

int ucx_list_contains	(	const 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

list	the list where to search for the data
elem	the element data
cmpfnc	the compare function
data	additional data for the compare function

Returns: 1, if and only if the list contains the specified element data

See also: ucx_list_find()

◆ ucx_list_difference()

UcxList* ucx_list_difference	(	const UcxList *	left,
		const UcxList *	right,
		cmp_func	cmpfnc,
		void *	cmpdata,
		copy_func	cpfnc,
		void *	cpdata
	)

Returns the difference of two lists.

The difference contains all elements of the left list (including duplicates) that are not equal to any element of the right list.

Parameters

left	the left source list
right	the right source list
cmpfnc	a function to compare elements
cmpdata	additional data for the compare function
cpfnc	a function to copy the elements
cpdata	additional data for the copy function

Returns: a new list containing the difference

◆ ucx_list_difference_a()

UcxList* ucx_list_difference_a	(	UcxAllocator *	allocator,
		const UcxList *	left,
		const UcxList *	right,
		cmp_func	cmpfnc,
		void *	cmpdata,
		copy_func	cpfnc,
		void *	cpdata
	)

Returns the difference of two lists.

The difference contains all elements of the left list (including duplicates) that are not equal to any element of the right list.

Parameters

allocator	allocates the new list elements
left	the left source list
right	the right source list
cmpfnc	a function to compare elements
cmpdata	additional data for the compare function
cpfnc	a function to copy the elements
cpdata	additional data for the copy function

Returns: a new list containing the difference

◆ ucx_list_equals()

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

list1	the first list
list2	the second list
cmpfnc	the compare function
data	additional data for the compare function

Returns: 1, if and only if the two lists equal element-wise, 0 otherwise

◆ ucx_list_find()

ssize_t ucx_list_find	(	const 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

list	the list where to search for the data
elem	the element data
cmpfnc	the compare function
data	additional 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

◆ ucx_list_first()

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

elem	one element of the list

Returns: the first element of the list, the specified element is a member of

◆ ucx_list_free()

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

list	the list to free

See also: ucx_list_free_contents()

◆ ucx_list_free_a()

void ucx_list_free_a	(	UcxAllocator *	allocator,
		UcxList *	list
	)

Destroys the entire list using a UcxAllocator.

See ucx_list_free() for details.

Parameters

allocator	the allocator to use
list	the list to free

See also: ucx_list_free()

◆ ucx_list_free_content()

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().

If no destructor is specified (NULL), stdlib's free() is used.

Parameters

list	the list for which the contents shall be freed
destr	optional destructor function

See also: ucx_list_free()

◆ ucx_list_get()

UcxList* ucx_list_get	(	const UcxList *	list,
		size_t	index
	)

Returns the list element at the specified index.

Parameters

list	the list to retrieve the element from
index	index of the element to return

Returns: the element at the specified index or NULL, if the index is greater than the list size

◆ ucx_list_indexof()

ssize_t ucx_list_indexof	(	const UcxList *	list,
		const UcxList *	elem
	)

Returns the index of an element.

Parameters

list	the list where to search for the element
elem	the element to find

Returns: the index of the element or -1 if the list does not contain the element

◆ ucx_list_intersection()

UcxList* ucx_list_intersection	(	const UcxList *	left,
		const UcxList *	right,
		cmp_func	cmpfnc,
		void *	cmpdata,
		copy_func	cpfnc,
		void *	cpdata
	)

Returns the intersection of two lists.

The intersection contains all elements of the left list (including duplicates) that can be found in the right list.

Parameters

left	the left source list
right	the right source list
cmpfnc	a function to compare elements
cmpdata	additional data for the compare function
cpfnc	a function to copy the elements
cpdata	additional data for the copy function

Returns: a new list containing the intersection

◆ ucx_list_intersection_a()

UcxList* ucx_list_intersection_a	(	UcxAllocator *	allocator,
		const UcxList *	left,
		const UcxList *	right,
		cmp_func	cmpfnc,
		void *	cmpdata,
		copy_func	cpfnc,
		void *	cpdata
	)

Returns the intersection of two lists.

The intersection contains all elements of the left list (including duplicates) that can be found in the right list.

Parameters

allocator	allocates the new list elements
left	the left source list
right	the right source list
cmpfnc	a function to compare elements
cmpdata	additional data for the compare function
cpfnc	a function to copy the elements
cpdata	additional data for the copy function

Returns: a new list containing the intersection

◆ ucx_list_last()

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

elem	one element of the list

Returns: the last element of the list, the specified element is a member of

◆ ucx_list_prepend()

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

list	the list where to insert the data or `NULL` to create a new list
data	the data to insert

Returns: a pointer to the new list head

◆ ucx_list_prepend_a()

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

allocator	the allocator to use
list	the list where to insert the data or `NULL` to create a new list
data	the data to insert

Returns: a pointer to the new list head

See also: ucx_list_prepend()

◆ ucx_list_remove()

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

list	the list from which the element shall be removed
element	the element to remove

Returns: returns the updated list pointer or NULL, if the list is now empty

◆ ucx_list_remove_a()

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

allocator	the allocator to use
list	the list from which the element shall be removed
element	the element to remove

Returns: returns the updated list pointer or NULL, if the list

See also: ucx_list_remove()

◆ ucx_list_size()

size_t ucx_list_size ( const UcxList * list )

Returns the element count of the list.

Parameters

list	the list whose elements are counted

Returns: the element count

◆ ucx_list_sort()

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

list	the list to sort
cmpfnc	the function that shall be used to compare the element data
data	additional data for the cmp_func()

Returns: the sorted list

◆ ucx_list_union()

UcxList* ucx_list_union	(	const UcxList *	left,
		const UcxList *	right,
		cmp_func	cmpfnc,
		void *	cmpdata,
		copy_func	cpfnc,
		void *	cpdata
	)

Returns the union of two lists.

The union is a list of unique elements regarding cmpfnc obtained from both source lists.

Parameters

left	the left source list
right	the right source list
cmpfnc	a function to compare elements
cmpdata	additional data for the compare function
cpfnc	a function to copy the elements
cpdata	additional data for the copy function

Returns: a new list containing the union

◆ ucx_list_union_a()

UcxList* ucx_list_union_a	(	UcxAllocator *	allocator,
		const UcxList *	left,
		const UcxList *	right,
		cmp_func	cmpfnc,
		void *	cmpdata,
		copy_func	cpfnc,
		void *	cpdata
	)

Returns the union of two lists.

The union is a list of unique elements regarding cmpfnc obtained from both source lists.

Parameters

allocator	allocates the new list elements
left	the left source list
right	the right source list
cmpfnc	a function to compare elements
cmpdata	additional data for the compare function
cpfnc	a function to copy the elements
cpdata	additional data for the copy function

Returns: a new list containing the union

Data Structures

Macros

Typedefs

Functions

Detailed Description

Macro Definition Documentation

◆ UCX_FOREACH

Typedef Documentation

◆ UcxList

Function Documentation

◆ ucx_list_append()

◆ ucx_list_append_a()

◆ ucx_list_clone()

◆ ucx_list_clone_a()

◆ ucx_list_concat()

◆ ucx_list_contains()

◆ ucx_list_difference()

◆ ucx_list_difference_a()

◆ ucx_list_equals()

◆ ucx_list_find()

◆ ucx_list_first()

◆ ucx_list_free()

◆ ucx_list_free_a()

◆ ucx_list_free_content()

◆ ucx_list_get()

◆ ucx_list_indexof()

◆ ucx_list_intersection()

◆ ucx_list_intersection_a()

◆ ucx_list_last()

◆ ucx_list_prepend()

◆ ucx_list_prepend_a()

◆ ucx_list_remove()

◆ ucx_list_remove_a()

◆ ucx_list_size()

◆ ucx_list_sort()

◆ ucx_list_union()

◆ ucx_list_union_a()