stdx_hpool.h

home

STDX - Handle Pool Part of the STDX General Purpose C Library by marciovmf License: MIT https://github.com/marciovmf/stdx

Overview

A paged object pool with versioned handles and fast iteration.

This module provides a stable storage container where objects are referenced through lightweight handles instead of raw pointers. It is designed for systems that create and destroy objects frequently while still needing - O(1) allocation and free - safe handle validation - stable storage (objects are never moved) - fast iteration over live objects

Implementation details: - Paged storage

Objects are stored in pages. New pages are allocated as needed,
and existing objects never move in memory.

- Versioned handles

A handle is `{ index, version }`. When a slot is freed the version
is incremented, automatically invalidating any stale handles that
still reference the old object.

- Free list

Freed slots are recycled through a linked free list, allowing
constant-time allocation without scanning.

- Alive list

Live objects are tracked in a dense array so iteration does not
need to scan empty slots.

Key properties:

- Handle = { index, version } - Storage grows by pages (no moving existing items) - Free is per-item (free list) + version bump to kill stale handles - Iteration is dense over alive[] (no hole scanning)

Basic Usage

1) Define the pool

XHPool pool;

2) Initialize it

XHPoolConfig cfg = {0};
cfg.page_capacity = 1024;   // slots per page (must be power of two)
cfg.initial_pages = 1;

x_hpool_init(&pool, sizeof(MyType), cfg, NULL, NULL, NULL);

3) Allocate an object

XHandle h = x_hpool_alloc(&pool);

MyType* obj = (MyType*)x_hpool_get(&pool, h);

4) Use the object normally through the returned pointer.

5) Free the object

x_hpool_free(&pool, h);

Iterating Over Live Objects

Iteration skips empty slots and visits only live items.

XHPoolIter it;
XHandle h;
MyType* obj;

for (obj = x_hpool_iter_begin(&pool, &it, &h);
obj;
obj = x_hpool_iter_next(&pool, &it, &h))
{
// use obj
}

Or use the convenience macro:

X_HPOOL_FOREACH(&pool, MyType, it, h, obj)
{
// use obj
}

Optional Constructors / Destructors

A constructor and destructor may be supplied when the pool is initialized. These functions are automatically invoked when items are allocated or freed.

void ctor(void* user, void* item);
void dtor(void* user, void* item);

x_hpool_init(&pool, sizeof(MyType), cfg, ctor, dtor, user_ptr);

How to compile

To compile the implementation define X_IMPL_HPOOL in one source file before including this header.

#define X_IMPL_HPOOL
#include "stdx_hpool.h"

Custom memory allocation

To override how this module allocates memory define the following macros before including this header:

X_HPOOL_ALLOC(sz)
X_HPOOL_REALLOC(ptr, sz)
X_HPOOL_FREE(ptr)
Macro

X_HPOOL_VERSION_MAJOR

#define X_HPOOL_VERSION_MAJOR 1
Macro

X_HPOOL_VERSION_MINOR

#define X_HPOOL_VERSION_MINOR 0
Macro

X_HPOOL_VERSION_PATCH

#define X_HPOOL_VERSION_PATCH 0
Macro

X_HPOOL_NULL_INDEX

#define X_HPOOL_NULL_INDEX 0xFFFFFFFFu
Struct

XHandle

typedef struct XHandle{
  uint32_t index;
  uint32_t version;
}XHandle;
Typedef

XHPoolCtorFn

typedef void(*XHPoolCtorFn)(void *user, void *item);
Typedef

XHPoolDtorFn

typedef void(*XHPoolDtorFn)(void *user, void *item);
Struct

XHPoolConfig

typedef struct XHPoolConfig{
  uint32_t page_capacity;
  uint32_t initial_pages;
}XHPoolConfig;
Struct

XHPoolIter

typedef struct XHPoolIter{
  uint32_t alive_pos;
}XHPoolIter;
Struct

XHPool

typedef struct XHPool{
  size_t item_size;
  uint32_t page_capacity;
  uint32_t page_shift;
  uint32_t page_mask;
  void **pages;
  uint32_t page_count;
  uint32_t page_cap;
  uint32_t free_head;
  uint32_t next_index;
  uint32_t *alive;
  uint32_t alive_count;
  uint32_t alive_cap;
  XHPoolCtorFn ctor;
  XHPoolDtorFn dtor;
  void *user;
}XHPool;
Function

x_handle_null

X_HPOOL_API XHandle x_handle_null(void);
Function

x_handle_is_null

X_HPOOL_API int x_handle_is_null(XHandle h);
Function

x_hpool_term

X_HPOOL_API void x_hpool_term(XHPool *p);
Function

x_hpool_page_capacity

X_HPOOL_API uint32_t x_hpool_page_capacity(XHPool *p);
Function

x_hpool_capacity

X_HPOOL_API uint32_t x_hpool_capacity(XHPool *p);
Function

x_hpool_alive_count

X_HPOOL_API uint32_t x_hpool_alive_count(XHPool *p);
Function

x_hpool_is_alive

X_HPOOL_API int x_hpool_is_alive(
 XHPool *p,
 XHandle h
);
Function

x_hpool_get

X_HPOOL_API void * x_hpool_get(
 XHPool *p,
 XHandle h
);
Function

x_hpool_get_fast

X_HPOOL_API void * x_hpool_get_fast(
 XHPool *p,
 XHandle h
);
Function

x_hpool_get_unchecked

X_HPOOL_API void * x_hpool_get_unchecked(
 XHPool *p,
 uint32_t index
);
Function

x_hpool_alloc

X_HPOOL_API XHandle x_hpool_alloc(XHPool *p);
Function

x_hpool_free

X_HPOOL_API void x_hpool_free(
 XHPool *p,
 XHandle h
);
Function

x_hpool_clear

X_HPOOL_API void x_hpool_clear(XHPool *p);
Macro

X_HPOOL_FOREACH

#define X_HPOOL_FOREACH(pHPool, Type, itVar, hVar, ptrVar) \
for(XHPoolIter itVar={0},*x__hpool_once_##itVar=&(itVar);x__hpool_once_##itVar!=NULL;x__hpool_once_##itVar=NULL)\
for((ptrVar)=(Type *)x_hpool_iter_begin((pHPool),&(itVar),&(hVar));(ptrVar)!=NULL;(ptrVar)=(Type *)x_hpool_iter_next((pHPool),&(itVar),&(hVar)))
Macro

X_HPOOL_ALLOC

Internal macro for allocating memory. To override how this header allocates memory, define this macro with a different implementation before including this header.

#define X_HPOOL_ALLOC(sz) malloc(sz)

Parameters

sz
The size of memory to alloc.
Macro

X_HPOOL_REALLOC

Internal macro for resizing memory. To override how this header resizes memory, define this macro with a different implementation before including this header.

#define X_HPOOL_REALLOC(p, sz) realloc((p), (sz))

Parameters

sz
The size of memory to resize.
Macro

X_HPOOL_FREE

Internal macro for freeing memory. To override how this header frees memory, define this macro with a different implementation before including this header.

#define X_HPOOL_FREE(p) free(p)

Parameters

p
The address of memory region to free.
Struct

XHPoolSlotHeader

typedef struct XHPoolSlotHeader{
  uint32_t version;
  uint32_t next_free;
  uint32_t alive_pos;
  uint32_t flags;
}XHPoolSlotHeader;
Macro

X_POOL_SLOT_ALIVE

#define X_POOL_SLOT_ALIVE 1u
Function

x_hpool_page_index

X_HPOOL_API uint32_t x_hpool_page_index(
 const XHPool *p,
 uint32_t index
);
Function

x_hpool_slot_index

X_HPOOL_API uint32_t x_hpool_slot_index(
 const XHPool *p,
 uint32_t index
);
Function

x_hpool_slot_stride

X_HPOOL_API size_t x_hpool_slot_stride(const XHPool *p);
Function

x_hpool_page_base

X_HPOOL_API uint8_t * x_hpool_page_base(
 const XHPool *p,
 uint32_t page_index
);
Function

x_hpool_slot_hdr

X_HPOOL_API XHPoolSlotHeader * x_hpool_slot_hdr(
 const XHPool *p,
 uint32_t index
);
Function

x_hpool_item_by_index

X_HPOOL_API void * x_hpool_item_by_index(
 const XHPool *p,
 uint32_t index
);
Function

x_hpool_ensure_pages_array

X_HPOOL_API int x_hpool_ensure_pages_array(
 XHPool *p,
 uint32_t want
);
Function

x_hpool_add_page

X_HPOOL_API int x_hpool_add_page(XHPool *p);
Function

x_hpool_ensure_page_for_index

X_HPOOL_API int x_hpool_ensure_page_for_index(
 XHPool *p,
 uint32_t index
);
Function

x_hpool_alive_reserve

X_HPOOL_API int x_hpool_alive_reserve(
 XHPool *p,
 uint32_t want
);
Function

x_hpool_alive_add

X_HPOOL_API void x_hpool_alive_add(
 XHPool *p,
 uint32_t index
);
Function

x_hpool_alive_remove

X_HPOOL_API void x_hpool_alive_remove(
 XHPool *p,
 uint32_t index
);