1.1 --- a/ucx/list.h Tue Jul 23 12:54:45 2013 +0200 1.2 +++ b/ucx/list.h Tue Jul 23 14:43:45 2013 +0200 1.3 @@ -26,7 +26,7 @@ 1.4 * POSSIBILITY OF SUCH DAMAGE. 1.5 */ 1.6 /** 1.7 - * Double linked list implementation. 1.8 + * Doubly linked list implementation. 1.9 * 1.10 * @file list.h 1.11 * @author Mike Becker 1.12 @@ -81,7 +81,37 @@ 1.13 UcxList *prev; 1.14 }; 1.15 1.16 +/** 1.17 + * Creates an element-wise copy of a list. 1.18 + * 1.19 + * This function clones the specified list by creating new list elements and 1.20 + * copying the data with the specified copy_func(). If no copy_func() is 1.21 + * specified, a shallow copy is created and the new list will reference the 1.22 + * same data as the source list. 1.23 + * 1.24 + * @param list the list to copy 1.25 + * @param cpyfnc a pointer to the function that shall copy an element (may be 1.26 + * <code>NULL</code>) 1.27 + * @param data additional data for the copy_func() 1.28 + * @return a pointer to the copy 1.29 + */ 1.30 UcxList *ucx_list_clone(UcxList *list, copy_func cpyfnc, void* data); 1.31 +/** 1.32 + * Creates an element-wise copy of a list using an UcxAllocator. 1.33 + * 1.34 + * See ucx_list_clone() for details. 1.35 + * 1.36 + * Keep in mind, that you might want to pass the allocator as an (part of the) 1.37 + * argument for the <code>data</code> parameter, if you want the copy_func() to 1.38 + * make use of the allocator. 1.39 + * 1.40 + * @param list the list to copy 1.41 + * @param cpyfnc a pointer to the function that shall copy an element (may be 1.42 + * <code>NULL</code>) 1.43 + * @param data additional data for the copy_func() 1.44 + * @return a pointer to the copy 1.45 + * @see ucx_list_clone() 1.46 + */ 1.47 UcxList *ucx_list_clone_a(UcxAllocator *allocator, UcxList *list, 1.48 copy_func cpyfnc, void* data); 1.49 1.50 @@ -115,14 +145,88 @@ 1.51 * <b>Caution:</b> the argument <b>MUST</b> denote an entire list (i.e. a call 1.52 * to ucx_list_first() on the argument must return the argument itself) 1.53 * 1.54 - * @param list The list to free. 1.55 + * @param list the list to free 1.56 */ 1.57 void ucx_list_free(UcxList *list); 1.58 +/** 1.59 + * Destroys the entire list using an UcxAllocator. 1.60 + * 1.61 + * See ucx_list_free() for details. 1.62 + * 1.63 + * @param allocator the allocator to use 1.64 + * @param list the list to free 1.65 + * @see ucx_list_free() 1.66 + */ 1.67 void ucx_list_free_a(UcxAllocator *allocator, UcxList *list); 1.68 +/** 1.69 + * Inserts an element at the end of the list. 1.70 + * 1.71 + * This is generally an O(n) operation, as the end of the list is seeked with 1.72 + * ucx_list_last(). 1.73 + * 1.74 + * @param list the list where to append the data, or <code>NULL</code> to 1.75 + * create a new list 1.76 + * @param data the data to insert 1.77 + * @return <code>list</code>, if it is not <code>NULL</code> or a pointer to 1.78 + * the newly created list otherwise 1.79 + */ 1.80 UcxList *ucx_list_append(UcxList *list, void *data); 1.81 +/** 1.82 + * Inserts an element at the end of the list using an UcxAllocator. 1.83 + * 1.84 + * See ucx_list_append() for details. 1.85 + * 1.86 + * @param allocator the allocator to use 1.87 + * @param list the list where to append the data, or <code>NULL</code> to 1.88 + * create a new list 1.89 + * @param data the data to insert 1.90 + * @return <code>list</code>, if it is not <code>NULL</code> or a pointer to 1.91 + * the newly created list otherwise 1.92 + * @see ucx_list_append() 1.93 + */ 1.94 UcxList *ucx_list_append_a(UcxAllocator *allocator, UcxList *list, void *data); 1.95 +/** 1.96 + * Inserts an element at the beginning of the list. 1.97 + * 1.98 + * You <i>should</i> overwrite the old list pointer by calling 1.99 + * <code>mylist = ucx_list_prepend(mylist, mydata);</code>. However, you may 1.100 + * also perform successive calls of ucx_list_prepend() on the same list pointer, 1.101 + * as this function always searchs for the head of the list with 1.102 + * ucx_list_first(). 1.103 + * 1.104 + * @param list the list where to insert the data or <code>NULL</code> to create 1.105 + * a new list 1.106 + * @param data the data to insert 1.107 + * @return a pointer to the new list head 1.108 + */ 1.109 UcxList *ucx_list_prepend(UcxList *list, void *data); 1.110 +/** 1.111 + * Inserts an element at the beginning of the list using an UcxAllocator. 1.112 + * 1.113 + * See ucx_list_prepend() for details. 1.114 + * 1.115 + * @param allocator the allocator to use 1.116 + * @param list the list where to insert the data or <code>NULL</code> to create 1.117 + * a new list 1.118 + * @param data the data to insert 1.119 + * @return a pointer to the new list head 1.120 + * @see ucx_list_prepend() 1.121 + */ 1.122 UcxList *ucx_list_prepend_a(UcxAllocator *allocator, UcxList *list, void *data); 1.123 +/** 1.124 + * Concatenates two lists. 1.125 + * 1.126 + * Either of the two arguments may be <code>NULL</code>. 1.127 + * 1.128 + * This function modifies the references to the next/previous element of 1.129 + * the last/first element of <code>list1</code>/<code> 1.130 + * list2</code>. 1.131 + * 1.132 + * @param list1 first list 1.133 + * @param list2 second list 1.134 + * @return if <code>list1</code> is <code>NULL</code>, <code>list2</code> is 1.135 + * returned, otherwise <code>list1</code> is returned 1.136 + */ 1.137 UcxList *ucx_list_concat(UcxList *list1, UcxList *list2); 1.138 /** 1.139 * Returns the first element of a list. 1.140 @@ -146,12 +250,77 @@ 1.141 * @return the last element of the list, the specified element is a member of 1.142 */ 1.143 UcxList *ucx_list_last(const UcxList *elem); 1.144 +/** 1.145 + * Returns the list element at the specified index. 1.146 + * 1.147 + * @param list the list to retrieve the element from 1.148 + * @param index index of the element to return 1.149 + * @return the element at the specified index or <code>NULL</code>, if the 1.150 + * index is greater than the list size 1.151 + */ 1.152 UcxList *ucx_list_get(const UcxList *list, int index); 1.153 +/** 1.154 + * Returns the index of an element. 1.155 + * 1.156 + * @param list the list where to search for the element 1.157 + * @param elem the element to find 1.158 + * @return the index of the element or -1 if the list does not contain the 1.159 + * element 1.160 + */ 1.161 ssize_t ucx_list_indexof(const UcxList *list, const UcxList *elem); 1.162 +/** 1.163 + * Returns the element count of the list. 1.164 + * 1.165 + * @param list the list whose elements are counted 1.166 + * @return the element count 1.167 + */ 1.168 size_t ucx_list_size(const UcxList *list); 1.169 +/** 1.170 + * Returns the index of an element containing the specified data. 1.171 + * 1.172 + * This function uses a cmp_func() to compare the data of each list element 1.173 + * with the specified data. If no cmp_func is provided, the pointers are 1.174 + * compared. 1.175 + * 1.176 + * If the list contains the data more than once, the index of the first 1.177 + * occurrence is returned. 1.178 + * 1.179 + * @param list the list where to search for the data 1.180 + * @param elem the element data 1.181 + * @param cmpfnc the compare function 1.182 + * @param data additional data for the compare function 1.183 + * @return the index of the element containing the specified data or -1 if the 1.184 + * data is not found in this list 1.185 + */ 1.186 ssize_t ucx_list_find(UcxList *list, void *elem, cmp_func cmpfnc, void *data); 1.187 +/** 1.188 + * Checks, if a list contains a specific element. 1.189 + * 1.190 + * An element is found, if ucx_list_find() returns a value greater than -1. 1.191 + * 1.192 + * @param list the list where to search for the data 1.193 + * @param elem the element data 1.194 + * @param cmpfnc the compare function 1.195 + * @param data additional data for the compare function 1.196 + * @return 1, if and only if the list contains the specified element data 1.197 + * @see ucx_list_find() 1.198 + */ 1.199 int ucx_list_contains(UcxList *list, void *elem, cmp_func cmpfnc, void *data); 1.200 1.201 +/** 1.202 + * Sorts an UcxList with natural merge sort. 1.203 + * 1.204 + * This function uses O(n) additional temporary memory for merge operations 1.205 + * that is automatically freed after each merge. 1.206 + * 1.207 + * As the head of the list might change, you <b>MUST</b> call this function 1.208 + * as follows: <code>mylist = ucx_list_sort(mylist, mycmpfnc, mydata);</code>. 1.209 + * 1.210 + * @param list the list to sort 1.211 + * @param cmpfnc the function that shall be used to compare the element data 1.212 + * @param data additional data for the cmp_func() 1.213 + * @return the sorted list 1.214 + */ 1.215 UcxList *ucx_list_sort(UcxList *list, cmp_func cmpfnc, void *data); 1.216 1.217 /** 1.218 @@ -167,6 +336,17 @@ 1.219 * is now empty 1.220 */ 1.221 UcxList *ucx_list_remove(UcxList *list, UcxList *element); 1.222 +/** 1.223 + * Removes an element from the list using an UcxAllocator. 1.224 + * 1.225 + * See ucx_list_remove() for details. 1.226 + * 1.227 + * @param allocator the allocator to use 1.228 + * @param list the list from which the element shall be removed 1.229 + * @param element the element to removed 1.230 + * @return returns the updated list pointer or <code>NULL</code>, if the list 1.231 + * @see ucx_list_remove() 1.232 + */ 1.233 UcxList *ucx_list_remove_a(UcxAllocator *allocator, UcxList *list, 1.234 UcxList *element); 1.235