X-Git-Url: https://develop.uap-core.de/gitweb/uwplayer.git/blobdiff_plain/83d9f3aaf8206aa081ead0ff630a1c33ed670d71..848befbcc166fff6fdde6a635cf7a31f9f9185e0:/ucx/ucx/array.h diff --git a/ucx/ucx/array.h b/ucx/ucx/array.h deleted file mode 100644 index 5b02ebf..0000000 --- a/ucx/ucx/array.h +++ /dev/null @@ -1,460 +0,0 @@ -/* - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. - * - * Copyright 2019 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. - */ -/** - * Dynamically allocated array implementation. - * - * @file array.h - * @author Mike Becker - * @author Olaf Wintermann - */ - -#ifndef UCX_ARRAY_H -#define UCX_ARRAY_H - -#include "ucx.h" -#include "allocator.h" - -#ifdef __cplusplus -extern "C" { -#endif - -/** - * UCX array type. - */ -typedef struct { - /** - * The current capacity of the array. - */ - size_t capacity; - /** - * The actual number of elements in the array. - */ - size_t size; - /** - * The size of an individual element in bytes. - */ - size_t elemsize; - /** - * A pointer to the data. - */ - void* data; - /** - * The allocator used for the data. - */ - UcxAllocator* allocator; -} UcxArray; - -/** - * Sets an element in an arbitrary user defined array. - * The data is copied from the specified data location. - * - * If the capacity is insufficient, the array is automatically reallocated and - * the possibly new pointer is stored in the array argument. - * - * On reallocation the capacity of the array is doubled until it is sufficient. - * The new capacity is stored back to capacity. - * - * @param array a pointer to location of the array pointer - * @param capacity a pointer to the capacity - * @param elmsize the size of each element - * @param idx the index of the element to set - * @param data a pointer to the element data - * @return zero on success or non-zero on error (errno will be set) - */ -#define ucx_array_util_set(array, capacity, elmsize, idx, data) \ - ucx_array_util_set_a(ucx_default_allocator(), (void**)(array), capacity, \ - elmsize, idx, data) - -/** - * Sets an element in an arbitrary user defined array. - * The data is copied from the specified data location. - * - * If the capacity is insufficient, the array is automatically reallocated - * using the specified allocator and the possibly new pointer is stored in - * the array argument. - * - * On reallocation the capacity of the array is doubled until it is sufficient. - * The new capacity is stored back to capacity. - * - * @param alloc the allocator that shall be used to reallocate the array - * @param array a pointer to location of the array pointer - * @param capacity a pointer to the capacity - * @param elmsize the size of each element - * @param idx the index of the element to set - * @param data a pointer to the element data - * @return zero on success or non-zero on error (errno will be set) - */ -int ucx_array_util_set_a(UcxAllocator* alloc, void** array, size_t* capacity, - size_t elmsize, size_t idx, void* data); - -/** - * Stores a pointer in an arbitrary user defined array. - * The element size of the array must be sizeof(void*). - * - * If the capacity is insufficient, the array is automatically reallocated and - * the possibly new pointer is stored in the array argument. - * - * On reallocation the capacity of the array is doubled until it is sufficient. - * The new capacity is stored back to capacity. - * - * @param array a pointer to location of the array pointer - * @param capacity a pointer to the capacity - * @param idx the index of the element to set - * @param ptr the pointer to store - * @return zero on success or non-zero on error (errno will be set) - */ -#define ucx_array_util_setptr(array, capacity, idx, ptr) \ - ucx_array_util_setptr_a(ucx_default_allocator(), (void**)(array), \ - capacity, idx, ptr) - -/** - * Stores a pointer in an arbitrary user defined array. - * The element size of the array must be sizeof(void*). - * - * If the capacity is insufficient, the array is automatically reallocated - * using the specified allocator and the possibly new pointer is stored in - * the array argument. - * - * On reallocation the capacity of the array is doubled until it is sufficient. - * The new capacity is stored back to capacity. - * - * @param alloc the allocator that shall be used to reallocate the array - * @param array a pointer to location of the array pointer - * @param capacity a pointer to the capacity - * @param idx the index of the element to set - * @param ptr the pointer to store - * @return zero on success or non-zero on error (errno will be set) - */ -int ucx_array_util_setptr_a(UcxAllocator* alloc, void** array, size_t* capacity, - size_t idx, void* ptr); - - -/** - * Creates a new UCX array with the given capacity and element size. - * @param capacity the initial capacity - * @param elemsize the element size - * @return a pointer to a new UCX array structure - */ -UcxArray* ucx_array_new(size_t capacity, size_t elemsize); - -/** - * Creates a new UCX array using the specified allocator. - * - * @param capacity the initial capacity - * @param elemsize the element size - * @param allocator the allocator to use - * @return a pointer to new UCX array structure - */ -UcxArray* ucx_array_new_a(size_t capacity, size_t elemsize, - UcxAllocator* allocator); - -/** - * Initializes a UCX array structure with the given capacity and element size. - * The structure must be uninitialized as the data pointer will be overwritten. - * - * @param array the structure to initialize - * @param capacity the initial capacity - * @param elemsize the element size - */ -void ucx_array_init(UcxArray* array, size_t capacity, size_t elemsize); - -/** - * Initializes a UCX array structure using the specified allocator. - * The structure must be uninitialized as the data pointer will be overwritten. - * - * @param array the structure to initialize - * @param capacity the initial capacity - * @param elemsize the element size - * @param allocator the allocator to use - */ -void ucx_array_init_a(UcxArray* array, size_t capacity, size_t elemsize, - UcxAllocator* allocator); - -/** - * Creates an shallow copy of an array. - * - * This function clones the specified array by using memcpy(). - * If the destination capacity is insufficient, an automatic reallocation is - * attempted. - * - * Note: if the destination array is uninitialized, the behavior is undefined. - * - * @param dest the array to copy to - * @param src the array to copy from - * @return zero on success, non-zero on reallocation failure. - */ -int ucx_array_clone(UcxArray* dest, UcxArray const* src); - - -/** - * Compares two UCX arrays element-wise by using a compare function. - * - * Elements of the two specified arrays 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. - * - * This function always returns zero, if the element sizes of the arrays do - * not match and performs no comparisons in this case. - * - * @param array1 the first array - * @param array2 the second array - * @param cmpfnc the compare function - * @param data additional data for the compare function - * @return 1, if and only if the two arrays equal element-wise, 0 otherwise - */ -int ucx_array_equals(UcxArray const *array1, UcxArray const *array2, - cmp_func cmpfnc, void* data); - -/** - * Destroys the array. - * - * The data is freed and both capacity and count are reset to zero. - * If the array structure itself has been dynamically allocated, it has to be - * freed separately. - * - * @param array the array to destroy - */ -void ucx_array_destroy(UcxArray *array); - -/** - * Destroys and frees the array. - * - * @param array the array to free - */ -void ucx_array_free(UcxArray *array); - -/** - * Inserts elements at the end of the array. - * - * This is an O(1) operation. - * The array will automatically grow, if the capacity is exceeded. - * If a pointer to data is provided, the data is copied into the array with - * memcpy(). Otherwise the new elements are completely zeroed. - * - * @param array a pointer the array where to append the data - * @param data a pointer to the data to insert (may be NULL) - * @param count number of elements to copy from data (if data is - * NULL, zeroed elements are appended) - * @return zero on success, non-zero if a reallocation was necessary but failed - * @see ucx_array_set_from() - * @see ucx_array_append() - */ -int ucx_array_append_from(UcxArray *array, void *data, size_t count); - - -/** - * Inserts elements at the beginning of the array. - * - * This is an expensive operation, because the contents must be moved. - * If there is no particular reason to prepend data, you should use - * ucx_array_append_from() instead. - * - * @param array a pointer the array where to prepend the data - * @param data a pointer to the data to insert (may be NULL) - * @param count number of elements to copy from data (if data is - * NULL, zeroed elements are inserted) - * @return zero on success, non-zero if a reallocation was necessary but failed - * @see ucx_array_append_from() - * @see ucx_array_set_from() - * @see ucx_array_prepend() - */ -int ucx_array_prepend_from(UcxArray *array, void *data, size_t count); - - -/** - * Sets elements starting at the specified index. - * - * If the any index is out of bounds, the array automatically grows. - * The pointer to the data may be NULL, in which case the elements are zeroed. - * - * @param array a pointer the array where to set the data - * @param index the index of the element to set - * @param data a pointer to the data to insert (may be NULL) - * @param count number of elements to copy from data (if data is - * NULL, the memory in the array is zeroed) - * @return zero on success, non-zero if a reallocation was necessary but failed - * @see ucx_array_append_from() - * @see ucx_array_set() - */ -int ucx_array_set_from(UcxArray *array, size_t index, void *data, size_t count); - -/** - * Concatenates two arrays. - * - * The contents of the second array are appended to the first array in one - * single operation. The second array is otherwise left untouched. - * - * The first array may grow automatically. If this fails, both arrays remain - * unmodified. - * - * @param array1 first array - * @param array2 second array - * @return zero on success, non-zero if reallocation was necessary but failed - * or the element size does not match - */ -int ucx_array_concat(UcxArray *array1, const UcxArray *array2); - -/** - * Returns a pointer to the array element at the specified index. - * - * @param array the array to retrieve the element from - * @param index index of the element to return - * @return a pointer to the element at the specified index or NULL, - * if the index is greater than the array size - */ -void *ucx_array_at(UcxArray const* array, size_t index); - -/** - * 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, memcmp() is used. - * - * If the array contains the data more than once, the index of the first - * occurrence is returned. - * If the array does not contain the data, the size of array is returned. - * - * @param array the array 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 the size of - * the array, if the data is not found in this array - */ -size_t ucx_array_find(UcxArray const *array, void *elem, - cmp_func cmpfnc, void *data); - -/** - * Checks, if an array contains a specific element. - * - * An element is found, if ucx_array_find() returns a value less than the size. - * - * @param array the array 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 array contains the specified element data - * @see ucx_array_find() - */ -int ucx_array_contains(UcxArray const *array, void *elem, - cmp_func cmpfnc, void *data); - -/** - * Sorts a UcxArray with the best available sort algorithm. - * - * The qsort_r() function is used, if available (glibc, FreeBSD or MacOS). - * The order of arguments is automatically adjusted for the FreeBSD and MacOS - * version of qsort_r(). - * - * If qsort_r() is not available, a merge sort algorithm is used, which is - * guaranteed to use no more additional memory than for exactly one element. - * - * @param array the array to sort - * @param cmpfnc the function that shall be used to compare the element data - * @param data additional data for the cmp_func() or NULL - */ -void ucx_array_sort(UcxArray* array, cmp_func cmpfnc, void *data); - -/** - * Removes an element from the array. - * - * This is in general an expensive operation, because several elements may - * be moved. If the order of the elements is not relevant, use - * ucx_array_remove_fast() instead. - * - * @param array pointer to the array from which the element shall be removed - * @param index the index of the element to remove - */ -void ucx_array_remove(UcxArray *array, size_t index); - -/** - * Removes an element from the array. - * - * This is an O(1) operation, but does not maintain the order of the elements. - * The last element in the array is moved to the location of the removed - * element. - * - * @param array pointer to the array from which the element shall be removed - * @param index the index of the element to remove - */ -void ucx_array_remove_fast(UcxArray *array, size_t index); - -/** - * Shrinks the memory to exactly fit the contents. - * - * After this operation, the capacity equals the size. - * - * @param array a pointer to the array - * @return zero on success, non-zero if reallocation failed - */ -int ucx_array_shrink(UcxArray* array); - -/** - * Sets the capacity of the array. - * - * If the new capacity is smaller than the size of the array, the elements - * are removed and the size is adjusted accordingly. - * - * @param array a pointer to the array - * @param capacity the new capacity - * @return zero on success, non-zero if reallocation failed - */ -int ucx_array_resize(UcxArray* array, size_t capacity); - -/** - * Resizes the array only, if the capacity is insufficient. - * - * If the requested capacity is smaller than the current capacity, this - * function does nothing. - * - * @param array a pointer to the array - * @param capacity the guaranteed capacity - * @return zero on success, non-zero if reallocation failed - */ -int ucx_array_reserve(UcxArray* array, size_t capacity); - -/** - * Resizes the capacity, if the specified number of elements would not fit. - * - * A call to ucx_array_grow(array, count) is effectively the same as - * ucx_array_reserve(array, array->size+count). - * - * @param array a pointer to the array - * @param count the number of elements that should additionally fit - * into the array - * @return zero on success, non-zero if reallocation failed - */ -int ucx_array_grow(UcxArray* array, size_t count); - - -#ifdef __cplusplus -} -#endif - -#endif /* UCX_ARRAY_H */ -