Pool.h

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

<T>Pool is a dynamic array that stores unordered <T> in a memory pool, which must be set using POOL_TYPE. You cannot shrink the capacity of this data type, only cause it to grow. Resizing incurs amortised cost, done though a Fibonacci sequence. <T>Pool is not synchronised. The preprocessor macros are all undefined at the end of the file for convenience.

parameter: POOL_NAME, POOL_TYPE
The name that literally becomes <T>, 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: POOL_STACK
Removing an element is normally done lazily through a linked-list internal to the pool. With this defined, there is no such linked-list; the data will be packed and one can only remove items by <T>PoolPop.
parameter: POOL_MIGRATE_EACH
Optional function implementing <PT>Migrate. Indices will remain the same throughout the lifetime of the data, but pointers may change on realloc expansion. This definition will call POOL_MIGRATE_EACH with all <T> in <T>Pool. Use when your data is self-referential, like a linked-list.
parameter: POOL_MIGRATE_ALL
Optional type <A>. When one may have pointers to the data that is contained in the Pool outside the data that can be accessed by the pool. It adds an element to the constructor, <PT>MigrateAll migrate_all, as well as it's constant parameter, <A> all. This usually is the parent of an agglomeration that includes and has references into the pool. This has the responsibility to call <T>MigratePointer or some migrate function for all references.
parameter: POOL_MIGRATE_UPDATE
Optional type association with <S>. <S> should be a super-type of <T>. If not set, <S> is <T>. Used in <T>PoolUpdateNew.
parameter: POOL_TO_STRING
Optional print function implementing <T>ToString; makes available <T>PoolToString.
parameter: POOL_TEST
Unit testing framework using <T>PoolTest, included in a separate header, ../test/PoolTest.h. Must be defined equal to a (random) filler function, satisfying <T>Action. If NDEBUG is not defined, turns on assert private function integrity testing. Requires POOL_TO_STRING.
minimum standard
C89
author
Neil
version
2018-04 Merged Stack into Pool again; augh ifdefs, but too much duplicate code.
since
2018-03 Why have an extra level of indirection? 2018-02 Errno instead of custom errors. 2017-12 Introduced POOL_PARENT for type-safety. 2017-11 Forked Stack from Pool. 2017-10 Replaced PoolIsEmpty by PoolElement, much more useful. 2017-10 Renamed Pool; made migrate automatic. 2017-07 Made migrate simpler. 2017-05 Split List from Pool; much simpler. 2017-01 Almost-redundant functions simplified. 2016-11 Multi-index. 2016-08 Permute.

Declarations

struct Migrate

struct Migrate

Contains information about a realloc.

typedef void (*<PT>Migrate)(T *const data, const struct Migrate *const migrate)

typedef void (*<PT>Migrate)(T *const data,
	const struct Migrate *const migrate)

This is the migrate function for <T>.

typedef void (*<PT>MigrateAll)(A *const all, const struct Migrate *const migrate)

typedef void (*<PT>MigrateAll)(A *const all,
	const struct Migrate *const migrate)

Function call on realloc if POOL_MIGRATE_ALL is defined.

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

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

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

struct <T>Pool

struct <T>Pool

The pool. To instantiate, see <T>Pool.

Function Summary

Return TypeFunction NameArgument List
static void <T>Pool_ struct <T>Pool *const pool
static void <T>Pool struct <T>Pool *const pool, const <PT>MigrateAll migrate_all, A *const all
static void <T>Pool struct <T>Pool *const pool
static size_t <T>PoolSize const struct <T>Pool *const pool
static int <T>PoolRemove struct <T>Pool *const pool, T *const data
static void <T>PoolClear struct <T>Pool *const pool
static T * <T>PoolGet const struct <T>Pool *const pool, const size_t idx
static size_t <T>PoolIndex struct <T>Pool *const pool, T *const data
static T * <T>PoolPeek const struct <T>Pool *const pool
static T * <T>PoolPop struct <T>Pool *const pool
static T * <T>PoolNext struct <T>Pool *const pool, T *const prev
static T * <T>PoolNew struct <T>Pool *const pool
static T * <T>PoolUpdateNew struct <T>Pool *const pool, S **const update_ptr
static void <T>PoolForEach struct <T>Pool *const pool, const <PT>Action action
static void <T>PoolMigrateEach struct <T>Pool *const pool, const <PT>Migrate handler, const struct Migrate *const migrate
static void <T>PoolMigratePointer T **const data_ptr, const struct Migrate *const migrate
static const char * <T>PoolToString const struct <T>Pool *const pool

Function Detail

<T>Pool_

static void <T>Pool_ (struct <T>Pool *const pool)

Destructor for pool. All the pool contents should not be accessed anymore and the pool takes no memory.

parameter: pool
If null, does nothing.
order
Θ(1)

<T>Pool

static void <T>Pool (struct <T>Pool *const pool,
	const <PT>MigrateAll migrate_all, A *const all)

Initialises pool to be empty and have a migrate function with a parameter. This is the constructor if POOL_MIGRATE_ALL is specified.

parameter: pool
If null, does nothing.
parameter: migrate_all
The general <PT>MigrateAll function.
parameter: all
The general migrate parameter.
order
Θ(1)

<T>Pool

static void <T>Pool (struct <T>Pool *const pool)

Initialises pool to be empty. This is the constructor is POOL_MIGRATE_ALL is not specified. If it is static data then it is initialised by default and one doesn't have to call this.

order
Θ(1)

<T>PoolSize

static size_t <T>PoolSize (const struct <T>Pool *const pool)

If POOL_STACK is specified, otherwise it doesn't keep track of the size.

parameter: pool
If null, returns zero.
return
The current size of the stack.
order
Θ(1)

<T>PoolRemove

static int <T>PoolRemove (struct <T>Pool *const pool, T *const data)

Removes data from pool. Only present if POOL_STACK is not defined.

parameter: pool, data
If null, returns false.
return
Success, otherwise errno will be set for valid input.
throws: EDOM
data is not part of pool.
order
amortised O(1)

<T>PoolClear

static void <T>PoolClear (struct <T>Pool *const pool)

Removes all from pool, but leaves the pool memory alone; if one wants to remove memory, see Pool_.

parameter: pool
If null, does nothing.
order
Θ(1)

<T>PoolGet

static T * <T>PoolGet (const struct <T>Pool *const pool, const size_t idx)

Gets an existing element by index. Causing something to be added to the <T>Pool may invalidate this pointer.

parameter: pool
If null, returns null.
parameter: idx
Index.
return
If failed, returns a null pointer.
order
Θ(1)

<T>PoolIndex

static size_t <T>PoolIndex (struct <T>Pool *const pool, T *const data)

Gets an index given data.

parameter: data
If the element is not part of the Pool, behaviour is undefined.
return
An index.
order
Θ(1)
fixme
Untested.

<T>PoolPeek

static T * <T>PoolPeek (const struct <T>Pool *const pool)
parameter: pool
If null, returns null.
return
One element from the pool or null if the pool is empty. If POOL_STACK was specified, this will be the last element added, otherwise, it may not be, but it is deterministic. Causing something to be added to the pool may invalidate this pointer.
order
Θ(1)
fixme
Untested.

<T>PoolPop

static T * <T>PoolPop (struct <T>Pool *const pool)

The same value as <T>PoolPeek.

parameter: pool
If null, returns null.
return
Value from the the top of the pool that is removed or null if the stack is empty. Causing something to be added to the pool may invalidate this pointer.
order
Θ(1) (amortized if not POOL_STACK)

<T>PoolNext

static T * <T>PoolNext (struct <T>Pool *const pool, T *const prev)

Provides a way to iterate through the pool. If <T> = <S>, it is safe to add using PoolUpdateNew with the return value as update. If POOL_STACK is not defined, it is safe to remove an element,

parameter: pool
If null, returns null. If prev is not from this pool and not null, returns null.
parameter: prev
Set it to null to start the iteration.
return
A pointer to the next element or null if there are no more.
order
Θ(1) (or O(pool space that has been deleted) if not POOL_STACK)

<T>PoolNew

static T * <T>PoolNew (struct <T>Pool *const pool)

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

parameter: pool
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)

<T>PoolUpdateNew

static T * <T>PoolUpdateNew (struct <T>Pool *const pool, S **const update_ptr)

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

parameter: pool
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.

<T>PoolForEach

static void <T>PoolForEach (struct <T>Pool *const pool,
	const <PT>Action action)

Iterates though pool from the bottom and calls action on all the elements. The topology of the list can not change while in this function.

parameter: stack, action
If null, does nothing.
order
O(size × action)
fixme
Untested.
fixme
Sequence interface.

<T>PoolMigrateEach

static void <T>PoolMigrateEach (struct <T>Pool *const pool,
	const <PT>Migrate handler, const struct Migrate *const migrate)

Use when the pool has pointers to another memory move structure in the MigrateAll function of the other data type.

parameter: pool
If null, does nothing.
parameter: handler
If null, does nothing, otherwise has the responsibility of calling the other data type's migrate pointer function on all pointers affected by the realloc.
parameter: migrate
If null, does nothing. Should only be called in a Migrate function; pass the migrate parameter.
order
O(greatest size)
fixme
Untested.
fixme
Migrate interface.

<T>PoolMigratePointer

static void <T>PoolMigratePointer (T **const data_ptr,
	const struct Migrate *const migrate)

Passed a migrate parameter, allows pointers to the pool to be updated. It doesn't affect pointers not in the realloced region.

order
Ω(1)
fixme
Untested.
fixme
Migrate interface.

<T>PoolToString

static const char * <T>PoolToString (const struct <T>Pool *const pool)

Can print 4 things at once before it overwrites. One must pool POOL_TO_STRING to a function implementing <T>ToString to get this functionality.

return
Prints pool in a static buffer.
order
Θ(1); it has a 255 character limit; every element takes some of it.
fixme
ToString interface.