Skip to content
Generic contiguous dynamically-allocated array.
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
src
test
web
Makefile
readme.md

readme.md

Array.h

2016 Neil Edelman, distributed under the terms of the MIT License; see [ https://opensource.org/licenses/MIT ].

Array is a dynamic contiguous array that stores , which must be set using ARRAY_TYPE. The capacity is greater then or equal to the size, and resizing incurs amortised cost. When adding new elements, the elements may change memory location to fit, it is therefore unstable; any pointers to this memory become stale and unusable.

Array is not synchronised. Errors are returned with errno. The parameters are preprocessor macros, and are all undefined at the end of the file for convenience. assert.h is included in this file; to stop the debug assertions, use #define NDEBUG before inclusion.

States

parameter: ARRAY_NAME, ARRAY_TYPE -- The name that literally becomes , and a valid type associated therewith, accessible to the compiler at the time of inclusion; should be conformant to naming and to the maximum available length of identifiers. Must each be present before including.

parameter: ARRAY_STACK -- Doesn't define removal functions except <T>ArrayPop, making it a stack.

parameter: ARRAY_TO_STRING -- Optional print function implementing ToString; makes available <T>ArrayToString.

parameter: ARRAY_TEST -- Unit testing framework using ArrayTest, included in a separate header, ../test/ArrayTest.h. Must be defined equal to a (random) filler function, satisfying Action. Requires ARRAY_TO_STRING and not NDEBUG.

minimum standard: C89

author: Neil

version: 2019-05 Added <T>ArrayReplace and <T>ArrayBuffer.

since: 2018-03 Renamed Pool to Array. Took out migrate.

Declarations

typedef void (*ToString)(const T *, char (*const)[12])

typedef void (*ToString)(const T *, char (*const)[12])

Responsible for turning (the first argument) into a 12 char null-terminated output string (the second.) Used for ARRAY_TO_STRING.

struct Array

struct Array

The array. Zeroed data is a valid state. To instantiate explicitly, see <T>Array or initialise it with ARRAY_INIT or _0_ (C99.)

Function Summary

Return Type Function Name Argument List
static void Array_ (struct Array *const a)
static void Array (struct Array *const a)
static size_t ArraySize (const struct Array *const a)
static int ArrayRemove (struct Array *const a, T *const data)
static int ArrayTailRemove (struct Array *const a, T *const data)
static void ArrayClear (struct Array *const a)
static T * ArrayGet (const struct Array *const a)
static T * ArrayEnd (const struct Array *const a)
static size_t ArrayIndex (const struct Array *const a, const T *const data)
static T * ArrayPeek (const struct Array *const a)
static T * ArrayPop (struct Array *const a)
static T * ArrayBack (const struct Array *const a, const T *const here)
static T * ArrayNext (const struct Array *const a, const T *const here)
static T * ArrayNew (struct Array *const a)
static T * ArrayUpdateNew (struct Array *const a, T **const update_ptr)
static T * ArrayBuffer (struct Array *const a, const size_t buffer)
static int ArrayAddSize (struct Array *const a, const size_t add)
static void ArrayForEach (struct Array *const a, const Action action)
static void ArrayIfEach (struct Array *const a, const Predicate predicate, const Action action)
static void ArrayKeepIf (struct Array *const a, const Predicate keep)
static void ArrayTrim (struct Array *const a, const Predicate predicate)
static int ArrayReplace (struct Array *const a, const T *anchor, const long range, const struct Array *const b)
static int ArrayIndexReplace (struct Array *const a, const size_t i0, const size_t i1, const struct Array *const b)
static const char * ArrayToString (const struct Array *const a)

Function Detail

Array_

static void Array_(struct Array *const a)

Destructor for a; returns an initialised a to the empty state where it takes no memory.

parameter: a -- If null, does nothing.

order: \Theta(1)

Array

static void Array(struct Array *const a)

Initialises a to be empty.

order: \Theta(1)

ArraySize

static size_t ArraySize(const struct Array *const a)

return: The size.

order: O(1)

ArrayRemove

static int ArrayRemove(struct Array *const a, T *const data)

Removes data from a.

parameter: a, data -- If null, returns false.

parameter: data -- Will be removed; data will remain the same but be updated to the next element, or if this was the last element, the pointer will be past the end.

return: Success, otherwise errno will be set for valid input.

throws: EDOM -- data is not part of a.

order: O(n).

ArrayTailRemove

static int ArrayTailRemove(struct Array *const a, T *const data)

Removes data from a and replaces the spot it was in with the tail.

parameter: a, data -- If null, returns false.

parameter: data -- Will be removed; data will remain the same but be updated to the last element, or if this was the last element, the pointer will be past the end.

return: Success, otherwise errno will be set for valid input.

throws: EDOM -- data is not part of a.

order: O(1).

ArrayClear

static void ArrayClear(struct Array *const a)

Sets the size of a to zero, effectively removing all the elements, but leaves the capacity alone, (the only thing that will free memory allocation is <T>Array_.)

parameter: a -- If null, does nothing.

order: \Theta(1)

ArrayGet

static T * ArrayGet(const struct Array *const a)

Causing something to be added to the Array may invalidate this pointer, see <T>ArrayUpdateNew.

parameter: a -- If null, returns null.

return: A pointer to the a's data, indexable up to the a's size.

order: \Theta(1)

ArrayEnd

static T * ArrayEnd(const struct Array *const a)

Causing something to be added to the Array may invalidate this pointer, see <T>ArrayUpdateNew.

parameter: a -- If null, returns null.

return: One past the end of the array; take care when dereferencing, as it is not part of the array.

order: \Theta(1)

ArrayIndex

static size_t ArrayIndex(const struct Array *const a, const T *const data)

Gets an index given data.

parameter: a -- Must be a valid object.

parameter: data -- If the element is not part of the a, behaviour is undefined.

return: An index.

order: \Theta(1)

fixme: Untested.

ArrayPeek

static T * ArrayPeek(const struct Array *const a)

parameter: a -- If null, returns null.

return: The last element or null if the a is empty. Causing something to be added to the a may invalidate this pointer.

order: \Theta(1)

fixme: Untested.

ArrayPop

static T * ArrayPop(struct Array *const a)

The same value as <T>ArrayPeek.

parameter: a -- If null, returns null.

return: Value from the the top of the a that is removed or null if the stack is empty. Causing something to be added to the a may invalidate this pointer. See <T>ArrayUpdateNew.

order: \Theta(1)

ArrayBack

static T * ArrayBack(const struct Array *const a, const T *const here)

Iterate through a backwards.

parameter: a -- The array; if null, returns null.

parameter: here -- Set it to null to get the last element, if it exists.

return: A pointer to the previous element or null if it does not exist.

order: \Theta(1)

ArrayNext

static T * ArrayNext(const struct Array *const a, const T *const here)

Iterate through a. It is safe to add using <T>ArrayUpdateNew with the return value as update. Removing an element causes the pointer to go to the next element, if it exists.

parameter: a -- The array; if null, returns null.

parameter: here -- Set it to null to get the first element, if it exists.

return: A pointer to the next element or null if there are no more.

order: \Theta(1)

ArrayNew

static T * ArrayNew(struct Array *const a)

Gets an uninitialised new element. May move the a to a new memory location to fit the new size.

parameter: a -- If is null, returns null.

return: A new, un-initialised, element, or null and errno may be set.

throws: ERANGE -- Tried allocating more then can fit in size_t objects.

throws: realloc errors -- IEEE Std 1003.1-2001.

order: Amortised O(1).

ArrayUpdateNew

static T * ArrayUpdateNew(struct Array *const a, T **const update_ptr)

Gets an uninitialised new element and updates the update_ptr if it is within the memory region that was changed to accomodate new space. For example, when iterating a pointer and new element is needed that could change the pointer.

parameter: a -- If null, returns null.

parameter: update_ptr -- Pointer to update on memory move.

return: A new, un-initialised, element, or null and errno may be set.

throws: ERANGE -- Tried allocating more then can fit in size_t.

throws: realloc errors -- IEEE Std 1003.1-2001.

order: amortised O(1)

fixme: Untested.

ArrayBuffer

static T * ArrayBuffer(struct Array *const a, const size_t buffer)

Ensures that a array is buffer capacity beyond the elements in the array.

parameter: a -- If is null, returns null.

parameter: buffer -- If this is zero, returns null.

return: One past the end of the array, or null and errno may be set.

throws: ERANGE

throws: realloc

order: Amortised O(buffer).

fixme: Test.

ArrayAddSize

static int ArrayAddSize(struct Array *const a, const size_t add)

Adds add to the size in a.

return: Success.

throws: ERANGE -- The size added is greater than the capacity. To avoid this, call <T>ArrayBuffer before.

order: O(1)

fixme: Test.

ArrayForEach

static void ArrayForEach(struct Array *const a, const Action action)

Iterates though a and calls action on all the elements. The topology of the list can not change while in this function. That is, don't call <T>ArrayNew, <T>ArrayRemove, etc in action.

parameter: a, action -- If null, does nothing.

order: O(size \times action)

fixme: Untested.

fixme: Sequence interface.

ArrayIfEach

static void ArrayIfEach(struct Array *const a, const Predicate predicate, const Action action)

Iterates though a and calls action on all the elements for which predicate returns true. The topology of the list can not change while in this function.

parameter: a, predicate, action -- If null, does nothing.

order: O(size \times action)

fixme: Untested.

fixme: Sequence interface.

ArrayKeepIf

static void ArrayKeepIf(struct Array *const a, const Predicate keep)

For all elements of a, calls keep, and for each element, if the return value is false, lazy deletes that item.

parameter: a, keep -- If null, does nothing.

order: O(size)

ArrayTrim

static void ArrayTrim(struct Array *const a, const Predicate predicate)

Removes at either end of a of things that predicate returns true.

parameter: a, predicate -- If null, does nothing.

order: O(size)

ArrayReplace

static int ArrayReplace(struct Array *const a, const T *anchor, const long range, const struct Array *const b)

In a, replaces the elements from anchor up to range with a copy of b.

parameter: a -- If null, returns zero.

parameter: anchor -- Beginning of the replaced value, inclusive. If null, appends to the end.

parameter: range -- How many replaced values; negative values are implicitly plus the length of the array; clamped at the minimum and maximum.

parameter: b -- The replacement array. If null, deletes without replacing.

return: Success.

throws: EDOM -- a and b are not null and the same.

throws: ERANGE -- anchor is not null and not in a.

throws: ERANGE -- range is greater then 65535 or smaller then -65534.

throws: ERANGE -- b would cause the array to overflow.

throws: realloc.

order: \Theta(b.size) if the elements have the same size, otherwise, amortised O(a.size + b.size).

ArrayIndexReplace

static int ArrayIndexReplace(struct Array *const a, const size_t i0, const size_t i1, const struct Array *const b)

In a, replaces the elements from indices i0 (inclusive) to i1 (exclusive) with a copy of b.

parameter: a -- If null, returns zero.

parameter: i0, i1 -- The replacement indices, [i0, i1), such that 0 <= i0 <= i1 <= a.size.

parameter: b -- The replacement array. If null, deletes without replacing.

return: Success.

throws: EDOM -- a and b are not null and the same.

throws: EDOM -- i0 or i1 are out-of-bounds or i0 > i1.

throws: ERANGE -- b would cause the array to overflow.

throws: realloc.

order: \Theta(b.size) if the elements have the same size, otherwise, amortised O(a.size + b.size).

ArrayToString

static const char * ArrayToString(const struct Array *const a)

Can print 4 things at once before it overwrites. One must a ARRAY_TO_STRING to a function implementing ToString to get this functionality.

return: Prints a in a static buffer.

order: \Theta(1); it has a 255 character limit; every element takes some of it.

fixme: ToString interface.

You can’t perform that action at this time.