1.1 --- a/src/ucx/list.h Thu Nov 10 18:44:48 2016 +0100 1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 1.3 @@ -1,395 +0,0 @@ 1.4 -/* 1.5 - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. 1.6 - * 1.7 - * Copyright 2015 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.h" 1.43 -#include "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 - * 1.60 - * @param list The first element of the list 1.61 - * @param elem The variable name of the element 1.62 - */ 1.63 -#define UCX_FOREACH(elem,list) \ 1.64 - for (UcxList* elem = list ; elem != NULL ; elem = elem->next) 1.65 - 1.66 -/** 1.67 - * UCX list type. 1.68 - * @see UcxList 1.69 - */ 1.70 -typedef struct UcxList UcxList; 1.71 - 1.72 -/** 1.73 - * UCX list structure. 1.74 - */ 1.75 -struct UcxList { 1.76 - /** 1.77 - * List element payload. 1.78 - */ 1.79 - void *data; 1.80 - /** 1.81 - * Pointer to the next list element or <code>NULL</code>, if this is the 1.82 - * last element. 1.83 - */ 1.84 - UcxList *next; 1.85 - /** 1.86 - * Pointer to the previous list element or <code>NULL</code>, if this is 1.87 - * the first element. 1.88 - */ 1.89 - UcxList *prev; 1.90 -}; 1.91 - 1.92 -/** 1.93 - * Creates an element-wise copy of a list. 1.94 - * 1.95 - * This function clones the specified list by creating new list elements and 1.96 - * copying the data with the specified copy_func(). If no copy_func() is 1.97 - * specified, a shallow copy is created and the new list will reference the 1.98 - * same data as the source list. 1.99 - * 1.100 - * @param list the list to copy 1.101 - * @param cpyfnc a pointer to the function that shall copy an element (may be 1.102 - * <code>NULL</code>) 1.103 - * @param data additional data for the copy_func() 1.104 - * @return a pointer to the copy 1.105 - */ 1.106 -UcxList *ucx_list_clone(UcxList *list, copy_func cpyfnc, void* data); 1.107 - 1.108 -/** 1.109 - * Creates an element-wise copy of a list using an UcxAllocator. 1.110 - * 1.111 - * See ucx_list_clone() for details. 1.112 - * 1.113 - * Keep in mind, that you might want to pass the allocator as an (part of the) 1.114 - * argument for the <code>data</code> parameter, if you want the copy_func() to 1.115 - * make use of the allocator. 1.116 - * 1.117 - * @param allocator the allocator to use 1.118 - * @param list the list to copy 1.119 - * @param cpyfnc a pointer to the function that shall copy an element (may be 1.120 - * <code>NULL</code>) 1.121 - * @param data additional data for the copy_func() 1.122 - * @return a pointer to the copy 1.123 - * @see ucx_list_clone() 1.124 - */ 1.125 -UcxList *ucx_list_clone_a(UcxAllocator *allocator, UcxList *list, 1.126 - copy_func cpyfnc, void* data); 1.127 - 1.128 -/** 1.129 - * Compares two UCX lists element-wise by using a compare function. 1.130 - * 1.131 - * Each element of the two specified lists are compared by using the specified 1.132 - * compare function and the additional data. The type and content of this 1.133 - * additional data depends on the cmp_func() used. 1.134 - * 1.135 - * If the list pointers denote elements within a list, the lists are compared 1.136 - * starting with the denoted elements. Thus any previous elements are not taken 1.137 - * into account. This might be useful to check, if certain list tails match 1.138 - * each other. 1.139 - * 1.140 - * @param list1 the first list 1.141 - * @param list2 the second list 1.142 - * @param cmpfnc the compare function 1.143 - * @param data additional data for the compare function 1.144 - * @return 1, if and only if the two lists equal element-wise, 0 otherwise 1.145 - */ 1.146 -int ucx_list_equals(const UcxList *list1, const UcxList *list2, 1.147 - cmp_func cmpfnc, void* data); 1.148 - 1.149 -/** 1.150 - * Destroys the entire list. 1.151 - * 1.152 - * The members of the list are not automatically freed, so ensure they are 1.153 - * otherwise referenced or destroyed by ucx_list_free_contents(). 1.154 - * Otherwise, a memory leak is likely to occur. 1.155 - * 1.156 - * <b>Caution:</b> the argument <b>MUST</b> denote an entire list (i.e. a call 1.157 - * to ucx_list_first() on the argument must return the argument itself) 1.158 - * 1.159 - * @param list the list to free 1.160 - * @see ucx_list_free_contents() 1.161 - */ 1.162 -void ucx_list_free(UcxList *list); 1.163 - 1.164 -/** 1.165 - * Destroys the entire list using an UcxAllocator. 1.166 - * 1.167 - * See ucx_list_free() for details. 1.168 - * 1.169 - * @param allocator the allocator to use 1.170 - * @param list the list to free 1.171 - * @see ucx_list_free() 1.172 - */ 1.173 -void ucx_list_free_a(UcxAllocator *allocator, UcxList *list); 1.174 - 1.175 -/** 1.176 - * Destroys the contents of the specified list by calling the specified 1.177 - * destructor on each of them. 1.178 - * 1.179 - * Note, that the contents are not usable afterwards and the list should be 1.180 - * destroyed with ucx_list_free(). 1.181 - * 1.182 - * @param list the list for which the contents shall be freed 1.183 - * @param destr the destructor function (e.g. stdlib free()) 1.184 - * @see ucx_list_free() 1.185 - */ 1.186 -void ucx_list_free_content(UcxList* list, ucx_destructor destr); 1.187 - 1.188 - 1.189 -/** 1.190 - * Inserts an element at the end of the list. 1.191 - * 1.192 - * This is generally an O(n) operation, as the end of the list is retrieved with 1.193 - * ucx_list_last(). 1.194 - * 1.195 - * @param list the list where to append the data, or <code>NULL</code> to 1.196 - * create a new list 1.197 - * @param data the data to insert 1.198 - * @return <code>list</code>, if it is not <code>NULL</code> or a pointer to 1.199 - * the newly created list otherwise 1.200 - */ 1.201 -UcxList *ucx_list_append(UcxList *list, void *data); 1.202 - 1.203 -/** 1.204 - * Inserts an element at the end of the list using an UcxAllocator. 1.205 - * 1.206 - * See ucx_list_append() for details. 1.207 - * 1.208 - * @param allocator the allocator to use 1.209 - * @param list the list where to append the data, or <code>NULL</code> to 1.210 - * create a new list 1.211 - * @param data the data to insert 1.212 - * @return <code>list</code>, if it is not <code>NULL</code> or a pointer to 1.213 - * the newly created list otherwise 1.214 - * @see ucx_list_append() 1.215 - */ 1.216 -UcxList *ucx_list_append_a(UcxAllocator *allocator, UcxList *list, void *data); 1.217 - 1.218 -/** 1.219 - * Inserts an element at the beginning of the list. 1.220 - * 1.221 - * You <i>should</i> overwrite the old list pointer by calling 1.222 - * <code>mylist = ucx_list_prepend(mylist, mydata);</code>. However, you may 1.223 - * also perform successive calls of ucx_list_prepend() on the same list pointer, 1.224 - * as this function always searchs for the head of the list with 1.225 - * ucx_list_first(). 1.226 - * 1.227 - * @param list the list where to insert the data or <code>NULL</code> to create 1.228 - * a new list 1.229 - * @param data the data to insert 1.230 - * @return a pointer to the new list head 1.231 - */ 1.232 -UcxList *ucx_list_prepend(UcxList *list, void *data); 1.233 - 1.234 -/** 1.235 - * Inserts an element at the beginning of the list using an UcxAllocator. 1.236 - * 1.237 - * See ucx_list_prepend() for details. 1.238 - * 1.239 - * @param allocator the allocator to use 1.240 - * @param list the list where to insert the data or <code>NULL</code> to create 1.241 - * a new list 1.242 - * @param data the data to insert 1.243 - * @return a pointer to the new list head 1.244 - * @see ucx_list_prepend() 1.245 - */ 1.246 -UcxList *ucx_list_prepend_a(UcxAllocator *allocator, UcxList *list, void *data); 1.247 - 1.248 -/** 1.249 - * Concatenates two lists. 1.250 - * 1.251 - * Either of the two arguments may be <code>NULL</code>. 1.252 - * 1.253 - * This function modifies the references to the next/previous element of 1.254 - * the last/first element of <code>list1</code>/<code> 1.255 - * list2</code>. 1.256 - * 1.257 - * @param list1 first list 1.258 - * @param list2 second list 1.259 - * @return if <code>list1</code> is <code>NULL</code>, <code>list2</code> is 1.260 - * returned, otherwise <code>list1</code> is returned 1.261 - */ 1.262 -UcxList *ucx_list_concat(UcxList *list1, UcxList *list2); 1.263 - 1.264 -/** 1.265 - * Returns the first element of a list. 1.266 - * 1.267 - * If the argument is the list pointer, it is directly returned. Otherwise 1.268 - * this function traverses to the first element of the list and returns the 1.269 - * list pointer. 1.270 - * 1.271 - * @param elem one element of the list 1.272 - * @return the first element of the list, the specified element is a member of 1.273 - */ 1.274 -UcxList *ucx_list_first(const UcxList *elem); 1.275 - 1.276 -/** 1.277 - * Returns the last element of a list. 1.278 - * 1.279 - * If the argument has no successor, it is the last element and therefore 1.280 - * directly returned. Otherwise this function traverses to the last element of 1.281 - * the list and returns it. 1.282 - * 1.283 - * @param elem one element of the list 1.284 - * @return the last element of the list, the specified element is a member of 1.285 - */ 1.286 -UcxList *ucx_list_last(const UcxList *elem); 1.287 - 1.288 -/** 1.289 - * Returns the list element at the specified index. 1.290 - * 1.291 - * @param list the list to retrieve the element from 1.292 - * @param index index of the element to return 1.293 - * @return the element at the specified index or <code>NULL</code>, if the 1.294 - * index is greater than the list size 1.295 - */ 1.296 -UcxList *ucx_list_get(const UcxList *list, size_t index); 1.297 - 1.298 -/** 1.299 - * Returns the index of an element. 1.300 - * 1.301 - * @param list the list where to search for the element 1.302 - * @param elem the element to find 1.303 - * @return the index of the element or -1 if the list does not contain the 1.304 - * element 1.305 - */ 1.306 -ssize_t ucx_list_indexof(const UcxList *list, const UcxList *elem); 1.307 - 1.308 -/** 1.309 - * Returns the element count of the list. 1.310 - * 1.311 - * @param list the list whose elements are counted 1.312 - * @return the element count 1.313 - */ 1.314 -size_t ucx_list_size(const UcxList *list); 1.315 - 1.316 -/** 1.317 - * Returns the index of an element containing the specified data. 1.318 - * 1.319 - * This function uses a cmp_func() to compare the data of each list element 1.320 - * with the specified data. If no cmp_func is provided, the pointers are 1.321 - * compared. 1.322 - * 1.323 - * If the list contains the data more than once, the index of the first 1.324 - * occurrence is returned. 1.325 - * 1.326 - * @param list the list where to search for the data 1.327 - * @param elem the element data 1.328 - * @param cmpfnc the compare function 1.329 - * @param data additional data for the compare function 1.330 - * @return the index of the element containing the specified data or -1 if the 1.331 - * data is not found in this list 1.332 - */ 1.333 -ssize_t ucx_list_find(UcxList *list, void *elem, cmp_func cmpfnc, void *data); 1.334 - 1.335 -/** 1.336 - * Checks, if a list contains a specific element. 1.337 - * 1.338 - * An element is found, if ucx_list_find() returns a value greater than -1. 1.339 - * 1.340 - * @param list the list where to search for the data 1.341 - * @param elem the element data 1.342 - * @param cmpfnc the compare function 1.343 - * @param data additional data for the compare function 1.344 - * @return 1, if and only if the list contains the specified element data 1.345 - * @see ucx_list_find() 1.346 - */ 1.347 -int ucx_list_contains(UcxList *list, void *elem, cmp_func cmpfnc, void *data); 1.348 - 1.349 -/** 1.350 - * Sorts an UcxList with natural merge sort. 1.351 - * 1.352 - * This function uses O(n) additional temporary memory for merge operations 1.353 - * that is automatically freed after each merge. 1.354 - * 1.355 - * As the head of the list might change, you <b>MUST</b> call this function 1.356 - * as follows: <code>mylist = ucx_list_sort(mylist, mycmpfnc, mydata);</code>. 1.357 - * 1.358 - * @param list the list to sort 1.359 - * @param cmpfnc the function that shall be used to compare the element data 1.360 - * @param data additional data for the cmp_func() 1.361 - * @return the sorted list 1.362 - */ 1.363 -UcxList *ucx_list_sort(UcxList *list, cmp_func cmpfnc, void *data); 1.364 - 1.365 -/** 1.366 - * Removes an element from the list. 1.367 - * 1.368 - * If the first element is removed, the list pointer changes. So it is 1.369 - * <i>highly recommended</i> to <i>always</i> update the pointer by calling 1.370 - * <code>mylist = ucx_list_remove(mylist, myelem);</code>. 1.371 - * 1.372 - * @param list the list from which the element shall be removed 1.373 - * @param element the element to remove 1.374 - * @return returns the updated list pointer or <code>NULL</code>, if the list 1.375 - * is now empty 1.376 - */ 1.377 -UcxList *ucx_list_remove(UcxList *list, UcxList *element); 1.378 - 1.379 -/** 1.380 - * Removes an element from the list using an UcxAllocator. 1.381 - * 1.382 - * See ucx_list_remove() for details. 1.383 - * 1.384 - * @param allocator the allocator to use 1.385 - * @param list the list from which the element shall be removed 1.386 - * @param element the element to remove 1.387 - * @return returns the updated list pointer or <code>NULL</code>, if the list 1.388 - * @see ucx_list_remove() 1.389 - */ 1.390 -UcxList *ucx_list_remove_a(UcxAllocator *allocator, UcxList *list, 1.391 - UcxList *element); 1.392 - 1.393 -#ifdef __cplusplus 1.394 -} 1.395 -#endif 1.396 - 1.397 -#endif /* UCX_LIST_H */ 1.398 -