1.1 --- a/src/ucx/list.h Mon Dec 30 09:54:10 2019 +0100
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,512 +0,0 @@
1.4 -/*
1.5 - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
1.6 - *
1.7 - * Copyright 2017 Mike Becker, 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 - * @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 = (UcxList*) 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(const 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, const 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 - * If no destructor is specified (<code>NULL</code>), stdlib's free() is used.
1.181 - *
1.182 - * @param list the list for which the contents shall be freed
1.183 - * @param destr optional destructor function
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 a 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 -/**
1.220 - * Inserts an element at the beginning of the list.
1.221 - *
1.222 - * You <i>should</i> overwrite the old list pointer by calling
1.223 - * <code>mylist = ucx_list_prepend(mylist, mydata);</code>. However, you may
1.224 - * also perform successive calls of ucx_list_prepend() on the same list pointer,
1.225 - * as this function always searchs for the head of the list with
1.226 - * ucx_list_first().
1.227 - *
1.228 - * @param list the list where to insert the data or <code>NULL</code> to create
1.229 - * a new list
1.230 - * @param data the data to insert
1.231 - * @return a pointer to the new list head
1.232 - */
1.233 -UcxList *ucx_list_prepend(UcxList *list, void *data);
1.234 -
1.235 -/**
1.236 - * Inserts an element at the beginning of the list using a UcxAllocator.
1.237 - *
1.238 - * See ucx_list_prepend() for details.
1.239 - *
1.240 - * @param allocator the allocator to use
1.241 - * @param list the list where to insert the data or <code>NULL</code> to create
1.242 - * a new list
1.243 - * @param data the data to insert
1.244 - * @return a pointer to the new list head
1.245 - * @see ucx_list_prepend()
1.246 - */
1.247 -UcxList *ucx_list_prepend_a(UcxAllocator *allocator, UcxList *list, void *data);
1.248 -
1.249 -/**
1.250 - * Concatenates two lists.
1.251 - *
1.252 - * Either of the two arguments may be <code>NULL</code>.
1.253 - *
1.254 - * This function modifies the references to the next/previous element of
1.255 - * the last/first element of <code>list1</code>/<code>
1.256 - * list2</code>.
1.257 - *
1.258 - * @param list1 first list
1.259 - * @param list2 second list
1.260 - * @return if <code>list1</code> is <code>NULL</code>, <code>list2</code> is
1.261 - * returned, otherwise <code>list1</code> is returned
1.262 - */
1.263 -UcxList *ucx_list_concat(UcxList *list1, UcxList *list2);
1.264 -
1.265 -/**
1.266 - * Returns the first element of a list.
1.267 - *
1.268 - * If the argument is the list pointer, it is directly returned. Otherwise
1.269 - * this function traverses to the first element of the list and returns the
1.270 - * list pointer.
1.271 - *
1.272 - * @param elem one element of the list
1.273 - * @return the first element of the list, the specified element is a member of
1.274 - */
1.275 -UcxList *ucx_list_first(const UcxList *elem);
1.276 -
1.277 -/**
1.278 - * Returns the last element of a list.
1.279 - *
1.280 - * If the argument has no successor, it is the last element and therefore
1.281 - * directly returned. Otherwise this function traverses to the last element of
1.282 - * the list and returns it.
1.283 - *
1.284 - * @param elem one element of the list
1.285 - * @return the last element of the list, the specified element is a member of
1.286 - */
1.287 -UcxList *ucx_list_last(const UcxList *elem);
1.288 -
1.289 -/**
1.290 - * Returns the list element at the specified index.
1.291 - *
1.292 - * @param list the list to retrieve the element from
1.293 - * @param index index of the element to return
1.294 - * @return the element at the specified index or <code>NULL</code>, if the
1.295 - * index is greater than the list size
1.296 - */
1.297 -UcxList *ucx_list_get(const UcxList *list, size_t index);
1.298 -
1.299 -/**
1.300 - * Returns the index of an element.
1.301 - *
1.302 - * @param list the list where to search for the element
1.303 - * @param elem the element to find
1.304 - * @return the index of the element or -1 if the list does not contain the
1.305 - * element
1.306 - */
1.307 -ssize_t ucx_list_indexof(const UcxList *list, const UcxList *elem);
1.308 -
1.309 -/**
1.310 - * Returns the element count of the list.
1.311 - *
1.312 - * @param list the list whose elements are counted
1.313 - * @return the element count
1.314 - */
1.315 -size_t ucx_list_size(const UcxList *list);
1.316 -
1.317 -/**
1.318 - * Returns the index of an element containing the specified data.
1.319 - *
1.320 - * This function uses a cmp_func() to compare the data of each list element
1.321 - * with the specified data. If no cmp_func is provided, the pointers are
1.322 - * compared.
1.323 - *
1.324 - * If the list contains the data more than once, the index of the first
1.325 - * occurrence is returned.
1.326 - *
1.327 - * @param list the list where to search for the data
1.328 - * @param elem the element data
1.329 - * @param cmpfnc the compare function
1.330 - * @param data additional data for the compare function
1.331 - * @return the index of the element containing the specified data or -1 if the
1.332 - * data is not found in this list
1.333 - */
1.334 -ssize_t ucx_list_find(const UcxList *list, void *elem,
1.335 - cmp_func cmpfnc, void *data);
1.336 -
1.337 -/**
1.338 - * Checks, if a list contains a specific element.
1.339 - *
1.340 - * An element is found, if ucx_list_find() returns a value greater than -1.
1.341 - *
1.342 - * @param list the list where to search for the data
1.343 - * @param elem the element data
1.344 - * @param cmpfnc the compare function
1.345 - * @param data additional data for the compare function
1.346 - * @return 1, if and only if the list contains the specified element data
1.347 - * @see ucx_list_find()
1.348 - */
1.349 -int ucx_list_contains(const UcxList *list, void *elem,
1.350 - cmp_func cmpfnc, void *data);
1.351 -
1.352 -/**
1.353 - * Sorts a UcxList with natural merge sort.
1.354 - *
1.355 - * This function uses O(n) additional temporary memory for merge operations
1.356 - * that is automatically freed after each merge.
1.357 - *
1.358 - * As the head of the list might change, you <b>MUST</b> call this function
1.359 - * as follows: <code>mylist = ucx_list_sort(mylist, mycmpfnc, mydata);</code>.
1.360 - *
1.361 - * @param list the list to sort
1.362 - * @param cmpfnc the function that shall be used to compare the element data
1.363 - * @param data additional data for the cmp_func()
1.364 - * @return the sorted list
1.365 - */
1.366 -UcxList *ucx_list_sort(UcxList *list, cmp_func cmpfnc, void *data);
1.367 -
1.368 -/**
1.369 - * Removes an element from the list.
1.370 - *
1.371 - * If the first element is removed, the list pointer changes. So it is
1.372 - * <i>highly recommended</i> to <i>always</i> update the pointer by calling
1.373 - * <code>mylist = ucx_list_remove(mylist, myelem);</code>.
1.374 - *
1.375 - * @param list the list from which the element shall be removed
1.376 - * @param element the element to remove
1.377 - * @return returns the updated list pointer or <code>NULL</code>, if the list
1.378 - * is now empty
1.379 - */
1.380 -UcxList *ucx_list_remove(UcxList *list, UcxList *element);
1.381 -
1.382 -/**
1.383 - * Removes an element from the list using a UcxAllocator.
1.384 - *
1.385 - * See ucx_list_remove() for details.
1.386 - *
1.387 - * @param allocator the allocator to use
1.388 - * @param list the list from which the element shall be removed
1.389 - * @param element the element to remove
1.390 - * @return returns the updated list pointer or <code>NULL</code>, if the list
1.391 - * @see ucx_list_remove()
1.392 - */
1.393 -UcxList *ucx_list_remove_a(UcxAllocator *allocator, UcxList *list,
1.394 - UcxList *element);
1.395 -
1.396 -/**
1.397 - * Returns the union of two lists.
1.398 - *
1.399 - * The union is a list of unique elements regarding cmpfnc obtained from
1.400 - * both source lists.
1.401 - *
1.402 - * @param left the left source list
1.403 - * @param right the right source list
1.404 - * @param cmpfnc a function to compare elements
1.405 - * @param cmpdata additional data for the compare function
1.406 - * @param cpfnc a function to copy the elements
1.407 - * @param cpdata additional data for the copy function
1.408 - * @return a new list containing the union
1.409 - */
1.410 -UcxList* ucx_list_union(const UcxList *left, const UcxList *right,
1.411 - cmp_func cmpfnc, void* cmpdata,
1.412 - copy_func cpfnc, void* cpdata);
1.413 -
1.414 -/**
1.415 - * Returns the union of two lists.
1.416 - *
1.417 - * The union is a list of unique elements regarding cmpfnc obtained from
1.418 - * both source lists.
1.419 - *
1.420 - * @param allocator allocates the new list elements
1.421 - * @param left the left source list
1.422 - * @param right the right source list
1.423 - * @param cmpfnc a function to compare elements
1.424 - * @param cmpdata additional data for the compare function
1.425 - * @param cpfnc a function to copy the elements
1.426 - * @param cpdata additional data for the copy function
1.427 - * @return a new list containing the union
1.428 - */
1.429 -UcxList* ucx_list_union_a(UcxAllocator *allocator,
1.430 - const UcxList *left, const UcxList *right,
1.431 - cmp_func cmpfnc, void* cmpdata,
1.432 - copy_func cpfnc, void* cpdata);
1.433 -
1.434 -/**
1.435 - * Returns the intersection of two lists.
1.436 - *
1.437 - * The intersection contains all elements of the left list
1.438 - * (including duplicates) that can be found in the right list.
1.439 - *
1.440 - * @param left the left source list
1.441 - * @param right the right source list
1.442 - * @param cmpfnc a function to compare elements
1.443 - * @param cmpdata additional data for the compare function
1.444 - * @param cpfnc a function to copy the elements
1.445 - * @param cpdata additional data for the copy function
1.446 - * @return a new list containing the intersection
1.447 - */
1.448 -UcxList* ucx_list_intersection(const UcxList *left, const UcxList *right,
1.449 - cmp_func cmpfnc, void* cmpdata,
1.450 - copy_func cpfnc, void* cpdata);
1.451 -
1.452 -/**
1.453 - * Returns the intersection of two lists.
1.454 - *
1.455 - * The intersection contains all elements of the left list
1.456 - * (including duplicates) that can be found in the right list.
1.457 - *
1.458 - * @param allocator allocates the new list elements
1.459 - * @param left the left source list
1.460 - * @param right the right source list
1.461 - * @param cmpfnc a function to compare elements
1.462 - * @param cmpdata additional data for the compare function
1.463 - * @param cpfnc a function to copy the elements
1.464 - * @param cpdata additional data for the copy function
1.465 - * @return a new list containing the intersection
1.466 - */
1.467 -UcxList* ucx_list_intersection_a(UcxAllocator *allocator,
1.468 - const UcxList *left, const UcxList *right,
1.469 - cmp_func cmpfnc, void* cmpdata,
1.470 - copy_func cpfnc, void* cpdata);
1.471 -
1.472 -/**
1.473 - * Returns the difference of two lists.
1.474 - *
1.475 - * The difference contains all elements of the left list
1.476 - * (including duplicates) that are not equal to any element of the right list.
1.477 - *
1.478 - * @param left the left source list
1.479 - * @param right the right source list
1.480 - * @param cmpfnc a function to compare elements
1.481 - * @param cmpdata additional data for the compare function
1.482 - * @param cpfnc a function to copy the elements
1.483 - * @param cpdata additional data for the copy function
1.484 - * @return a new list containing the difference
1.485 - */
1.486 -UcxList* ucx_list_difference(const UcxList *left, const UcxList *right,
1.487 - cmp_func cmpfnc, void* cmpdata,
1.488 - copy_func cpfnc, void* cpdata);
1.489 -
1.490 -/**
1.491 - * Returns the difference of two lists.
1.492 - *
1.493 - * The difference contains all elements of the left list
1.494 - * (including duplicates) that are not equal to any element of the right list.
1.495 - *
1.496 - * @param allocator allocates the new list elements
1.497 - * @param left the left source list
1.498 - * @param right the right source list
1.499 - * @param cmpfnc a function to compare elements
1.500 - * @param cmpdata additional data for the compare function
1.501 - * @param cpfnc a function to copy the elements
1.502 - * @param cpdata additional data for the copy function
1.503 - * @return a new list containing the difference
1.504 - */
1.505 -UcxList* ucx_list_difference_a(UcxAllocator *allocator,
1.506 - const UcxList *left, const UcxList *right,
1.507 - cmp_func cmpfnc, void* cmpdata,
1.508 - copy_func cpfnc, void* cpdata);
1.509 -
1.510 -#ifdef __cplusplus
1.511 -}
1.512 -#endif
1.513 -
1.514 -#endif /* UCX_LIST_H */
1.515 -
