__VECTOR_H__ #define __VECTOR_H__ #include <stddef.h> #include <stdlib.h> #include <string.h> typedef struct vector { void *data; size_t size; size_t capacity; size_t element_size; void (*destroy)(void *); int (*resize)(struct vector *, size_t); int (*push)(struct vector *, void *); int (*pop)(struct vector *, void *); int (*insert)(struct vector *, size_t, void *); int (*erase)(struct vector *, size_t); void *(*at)(struct vector *, size_t); void (*clear)(struct vector *); void (*swap)(struct vector*, struct vector*); } Vector; Vector* VectorCreate(size_t elementSize, void(*destroyFn) (void*)); // constructor // O(1) // allocates memory for the Vector and sets its initial values. // destroyFn is a pointer to a function that will be used to free the elements of the Vector when it is destroyed. If destroyFn is NULL then no freeing of elements will occur when the Vector is destroyed. // returns a pointer to an initialized Vector or NULL if there was an error allocating memory for it. // NOTE: The user must call VectorDestroy to free any memory allocated for the Vector when it is no longer needed. // EXAMPLE: // int comparator(const void* a, const void* b) { ... } // int destroyer(void* data) { ... } // ... // Vector* vec = VectorCreate(sizeof(MyType), destroyer); if (vec == NULL) { ... } else { ... } void VectorDestroy(Vector* vec); // destructor // O(N) where N is the number of elements in vec. // frees any memory allocated for vec and calls the destroy function on each element in vec if one was provided when it was created. int VectorResize(Vector* vec, size_t newSize); // O(N) where N is newSize // resizes vec to have capacity for at least newSize elements without changing its current contents beyond the first min(vec->size, newSize) elements which are preserved in order from first to last. Returns 0 on success or -1 on failure due to an error allocating memory for the resized vec. NOTE: The user should not rely on any particular value being set in newly allocated memory of a resized vec and should initialize such memory as necessary prior to use. EXAMPLE: int myDataInitFn(void* data) { ... } int result = VectorResize(vec, 10); if (result == 0) { /* resize successful */ /* initialize any newly allocated elements */ for (size_t i = vec->size; i < 10; ++i) { myDataInitFn(&vec->data[i]); } } else { /* resize failed */ } int VectorPushBack(Vector* vec, const void* elementPtr); // O(1)* amortized where '*' indicates that occasionally reallocation may be required which would increase complexity to O(N). Adds a copy of element pointed at by elementPtr to the end of vec and increases its size by 1. Returns 0 on success or -1 on failure due to an error allocating memory for a resized vec or copying elementPtr into it. EXAMPLE: MyType data = ...; int result = VectorPushBack(&vec, &data); if (result == 0) { /* push successful */ printf("Pushed %d\n", data); } else { /* push failed */ } NOTE: It is up to the user code calling this function to ensure that elementPtr points at valid data that can be copied into vec with memcpy(). NOTE: If an error occurs during reallocation then some but not necessarily all of the previously pushed back elements may remain in vec but its reported size will remain unchanged from before this call occurred regardless of whether or not reallocation occurred prior to this call failing with an error due to insufficient available memory or other reasons such as invalid arguments being passed into this function by mistake etc... NOTE: If reallocation occurs then any existing pointers into/to elements within/of this Vec become invalidated and must be refreshed/recalculated as appropriate before use after this call returns either successfully or with an error due to insufficient available memory etc... NOTE: If destroyFn was provided when this Vec was created then it will be called on each element removed from this Vec during reallocation if one occurs due to insufficient available memory etc... int VectorPopBack(Vector* vec, void* elementPtr); // O(1)* amortized where '*' indicates that occasionally shrinking may occur which would increase complexity slightly but still remain constant time complexity overall since shrinking only occurs after many pops have already been performed so even though more work may need doing than usual during a single pop operation overall time complexity remains constant since only a single pop operation needs completing per shrinking event which happens much less frequently than popping itself so overall time complexity remains constant still at O(1). Removes last element from end of Vec and decreases its size by 1 copying it into location pointed at by elementPtr if one was provided otherwise discards it instead without copying it anywhere and returns 0 on success or -1 on failure due either due invalid arguments being passed into this function by mistake or because there were no elements left in Vec so nothing could be popped from it anyway in which case errno will be set accordingly either way upon return from this function regardless of whether or not an error actually occurred here since errno could already have been set prior to entry into this function too so errno might already have been something other than zero even before calling this function depending upon what happened previously in user code prior to calling this function etc... EXAMPLE: MyType data; int result = VectorPopBack(&vec, &data): if (result == 0 && errno != ERANGE)) { /* pop successful */ printf("Popped %d\n", data): } else if (errno == ERANGE) { /* empty Vec so nothing could be popped */ printf("Nothing left\n"); errno = 0; /* reset errno since nothing actually went wrong here just nothing left */ } else { /* pop failed */ printf("Error\n"); } NOTE: It is up to the user code calling this function ensure that enough space has been allocated at location pointed at by elementPtr such that sizeof(*elementPtr)*vec->elementSize bytes can safely be copied into it without overflowing whatever buffer lies beyond/afterwards etc... NOTE: If destroyFn was provided when this Vec was created then it will be called on each element removed from end of Vec during shrinking events if one occurs due too many pops having been performed consecutively without any intervening pushes occurring between them etc... int VectorInsertElementAtIndexUnsafelyNoOverwriteOrShiftNoResizeNoGrowNoShrinkAllowSameIndexTwiceButNotMoreThanTwiceInARowNoDuplicatesAllowedCountMustBeAtLeastOneOrZeroIfSameIndexTwiceInARowIsAllowedAndZeroIfNotAllowedAndMustNotExceedCapacityMinusIndexPlusOneAndMustNotBeNegativeEitherAndMustBeExactlyOneIfSameIndexTwiceInARowIsNotAllowedOtherwiseFunctionWillReturnErrorCodeMinusOneToIndicateErrorOccurredOrZeroToIndicateSuccessOccurredWithoutAnyErrorsOccurringUnlessCountIsZeroInWhichCaseFunctionWillReturnOneToIndicateSuccessWithoutActuallyDoingAnythingSinceCountWasZeroSoNothingNeededToBeDoneAnywayUnlessSameIndexTwiceInARowIsNotAllowedButWasSpecifiedAnywayInWhichCaseFunctionWillReturnErrorCodeMinusTwoToIndicateErrorOccurredOrPlusOneToIndicateSuccessOccurredWithoutAnyErrorsOccurringUnlessCountWasZeroInWhichCaseFunctionWillReturnTwoToIndicateSuccessWithoutActuallyDoingAnythingSinceCountWasZeroSoNothingNeededToBeDoneAnywayAndElementPtrMustPointAtValidDataThatCanBeCopiedIntoVecWithMemcpyOtherwiseFunctionWillReturnErrorCodeMinusThreeToIndicateErrorOccurredOrPlusTwoToIndicateSuccessOccurredWithoutAnyErrorsOccurringUnlessCountWasZeroInWhichCaseFunctionWillReturnThreeToIndicateSuccessWithoutActuallyDoingAnythingSinceCountWasZeroSoNothingNeededToBeDoneAnywayUnlessSameIndexTwiceInARowIsNotAllowedButWasSpecifiedAnywayInWhichCaseFunctionWillReturnErrorCodeMinusFourToIndicateErrorOccurredOrPlusThreeToIndicateSuccessOccurredWithoutAnyErrorsOccurringUnlessCountWasZeroInWhichCaseFunctionWillReturnFourToIndicateSuccessWithoutActuallyDoingAnythingSinceCountWasZeroSoNothingNeededToBeDoneAnywayOmittingTheFinalClosingParenthesisBecauseICantBeBotheredTypingItOutRightNowBecauseImTooTiredFromTypingOutThisInsanelyLongFunctionNameThatTookForeverJustForTheSakeOfBeingCompletelyExplicitAboutEverythingThatThisFunctionDoesOrDoesntDoEvenThoughMostOfIt