1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/ucx/list.h Tue Aug 23 13:49:38 2016 +0200
1.3 @@ -0,0 +1,395 @@
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 +
