diff options
Diffstat (limited to 'libparc/parc/algol/parc_ArrayList.h')
| -rw-r--r-- | libparc/parc/algol/parc_ArrayList.h | 577 |
1 files changed, 577 insertions, 0 deletions
diff --git a/libparc/parc/algol/parc_ArrayList.h b/libparc/parc/algol/parc_ArrayList.h new file mode 100644 index 00000000..1e2be6b0 --- /dev/null +++ b/libparc/parc/algol/parc_ArrayList.h @@ -0,0 +1,577 @@ +/* + * Copyright (c) 2017 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/** + * @file parc_ArrayList.h + * @ingroup datastructures + * @brief A dynamic array of void * pointers. + * + * This module implements a dynamic array of simple void pointers. + * Users can create an empty array, or preprovisioned with an initial capacity of N elements. + * + */ +#ifndef libparc_parc_ArrayList_h +#define libparc_parc_ArrayList_h + +#include <stdint.h> +#include <stdbool.h> + +#include <parc/algol/parc_List.h> +#include <parc/algol/parc_Iterator.h> + +#ifdef PARCLibrary_DISABLE_VALIDATION +# define parcArrayList_OptionalAssertValid(_instance_) +#else +# define parcArrayList_OptionalAssertValid(_instance_) parcArrayList_AssertValid(_instance_) +#endif + +struct parc_array_list; +typedef struct parc_array_list PARCArrayList; + +/** + * The mapping of a `PARCArrayList` to the generic `PARCList`. + */ +extern PARCListInterface *PARCArrayListAsPARCList; + +/** + * Determine if a `PARCArrayList` is valid. + * + * @param [in] instance A pointer to a PARCArrayList instance. + * + * @return true The instance is valid. + * @return true The instance is invalid. + * + * Example: + * @code + * { + * PARCArrayList *list = parcArrayList_Create(NULL); + * if (parcArrayList_IsValid(list)) { + * printf("The list is valid."); + * } + * parcArrayList_Destroy((list); + * @endcode + */ +bool parcArrayList_IsValid(const PARCArrayList *instance); + +/** + * Assert that a `PARCArrayList` is valid. + * + * @param [in] instance A pointer to a PARCArrayList instance. + * + * Example: + * @code + * { + * PARCArrayList *list = parcArrayList_Create(NULL); + * + * parcArrayList_AssertValid(list); + * + * parcArrayList_Destroy((list); + * @endcode + */ +void parcArrayList_AssertValid(const PARCArrayList *instance); + +/** + * Add an element to the given PARCArrayList. + * + * If the PARCArrayList was constructed with a destroyer, + * the pointer will be destroyed when element is removed or the list is destroyed. + * + * @param [in] array A pointer to a `PARCArrayList`. + * @param [in] pointer A void pointer to the item to be added to the list. + * + * @return True If the value was successfully added to the list. + * @return False Otherwise + * + * Example: + * @code + * { + * PARCArrayList *array = parcArrayList_Create(parcArrayList_StdlibFreeFunction); + * void *elements[] = { + * strdup("a"), + * strdup("b"), + * strdup("c"), + * }; + * + * bool wasAdded = parcArrayList_Add(array, elements); + * printf("Successfully added the base pointer? %d\n", wasAdded); + * + * ... + * + * parcArrayList_Destroy(&array); + * } + * @endcode + */ +bool parcArrayList_Add(PARCArrayList *array, const void *pointer); + +/** + * Add all of the pointers in the given array of pointers to the `PARCArrayList`. + * + * This is synonymous with calling {@link parcArrayList_Add()} multiple times + * + * @param [in] array A pointer to `PARCArrayList`. + * @param [in] argv A pointer to the base list of pointers. + * @param [in] argc The number of items to add to the list, starting from the abse void pointer. + * + * @return A pointer to the modified PARCArrayList. + * + * Example: + * @code + * { + * PARCArrayList *array = parcArrayList_Create(parcArrayList_StdlibFreeFunction); + * void *elements[] = { + * strdup("a"), + * strdup("b"), + * strdup("c"), + * }; + * + * parcArrayList_AddAll(array, elements, 3); + * + * ... + * + * parcArrayList_Destroy(&array); + * } + * @endcode + */ +PARCArrayList *parcArrayList_AddAll(PARCArrayList *array, void **argv, size_t argc); + +/** + * Remove an element at a specific index from a `PARCArrayList`. + * + * The element is destroyed via the function provided when calling {@link parcArrayList_Create()}. + * The index must be 0 <= index < length. + * + * @param [in,out] array A pointer to `PARCArrayList`. + * @param [in] index The index of the element to remove and destroy. + * + * @return A pointer to the modified `PARCArrayList`. + * + * Example: + * @code + * { + * PARCArrayList *array = parcArrayList_Create(parcArrayList_StdlibFreeFunction); + * void *elements[] = { + * strdup("a"), + * strdup("b"), + * strdup("c"), + * }; + * + * parcArrayList_AddAll(array, elements, 3); + * parcArrayList_RemoveAndDestroyAtIndex(array, 0); + * + * size_t size = parcArrayList_Size(array); + * // size will now be three + * + * ... + * + * parcArrayList_Destroy(&array); + * } + * @endcode + */ +PARCArrayList *parcArrayList_RemoveAndDestroyAtIndex(PARCArrayList *array, size_t index); + +/** + * Return the element at index. Remove the element from the array. + * + * The index must be 0 <= index < length. + * + * @param [in,out] array A pointer to a `PARCArrayList` instance. + * @param [in] index The index of the element to remove. + * + * @return void* A pointer (void *) to the element that was removed. + * + * Example: + * @code + * { + * PARCArrayList *array = parcArrayList_Create(parcArrayList_StdlibFreeFunction); + * void *elements[] = { + * strdup("a"), + * strdup("b"), + * strdup("c"), + * }; + * + * parcArrayList_AddAll(array, elements, 3); + * void *firstString = parcArrayList_RemoveAtIndex(array, 0); + * + * printf("First string: %s\n", firstString); + * + * ... + * + * parcArrayList_Destroy(&array); + * } + * @endcode + */ +void *parcArrayList_RemoveAtIndex(PARCArrayList *array, size_t index); + +/** + * Insert an element at the index location. Elements will be moved up if required. + * + * You may not insert beyond the list end. (You can insert at the end, but not any more). + * + * @param [in,out] array A `PARCArrayList` + * @param [in] pointer A pointer to the element to insert + * @param [in] index An index in the `PARCArrayList` + * @return A pointer to the modified `PARCArrayList` + * + * Example: + * @code + * { + * PARCArrayList *array = parcArrayList_Create(parcArrayList_StdlibFreeFunction); + * + * parcArrayList_InsertAtIndex(array, strdup("a"), 0); + * void *firstString = parcArrayList_RemoveAtIndex(array, 0); + * printf("First string is 'a': %s\n", firstString); + * + * ... + * + * parcArrayList_Destroy(&array); + * } + * @endcode + */ +PARCArrayList *parcArrayList_InsertAtIndex(PARCArrayList *array, size_t index, const void *pointer); + +/** + * Create an instance of an empty `PARCArrayList`. + * + * @param [in] destroyElement + * A pointer to a function that will destroy (or equivalent) the element pointed to by `element` + * + * @return A pointer to the new `PARCArrayList` instance, or NULL if no memory could be allocated. + * + * Example: + * @code + * { + * PARCArrayList *array = parcArrayList_Create(parcArrayList_StdlibFreeFunction); + * ... + * } + * @endcode + */ +PARCArrayList *parcArrayList_Create(void (*destroyElement)(void **elementAddress)); + +/** + * Create an instance of a PARCArrayList pre-provisioned to contain the specified number of elements. + * + * @param [in] equalsElement + * A pointer to a function that will determine equality between two elements in the array. + * @param [in] destroyElement + * A pointer to a function that will destroy (or equivalent) the element pointed to by <code>element</code> + * @param [in] size + * The number of initial elements to provision for. + * @return A pointer to a new `PARCArrayList` instance, or NULL if no memory could be allocated. + * + * Example: + * @code + * <#example#> + * @endcode + */ +PARCArrayList *parcArrayList_Create_Capacity(bool (*equalsElement)(void *x, void *y), void (*destroyElement)(void **elementAddress), size_t size); + +/** + * Copy a `PARCArrayList` instance. + * + * Create a new `PARCArrayList` instance with the same structure and content as the original. + * + * @param [in] array A pointer to a `PARCArrayList` instance to copy. + * + * @return A pointer to a new `PARCArrayList` instance with a copy of the original, or NULL if no memory could be allocated. + * + * Example: + * @code + * { + * PARCArrayList *array = parcArrayList_Create(parcArrayList_StdlibFreeFunction); + * parcArrayList_InsertAtIndex(array, strdup("a"), 0); + * + * PARCArrayList *sameList = parcArrayList_Copy(array); + * + * if (parcArrayList_Equals(array, sameList)) { + * // true + * } else { + * // false + * } + * + * parcArrayList_Destroy(&array); + * } + * @endcode + */ +PARCArrayList *parcArrayList_Copy(const PARCArrayList *array); + +/** + * Destroy a `PARCArrayList` instance. + * + * Destroy the given `PARCArrayList` by freeing all memory used by it. + * + * @param [in,out] arrayPtr A pointer to the pointer of the `PARCArrayList` to be destroyed. + * + * Example: + * @code + * { + * PARCArrayList *array = parcArrayList_Create(parcArrayList_StdlibFreeFunction); + * + * ... + * + * parcArrayList_Destroy(&array); + * } + * @endcode + */ +void parcArrayList_Destroy(PARCArrayList **arrayPtr); + +/** + * Set an element from the given `PARCArrayList` at a specified index to a value. + * + * The index must be 0 <= index < length. + * + * @param [in] array A pointer to a `PARCArrayList` instance. + * @param [in] index The index into the `PARCArrayList` instance. + * @param [in] pointer A void pointer to the item to be assigned to the index + * + * Example: + * @code + * { + * PARCArrayList *array = parcArrayList_Create(parcArrayList_StdlibFreeFunction); + * void *elements[] = { + * strdup("a"), + * strdup("b"), + * strdup("c"), + * }; + * + * bool wasAdded = parcArrayList_Add(array, elements); + * // how to free the pointer at index 1 without deallocating the slot? XXX + * parcArrayList_Set(array, 1, strdup("d"); + * parcArrayList_Destroy(&array); + * } + * @endcode + */ +void parcArrayList_Set(const PARCArrayList *array, size_t index, void *pointer); + +/** + * Get an element from the given `PARCArrayList` at a specified index. + * + * The index must be 0 <= index < length. + * + * @param [in] array A pointer to a `PARCArrayList` instance. + * @param [in] index The index into the `PARCArrayList` instance. + * + * @return A pointer (void *) to the element in the list. + * + * Example: + * @code + * { + * PARCArrayList *array = parcArrayList_Create(parcArrayList_StdlibFreeFunction); + * void *elements[] = { + * strdup("a"), + * strdup("b"), + * strdup("c"), + * }; + * + * parcArrayList_AddAll(array, elements, 3); + * void *firstString = parcArrayList_Get(array, 0); + * + * printf("First string: %s\n", firstString); + * + * ... + * + * parcArrayList_Destroy(&array); + * } + * @endcode + */ +void *parcArrayList_Get(const PARCArrayList *array, size_t index); + +/** + * Return the number of elements in the given `PARCArrayList`. + * + * The size is the number of elements, NOT the size in bytes of all elements maintained in the list. + * + * @param [in] array A pointer to a `PARCArrayList` instance. + * + * @return A size_t of the number of elements in the given `PARCArrayList`. + * + * Example: + * @code + * { + * PARCArrayList *array = parcArrayList_Create(parcArrayList_StdlibFreeFunction); + * void *elements[] = { + * strdup("a"), + * strdup("b"), + * strdup("c"), + * }; + * + * parcArrayList_AddAll(array, elements, 3); + * + * size_t size = parcArrayList_Size(array); + * printf("Size =?= 3: %d\n", size == 3); + * + * parcArrayList_Destroy(&array); + * } + * @endcode + */ +size_t parcArrayList_Size(const PARCArrayList *array); + +/** + * Determine if two `PARCArrayList` instances are equal. + * + * The following equivalence relations on non-null `PARCArrayList` instances are maintained: + * + * * It is reflexive: for any non-null reference value x, parcArrayList_Equals(x, x) must return true. + * + * * It is symmetric: for any non-null reference values x and y, parcArrayList_Equals(x, y) must return true if and only if + * parcArrayList_Equals(y x) returns true. + * + * * It is transitive: for any non-null reference values x, y, and z, if + * parcArrayList_Equals(x, y) returns true and + * parcArrayList_Equals(y, z) returns true, + * then parcArrayList_Equals(x, z) must return true. + * + * * It is consistent: for any non-null reference values x and y, multiple invocations of parcArrayList_Equals(x, y) + * consistently return true or consistently return false. + * + * * For any non-null reference value x, parcArrayList_Equals(x, NULL)) must return false. + * + * @param [in] a The first `PARCArrayList` instance. + * @param [in] b The second `PARCArrayList` instance. + * + * @return true the given PARCArrayList instances are equal. + * @return false the given PARCArrayList instances are not equal. + * + * Example: + * @code + * { + * PARCArrayList *a = parcArrayList_Create(); + * PARCArrayList *b = parcArrayList_Create(); + * + * if (parcArrayList_Equals(a, b)) { + * // true + * } else { + * // false + * } + * } + * @endcode + */ +bool parcArrayList_Equals(const PARCArrayList *a, const PARCArrayList *b); + +/** + * Standard library free(3) wrapper for use as a destructor function for elements of a `PARCArrayList`. + * + * The create functions for `PARCArrayList` have an input parameter that is a pointer to a function that + * will be called for each element when the `PARCArrayList` is destroyed, and when an element is removed via + * {@link parcArrayList_RemoveAndDestroyAtIndex}. + * This destroy function has a different calling signature than the standard library's free(3) function. + * This function is a wrapper providing the correct facade for the standard library free(3) function. + * + * @param [in,out] element A pointer to the element to be destroyed. + * + * Example: + * @code + * <#example#> + * @endcode + */ +void parcArrayList_StdlibFreeFunction(void **element); + +/** + * PARC_Memory free() wrapper for use as a destructor function for elements of a `PARCArrayList`. + * + * The create functions for `PARCArrayList` have an input parameter that is a pointer to a function that + * will be called for each element when the `PARCArrayList` is destroyed, and when an element is removed via + * {@link parcArrayList_RemoveAndDestroyAtIndex}. + * This destroy function has a different calling signature than the PARC_Memory's free(3) function. + * This function is a wrapper providing the correct facade for the PARC_Memory's free(3) function. + * + * @param [in,out] elementPtr A pointer to the element to be destroyed. + * + * Example: + * @code + * <#example#> + * @endcode + */ +void parcArrayList_PARCMemoryFreeFunction(void **elementPtr); + +/** + * Tests if this list is empty. + * + * + * @param [in] list A pointer to the `PARCArrayList` to test. + * @return true if the stack is empty. + * + * Example: + * @code + * <#example#> + * @endcode + */ +bool parcArrayList_IsEmpty(const PARCArrayList *list); + +/** + * Returns a pointer to object at the top of this stack without removing it from the stack. + * + * @param [in] list A pointer to `PARCArrayList`. + * @return A pointer to the first element of the `PARCArrayList`. + * + * Example: + * @code + * <#example#> + * @endcode + */ +void *parcArrayList_Peek(const PARCArrayList *list); + +/** + * Removes the object at the top of this stack and returns that object as the value of this function. + * + * @param [in,out] list A pointer to the `PARCArrayList`. + * @return A pointer to what was the first element of the `PARCArrayList`. + * + * Example: + * @code + * <#example#> + * @endcode + */ +void *parcArrayList_Pop(PARCArrayList *list); + +/** + * Removes all objects from this stack. + * + * @param [in,out] list A pointer to the `PARCArrayList`. + * + * Example: + * @code + * <#example#> + * @endcode + */ +void parcArrayList_Clear(PARCArrayList *list); + +/** + * Pushes an item onto the top of this stack. + * + * @param [in,out] list A pointer to a `PARCArrayList`. + * @param [in] item A pointer to an element to be added to the `PARCArrayList`. + * @return A pointer to the item just pushed on to the `PARCArrayLis. + * + * Example: + * @code + * <#example#> + * @endcode + */ +void *parcArrayList_Push(PARCArrayList *list, void *item); + +/** + * Returns the 1-based position where an object is on this stack. + * + * @param [in] list A pointer to `PARCArrayList`. + * @param [in] element A pointer to the element to locate in the `PARCArrayList`. + * @return int The index of the located element in the `PARCArrayList` + * + * Example: + * @code + * <#example#> + * @endcode + */ +int parcArrayList_Search(PARCArrayList *list, void *element); +#endif // libparc_parc_ArrayList_h |