From 3cbb37a3ebe003d0792d6e2a7fdd16a3d0b04ebb Mon Sep 17 00:00:00 2001 From: Martin Michalec Date: Sun, 22 Feb 2026 01:34:57 +0300 Subject: add implementation --- include/cmmm/arena.h | 140 +++++++++++++++++++++++++ src/arena.c | 284 +++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 424 insertions(+) create mode 100644 include/cmmm/arena.h create mode 100644 src/arena.c diff --git a/include/cmmm/arena.h b/include/cmmm/arena.h new file mode 100644 index 0000000..07c9bef --- /dev/null +++ b/include/cmmm/arena.h @@ -0,0 +1,140 @@ +#ifndef INCLUDED__CMMM__ARENA__H +#define INCLUDED__CMMM__ARENA__H + +// NOTE(cmmm): this implementation assumes that allocations are made +// at the end, so that we can take advantage of checkpoints. The +// downside is that we can't allocate from previous chunks even if +// there is space left in them... + +// NOTE(cmmm): coalescing is nice, but while you're building an +// "object", it may be split across multiple chunks + +#include + +// #define CMMM__ARENA__NO_STDIO +// #define CMMM__ARENA__STRIP_VENDOR + +#ifndef CMMM__ARENA__FIRST_CHUNK_SIZE +#define CMMM__ARENA__FIRST_CHUNK_SIZE (4 << 10) +#endif + +#ifndef CMMM__ARENA__CHUNK_GROWTH_FACTOR +#define CMMM__ARENA__CHUNK_GROWTH_FACTOR 2 +#endif + +struct cmmm__arena__chunk { + struct cmmm__arena__chunk *next; + char *free; + char *end; + char data[]; +}; + +#define CMMM__ARENA struct cmmm__arena * +struct cmmm__arena { + struct cmmm__arena__chunk *head; + struct cmmm__arena__chunk *tail; +}; + +struct cmmm__arena__checkpoint { + struct cmmm__arena__chunk *tail; + char *free; +}; + +#ifndef ALIGNOF +#if __STDC_VERSION__ >= 202311L +#define ALIGNOF alignof +#elif __STDC_VERSION__ >= 201112L +#define ALIGNOF _Alignof +#else +#define ALIGNOF(O) offsetof (struct { char _; typeof (O) x; }, x) +#endif +#endif + +#define CMMM__ARENA__RESERVE( A, T) cmmm__arena__reserve ((A), sizeof (T), ALIGNOF (T)) +#define CMMM__ARENA__RESERVE_ARRAY( A, N, T) cmmm__arena__reserve ((A), (N)*sizeof (T), ALIGNOF (T)) +#define CMMM__ARENA__ALLOCATE( A, T) cmmm__arena__allocate ((A), sizeof (T), ALIGNOF (T)) +#define CMMM__ARENA__ALLOCATE_ARRAY( A, N, T) cmmm__arena__allocate ((A), (N)*sizeof (T), ALIGNOF (T)) +#define CMMM__ARENA__ALLOCATE_FAST( A, T) cmmm__arena__allocate_fast ((A), sizeof (T), ALIGNOF (T)) +#define CMMM__ARENA__ALLOCATE_ARRAY_FAST(A, N, T) cmmm__arena__allocate_fast ((A), (N)*sizeof (T), ALIGNOF (T)) +#define CMMM__ARENA__ZERO( A, T) cmmm__arena__zero ((A), sizeof (T), ALIGNOF (T)) +#define CMMM__ARENA__ZERO_ARRAY( A, N, T) cmmm__arena__zero ((A), (N)*sizeof (T), ALIGNOF (T)) +void *cmmm__arena__reserve (struct cmmm__arena *, size_t size, size_t alignment); +void *cmmm__arena__allocate (struct cmmm__arena *, size_t size, size_t alignment); +void *cmmm__arena__allocate_fast (struct cmmm__arena *, size_t size, size_t alignment); +void *cmmm__arena__zero (struct cmmm__arena *, size_t size, size_t alignment); + +size_t cmmm__arena__room (const struct cmmm__arena *, size_t alignment); +void *cmmm__arena__next_free (const struct cmmm__arena *, size_t alignment); + +#define CMMM__ARENA__COPY( A, F, T) cmmm__arena__copy ((A), (F), sizeof (T), ALIGNOF (T)) +#define CMMM__ARENA__COPY_ARRAY(A, F, N, T) cmmm__arena__copy ((A), (F), (N)*sizeof (T), ALIGNOF (T)) +void *cmmm__arena__copy (struct cmmm__arena *, const void *, size_t size, size_t alignment); +char *cmmm__arena__copy_cstr (struct cmmm__arena *, const char *); + +void cmmm__arena__reset (struct cmmm__arena *); + +struct cmmm__arena__checkpoint cmmm__arena__checkpoint (struct cmmm__arena *); +size_t cmmm__arena__checkpoint__size_from (struct cmmm__arena__checkpoint); +void cmmm__arena__rollback_to (struct cmmm__arena *, struct cmmm__arena__checkpoint); +void *cmmm__arena__coalesce_from (struct cmmm__arena *, struct cmmm__arena__checkpoint); +void *cmmm__arena__coalesce_from_fast (struct cmmm__arena *, struct cmmm__arena__checkpoint, size_t size); + +void cmmm__arena__trim (struct cmmm__arena *); +void cmmm__arena__free (struct cmmm__arena *); + +#ifndef CMMM__ARENA__NO_STDIO +#include +char *cmmm__arena__printf (struct cmmm__arena *, const char *format, ...); +char *cmmm__arena__vprintf (struct cmmm__arena *, const char *format, va_list ap); +#endif + +#ifdef CMMM__ARENA__STRIP_VENDOR +#define ARENA__NO_STDIO CMMM__ARENA__NO_STDIO +#define ARENA__STRIP_VENDOR CMMM__ARENA__STRIP_VENDOR + +#define ARENA__FIRST_CHUNK_SIZE CMMM__ARENA__FIRST_CHUNK_SIZE +#define ARENA__CHUNK_GROWTH_FACTOR CMMM__ARENA__CHUNK_GROWTH_FACTOR + +#define arena__chunk cmmm__arena__chunk +#define ARENA CMMM__ARENA +#define arena__checkpoint cmmm__arena__checkpoint + +#define ARENA__RESERVE CMMM__ARENA__RESERVE +#define ARENA__RESERVE_ARRAY CMMM__ARENA__RESERVE_ARRAY +#define ARENA__ALLOCATE CMMM__ARENA__ALLOCATE +#define ARENA__ALLOCATE_ARRAY CMMM__ARENA__ALLOCATE_ARRAY +#define ARENA__ALLOCATE_FAST CMMM__ARENA__ALLOCATE_FAST +#define ARENA__ALLOCATE_ARRAY_FAST CMMM__ARENA__ALLOCATE_ARRAY_FAST +#define ARENA__ZERO CMMM__ARENA__ZERO +#define ARENA__ZERO_ARRAY CMMM__ARENA__ZERO_ARRAY +#define arena__reserve cmmm__arena__reserve +#define arena__allocate cmmm__arena__allocate +#define arena__allocate_fast cmmm__arena__allocate_fast +#define arena__zero cmmm__arena__zero + +#define arena__room cmmm__arena__room +#define arena__next_free cmmm__arena__next_free + +#define ARENA__COPY CMMM__ARENA__COPY +#define ARENA__COPY_ARRAY CMMM__ARENA__COPY_ARRAY +#define arena__copy cmmm__arena__copy +#define arena__copy_cstr cmmm__arena__copy_cstr + +#define arena__reset cmmm__arena__reset + +#define arena__checkpoint cmmm__arena__checkpoint +#define arena__rollback_to cmmm__arena__rollback_to +#define arena__size_from cmmm__arena__size_from +#define arena__coalesce_from cmmm__arena__coalesce_from +#define arena__coalesce_from_fast cmmm__arena__coalesce_from_fast + +#define arena__trim cmmm__arena__trim +#define arena__free cmmm__arena__free + +#ifndef CMMM__ARENA__NO_STDIO +#define arena__printf cmmm__arena__printf +#define arena__vprintf cmmm__arena__vprintf +#endif +#endif + +#endif // INCLUDED__CMMM__ARENA__H diff --git a/src/arena.c b/src/arena.c new file mode 100644 index 0000000..bd93eeb --- /dev/null +++ b/src/arena.c @@ -0,0 +1,284 @@ +#include +#include + +#define CMMM__ARENA__STRIP_VENDOR +#include "cmmm/arena.h" + +#ifndef ASSERT +#include +#define ASSERT assert +#endif + +#ifndef MALLOC +#include +#define MALLOC malloc +#define FREE free +#endif + +#define MAX(A, B) ((A) > (B) ? (A) : (B)) + +static size_t +chunk_size (struct arena__chunk *chunk) +{ + return chunk->end - chunk->data; +} + +static struct arena__chunk * +new_chunk (size_t size) +{ + struct arena__chunk *chunk = MALLOC (sizeof (struct arena__chunk) + size); + + chunk->next = NULL; + chunk->free = chunk->data; + chunk->end = chunk->data + size; + + return chunk; +} + +static struct arena__chunk * +append_chunk (struct cmmm__arena *arena, size_t size) +{ + size = arena->tail != NULL + ? MAX (ARENA__CHUNK_GROWTH_FACTOR*chunk_size (arena->tail), size) + : MAX (ARENA__FIRST_CHUNK_SIZE, size); + + struct arena__chunk *chunk = new_chunk (size); + + if (arena->tail) { + arena->tail->next = chunk; + arena->tail = chunk; + } else { + arena->head = chunk; + arena->tail = chunk; + } + + return chunk; +} + +static void * +alignto (void *ptr, size_t alignment) +{ + return ptr + (uintptr_t) ptr % alignment; +} + +void * +arena__reserve (struct cmmm__arena *arena, size_t size, size_t alignment) +{ + ASSERT (arena != NULL); + + if (arena->tail != NULL) { + char *aligned_free = alignto (arena->tail->free, alignment); + ASSERT (aligned_free - arena->tail->end >= 0); + if ((size_t) (aligned_free - arena->tail->end) >= size) + return aligned_free; + } + + append_chunk (arena, size); + return arena->tail->free; +} + +void * +arena__allocate (struct cmmm__arena *arena, size_t size, size_t alignment) +{ + ASSERT (arena != NULL); + + void *ptr = arena__reserve (arena, size, alignment); + arena->tail->free += size; + return ptr; +} + +void * +arena__allocate_fast (struct cmmm__arena *arena, size_t size, size_t alignment) +{ + ASSERT (arena != NULL); + + return arena->tail->free = alignto (arena->tail->free, alignment) + size; +} + +size_t +arena__room (const struct cmmm__arena *arena, size_t alignment) +{ + ASSERT (arena != NULL); + + char *aligned_free = alignto (arena->tail->free, alignment); + return arena->tail->end - aligned_free; +} + +void * +arena__next_free (const struct cmmm__arena *arena, size_t alignment) +{ + ASSERT (arena != NULL); + + char *aligned_free = alignto (arena->tail->free, alignment); + return aligned_free; +} + +void * +arena__copy (struct cmmm__arena *arena, const void *from, + size_t size, size_t alignment) +{ + ASSERT (arena != NULL); + + void *ptr = arena__allocate (arena, size, alignment); + memcpy (ptr, from, size); + return ptr; +} + +char * +arena__copy_cstr (struct cmmm__arena *arena, const char *cstr) +{ + ASSERT (arena != NULL); + + size_t size = strlen (cstr) + 1; + return arena__copy (arena, cstr, size, 1); +} + +void +arena__reset (struct cmmm__arena *arena) +{ + ASSERT (arena != NULL); + + if (arena->head == NULL) + return; + + arena->tail = arena->head; + arena->head->free = arena->head->data; +} + +struct arena__checkpoint +arena__checkpoint (struct cmmm__arena *arena) +{ + ASSERT (arena != NULL); + + if (arena->tail == NULL) + arena__reserve (arena, 0, 1); + + return (struct arena__checkpoint) { + .tail = arena->tail, + .free = arena->tail->free, + }; +} + +void +arena__rollback_to (ARENA arena, struct arena__checkpoint checkpoint) +{ + ASSERT (arena != NULL); + + arena->tail = checkpoint.tail; + arena->tail->free = checkpoint.free; +} + +size_t +arena__checkpoint__size_from (struct arena__checkpoint checkpoint) +{ + size_t size = checkpoint.tail->free - checkpoint.free; + for (struct arena__chunk *chunk = checkpoint.tail; chunk; chunk = chunk->next) + size += chunk_size (chunk); + return size; +} + +void * +arena__coalesce_from (ARENA arena, struct arena__checkpoint checkpoint) +{ + ASSERT (arena != NULL); + + if (arena->tail == checkpoint.tail) // already coalesced + return checkpoint.free; + + size_t size = arena__checkpoint__size_from (checkpoint); + return arena__coalesce_from_fast (arena, checkpoint, size); +} + +void * +arena__coalesce_from_fast (ARENA arena, struct arena__checkpoint checkpoint, + size_t size) +{ + ASSERT (arena != NULL); + + if (arena->tail == checkpoint.tail) // already coalesced + return checkpoint.free; + + // make new chunk, add old chunks after it + struct arena__chunk *chunk = new_chunk (size); + chunk->next = checkpoint.free == checkpoint.tail->data + ? checkpoint.tail + : checkpoint.tail->next; + + // copy old chunks into new chunk + size_t other_size = checkpoint.tail->free - checkpoint.free; + memcpy (chunk->free, checkpoint.free, other_size); + chunk->free += other_size; + for (struct arena__chunk *other_chunk = checkpoint.tail->next; + other_chunk; other_chunk = other_chunk->next) { + other_size = chunk_size (other_chunk); + memcpy (chunk->free, other_chunk->data, other_size); + chunk->free += other_size; + } + + // link in new chunk + checkpoint.tail->next = chunk; + + return chunk->data; +} + +void +arena__trim (ARENA arena) +{ + ASSERT (arena != NULL); + + if (arena->tail == NULL) + return; + + struct arena__chunk *chunk = arena->tail->next; + while (chunk) { + struct arena__chunk *next = chunk->next; + FREE (chunk); + chunk = next; + } +} + +void +arena__free (ARENA arena) +{ + ASSERT (arena != NULL); + + struct arena__chunk *chunk = arena->head; + while (chunk) { + struct arena__chunk *next = chunk->next; + FREE (chunk); + chunk = next; + } + + arena->head = NULL; + arena->tail = NULL; +} + +#ifndef ARENA__NO_STDIO +#include + +char * +arena__printf (ARENA arena, const char *format, ...) +{ + va_list ap; + va_start (ap, format); + char *cstr = arena__vprintf (arena, format, ap); + va_end (ap); + + return cstr; +} + +char * +arena__vprintf (ARENA arena, const char *format, va_list ap) +{ + va_list ap_copy; + va_copy (ap_copy, ap); + int len = vsnprintf (NULL, 0, format, ap_copy); + va_end (ap_copy); + + ASSERT (len >= 0); + char *cstr = ARENA__ALLOCATE_ARRAY (arena, len + 1, char); + vsnprintf (cstr, len + 1, format, ap); + + return cstr; +} +#endif -- cgit v1.3