# HG changeset patch # User Mike Becker # Date 1374583425 -7200 # Node ID b79b1ce438ddc2256f8eb3c1a60e20a78694c9a5 # Parent 5418bda2189686f7d44a453fbfad314e1b5cc170 finished documentation of UcxList diff -r 5418bda21896 -r b79b1ce438dd ucx/list.c --- a/ucx/list.c Tue Jul 23 12:54:45 2013 +0200 +++ b/ucx/list.c Tue Jul 23 14:43:45 2013 +0200 @@ -118,13 +118,13 @@ } UcxList *ucx_list_concat(UcxList *l1, UcxList *l2) { - if (l1 == NULL) { - return l2; - } else { + if (l1) { UcxList *last = ucx_list_last(l1); last->next = l2; l2->prev = last; return l1; + } else { + return l2; } } @@ -154,7 +154,7 @@ if (l == NULL) return NULL; const UcxList *e = l; - while (e->next != NULL && index > 0) { + while (e->next && index > 0) { e = e->next; index--; } @@ -165,8 +165,14 @@ ssize_t ucx_list_find(UcxList *l, void *elem, cmp_func fnc, void *cmpdata) { ssize_t index = 0; UCX_FOREACH(e, l) { - if (fnc(elem, e->data, cmpdata) == 0) { - return index; + if (fnc) { + if (fnc(elem, e->data, cmpdata) == 0) { + return index; + } + } else { + if (elem == e->data) { + return index; + } } index++; } diff -r 5418bda21896 -r b79b1ce438dd ucx/list.h --- a/ucx/list.h Tue Jul 23 12:54:45 2013 +0200 +++ b/ucx/list.h Tue Jul 23 14:43:45 2013 +0200 @@ -26,7 +26,7 @@ * POSSIBILITY OF SUCH DAMAGE. */ /** - * Double linked list implementation. + * Doubly linked list implementation. * * @file list.h * @author Mike Becker @@ -81,7 +81,37 @@ UcxList *prev; }; +/** + * 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. + * + * @param list the list to copy + * @param cpyfnc a pointer to the function that shall copy an element (may be + * NULL) + * @param data additional data for the copy_func() + * @return a pointer to the copy + */ UcxList *ucx_list_clone(UcxList *list, copy_func cpyfnc, void* data); +/** + * Creates an element-wise copy of a list using an UcxAllocator. + * + * See ucx_list_clone() for details. + * + * Keep in mind, that you might want to pass the allocator as an (part of the) + * argument for the data parameter, if you want the copy_func() to + * make use of the allocator. + * + * @param list the list to copy + * @param cpyfnc a pointer to the function that shall copy an element (may be + * NULL) + * @param data additional data for the copy_func() + * @return a pointer to the copy + * @see ucx_list_clone() + */ UcxList *ucx_list_clone_a(UcxAllocator *allocator, UcxList *list, copy_func cpyfnc, void* data); @@ -115,14 +145,88 @@ * Caution: the argument MUST denote an entire list (i.e. a call * to ucx_list_first() on the argument must return the argument itself) * - * @param list The list to free. + * @param list the list to free */ void ucx_list_free(UcxList *list); +/** + * Destroys the entire list using an UcxAllocator. + * + * See ucx_list_free() for details. + * + * @param allocator the allocator to use + * @param list the list to free + * @see ucx_list_free() + */ void ucx_list_free_a(UcxAllocator *allocator, UcxList *list); +/** + * Inserts an element at the end of the list. + * + * This is generally an O(n) operation, as the end of the list is seeked with + * ucx_list_last(). + * + * @param list the list where to append the data, or NULL to + * create a new list + * @param data the data to insert + * @return list, if it is not NULL or a pointer to + * the newly created list otherwise + */ UcxList *ucx_list_append(UcxList *list, void *data); +/** + * Inserts an element at the end of the list using an UcxAllocator. + * + * See ucx_list_append() for details. + * + * @param allocator the allocator to use + * @param list the list where to append the data, or NULL to + * create a new list + * @param data the data to insert + * @return list, if it is not NULL or a pointer to + * the newly created list otherwise + * @see ucx_list_append() + */ UcxList *ucx_list_append_a(UcxAllocator *allocator, 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(). + * + * @param list the list where to insert the data or NULL to create + * a new list + * @param data the data to insert + * @return a pointer to the new list head + */ UcxList *ucx_list_prepend(UcxList *list, void *data); +/** + * Inserts an element at the beginning of the list using an UcxAllocator. + * + * See ucx_list_prepend() for details. + * + * @param allocator the allocator to use + * @param list the list where to insert the data or NULL to create + * a new list + * @param data the data to insert + * @return a pointer to the new list head + * @see ucx_list_prepend() + */ UcxList *ucx_list_prepend_a(UcxAllocator *allocator, UcxList *list, void *data); +/** + * 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. + * + * @param list1 first list + * @param list2 second list + * @return if list1 is NULL, list2 is + * returned, otherwise list1 is returned + */ UcxList *ucx_list_concat(UcxList *list1, UcxList *list2); /** * Returns the first element of a list. @@ -146,12 +250,77 @@ * @return the last element of the list, the specified element is a member of */ UcxList *ucx_list_last(const UcxList *elem); +/** + * Returns the list element at the specified index. + * + * @param list the list to retrieve the element from + * @param index index of the element to return + * @return the element at the specified index or NULL, if the + * index is greater than the list size + */ UcxList *ucx_list_get(const UcxList *list, int index); +/** + * Returns the index of an element. + * + * @param list the list where to search for the element + * @param elem the element to find + * @return the index of the element or -1 if the list does not contain the + * element + */ ssize_t ucx_list_indexof(const UcxList *list, const UcxList *elem); +/** + * Returns the element count of the list. + * + * @param list the list whose elements are counted + * @return the element count + */ size_t ucx_list_size(const UcxList *list); +/** + * 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. + * + * @param list the list where to search for the data + * @param elem the element data + * @param cmpfnc the compare function + * @param data additional data for the compare function + * @return the index of the element containing the specified data or -1 if the + * data is not found in this list + */ ssize_t ucx_list_find(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. + * + * @param list the list where to search for the data + * @param elem the element data + * @param cmpfnc the compare function + * @param data additional data for the compare function + * @return 1, if and only if the list contains the specified element data + * @see ucx_list_find() + */ int ucx_list_contains(UcxList *list, void *elem, cmp_func cmpfnc, void *data); +/** + * Sorts an 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);. + * + * @param list the list to sort + * @param cmpfnc the function that shall be used to compare the element data + * @param data additional data for the cmp_func() + * @return the sorted list + */ UcxList *ucx_list_sort(UcxList *list, cmp_func cmpfnc, void *data); /** @@ -167,6 +336,17 @@ * is now empty */ UcxList *ucx_list_remove(UcxList *list, UcxList *element); +/** + * Removes an element from the list using an UcxAllocator. + * + * See ucx_list_remove() for details. + * + * @param allocator the allocator to use + * @param list the list from which the element shall be removed + * @param element the element to removed + * @return returns the updated list pointer or NULL, if the list + * @see ucx_list_remove() + */ UcxList *ucx_list_remove_a(UcxAllocator *allocator, UcxList *list, UcxList *element); diff -r 5418bda21896 -r b79b1ce438dd ucx/test.h --- a/ucx/test.h Tue Jul 23 12:54:45 2013 +0200 +++ b/ucx/test.h Tue Jul 23 14:43:45 2013 +0200 @@ -47,8 +47,6 @@ * PLEASE NOTE: if a test fails, a longjump is performed * back to the UCX_TEST_BEGIN macro! * - * You may use multiple BEGIN-END blocks if you are aware of the - * longjmp behaviour. * */