1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/src/ucx/list.h Tue Oct 17 16:15:41 2017 +0200 1.3 @@ -0,0 +1,428 @@ 1.4 +/* 1.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. 1.6 + * 1.7 + * Copyright 2017 Olaf Wintermann. All rights reserved. 1.8 + * 1.9 + * Redistribution and use in source and binary forms, with or without 1.10 + * modification, are permitted provided that the following conditions are met: 1.11 + * 1.12 + * 1. Redistributions of source code must retain the above copyright 1.13 + * notice, this list of conditions and the following disclaimer. 1.14 + * 1.15 + * 2. Redistributions in binary form must reproduce the above copyright 1.16 + * notice, this list of conditions and the following disclaimer in the 1.17 + * documentation and/or other materials provided with the distribution. 1.18 + * 1.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 1.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 1.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 1.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE 1.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 1.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 1.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 1.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 1.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 1.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 1.29 + * POSSIBILITY OF SUCH DAMAGE. 1.30 + */ 1.31 +/** 1.32 + * Doubly linked list implementation. 1.33 + * 1.34 + * @file list.h 1.35 + * @author Mike Becker 1.36 + * @author Olaf Wintermann 1.37 + */ 1.38 + 1.39 +#ifndef UCX_LIST_H 1.40 +#define UCX_LIST_H 1.41 + 1.42 +#include <ucx/ucx.h> 1.43 +#include <ucx/allocator.h> 1.44 + 1.45 +#ifdef __cplusplus 1.46 +extern "C" { 1.47 +#endif 1.48 + 1.49 +/** 1.50 + * Loop statement for UCX lists. 1.51 + * 1.52 + * The first argument is the name of the iteration variable. The scope of 1.53 + * this variable is limited to the <code>UCX_FOREACH</code> statement. 1.54 + * 1.55 + * The second argument is a pointer to the list. In most cases this will be the 1.56 + * pointer to the first element of the list, but it may also be an arbitrary 1.57 + * element of the list. The iteration will then start with that element. 1.58 + * 1.59 + * @param list The first element of the list 1.60 + * @param elem The variable name of the element 1.61 + */ 1.62 +#define UCX_FOREACH(elem,list) \ 1.63 + for (UcxList* elem = list ; elem != NULL ; elem = elem->next) 1.64 + 1.65 +/** 1.66 + * UCX list type. 1.67 + * @see UcxList 1.68 + */ 1.69 +typedef struct UcxList UcxList; 1.70 + 1.71 +/** 1.72 + * UCX list structure. 1.73 + */ 1.74 +struct UcxList { 1.75 + /** 1.76 + * List element payload. 1.77 + */ 1.78 + void *data; 1.79 + /** 1.80 + * Pointer to the next list element or <code>NULL</code>, if this is the 1.81 + * last element. 1.82 + */ 1.83 + UcxList *next; 1.84 + /** 1.85 + * Pointer to the previous list element or <code>NULL</code>, if this is 1.86 + * the first element. 1.87 + */ 1.88 + UcxList *prev; 1.89 +}; 1.90 + 1.91 +/** 1.92 + * Creates an element-wise copy of a list. 1.93 + * 1.94 + * This function clones the specified list by creating new list elements and 1.95 + * copying the data with the specified copy_func(). If no copy_func() is 1.96 + * specified, a shallow copy is created and the new list will reference the 1.97 + * same data as the source list. 1.98 + * 1.99 + * @param list the list to copy 1.100 + * @param cpyfnc a pointer to the function that shall copy an element (may be 1.101 + * <code>NULL</code>) 1.102 + * @param data additional data for the copy_func() 1.103 + * @return a pointer to the copy 1.104 + */ 1.105 +UcxList *ucx_list_clone(UcxList *list, copy_func cpyfnc, void* data); 1.106 + 1.107 +/** 1.108 + * Creates an element-wise copy of a list using a UcxAllocator. 1.109 + * 1.110 + * See ucx_list_clone() for details. 1.111 + * 1.112 + * You might want to pass the allocator via the <code>data</code> parameter, 1.113 + * to access it within the copy function for making deep copies. 1.114 + * 1.115 + * @param allocator the allocator to use 1.116 + * @param list the list to copy 1.117 + * @param cpyfnc a pointer to the function that shall copy an element (may be 1.118 + * <code>NULL</code>) 1.119 + * @param data additional data for the copy_func() 1.120 + * @return a pointer to the copy 1.121 + * @see ucx_list_clone() 1.122 + */ 1.123 +UcxList *ucx_list_clone_a(UcxAllocator *allocator, UcxList *list, 1.124 + copy_func cpyfnc, void* data); 1.125 + 1.126 +/** 1.127 + * Compares two UCX lists element-wise by using a compare function. 1.128 + * 1.129 + * Each element of the two specified lists are compared by using the specified 1.130 + * compare function and the additional data. The type and content of this 1.131 + * additional data depends on the cmp_func() used. 1.132 + * 1.133 + * If the list pointers denote elements within a list, the lists are compared 1.134 + * starting with the denoted elements. Thus any previous elements are not taken 1.135 + * into account. This might be useful to check, if certain list tails match 1.136 + * each other. 1.137 + * 1.138 + * @param list1 the first list 1.139 + * @param list2 the second list 1.140 + * @param cmpfnc the compare function 1.141 + * @param data additional data for the compare function 1.142 + * @return 1, if and only if the two lists equal element-wise, 0 otherwise 1.143 + */ 1.144 +int ucx_list_equals(const UcxList *list1, const UcxList *list2, 1.145 + cmp_func cmpfnc, void* data); 1.146 + 1.147 +/** 1.148 + * Destroys the entire list. 1.149 + * 1.150 + * The members of the list are not automatically freed, so ensure they are 1.151 + * otherwise referenced or destroyed by ucx_list_free_contents(). 1.152 + * Otherwise, a memory leak is likely to occur. 1.153 + * 1.154 + * <b>Caution:</b> the argument <b>MUST</b> denote an entire list (i.e. a call 1.155 + * to ucx_list_first() on the argument must return the argument itself) 1.156 + * 1.157 + * @param list the list to free 1.158 + * @see ucx_list_free_contents() 1.159 + */ 1.160 +void ucx_list_free(UcxList *list); 1.161 + 1.162 +/** 1.163 + * Destroys the entire list using a UcxAllocator. 1.164 + * 1.165 + * See ucx_list_free() for details. 1.166 + * 1.167 + * @param allocator the allocator to use 1.168 + * @param list the list to free 1.169 + * @see ucx_list_free() 1.170 + */ 1.171 +void ucx_list_free_a(UcxAllocator *allocator, UcxList *list); 1.172 + 1.173 +/** 1.174 + * Destroys the contents of the specified list by calling the specified 1.175 + * destructor on each of them. 1.176 + * 1.177 + * Note, that the contents are not usable afterwards and the list should be 1.178 + * destroyed with ucx_list_free(). 1.179 + * 1.180 + * @param list the list for which the contents shall be freed 1.181 + * @param destr the destructor function (e.g. stdlib free()) 1.182 + * @see ucx_list_free() 1.183 + */ 1.184 +void ucx_list_free_content(UcxList* list, ucx_destructor destr); 1.185 + 1.186 + 1.187 +/** 1.188 + * Inserts an element at the end of the list. 1.189 + * 1.190 + * This is generally an O(n) operation, as the end of the list is retrieved with 1.191 + * ucx_list_last(). 1.192 + * 1.193 + * @param list the list where to append the data, or <code>NULL</code> to 1.194 + * create a new list 1.195 + * @param data the data to insert 1.196 + * @return <code>list</code>, if it is not <code>NULL</code> or a pointer to 1.197 + * the newly created list otherwise 1.198 + */ 1.199 +UcxList *ucx_list_append(UcxList *list, void *data); 1.200 + 1.201 +/** 1.202 + * Inserts an element at the end of the list using a UcxAllocator. 1.203 + * 1.204 + * See ucx_list_append() for details. 1.205 + * 1.206 + * @param allocator the allocator to use 1.207 + * @param list the list where to append the data, or <code>NULL</code> to 1.208 + * create a new list 1.209 + * @param data the data to insert 1.210 + * @return <code>list</code>, if it is not <code>NULL</code> or a pointer to 1.211 + * the newly created list otherwise 1.212 + * @see ucx_list_append() 1.213 + */ 1.214 +UcxList *ucx_list_append_a(UcxAllocator *allocator, UcxList *list, void *data); 1.215 + 1.216 +/** 1.217 + * Inserts an element at the end of the list, if it is not present in the list. 1.218 + * 1.219 + * 1.220 + * @param list the list where to append the data, or <code>NULL</code> to 1.221 + * create a new list 1.222 + * @param data the data to insert 1.223 + * @param cmpfnc the compare function 1.224 + * @param cmpdata additional data for the compare function 1.225 + * @return <code>list</code>, if it is not <code>NULL</code> or a pointer to 1.226 + * the newly created list otherwise 1.227 + * @see ucx_list_append() 1.228 + */ 1.229 +UcxList *ucx_list_append_once(UcxList *list, void *data, 1.230 + cmp_func cmpfnc, void *cmpdata); 1.231 + 1.232 +/** 1.233 + * Inserts an element at the end of the list, if it is not present in the list, 1.234 + * using a UcxAllocator. 1.235 + * 1.236 + * See ucx_list_append() for details. 1.237 + * 1.238 + * @param allocator the allocator to use 1.239 + * @param list the list where to append the data, or <code>NULL</code> to 1.240 + * create a new list 1.241 + * @param data the data to insert 1.242 + * @param cmpfnc the compare function 1.243 + * @param cmpdata additional data for the compare function 1.244 + * @return <code>list</code>, if it is not <code>NULL</code> or a pointer to 1.245 + * the newly created list otherwise 1.246 + * @see ucx_list_append_a() 1.247 + */ 1.248 +UcxList *ucx_list_append_once_a(UcxAllocator *allocator, 1.249 + UcxList *list, void *data, cmp_func cmpfnc, void *cmpdata); 1.250 + 1.251 +/** 1.252 + * Inserts an element at the beginning of the list. 1.253 + * 1.254 + * You <i>should</i> overwrite the old list pointer by calling 1.255 + * <code>mylist = ucx_list_prepend(mylist, mydata);</code>. However, you may 1.256 + * also perform successive calls of ucx_list_prepend() on the same list pointer, 1.257 + * as this function always searchs for the head of the list with 1.258 + * ucx_list_first(). 1.259 + * 1.260 + * @param list the list where to insert the data or <code>NULL</code> to create 1.261 + * a new list 1.262 + * @param data the data to insert 1.263 + * @return a pointer to the new list head 1.264 + */ 1.265 +UcxList *ucx_list_prepend(UcxList *list, void *data); 1.266 + 1.267 +/** 1.268 + * Inserts an element at the beginning of the list using a UcxAllocator. 1.269 + * 1.270 + * See ucx_list_prepend() for details. 1.271 + * 1.272 + * @param allocator the allocator to use 1.273 + * @param list the list where to insert the data or <code>NULL</code> to create 1.274 + * a new list 1.275 + * @param data the data to insert 1.276 + * @return a pointer to the new list head 1.277 + * @see ucx_list_prepend() 1.278 + */ 1.279 +UcxList *ucx_list_prepend_a(UcxAllocator *allocator, UcxList *list, void *data); 1.280 + 1.281 +/** 1.282 + * Concatenates two lists. 1.283 + * 1.284 + * Either of the two arguments may be <code>NULL</code>. 1.285 + * 1.286 + * This function modifies the references to the next/previous element of 1.287 + * the last/first element of <code>list1</code>/<code> 1.288 + * list2</code>. 1.289 + * 1.290 + * @param list1 first list 1.291 + * @param list2 second list 1.292 + * @return if <code>list1</code> is <code>NULL</code>, <code>list2</code> is 1.293 + * returned, otherwise <code>list1</code> is returned 1.294 + */ 1.295 +UcxList *ucx_list_concat(UcxList *list1, UcxList *list2); 1.296 + 1.297 +/** 1.298 + * Returns the first element of a list. 1.299 + * 1.300 + * If the argument is the list pointer, it is directly returned. Otherwise 1.301 + * this function traverses to the first element of the list and returns the 1.302 + * list pointer. 1.303 + * 1.304 + * @param elem one element of the list 1.305 + * @return the first element of the list, the specified element is a member of 1.306 + */ 1.307 +UcxList *ucx_list_first(const UcxList *elem); 1.308 + 1.309 +/** 1.310 + * Returns the last element of a list. 1.311 + * 1.312 + * If the argument has no successor, it is the last element and therefore 1.313 + * directly returned. Otherwise this function traverses to the last element of 1.314 + * the list and returns it. 1.315 + * 1.316 + * @param elem one element of the list 1.317 + * @return the last element of the list, the specified element is a member of 1.318 + */ 1.319 +UcxList *ucx_list_last(const UcxList *elem); 1.320 + 1.321 +/** 1.322 + * Returns the list element at the specified index. 1.323 + * 1.324 + * @param list the list to retrieve the element from 1.325 + * @param index index of the element to return 1.326 + * @return the element at the specified index or <code>NULL</code>, if the 1.327 + * index is greater than the list size 1.328 + */ 1.329 +UcxList *ucx_list_get(const UcxList *list, size_t index); 1.330 + 1.331 +/** 1.332 + * Returns the index of an element. 1.333 + * 1.334 + * @param list the list where to search for the element 1.335 + * @param elem the element to find 1.336 + * @return the index of the element or -1 if the list does not contain the 1.337 + * element 1.338 + */ 1.339 +ssize_t ucx_list_indexof(const UcxList *list, const UcxList *elem); 1.340 + 1.341 +/** 1.342 + * Returns the element count of the list. 1.343 + * 1.344 + * @param list the list whose elements are counted 1.345 + * @return the element count 1.346 + */ 1.347 +size_t ucx_list_size(const UcxList *list); 1.348 + 1.349 +/** 1.350 + * Returns the index of an element containing the specified data. 1.351 + * 1.352 + * This function uses a cmp_func() to compare the data of each list element 1.353 + * with the specified data. If no cmp_func is provided, the pointers are 1.354 + * compared. 1.355 + * 1.356 + * If the list contains the data more than once, the index of the first 1.357 + * occurrence is returned. 1.358 + * 1.359 + * @param list the list where to search for the data 1.360 + * @param elem the element data 1.361 + * @param cmpfnc the compare function 1.362 + * @param data additional data for the compare function 1.363 + * @return the index of the element containing the specified data or -1 if the 1.364 + * data is not found in this list 1.365 + */ 1.366 +ssize_t ucx_list_find(UcxList *list, void *elem, cmp_func cmpfnc, void *data); 1.367 + 1.368 +/** 1.369 + * Checks, if a list contains a specific element. 1.370 + * 1.371 + * An element is found, if ucx_list_find() returns a value greater than -1. 1.372 + * 1.373 + * @param list the list where to search for the data 1.374 + * @param elem the element data 1.375 + * @param cmpfnc the compare function 1.376 + * @param data additional data for the compare function 1.377 + * @return 1, if and only if the list contains the specified element data 1.378 + * @see ucx_list_find() 1.379 + */ 1.380 +int ucx_list_contains(UcxList *list, void *elem, cmp_func cmpfnc, void *data); 1.381 + 1.382 +/** 1.383 + * Sorts a UcxList with natural merge sort. 1.384 + * 1.385 + * This function uses O(n) additional temporary memory for merge operations 1.386 + * that is automatically freed after each merge. 1.387 + * 1.388 + * As the head of the list might change, you <b>MUST</b> call this function 1.389 + * as follows: <code>mylist = ucx_list_sort(mylist, mycmpfnc, mydata);</code>. 1.390 + * 1.391 + * @param list the list to sort 1.392 + * @param cmpfnc the function that shall be used to compare the element data 1.393 + * @param data additional data for the cmp_func() 1.394 + * @return the sorted list 1.395 + */ 1.396 +UcxList *ucx_list_sort(UcxList *list, cmp_func cmpfnc, void *data); 1.397 + 1.398 +/** 1.399 + * Removes an element from the list. 1.400 + * 1.401 + * If the first element is removed, the list pointer changes. So it is 1.402 + * <i>highly recommended</i> to <i>always</i> update the pointer by calling 1.403 + * <code>mylist = ucx_list_remove(mylist, myelem);</code>. 1.404 + * 1.405 + * @param list the list from which the element shall be removed 1.406 + * @param element the element to remove 1.407 + * @return returns the updated list pointer or <code>NULL</code>, if the list 1.408 + * is now empty 1.409 + */ 1.410 +UcxList *ucx_list_remove(UcxList *list, UcxList *element); 1.411 + 1.412 +/** 1.413 + * Removes an element from the list using a UcxAllocator. 1.414 + * 1.415 + * See ucx_list_remove() for details. 1.416 + * 1.417 + * @param allocator the allocator to use 1.418 + * @param list the list from which the element shall be removed 1.419 + * @param element the element to remove 1.420 + * @return returns the updated list pointer or <code>NULL</code>, if the list 1.421 + * @see ucx_list_remove() 1.422 + */ 1.423 +UcxList *ucx_list_remove_a(UcxAllocator *allocator, UcxList *list, 1.424 + UcxList *element); 1.425 + 1.426 +#ifdef __cplusplus 1.427 +} 1.428 +#endif 1.429 + 1.430 +#endif /* UCX_LIST_H */ 1.431 +