Functions | |
| element_t * | memory_pool_add (memory_pool_t *pool) |
| s32 | memory_pool_clear (memory_pool_t *pool) |
| void | memory_pool_destroy (memory_pool_t *pool) |
| double | memory_pool_dfold (memory_pool_t *pool, double x0, double(*f)(double x, element_t *elem)) |
| u8 | memory_pool_empty (memory_pool_t *pool) |
| float | memory_pool_ffold (memory_pool_t *pool, float x0, float(*f)(float x, element_t *elem)) |
| s32 | memory_pool_filter (memory_pool_t *pool, void *arg, s8(*f)(void *arg, element_t *elem)) |
| s32 | memory_pool_fold (memory_pool_t *pool, void *x0, void(*f)(void *x, element_t *elem)) |
| void | memory_pool_group_by (memory_pool_t *pool, void *arg, s32(*cmp)(void *arg, element_t *a, element_t *b), void *x0, size_t x_size, void(*agg)(element_t *new, void *x, u32 n, element_t *elem)) |
| s32 | memory_pool_ifold (memory_pool_t *pool, s32 x0, s32(*f)(s32 x, element_t *elem)) |
| s8 | memory_pool_init (memory_pool_t *new_pool, u32 n_elements, size_t element_size, void *buff) |
| s32 | memory_pool_map (memory_pool_t *pool, void *arg, void(*f)(void *arg, element_t *elem)) |
| s32 | memory_pool_n_allocated (memory_pool_t *pool) |
| u32 | memory_pool_n_elements (memory_pool_t *pool) |
| s32 | memory_pool_n_free (memory_pool_t *pool) |
| memory_pool_t * | memory_pool_new (u32 n_elements, size_t element_size) |
| s32 | memory_pool_product (memory_pool_t *pool, void *xs, u32 n_xs, size_t x_size, void(*prod)(element_t *new, void *x, u32 n_xs, u32 n, element_t *elem)) |
| s32 | memory_pool_product_generator (memory_pool_t *pool, void *x0, u32 max_xs, size_t x_size, s8(*next)(void *x, u32 n), void(*prod)(element_t *new, void *x, u32 n, element_t *elem)) |
| void | memory_pool_sort (memory_pool_t *pool, void *arg, s32(*cmp)(void *arg, element_t *a, element_t *b)) |
| s32 | memory_pool_to_array (memory_pool_t *pool, void *array) |
Simple fixed size memory pool collection supporting functional operations.
The functional memory pool container is both a memory pool handling allocation of fixed size 'elements' and a container type that arranges allocated elements in a linked list, exposing functional style primitives such as map and fold that operate over the container. Elements can be removed from the container and released back to the pool with a filter operation.
Allocation and deallocation from the pool are guaranteed constant time and map and fold are O(N).
| element_t* memory_pool_add | ( | memory_pool_t * | pool | ) |
Adds an element to a collection. Allocates and element from the pool and adds it to the collection of elements, then returns a pointer to the new element.
| pool | Pointer to a memory pool |
Definition at line 254 of file memory_pool.c.
| s32 memory_pool_clear | ( | memory_pool_t * | pool | ) |
Remove all elements from the collection and return them all back to the pool. This function is O(n) in the number of currently allocated nodes.
| pool | Pointer to a memory pool |
Definition at line 461 of file memory_pool.c.
| void memory_pool_destroy | ( | memory_pool_t * | pool | ) |
Destroy a memory pool. Cleans up and frees the memory associated with the pool. This must only be called on memory pools allocated with memory_pool_new().
| pool | Pointer to the memory pool to destroy. |
Definition at line 144 of file memory_pool.c.
| double memory_pool_dfold | ( | memory_pool_t * | pool, |
| double | x0, | ||
| double(*)(double x, element_t *elem) | f | ||
| ) |
Calculate a double valued fold reduction on the collection, optionally applying a map at the same time.
| pool | Pointer to a memory pool |
| x0 | Initial accumulator state. |
| f | Pointer to a function that returns a new accumulator value given a current accumulator value and an element, optionally updating the element in-place. |
Definition at line 338 of file memory_pool.c.
| u8 memory_pool_empty | ( | memory_pool_t * | pool | ) |
Check if the memory pool is empty. This operation is O(1) in the number of allocated elements.
| pool | Pointer to a memory pool |
Definition at line 205 of file memory_pool.c.
| float memory_pool_ffold | ( | memory_pool_t * | pool, |
| float | x0, | ||
| float(*)(float x, element_t *elem) | f | ||
| ) |
Calculate a float valued fold reduction on the collection, optionally applying a map at the same time.
| pool | Pointer to a memory pool |
| x0 | Initial accumulator state. |
| f | Pointer to a function that returns a new accumulator value given a current accumulator value and an element, optionally updating the element in-place. |
Definition at line 364 of file memory_pool.c.
| s32 memory_pool_filter | ( | memory_pool_t * | pool, |
| void * | arg, | ||
| s8(*)(void *arg, element_t *elem) | f | ||
| ) |
Filter elements in the collection, returning filtered out elements back to the pool.
| pool | Pointer to a memory pool |
| f | Pointer to a function that takes an element and returns `0` to discard that element or `!=0` to keep that element. |
Definition at line 414 of file memory_pool.c.
| s32 memory_pool_fold | ( | memory_pool_t * | pool, |
| void * | x0, | ||
| void(*)(void *x, element_t *elem) | f | ||
| ) |
Calculate a fold reduction on the collection, optionally applying a map at the same time.
| pool | Pointer to a memory pool |
| x0 | Pointer to an initial accumulator state. |
| f | Pointer to a function that does an in-place update of an accumulator state given an element and optionally updates that element in-place. |
Definition at line 308 of file memory_pool.c.
| void memory_pool_group_by | ( | memory_pool_t * | pool, |
| void * | arg, | ||
| s32(*)(void *arg, element_t *a, element_t *b) | cmp, | ||
| void * | x0, | ||
| size_t | x_size, | ||
| void(*)(element_t *new, void *x, u32 n, element_t *elem) | agg | ||
| ) |
Perform a groupby type reduction on a collection. A groupby reduction consists of two steps:
1. First the collection is grouped according to some comparison function, i.e. grouped into sets where the comparison function evaluates to `0` for any pair of elements in that set.
The definition of the comparison function is the same as for memory_pool_sort() and is required to define a global ordering on the whole collection.
2. Next each group is iterated over by an aggregation function which reduces the whole group to exactly one new element that will be in the collection after reduction. The aggregation function is similar to a fold function.
The aggregation function is called once for each element of the group and passed a pointer to the new element that is the aggregate of all elements in the group. The new element is initialized as being a copy of the first element of the group but should be updated in-place by the aggregation function. The aggregation function is also passed a variable `n` which indicated which element of the group is being passed and the current group element is passed as parameter `elem`.
The aggregation function also takes an arbitrary argument `x` which is reset to `x0` at the start of processing each group by copying `x0` into a working area each time.
| pool | Pointer to a memory pool |
| arg | Arbitrary argument passed through to the comparison function |
| cmp | Comparison function used to define the grouping |
| x0 | Arbitrary argument passed to the aggregation function, reset to this value on each new group. |
| x_size | The size in bytes of the `x0` argument |
| agg | The aggregation function |
Definition at line 644 of file memory_pool.c.
| s32 memory_pool_ifold | ( | memory_pool_t * | pool, |
| s32 | x0, | ||
| s32(*)(s32 x, element_t *elem) | f | ||
| ) |
Calculate a s32 valued fold reduction on the collection, optionally applying a map at the same time.
| pool | Pointer to a memory pool |
| x0 | Initial accumulator state. |
| f | Pointer to a function that returns a new accumulator value given a current accumulator value and an element, optionally updating the element in-place. |
Definition at line 390 of file memory_pool.c.
| s8 memory_pool_init | ( | memory_pool_t * | new_pool, |
| u32 | n_elements, | ||
| size_t | element_size, | ||
| void * | buff | ||
| ) |
Initialise a new memory pool. Initialises a new memory pool containing a maximum of `n_elements` elements of size `element_size`. This function does not allocate memory and must be passed a buffer of a suitable size to hold the memory pool elements. Each element stored in the memory pool has an overhead of one pointer size so the total space used for the pool will be:
~~~ n_elements * (element_size + sizeof(void *)) ~~~
Remember to free the pool with memory_pool_destroy(), and for embedded systems it is recommended that all pools be initialized once at start-up to prevent all the usual caveats associated with dynamic memory allocation.
| pool | Pointer to a memory pool to initialise |
| n_elements | Number of elements that the pool can hold |
| element_size | Size in bytes of the user payload elements |
| buff | Pointer to a buffer to use as the memory pool working area |
Definition at line 103 of file memory_pool.c.
| s32 memory_pool_map | ( | memory_pool_t * | pool, |
| void * | arg, | ||
| void(*)(void *arg, element_t *elem) | f | ||
| ) |
Map a function across all elements allocated in the collection.
| pool | Pointer to a memory pool |
| f | Pointer to a function that does an in-place update of an element. |
Definition at line 279 of file memory_pool.c.
| s32 memory_pool_n_allocated | ( | memory_pool_t * | pool | ) |
Calculates the number of elements already allocated in the collection. This operation is O(N) in the number of allocated elements.
| pool | Pointer to a memory pool |
Definition at line 181 of file memory_pool.c.
| u32 memory_pool_n_elements | ( | memory_pool_t * | pool | ) |
Basic getter method for memory_pool_t's n_elements field.
Definition at line 212 of file memory_pool.c.
| s32 memory_pool_n_free | ( | memory_pool_t * | pool | ) |
Calculates the number of free (unallocated) elements remaining in the collection. This operation is O(N) in the number of free elements.
| pool | Pointer to a memory pool |
Definition at line 157 of file memory_pool.c.
| memory_pool_t* memory_pool_new | ( | u32 | n_elements, |
| size_t | element_size | ||
| ) |
Create a new memory pool. Creates a new memory pool containing a maximum of `n_elements` elements of size `element_size`. This function calles malloc() to reserve space for a memory_pool_t struct and for the memory pool itself. Each element stored in the memory pool has an overhead of one pointer size so the total space used for the pool will be:
~~~ n_elements * (element_size + sizeof(void *)) ~~~
Remember to free the pool with memory_pool_destroy(), and for embedded systems it is recommended that all pools be initialized once at start-up to prevent all the usual caveats associated with dynamic memory allocation.
| n_elements | Number of elements that the pool can hold |
| element_size | Size in bytes of the user payload elements |
Definition at line 62 of file memory_pool.c.
| s32 memory_pool_product | ( | memory_pool_t * | pool, |
| void * | xs, | ||
| u32 | n_xs, | ||
| size_t | x_size, | ||
| void(*)(element_t *new, void *x, u32 n_xs, u32 n, element_t *elem) | prod | ||
| ) |
Cartesian product of a memory pool collection with an array. For each pair of an element in the original collection and an item in the array `xs`, a new element is created in the updated collection formed by the function `prod` acting on that element together with that array item.
The product function takes a pointer to the new element which should be updated in-place, a pointer to an item `x` from the input array `xs` and a pointer to the old element `elem`.
As a convenience the product function is also supplied with the total numer of items in the array `n_xs` and the current item number from the array `n`.
| pool | Pointer to a memory pool |
| xs | Array to take the Cartesian product with |
| n_xs | Number of items in array `xs` |
| x_size | The size in bytes of each item in `xs` |
| prod | The product function |
Definition at line 721 of file memory_pool.c.
| s32 memory_pool_product_generator | ( | memory_pool_t * | pool, |
| void * | x0, | ||
| u32 | max_xs, | ||
| size_t | x_size, | ||
| s8(*)(void *x, u32 n) | next, | ||
| void(*)(element_t *new, void *x, u32 n, element_t *elem) | prod | ||
| ) |
Definition at line 765 of file memory_pool.c.
| void memory_pool_sort | ( | memory_pool_t * | pool, |
| void * | arg, | ||
| s32(*)(void *arg, element_t *a, element_t *b) | cmp | ||
| ) |
Sort the elements in a collection. This is implemented as a merge sort on a linked list and has O(N log N) time complexity and O(1) space complexity. The implementation is stable and has no pathological cases. The worst-case running time is still O(N log N).
Ordering is defined by a comparison function `cmp` which takes two elements `a` and `b` and returns `>0` if `a` should be placed before `b`, `<0` if `b` should be placed before `a` and `0` if they are 'equal' and their current ordering should be preserved.
The comparison function also takes an arbitrary argument which is passed through from memory_pool_sort(), this can be used to pass a key or index to sort on to a general comparison function, for example.
This implementation is based on the excellent implementation by Simon Tatham:
http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html
> Based on code copyright 2001 Simon Tatham. > > Permission is hereby granted, free of charge, to any person > obtaining a copy of this software and associated documentation > files (the "Software"), to deal in the Software without > restriction, including without limitation the rights to use, > copy, modify, merge, publish, distribute, sublicense, and/or > sell copies of the Software, and to permit persons to whom the > Software is furnished to do so, subject to the following > conditions: > > The above copyright notice and this permission notice shall be > included in all copies or substantial portions of the Software. > > THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, > EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES > OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND > NONINFRINGEMENT. IN NO EVENT SHALL SIMON TATHAM BE LIABLE FOR > ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF > CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN > CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE > SOFTWARE.
| pool | Pointer to a memory pool |
| arg | Arbitrary argument passed through to the comparison function |
| cmp | Comparison function used to define the sort ordering |
Definition at line 535 of file memory_pool.c.
| s32 memory_pool_to_array | ( | memory_pool_t * | pool, |
| void * | array | ||
| ) |
Write all of the elements of a collection to an array. To determine how much space is needed in the destination array you must call memory_pool_n_allocated(). The required space is:
~~~ memory_pool_n_allocated() * element_size ~~~
| pool | Pointer to a memory pool |
| array | Array to which the elements will be written |
Definition at line 228 of file memory_pool.c.