+++ /dev/null
-/*
- * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
- *
- * Copyright 2017 Mike Becker, 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 = (UcxList*) 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(const 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, const 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().
- *
- * If no destructor is specified (<code>NULL</code>), stdlib's free() is used.
- *
- * @param list the list for which the contents shall be freed
- * @param destr optional destructor function
- * @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(const 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(const 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);
-
-/**
- * Returns the union of two lists.
- *
- * The union is a list of unique elements regarding cmpfnc obtained from
- * both source lists.
- *
- * @param left the left source list
- * @param right the right source list
- * @param cmpfnc a function to compare elements
- * @param cmpdata additional data for the compare function
- * @param cpfnc a function to copy the elements
- * @param cpdata additional data for the copy function
- * @return a new list containing the union
- */
-UcxList* ucx_list_union(const UcxList *left, const UcxList *right,
- cmp_func cmpfnc, void* cmpdata,
- copy_func cpfnc, void* cpdata);
-
-/**
- * Returns the union of two lists.
- *
- * The union is a list of unique elements regarding cmpfnc obtained from
- * both source lists.
- *
- * @param allocator allocates the new list elements
- * @param left the left source list
- * @param right the right source list
- * @param cmpfnc a function to compare elements
- * @param cmpdata additional data for the compare function
- * @param cpfnc a function to copy the elements
- * @param cpdata additional data for the copy function
- * @return a new list containing the union
- */
-UcxList* ucx_list_union_a(UcxAllocator *allocator,
- const UcxList *left, const UcxList *right,
- cmp_func cmpfnc, void* cmpdata,
- copy_func cpfnc, void* cpdata);
-
-/**
- * Returns the intersection of two lists.
- *
- * The intersection contains all elements of the left list
- * (including duplicates) that can be found in the right list.
- *
- * @param left the left source list
- * @param right the right source list
- * @param cmpfnc a function to compare elements
- * @param cmpdata additional data for the compare function
- * @param cpfnc a function to copy the elements
- * @param cpdata additional data for the copy function
- * @return a new list containing the intersection
- */
-UcxList* ucx_list_intersection(const UcxList *left, const UcxList *right,
- cmp_func cmpfnc, void* cmpdata,
- copy_func cpfnc, void* cpdata);
-
-/**
- * Returns the intersection of two lists.
- *
- * The intersection contains all elements of the left list
- * (including duplicates) that can be found in the right list.
- *
- * @param allocator allocates the new list elements
- * @param left the left source list
- * @param right the right source list
- * @param cmpfnc a function to compare elements
- * @param cmpdata additional data for the compare function
- * @param cpfnc a function to copy the elements
- * @param cpdata additional data for the copy function
- * @return a new list containing the intersection
- */
-UcxList* ucx_list_intersection_a(UcxAllocator *allocator,
- const UcxList *left, const UcxList *right,
- cmp_func cmpfnc, void* cmpdata,
- copy_func cpfnc, void* cpdata);
-
-/**
- * Returns the difference of two lists.
- *
- * The difference contains all elements of the left list
- * (including duplicates) that are not equal to any element of the right list.
- *
- * @param left the left source list
- * @param right the right source list
- * @param cmpfnc a function to compare elements
- * @param cmpdata additional data for the compare function
- * @param cpfnc a function to copy the elements
- * @param cpdata additional data for the copy function
- * @return a new list containing the difference
- */
-UcxList* ucx_list_difference(const UcxList *left, const UcxList *right,
- cmp_func cmpfnc, void* cmpdata,
- copy_func cpfnc, void* cpdata);
-
-/**
- * Returns the difference of two lists.
- *
- * The difference contains all elements of the left list
- * (including duplicates) that are not equal to any element of the right list.
- *
- * @param allocator allocates the new list elements
- * @param left the left source list
- * @param right the right source list
- * @param cmpfnc a function to compare elements
- * @param cmpdata additional data for the compare function
- * @param cpfnc a function to copy the elements
- * @param cpdata additional data for the copy function
- * @return a new list containing the difference
- */
-UcxList* ucx_list_difference_a(UcxAllocator *allocator,
- const UcxList *left, const UcxList *right,
- cmp_func cmpfnc, void* cmpdata,
- copy_func cpfnc, void* cpdata);
-
-#ifdef __cplusplus
-}
-#endif
-
-#endif /* UCX_LIST_H */
-
develop.uap-core.de/git / uwplayer.git / blobdiff