add implementation

2 files changed, 424 insertions, 0 deletions

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 <stddef.h>
+
+// #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 <stdarg.h>
+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 <stdint.h>
+#include <string.h>
+
+#define CMMM__ARENA__STRIP_VENDOR
+#include "cmmm/arena.h"
+
+#ifndef ASSERT
+#include <assert.h>
+#define ASSERT assert
+#endif
+
+#ifndef MALLOC
+#include <stdlib.h>
+#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 <stdio.h>
+
+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