+
+
+
+
+
+
+
+
+
+
+
+
+ |
+
+ ucx
+
+ UAP Common Extensions
+ |
+
+
+
+
+
+
+
+
+
+ |
+
+ ucx
+
+ UAP Common Extensions
+ |
+
Doubly linked list implementation. +More...
+ +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 = (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... | |
Doubly linked list implementation.
+ +| #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.
+| list | The first element of the list |
| elem | The variable name of the element |
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().
+| list | the list where to append the data, or NULL to create a new list |
| data | the data to insert |
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.
+| 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 |
list, if it is not NULL or a pointer to the newly created list otherwise | 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.
+| 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() |
| 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.
| 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() |
| 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.
| list1 | first list |
| list2 | second list |
list1 is NULL, list2 is returned, otherwise list1 is returned | 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.
+| list | the list where to search for the data |
| elem | the element data |
| cmpfnc | the compare function |
| data | additional data for the compare function |
| 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.
+| 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 |
| 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.
+| 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 |
| 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.
+| list1 | the first list |
| list2 | the second list |
| cmpfnc | the compare function |
| data | additional data for the compare function |
| 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.
+| 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 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.
+| elem | one element of the list |
| 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)
+| list | the list to free |
| void ucx_list_free_a | +( | +UcxAllocator * | +allocator, | +
| + | + | UcxList * | +list | +
| + | ) | ++ |
Destroys the entire list using a UcxAllocator.
+See ucx_list_free() for details.
+| allocator | the allocator to use |
| list | the list to 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().
+If no destructor is specified (NULL), stdlib's free() is used.
| list | the list for which the contents shall be freed |
| destr | optional destructor function |
| UcxList* ucx_list_get | +( | +const UcxList * | +list, | +
| + | + | size_t | +index | +
| + | ) | ++ |
Returns the list element at the specified index.
+| list | the list to retrieve the element from |
| index | index of the element to return |
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.
+| list | the list where to search for the element |
| elem | the element to find |
| 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.
+| 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 |
| 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.
+| 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 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.
+| elem | one element of the list |
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().
| list | the list where to insert the data or NULL to create a new list |
| data | the data to insert |
| 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.
+| 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 |
| 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);.
| list | the list from which the element shall be removed |
| element | the element to remove |
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.
+| allocator | the allocator to use |
| list | the list from which the element shall be removed |
| element | the element to remove |
NULL, if the list | size_t ucx_list_size | +( | +const UcxList * | +list | ) | ++ |
Returns the element count of the list.
+| list | the list whose elements are counted |
| 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);.
| list | the list to sort |
| cmpfnc | the function that shall be used to compare the element data |
| data | additional data for the cmp_func() |
| 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.
+| 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 |
| 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.
+| 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 |
+ 1.8.13
+
+
+