pool

pool.h

Header ../../src/pool.h depends on ../../src/heap.h and ../../src/array.h; examples ../../test/test_pool.c; article ../pool/pool.pdf.

Stable pool

• Description
• Typedef Aliases: <pT>type, <pT>to_string_fn
• Struct, Union, and Enum Definitions: <t>pool, table_stats
• Function Summary
• Function Definitions
• License

Description

<t>pool is a memory pool that stores only one size—<pT>type—using slab allocation. As Bonwick, 1994, Slab, it helps reduce internal fragmentation from repeated allocation and destruction by caching contiguous blocks. Pointers to valid items in the pool are stable. Instead of freeing memory, a free-heap in the active-slab allows lazily reusing the same space. If removal is ongoing and uniformly sampled while reaching a steady-state size, it will eventually settle in one contiguous region.

• Parameter: POOL_NAME, POOL_TYPE
  <t> that satisfies C naming conventions when mangled and a valid tag type, <pT>type, associated therewith; required.
• Parameter: POOL_DECLARE_ONLY
  For headers in different compilation units.
• Standard:
  C89. However, when compiling for segmented memory models, C99 with uintptr_t is recommended because of it's implementation-defined instead of undefined-behaviour when comparing pointers from different objects in the heap of memory addresses. Still, this is not guaranteed to produce meaningful results on all systems.
• Dependancies:
  array, heap, box

Typedef Aliases

<pT>type

typedef POOL_TYPE <pT>type;

A valid tag type set by POOL_TYPE.

<pT>to_string_fn

typedef void(*<pT>to_string_fn)(const <pT>type , char()[12]);

Type of the required <tr>to_string. Responsible for turning the read-only argument into a 12-max-char output string.

Struct, Union, and Enum Definitions

<t>pool

struct <t>pool { struct <pT>slot_array slots; struct poolfree_heap free0; size_t capacity0; };

A zeroed pool is a valid state. See <t>pool.

table_stats

struct table_stats { size_t n, max; double mean, ssdm; };

Welford1962Note: population variance: ssdm/n, sample variance: ssdm/(n-1).

Function Summary

Modifiers	Function Name	Argument List
struct <T>cursor	<T>begin	<t>pool
int	<T>exists	<T>cursor
<pT>type *	<T>entry	<T>cursor
void	<T>next	<T>cursor
struct <t>pool	<t>pool
void	<t>pool_	<t>pool
int	<T>buffer	<t>pool, size_t
<pT>type *	<T>new	<t>pool
int	<T>remove	<t>pool, <pT>type
void	<T>clear	<t>pool
static struct <t>pool	<t>pool
static void	<t>pool_	pool
static int	<T>buffer	pool, n
static <pT>type *	<T>new	pool
static int	<T>remove	pool, data
static void	<T>clear	pool
void	<T>graph	<pT>box
int	<T>graph_fn	<pT>box, char

Function Definitions

<T>begin

struct <T>cursor <T>begin(const struct <t>pool *);

<T>exists

int <T>exists(const struct <T>cursor *);

<T>entry

<pT>type *<T>entry(struct <T>cursor *);

<T>next

void <T>next(struct <T>cursor *);

<t>pool

struct <t>pool <t>pool(void);

<t>pool_

void <t>pool_(struct <t>pool *);

<T>buffer

int <T>buffer(struct <t>pool *, size_t);

<T>new

<pT>type *<T>new(struct <t>pool *);

<T>remove

int <T>remove(struct <t>pool *, <pT>type *);

<T>clear

void <T>clear(struct <t>pool *);

<t>pool

static struct <t>pool <t>pool(void)

• Return:
  An idle pool is zeroed.
• Order:
  Θ(1)

<t>pool_

static void <t>pool_(struct <t>pool *const pool)

Destroys pool and returns it to idle.

• Order:
  Ο(log data)

<T>buffer

static int <T>buffer(struct <t>pool *const pool, const size_t n)

Ensure capacity of at least n further items in pool. Pre-sizing is better for contiguous blocks, but takes up that memory.

• Return:
  Success.
• Exceptional return: ERANGE, malloc

<T>new

static <pT>type *<T>new(struct <t>pool *const pool)

This pointer is constant until it gets <T>remove.

• Return:
  A pointer to a new uninitialized element from pool.
• Exceptional return: ERANGE, malloc
• Order:
  amortised O(1)

<T>remove

static int <T>remove(struct <t>pool *const pool, <pT>type *const data)

Deletes data from pool. (Do not remove data that is not in pool.)

• Return:
  Success.
• Exceptional return: malloc
  Because of lazy deletion, remove can actually demand memory when data requires adding to the free-heap.
• Order:
  Ο(log (slab0-free-heap | slabs))

<T>clear

static void <T>clear(struct <t>pool *const pool)

Removes all from pool, but keeps it's active state, only freeing the smaller blocks.

• Order:
  Ο(log items)

<T>graph

void <T>graph(const <pT>box *, FILE *);

<T>graph_fn

int <T>graph_fn(const <pT>box *, const char *);

License

2021 Neil Edelman, distributed under the terms of the MIT License.