src/ucx/list.h

Wed, 02 May 2018 16:14:40 +0200

author
Mike Becker <universe@uap-core.de>
date
Wed, 02 May 2018 16:14:40 +0200
changeset 277
f819fe5e20f5
parent 259
2f5dea574a75
child 291
deb0035635eb
permissions
-rw-r--r--

makes destructor functions for *_free_content() optional + more documentation for UcxProperties

     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  */
    36 #ifndef UCX_LIST_H
    37 #define	UCX_LIST_H
    39 #include "ucx.h"
    40 #include "allocator.h"
    42 #ifdef	__cplusplus
    43 extern "C" {
    44 #endif
    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 = list ; elem != NULL ; elem = elem->next)
    62 /**
    63  * UCX list type.
    64  * @see UcxList
    65  */
    66 typedef struct UcxList UcxList;
    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 };
    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(UcxList *list, copy_func cpyfnc, void* data);
   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, UcxList *list,
   121         copy_func cpyfnc, void* data);
   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);
   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);
   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);
   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);
   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);
   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);
   215 /**
   216  * Inserts an element at the end of the list, if it is not present in the list.
   217  * 
   218  * 
   219  * @param list the list where to append the data, or <code>NULL</code> to
   220  * create a new list
   221  * @param data the data to insert
   222  * @param cmpfnc the compare function
   223  * @param cmpdata additional data for the compare function
   224  * @return <code>list</code>, if it is not <code>NULL</code> or a pointer to
   225  * the newly created list otherwise
   226  * @see ucx_list_append()
   227  */
   228 UcxList *ucx_list_append_once(UcxList *list, void *data,
   229         cmp_func cmpfnc, void *cmpdata);
   231 /**
   232  * Inserts an element at the end of the list, if it is not present in the list,
   233  * using a UcxAllocator.
   234  * 
   235  * See ucx_list_append() for details.
   236  * 
   237  * @param allocator the allocator to use
   238  * @param list the list where to append the data, or <code>NULL</code> to
   239  * create a new list
   240  * @param data the data to insert
   241  * @param cmpfnc the compare function
   242  * @param cmpdata additional data for the compare function
   243  * @return <code>list</code>, if it is not <code>NULL</code> or a pointer to
   244  * the newly created list otherwise
   245  * @see ucx_list_append_a()
   246  */
   247 UcxList *ucx_list_append_once_a(UcxAllocator *allocator,
   248         UcxList *list, void *data, cmp_func cmpfnc, void *cmpdata);
   250 /**
   251  * Inserts an element at the beginning of the list.
   252  * 
   253  * You <i>should</i> overwrite the old list pointer by calling
   254  * <code>mylist = ucx_list_prepend(mylist, mydata);</code>. However, you may
   255  * also perform successive calls of ucx_list_prepend() on the same list pointer,
   256  * as this function always searchs for the head of the list with
   257  * ucx_list_first().
   258  * 
   259  * @param list the list where to insert the data or <code>NULL</code> to create
   260  * a new list
   261  * @param data the data to insert
   262  * @return a pointer to the new list head
   263  */
   264 UcxList *ucx_list_prepend(UcxList *list, void *data);
   266 /**
   267  * Inserts an element at the beginning of the list using a UcxAllocator.
   268  * 
   269  * See ucx_list_prepend() for details.
   270  * 
   271  * @param allocator the allocator to use
   272  * @param list the list where to insert the data or <code>NULL</code> to create
   273  * a new list
   274  * @param data the data to insert
   275  * @return a pointer to the new list head
   276  * @see ucx_list_prepend()
   277  */
   278 UcxList *ucx_list_prepend_a(UcxAllocator *allocator, UcxList *list, void *data);
   280 /**
   281  * Concatenates two lists.
   282  * 
   283  * Either of the two arguments may be <code>NULL</code>.
   284  * 
   285  * This function modifies the references to the next/previous element of
   286  * the last/first element of <code>list1</code>/<code>
   287  * list2</code>.
   288  * 
   289  * @param list1 first list
   290  * @param list2 second list
   291  * @return if <code>list1</code> is <code>NULL</code>, <code>list2</code> is
   292  * returned, otherwise <code>list1</code> is returned
   293  */
   294 UcxList *ucx_list_concat(UcxList *list1, UcxList *list2);
   296 /**
   297  * Returns the first element of a list.
   298  * 
   299  * If the argument is the list pointer, it is directly returned. Otherwise
   300  * this function traverses to the first element of the list and returns the
   301  * list pointer.
   302  * 
   303  * @param elem one element of the list
   304  * @return the first element of the list, the specified element is a member of
   305  */
   306 UcxList *ucx_list_first(const UcxList *elem);
   308 /**
   309  * Returns the last element of a list.
   310  * 
   311  * If the argument has no successor, it is the last element and therefore
   312  * directly returned. Otherwise this function traverses to the last element of
   313  * the list and returns it.
   314  * 
   315  * @param elem one element of the list
   316  * @return the last element of the list, the specified element is a member of
   317  */
   318 UcxList *ucx_list_last(const UcxList *elem);
   320 /**
   321  * Returns the list element at the specified index.
   322  * 
   323  * @param list the list to retrieve the element from
   324  * @param index index of the element to return
   325  * @return the element at the specified index or <code>NULL</code>, if the
   326  * index is greater than the list size
   327  */
   328 UcxList *ucx_list_get(const UcxList *list, size_t index);
   330 /**
   331  * Returns the index of an element.
   332  * 
   333  * @param list the list where to search for the element
   334  * @param elem the element to find
   335  * @return the index of the element or -1 if the list does not contain the
   336  * element
   337  */
   338 ssize_t ucx_list_indexof(const UcxList *list, const UcxList *elem);
   340 /**
   341  * Returns the element count of the list.
   342  * 
   343  * @param list the list whose elements are counted
   344  * @return the element count
   345  */
   346 size_t ucx_list_size(const UcxList *list);
   348 /**
   349  * Returns the index of an element containing the specified data.
   350  *
   351  * This function uses a cmp_func() to compare the data of each list element
   352  * with the specified data. If no cmp_func is provided, the pointers are
   353  * compared.
   354  * 
   355  * If the list contains the data more than once, the index of the first
   356  * occurrence is returned.
   357  *  
   358  * @param list the list where to search for the data
   359  * @param elem the element data
   360  * @param cmpfnc the compare function
   361  * @param data additional data for the compare function
   362  * @return the index of the element containing the specified data or -1 if the
   363  * data is not found in this list
   364  */
   365 ssize_t ucx_list_find(UcxList *list, void *elem, cmp_func cmpfnc, void *data);
   367 /**
   368  * Checks, if a list contains a specific element.
   369  * 
   370  * An element is found, if ucx_list_find() returns a value greater than -1.
   371  * 
   372  * @param list the list where to search for the data
   373  * @param elem the element data
   374  * @param cmpfnc the compare function
   375  * @param data additional data for the compare function
   376  * @return 1, if and only if the list contains the specified element data
   377  * @see ucx_list_find()
   378  */
   379 int ucx_list_contains(UcxList *list, void *elem, cmp_func cmpfnc, void *data);
   381 /**
   382  * Sorts a UcxList with natural merge sort.
   383  * 
   384  * This function uses O(n) additional temporary memory for merge operations
   385  * that is automatically freed after each merge.
   386  * 
   387  * As the head of the list might change, you <b>MUST</b> call this function
   388  * as follows: <code>mylist = ucx_list_sort(mylist, mycmpfnc, mydata);</code>.
   389  * 
   390  * @param list the list to sort
   391  * @param cmpfnc the function that shall be used to compare the element data
   392  * @param data additional data for the cmp_func()
   393  * @return the sorted list
   394  */
   395 UcxList *ucx_list_sort(UcxList *list, cmp_func cmpfnc, void *data);
   397 /**
   398  * Removes an element from the list.
   399  * 
   400  * If the first element is removed, the list pointer changes. So it is
   401  * <i>highly recommended</i> to <i>always</i> update the pointer by calling
   402  * <code>mylist = ucx_list_remove(mylist, myelem);</code>.
   403  * 
   404  * @param list the list from which the element shall be removed
   405  * @param element the element to remove
   406  * @return returns the updated list pointer or <code>NULL</code>, if the list
   407  * is now empty
   408  */
   409 UcxList *ucx_list_remove(UcxList *list, UcxList *element);
   411 /**
   412  * Removes an element from the list using a UcxAllocator.
   413  * 
   414  * See ucx_list_remove() for details.
   415  * 
   416  * @param allocator the allocator to use
   417  * @param list the list from which the element shall be removed
   418  * @param element the element to remove
   419  * @return returns the updated list pointer or <code>NULL</code>, if the list
   420  * @see ucx_list_remove()
   421  */
   422 UcxList *ucx_list_remove_a(UcxAllocator *allocator, UcxList *list,
   423         UcxList *element);
   425 #ifdef	__cplusplus
   426 }
   427 #endif
   429 #endif	/* UCX_LIST_H */

mercurial