/*
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
*
* Copyright 2016 Olaf Wintermann. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*/
/**
* Doubly linked list implementation.
*
* @file list.h
* @author Mike Becker
* @author Olaf Wintermann
*/
#ifndef UCX_LIST_H
#define UCX_LIST_H
#include "ucx.h"
#include "allocator.h"
#ifdef __cplusplus
extern "C" {
#endif
/**
* Loop statement for UCX lists.
*
* The first argument is the name of the iteration variable. The scope of
* this variable is limited to the <code>UCX_FOREACH</code> statement.
*
* The second argument is a pointer to the list. In most cases this will be the
* pointer to the first element of the list, but it may also be an arbitrary
* element of the list. The iteration will then start with that element.
*
* @param list The first element of the list
* @param elem The variable name of the element
*/
#define UCX_FOREACH(elem,list) \
for (UcxList* elem = list ; elem != NULL ; elem = elem->next)
/**
* UCX list type.
* @see UcxList
*/
typedef struct UcxList UcxList;
/**
* UCX list structure.
*/
struct UcxList {
/**
* List element payload.
*/
void *data;
/**
* Pointer to the next list element or <code>NULL</code>, if this is the
* last element.
*/
UcxList *next;
/**
* Pointer to the previous list element or <code>NULL</code>, if this is
* the first element.
*/
UcxList *prev;
};
/**
* Creates an element-wise copy of a list.
*
* This function clones the specified list by creating new list elements and
* copying the data with the specified copy_func(). If no copy_func() is
* specified, a shallow copy is created and the new list will reference the
* same data as the source list.
*
* @param list the list to copy
* @param cpyfnc a pointer to the function that shall copy an element (may be
* <code>NULL</code>)
* @param data additional data for the copy_func()
* @return a pointer to the copy
*/
UcxList *ucx_list_clone(UcxList *list, copy_func cpyfnc, void* data);
/**
* Creates an element-wise copy of a list using a UcxAllocator.
*
* See ucx_list_clone() for details.
*
* You might want to pass the allocator via the <code>data</code> parameter,
* to access it within the copy function for making deep copies.
*
* @param allocator the allocator to use
* @param list the list to copy
* @param cpyfnc a pointer to the function that shall copy an element (may be
* <code>NULL</code>)
* @param data additional data for the copy_func()
* @return a pointer to the copy
* @see ucx_list_clone()
*/
UcxList *ucx_list_clone_a(UcxAllocator *allocator, UcxList *list,
copy_func cpyfnc, void* data);
/**
* Compares two UCX lists element-wise by using a compare function.
*
* Each element of the two specified lists are compared by using the specified
* compare function and the additional data. The type and content of this
* additional data depends on the cmp_func() used.
*
* If the list pointers denote elements within a list, the lists are compared
* starting with the denoted elements. Thus any previous elements are not taken
* into account. This might be useful to check, if certain list tails match
* each other.
*
* @param list1 the first list
* @param list2 the second list
* @param cmpfnc the compare function
* @param data additional data for the compare function
* @return 1, if and only if the two lists equal element-wise, 0 otherwise
*/
int ucx_list_equals(const UcxList *list1, const UcxList *list2,
cmp_func cmpfnc, void* data);
/**
* Destroys the entire list.
*
* The members of the list are not automatically freed, so ensure they are
* otherwise referenced or destroyed by ucx_list_free_contents().
* Otherwise, a memory leak is likely to occur.
*
* <b>Caution:</b> the argument <b>MUST</b> denote an entire list (i.e. a call
* to ucx_list_first() on the argument must return the argument itself)
*
* @param list the list to free
* @see ucx_list_free_contents()
*/
void ucx_list_free(UcxList *list);
/**
* Destroys the entire list using a UcxAllocator.
*
* See ucx_list_free() for details.
*
* @param allocator the allocator to use
* @param list the list to free
* @see ucx_list_free()
*/
void ucx_list_free_a(UcxAllocator *allocator, UcxList *list);
/**
* Destroys the contents of the specified list by calling the specified
* destructor on each of them.
*
* Note, that the contents are not usable afterwards and the list should be
* destroyed with ucx_list_free().
*
* @param list the list for which the contents shall be freed
* @param destr the destructor function (e.g. stdlib free())
* @see ucx_list_free()
*/
void ucx_list_free_content(UcxList* list, ucx_destructor destr);
/**
* Inserts an element at the end of the list.
*
* This is generally an O(n) operation, as the end of the list is retrieved with
* ucx_list_last().
*
* @param list the list where to append the data, or <code>NULL</code> to
* create a new list
* @param data the data to insert
* @return <code>list</code>, if it is not <code>NULL</code> or a pointer to
* the newly created list otherwise
*/
UcxList *ucx_list_append(UcxList *list, void *data);
/**
* Inserts an element at the end of the list using a UcxAllocator.
*
* See ucx_list_append() for details.
*
* @param allocator the allocator to use
* @param list the list where to append the data, or <code>NULL</code> to
* create a new list
* @param data the data to insert
* @return <code>list</code>, if it is not <code>NULL</code> or a pointer to
* the newly created list otherwise
* @see ucx_list_append()
*/
UcxList *ucx_list_append_a(UcxAllocator *allocator, UcxList *list, void *data);
/**
* Inserts an element at the beginning of the list.
*
* You <i>should</i> overwrite the old list pointer by calling
* <code>mylist = ucx_list_prepend(mylist, mydata);</code>. However, you may
* also perform successive calls of ucx_list_prepend() on the same list pointer,
* as this function always searchs for the head of the list with
* ucx_list_first().
*
* @param list the list where to insert the data or <code>NULL</code> to create
* a new list
* @param data the data to insert
* @return a pointer to the new list head
*/
UcxList *ucx_list_prepend(UcxList *list, void *data);
/**
* Inserts an element at the beginning of the list using a UcxAllocator.
*
* See ucx_list_prepend() for details.
*
* @param allocator the allocator to use
* @param list the list where to insert the data or <code>NULL</code> to create
* a new list
* @param data the data to insert
* @return a pointer to the new list head
* @see ucx_list_prepend()
*/
UcxList *ucx_list_prepend_a(UcxAllocator *allocator, UcxList *list, void *data);
/**
* Concatenates two lists.
*
* Either of the two arguments may be <code>NULL</code>.
*
* This function modifies the references to the next/previous element of
* the last/first element of <code>list1</code>/<code>
* list2</code>.
*
* @param list1 first list
* @param list2 second list
* @return if <code>list1</code> is <code>NULL</code>, <code>list2</code> is
* returned, otherwise <code>list1</code> is returned
*/
UcxList *ucx_list_concat(UcxList *list1, UcxList *list2);
/**
* Returns the first element of a list.
*
* If the argument is the list pointer, it is directly returned. Otherwise
* this function traverses to the first element of the list and returns the
* list pointer.
*
* @param elem one element of the list
* @return the first element of the list, the specified element is a member of
*/
UcxList *ucx_list_first(const UcxList *elem);
/**
* Returns the last element of a list.
*
* If the argument has no successor, it is the last element and therefore
* directly returned. Otherwise this function traverses to the last element of
* the list and returns it.
*
* @param elem one element of the list
* @return the last element of the list, the specified element is a member of
*/
UcxList *ucx_list_last(const UcxList *elem);
/**
* Returns the list element at the specified index.
*
* @param list the list to retrieve the element from
* @param index index of the element to return
* @return the element at the specified index or <code>NULL</code>, if the
* index is greater than the list size
*/
UcxList *ucx_list_get(const UcxList *list, size_t index);
/**
* Returns the index of an element.
*
* @param list the list where to search for the element
* @param elem the element to find
* @return the index of the element or -1 if the list does not contain the
* element
*/
ssize_t ucx_list_indexof(const UcxList *list, const UcxList *elem);
/**
* Returns the element count of the list.
*
* @param list the list whose elements are counted
* @return the element count
*/
size_t ucx_list_size(const UcxList *list);
/**
* Returns the index of an element containing the specified data.
*
* This function uses a cmp_func() to compare the data of each list element
* with the specified data. If no cmp_func is provided, the pointers are
* compared.
*
* If the list contains the data more than once, the index of the first
* occurrence is returned.
*
* @param list the list where to search for the data
* @param elem the element data
* @param cmpfnc the compare function
* @param data additional data for the compare function
* @return the index of the element containing the specified data or -1 if the
* data is not found in this list
*/
ssize_t ucx_list_find(UcxList *list, void *elem, cmp_func cmpfnc, void *data);
/**
* Checks, if a list contains a specific element.
*
* An element is found, if ucx_list_find() returns a value greater than -1.
*
* @param list the list where to search for the data
* @param elem the element data
* @param cmpfnc the compare function
* @param data additional data for the compare function
* @return 1, if and only if the list contains the specified element data
* @see ucx_list_find()
*/
int ucx_list_contains(UcxList *list, void *elem, cmp_func cmpfnc, void *data);
/**
* Sorts a UcxList with natural merge sort.
*
* This function uses O(n) additional temporary memory for merge operations
* that is automatically freed after each merge.
*
* As the head of the list might change, you <b>MUST</b> call this function
* as follows: <code>mylist = ucx_list_sort(mylist, mycmpfnc, mydata);</code>.
*
* @param list the list to sort
* @param cmpfnc the function that shall be used to compare the element data
* @param data additional data for the cmp_func()
* @return the sorted list
*/
UcxList *ucx_list_sort(UcxList *list, cmp_func cmpfnc, void *data);
/**
* Removes an element from the list.
*
* If the first element is removed, the list pointer changes. So it is
* <i>highly recommended</i> to <i>always</i> update the pointer by calling
* <code>mylist = ucx_list_remove(mylist, myelem);</code>.
*
* @param list the list from which the element shall be removed
* @param element the element to remove
* @return returns the updated list pointer or <code>NULL</code>, if the list
* is now empty
*/
UcxList *ucx_list_remove(UcxList *list, UcxList *element);
/**
* Removes an element from the list using a UcxAllocator.
*
* See ucx_list_remove() for details.
*
* @param allocator the allocator to use
* @param list the list from which the element shall be removed
* @param element the element to remove
* @return returns the updated list pointer or <code>NULL</code>, if the list
* @see ucx_list_remove()
*/
UcxList *ucx_list_remove_a(UcxAllocator *allocator, UcxList *list,
UcxList *element);
#ifdef __cplusplus
}
#endif
#endif /* UCX_LIST_H */