ucx/ucx/list.h

   1 /*
   2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
   3  *
   4  * Copyright 2017 Mike Becker, Olaf Wintermann All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions are met:
   8  *
   9  *   1. Redistributions of source code must retain the above copyright
  10  *      notice, this list of conditions and the following disclaimer.
  11  *
  12  *   2. Redistributions in binary form must reproduce the above copyright
  13  *      notice, this list of conditions and the following disclaimer in the
  14  *      documentation and/or other materials provided with the distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  17  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  19  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
  20  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  21  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  22  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  23  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  24  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  25  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  26  * POSSIBILITY OF SUCH DAMAGE.
  27  */
  28 /**
  29  * Doubly linked list implementation.
  30  *
  31  * @file   list.h
  32  * @author Mike Becker
  33  * @author Olaf Wintermann
  34  */
  35
  36 #ifndef UCX_LIST_H
  37 #define UCX_LIST_H
  38
  39 #include "ucx.h"
  40 #include "allocator.h"
  41
  42 #ifdef  __cplusplus
  43 extern "C" {
  44 #endif
  45
  46 /**
  47  * Loop statement for UCX lists.
  48  *
  49  * The first argument is the name of the iteration variable. The scope of
  50  * this variable is limited to the <code>UCX_FOREACH</code> statement.
  51  *
  52  * The second argument is a pointer to the list. In most cases this will be the
  53  * pointer to the first element of the list, but it may also be an arbitrary
  54  * element of the list. The iteration will then start with that element.
  55  *
  56  * @param list The first element of the list
  57  * @param elem The variable name of the element
  58  */
  59 #define UCX_FOREACH(elem,list) \
  60         for (UcxList* elem = (UcxList*) list ; elem != NULL ; elem = elem->next)
  61
  62 /**
  63  * UCX list type.
  64  * @see UcxList
  65  */
  66 typedef struct UcxList UcxList;
  67
  68 /**
  69  * UCX list structure.
  70  */
  71 struct UcxList {
  72     /**
  73      * List element payload.
  74      */
  75     void    *data;
  76     /**
  77      * Pointer to the next list element or <code>NULL</code>, if this is the
  78      * last element.
  79      */
  80     UcxList *next;
  81     /**
  82      * Pointer to the previous list element or <code>NULL</code>, if this is
  83      * the first element.
  84      */
  85     UcxList *prev;
  86 };
  87
  88 /**
  89  * Creates an element-wise copy of a list.
  90  *
  91  * This function clones the specified list by creating new list elements and
  92  * copying the data with the specified copy_func(). If no copy_func() is
  93  * specified, a shallow copy is created and the new list will reference the
  94  * same data as the source list.
  95  *
  96  * @param list the list to copy
  97  * @param cpyfnc a pointer to the function that shall copy an element (may be
  98  * <code>NULL</code>)
  99  * @param data additional data for the copy_func()
 100  * @return a pointer to the copy
 101  */
 102 UcxList *ucx_list_clone(const UcxList *list, copy_func cpyfnc, void* data);
 103
 104 /**
 105  * Creates an element-wise copy of a list using a UcxAllocator.
 106  *
 107  * See ucx_list_clone() for details.
 108  *
 109  * You might want to pass the allocator via the <code>data</code> parameter,
 110  * to access it within the copy function for making deep copies.
 111  *
 112  * @param allocator the allocator to use
 113  * @param list the list to copy
 114  * @param cpyfnc a pointer to the function that shall copy an element (may be
 115  * <code>NULL</code>)
 116  * @param data additional data for the copy_func()
 117  * @return a pointer to the copy
 118  * @see ucx_list_clone()
 119  */
 120 UcxList *ucx_list_clone_a(UcxAllocator *allocator, const UcxList *list,
 121         copy_func cpyfnc, void* data);
 122
 123 /**
 124  * Compares two UCX lists element-wise by using a compare function.
 125  *
 126  * Each element of the two specified lists are compared by using the specified
 127  * compare function and the additional data. The type and content of this
 128  * additional data depends on the cmp_func() used.
 129  *
 130  * If the list pointers denote elements within a list, the lists are compared
 131  * starting with the denoted elements. Thus any previous elements are not taken
 132  * into account. This might be useful to check, if certain list tails match
 133  * each other.
 134  *
 135  * @param list1 the first list
 136  * @param list2 the second list
 137  * @param cmpfnc the compare function
 138  * @param data additional data for the compare function
 139  * @return 1, if and only if the two lists equal element-wise, 0 otherwise
 140  */
 141 int ucx_list_equals(const UcxList *list1, const UcxList *list2,
 142         cmp_func cmpfnc, void* data);
 143
 144 /**
 145  * Destroys the entire list.
 146  *
 147  * The members of the list are not automatically freed, so ensure they are
 148  * otherwise referenced or destroyed by ucx_list_free_contents().
 149  * Otherwise, a memory leak is likely to occur.
 150  *
 151  * <b>Caution:</b> the argument <b>MUST</b> denote an entire list (i.e. a call
 152  * to ucx_list_first() on the argument must return the argument itself)
 153  *
 154  * @param list the list to free
 155  * @see ucx_list_free_contents()
 156  */
 157 void ucx_list_free(UcxList *list);
 158
 159 /**
 160  * Destroys the entire list using a UcxAllocator.
 161  *
 162  * See ucx_list_free() for details.
 163  *
 164  * @param allocator the allocator to use
 165  * @param list the list to free
 166  * @see ucx_list_free()
 167  */
 168 void ucx_list_free_a(UcxAllocator *allocator, UcxList *list);
 169
 170 /**
 171  * Destroys the contents of the specified list by calling the specified
 172  * destructor on each of them.
 173  *
 174  * Note, that the contents are not usable afterwards and the list should be
 175  * destroyed with ucx_list_free().
 176  *
 177  * If no destructor is specified (<code>NULL</code>), stdlib's free() is used.
 178  *
 179  * @param list the list for which the contents shall be freed
 180  * @param destr optional destructor function
 181  * @see ucx_list_free()
 182  */
 183 void ucx_list_free_content(UcxList* list, ucx_destructor destr);
 184
 185
 186 /**
 187  * Inserts an element at the end of the list.
 188  *
 189  * This is generally an O(n) operation, as the end of the list is retrieved with
 190  * ucx_list_last().
 191  *
 192  * @param list the list where to append the data, or <code>NULL</code> to
 193  * create a new list
 194  * @param data the data to insert
 195  * @return <code>list</code>, if it is not <code>NULL</code> or a pointer to
 196  * the newly created list otherwise
 197  */
 198 UcxList *ucx_list_append(UcxList *list, void *data);
 199
 200 /**
 201  * Inserts an element at the end of the list using a UcxAllocator.
 202  *
 203  * See ucx_list_append() for details.
 204  *
 205  * @param allocator the allocator to use
 206  * @param list the list where to append the data, or <code>NULL</code> to
 207  * create a new list
 208  * @param data the data to insert
 209  * @return <code>list</code>, if it is not <code>NULL</code> or a pointer to
 210  * the newly created list otherwise
 211  * @see ucx_list_append()
 212  */
 213 UcxList *ucx_list_append_a(UcxAllocator *allocator, UcxList *list, void *data);
 214
 215
 216 /**
 217  * Inserts an element at the beginning of the list.
 218  *
 219  * You <i>should</i> overwrite the old list pointer by calling
 220  * <code>mylist = ucx_list_prepend(mylist, mydata);</code>. However, you may
 221  * also perform successive calls of ucx_list_prepend() on the same list pointer,
 222  * as this function always searchs for the head of the list with
 223  * ucx_list_first().
 224  *
 225  * @param list the list where to insert the data or <code>NULL</code> to create
 226  * a new list
 227  * @param data the data to insert
 228  * @return a pointer to the new list head
 229  */
 230 UcxList *ucx_list_prepend(UcxList *list, void *data);
 231
 232 /**
 233  * Inserts an element at the beginning of the list using a UcxAllocator.
 234  *
 235  * See ucx_list_prepend() for details.
 236  *
 237  * @param allocator the allocator to use
 238  * @param list the list where to insert the data or <code>NULL</code> to create
 239  * a new list
 240  * @param data the data to insert
 241  * @return a pointer to the new list head
 242  * @see ucx_list_prepend()
 243  */
 244 UcxList *ucx_list_prepend_a(UcxAllocator *allocator, UcxList *list, void *data);
 245
 246 /**
 247  * Concatenates two lists.
 248  *
 249  * Either of the two arguments may be <code>NULL</code>.
 250  *
 251  * This function modifies the references to the next/previous element of
 252  * the last/first element of <code>list1</code>/<code>
 253  * list2</code>.
 254  *
 255  * @param list1 first list
 256  * @param list2 second list
 257  * @return if <code>list1</code> is <code>NULL</code>, <code>list2</code> is
 258  * returned, otherwise <code>list1</code> is returned
 259  */
 260 UcxList *ucx_list_concat(UcxList *list1, UcxList *list2);
 261
 262 /**
 263  * Returns the first element of a list.
 264  *
 265  * If the argument is the list pointer, it is directly returned. Otherwise
 266  * this function traverses to the first element of the list and returns the
 267  * list pointer.
 268  *
 269  * @param elem one element of the list
 270  * @return the first element of the list, the specified element is a member of
 271  */
 272 UcxList *ucx_list_first(const UcxList *elem);
 273
 274 /**
 275  * Returns the last element of a list.
 276  *
 277  * If the argument has no successor, it is the last element and therefore
 278  * directly returned. Otherwise this function traverses to the last element of
 279  * the list and returns it.
 280  *
 281  * @param elem one element of the list
 282  * @return the last element of the list, the specified element is a member of
 283  */
 284 UcxList *ucx_list_last(const UcxList *elem);
 285
 286 /**
 287  * Returns the list element at the specified index.
 288  *
 289  * @param list the list to retrieve the element from
 290  * @param index index of the element to return
 291  * @return the element at the specified index or <code>NULL</code>, if the
 292  * index is greater than the list size
 293  */
 294 UcxList *ucx_list_get(const UcxList *list, size_t index);
 295
 296 /**
 297  * Returns the index of an element.
 298  *
 299  * @param list the list where to search for the element
 300  * @param elem the element to find
 301  * @return the index of the element or -1 if the list does not contain the
 302  * element
 303  */
 304 ssize_t ucx_list_indexof(const UcxList *list, const UcxList *elem);
 305
 306 /**
 307  * Returns the element count of the list.
 308  *
 309  * @param list the list whose elements are counted
 310  * @return the element count
 311  */
 312 size_t ucx_list_size(const UcxList *list);
 313
 314 /**
 315  * Returns the index of an element containing the specified data.
 316  *
 317  * This function uses a cmp_func() to compare the data of each list element
 318  * with the specified data. If no cmp_func is provided, the pointers are
 319  * compared.
 320  *
 321  * If the list contains the data more than once, the index of the first
 322  * occurrence is returned.
 323  *
 324  * @param list the list where to search for the data
 325  * @param elem the element data
 326  * @param cmpfnc the compare function
 327  * @param data additional data for the compare function
 328  * @return the index of the element containing the specified data or -1 if the
 329  * data is not found in this list
 330  */
 331 ssize_t ucx_list_find(const UcxList *list, void *elem,
 332     cmp_func cmpfnc, void *data);
 333
 334 /**
 335  * Checks, if a list contains a specific element.
 336  *
 337  * An element is found, if ucx_list_find() returns a value greater than -1.
 338  *
 339  * @param list the list where to search for the data
 340  * @param elem the element data
 341  * @param cmpfnc the compare function
 342  * @param data additional data for the compare function
 343  * @return 1, if and only if the list contains the specified element data
 344  * @see ucx_list_find()
 345  */
 346 int ucx_list_contains(const UcxList *list, void *elem,
 347     cmp_func cmpfnc, void *data);
 348
 349 /**
 350  * Sorts a UcxList with natural merge sort.
 351  *
 352  * This function uses O(n) additional temporary memory for merge operations
 353  * that is automatically freed after each merge.
 354  *
 355  * As the head of the list might change, you <b>MUST</b> call this function
 356  * as follows: <code>mylist = ucx_list_sort(mylist, mycmpfnc, mydata);</code>.
 357  *
 358  * @param list the list to sort
 359  * @param cmpfnc the function that shall be used to compare the element data
 360  * @param data additional data for the cmp_func()
 361  * @return the sorted list
 362  */
 363 UcxList *ucx_list_sort(UcxList *list, cmp_func cmpfnc, void *data);
 364
 365 /**
 366  * Removes an element from the list.
 367  *
 368  * If the first element is removed, the list pointer changes. So it is
 369  * <i>highly recommended</i> to <i>always</i> update the pointer by calling
 370  * <code>mylist = ucx_list_remove(mylist, myelem);</code>.
 371  *
 372  * @param list the list from which the element shall be removed
 373  * @param element the element to remove
 374  * @return returns the updated list pointer or <code>NULL</code>, if the list
 375  * is now empty
 376  */
 377 UcxList *ucx_list_remove(UcxList *list, UcxList *element);
 378
 379 /**
 380  * Removes an element from the list using a UcxAllocator.
 381  *
 382  * See ucx_list_remove() for details.
 383  *
 384  * @param allocator the allocator to use
 385  * @param list the list from which the element shall be removed
 386  * @param element the element to remove
 387  * @return returns the updated list pointer or <code>NULL</code>, if the list
 388  * @see ucx_list_remove()
 389  */
 390 UcxList *ucx_list_remove_a(UcxAllocator *allocator, UcxList *list,
 391         UcxList *element);
 392
 393 /**
 394  * Returns the union of two lists.
 395  *
 396  * The union is a list of unique elements regarding cmpfnc obtained from
 397  * both source lists.
 398  *
 399  * @param left the left source list
 400  * @param right the right source list
 401  * @param cmpfnc a function to compare elements
 402  * @param cmpdata additional data for the compare function
 403  * @param cpfnc a function to copy the elements
 404  * @param cpdata additional data for the copy function
 405  * @return a new list containing the union
 406  */
 407 UcxList* ucx_list_union(const UcxList *left, const UcxList *right,
 408     cmp_func cmpfnc, void* cmpdata,
 409     copy_func cpfnc, void* cpdata);
 410
 411 /**
 412  * Returns the union of two lists.
 413  *
 414  * The union is a list of unique elements regarding cmpfnc obtained from
 415  * both source lists.
 416  *
 417  * @param allocator allocates the new list elements
 418  * @param left the left source list
 419  * @param right the right source list
 420  * @param cmpfnc a function to compare elements
 421  * @param cmpdata additional data for the compare function
 422  * @param cpfnc a function to copy the elements
 423  * @param cpdata additional data for the copy function
 424  * @return a new list containing the union
 425  */
 426 UcxList* ucx_list_union_a(UcxAllocator *allocator,
 427     const UcxList *left, const UcxList *right,
 428     cmp_func cmpfnc, void* cmpdata,
 429     copy_func cpfnc, void* cpdata);
 430
 431 /**
 432  * Returns the intersection of two lists.
 433  *
 434  * The intersection contains all elements of the left list
 435  * (including duplicates) that can be found in the right list.
 436  *
 437  * @param left the left source list
 438  * @param right the right source list
 439  * @param cmpfnc a function to compare elements
 440  * @param cmpdata additional data for the compare function
 441  * @param cpfnc a function to copy the elements
 442  * @param cpdata additional data for the copy function
 443  * @return a new list containing the intersection
 444  */
 445 UcxList* ucx_list_intersection(const UcxList *left, const UcxList *right,
 446     cmp_func cmpfnc, void* cmpdata,
 447     copy_func cpfnc, void* cpdata);
 448
 449 /**
 450  * Returns the intersection of two lists.
 451  *
 452  * The intersection contains all elements of the left list
 453  * (including duplicates) that can be found in the right list.
 454  *
 455  * @param allocator allocates the new list elements
 456  * @param left the left source list
 457  * @param right the right source list
 458  * @param cmpfnc a function to compare elements
 459  * @param cmpdata additional data for the compare function
 460  * @param cpfnc a function to copy the elements
 461  * @param cpdata additional data for the copy function
 462  * @return a new list containing the intersection
 463  */
 464 UcxList* ucx_list_intersection_a(UcxAllocator *allocator,
 465     const UcxList *left, const UcxList *right,
 466     cmp_func cmpfnc, void* cmpdata,
 467     copy_func cpfnc, void* cpdata);
 468
 469 /**
 470  * Returns the difference of two lists.
 471  *
 472  * The difference contains all elements of the left list
 473  * (including duplicates) that are not equal to any element of the right list.
 474  *
 475  * @param left the left source list
 476  * @param right the right source list
 477  * @param cmpfnc a function to compare elements
 478  * @param cmpdata additional data for the compare function
 479  * @param cpfnc a function to copy the elements
 480  * @param cpdata additional data for the copy function
 481  * @return a new list containing the difference
 482  */
 483 UcxList* ucx_list_difference(const UcxList *left, const UcxList *right,
 484     cmp_func cmpfnc, void* cmpdata,
 485     copy_func cpfnc, void* cpdata);
 486
 487 /**
 488  * Returns the difference of two lists.
 489  *
 490  * The difference contains all elements of the left list
 491  * (including duplicates) that are not equal to any element of the right list.
 492  *
 493  * @param allocator allocates the new list elements
 494  * @param left the left source list
 495  * @param right the right source list
 496  * @param cmpfnc a function to compare elements
 497  * @param cmpdata additional data for the compare function
 498  * @param cpfnc a function to copy the elements
 499  * @param cpdata additional data for the copy function
 500  * @return a new list containing the difference
 501  */
 502 UcxList* ucx_list_difference_a(UcxAllocator *allocator,
 503     const UcxList *left, const UcxList *right,
 504     cmp_func cmpfnc, void* cmpdata,
 505     copy_func cpfnc, void* cpdata);
 506
 507 #ifdef  __cplusplus
 508 }
 509 #endif
 510
 511 #endif  /* UCX_LIST_H */
 512