Add mem allocator, remove listpool.

12 files changed, 592 insertions, 417 deletions

diff --git a/CMakeLists.txt b/CMakeLists.txt
index 498b771..868268d 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -6,7 +6,7 @@ add_subdirectory(cstring)
 add_subdirectory(error)
 add_subdirectory(filesystem)
 add_subdirectory(list)
-add_subdirectory(listpool)
+add_subdirectory(mem)
 add_subdirectory(log)
 add_subdirectory(mempool)
 add_subdirectory(plugin)
diff --git a/listpool/CMakeLists.txt b/listpool/CMakeLists.txt
deleted file mode 100644
index 2dcd983..0000000
--- a/listpool/CMakeLists.txt
+++ /dev/null
@@ -1,26 +0,0 @@
-cmake_minimum_required(VERSION 3.0)
-
-project(listpool)
-
-# Library
-
-add_library(listpool
-  src/listpool.c)
-
-target_include_directories(listpool PUBLIC
-  include)
-
-target_link_libraries(listpool
-  list)
-
-target_compile_options(listpool PRIVATE -Wall -Wextra)
-
-# Test
-
-add_executable(listpool_test
-  test/listpool_test.c)
-
-target_link_libraries(listpool_test
-listpool)
-
-target_compile_options(listpool_test PRIVATE -DUNIT_TEST -DNDEBUG -Wall -Wextra)
diff --git a/listpool/README.md b/listpool/README.md
deleted file mode 100644
index ed38980..0000000
--- a/listpool/README.md
+++ /dev/null
@@ -1,14 +0,0 @@
-# Listpool
-
-A block allocator built from a single, contiguous array of memory that maintains
-free and used blocks in doubly linked lists.
-
-A `listpool` is similar to a `mempool`, but the additional structure allows it
-to:
-
-- Allocate and free blocks in constant time.
-- Traverse used blocks in linear time in the number of used blocks, as opposed
-  to the total number of blocks like in a `mempool`.
-
-A `listpool` otherwise provides the same guarantees and characteristics as a
-`mempool`.
diff --git a/listpool/include/listpool.h b/listpool/include/listpool.h
deleted file mode 100644
index 85a3b27..0000000
--- a/listpool/include/listpool.h
+++ /dev/null
@@ -1,100 +0,0 @@
-#pragma once
-
-#include "list.h"
-
-#include <assert.h>
-#include <stddef.h>
-#include <stdint.h>
-
-/// Define a typed listpool of a given size.
-#define DEF_LISTPOOL(POOL, TYPE, NUM_BLOCKS) \
-  typedef struct POOL {                      \
-    listpool pool;                           \
-    list     nodes[NUM_BLOCKS];              \
-    TYPE     blocks[NUM_BLOCKS];             \
-  } POOL;
-
-/// Creates a new listpool.
-#define listpool_make(POOL)                                                    \
-  {                                                                            \
-    assert(POOL);                                                              \
-    const size_t block_size = sizeof((POOL)->blocks[0]);                       \
-    const size_t num_blocks = sizeof((POOL)->blocks) / block_size;             \
-    listpool_make_(                                                            \
-        &(POOL)->pool, (POOL)->nodes, (POOL)->blocks, num_blocks, block_size); \
-  }
-
-/// Allocate a new block.
-/// Return 0 if there is no memory left.
-#define listpool_alloc(POOL) listpool_alloc_(&(POOL)->pool)
-
-/// Free the block.
-/// The block pointer is conveniently set to 0.
-#define listpool_free(POOL, ITEM) listpool_free_(&(POOL)->pool, (void**)ITEM)
-
-/// Remove a value from the list.
-/// Defined here instead of DEF_LISTPOOL_IMPL() because not all types may have
-/// an operator==.
-#define listpool_remove(POOL, VAL)  \
-  {                                 \
-    listpool_foreach(POOL, iter, {  \
-      if (*iter == VAL) {           \
-        listpool_free(POOL, &iter); \
-        break;                      \
-      }                             \
-    });                             \
-  }
-
-/// Return the ith block.
-/// The block must have been allocated.
-#define listpool_get_block(POOL, INDEX) \
-  ((typeof((POOL)->blocks[0])*)listpool_get_block_(&(POOL)->pool, INDEX))
-
-/// Get the index to the given block.
-#define listpool_get_block_index(POOL, BLOCK_PTR) \
-  listpool_get_block_index_(&(POOL)->pool, BLOCK_PTR)
-
-/// Iterate over the used items of the pool.
-///
-/// The caller can use 'i' as the index of the current block.
-///
-/// It is valid to mempool_free() the object at each step of the iteration.
-#define listpool_foreach(POOL, ITER, BODY)                      \
-  for (list* it_ = (POOL)->pool.used; it_; it_ = it_->next) {   \
-    const size_t               i    = it_ - (POOL)->pool.nodes; \
-    typeof((POOL)->blocks[0])* ITER = &(POOL)->blocks[i];       \
-    (void)ITER;                                                 \
-    BODY;                                                       \
-  }
-
-typedef struct listpool {
-  size_t   block_size_bytes;
-  size_t   num_blocks;
-  list*    free;   // Head of the free list.
-  list*    used;   // Head of the used list.
-  list*    nodes;  // Array of nodes.
-  uint8_t* blocks; // Array of blocks;
-} listpool;
-
-/// Create a new list pool from a user-provided array of memory.
-/// `nodes` must have at least `num_blocks` nodes.
-/// `blocks` must be at least `num_blocks` * `block_size_bytes` bytes.
-/// All blocks are zeroed out for convenience.
-void listpool_make_(
-    listpool* pool, list* nodes, void* blocks, size_t num_blocks,
-    size_t block_size_bytes);
-
-/// Allocate a new block.
-/// Return 0 if there is no memory left.
-void* listpool_alloc_(listpool* pool);
-
-/// Free the block.
-/// The block pointer is conveniently set to 0.
-void listpool_free_(listpool* pool, void** block_ptr);
-
-/// Return the ith block.
-/// The block must have been allocated.
-void* listpool_get_block_(const listpool*, size_t block_index);
-
-/// Get the index to the given block.
-size_t listpool_get_block_index_(const listpool*, const void* block);
diff --git a/listpool/src/listpool.c b/listpool/src/listpool.c
deleted file mode 100644
index 758062c..0000000
--- a/listpool/src/listpool.c
+++ /dev/null
@@ -1,92 +0,0 @@
-#include "listpool.h"
-
-#include <string.h>
-
-void listpool_make_(
-    listpool* pool, list* nodes, void* blocks, size_t num_blocks,
-    size_t block_size_bytes) {
-  assert(pool);
-  pool->block_size_bytes = block_size_bytes;
-  pool->num_blocks       = num_blocks;
-  pool->free             = &nodes[0];
-  pool->used             = 0;
-  pool->nodes            = nodes;
-  pool->blocks           = blocks;
-  list_make(nodes, num_blocks);
-  memset(blocks, 0, num_blocks * block_size_bytes);
-}
-
-void* listpool_alloc_(listpool* pool) {
-  assert(pool);
-  if (!pool->free) {
-    return 0;
-  }
-
-  const size_t index = pool->free - pool->nodes;
-  assert(index < pool->num_blocks);
-
-  list* free = pool->free;
-  pool->free = pool->free->next;
-
-  // pool->used is always the head of the used list, so prepend the new item to
-  // the list.
-  list* new_used = free;
-  new_used->prev = 0;
-  new_used->next = pool->used;
-  if (pool->used) {
-    pool->used->prev = new_used;
-  }
-  pool->used = new_used;
-
-  return pool->blocks + index * pool->block_size_bytes;
-}
-
-void listpool_free_(listpool* pool, void** block_ptr) {
-  assert(pool);
-  assert(block_ptr);
-
-  memset(*block_ptr, 0, pool->block_size_bytes);
-
-  const size_t index =
-      ((uint8_t*)*block_ptr - pool->blocks) / pool->block_size_bytes;
-  assert(index < pool->num_blocks);
-
-  list* item = &pool->nodes[index];
-
-  // We must remove the item from the used list first.
-  if (item->prev) {
-    item->prev->next = item->next;
-  }
-  if (item->next) {
-    item->next->prev = item->prev;
-  }
-  if (item == pool->used) {
-    pool->used = item->next;
-  }
-
-  // pool->free is always the head of the free list, so prepend the new item to
-  // the list. The item is now free to wire after removing it from the used
-  // list.
-  if (!pool->free) {
-    pool->free = item;
-  } else {
-    item->next       = pool->free;
-    pool->free->prev = item;
-    pool->free       = item;
-  }
-
-  *block_ptr = 0;
-}
-
-void* listpool_get_block_(const listpool* pool, size_t block_index) {
-  assert(pool);
-  assert(block_index < pool->num_blocks);
-  return pool->blocks + block_index * pool->block_size_bytes;
-}
-
-size_t listpool_get_block_index_(const listpool* pool, const void* block) {
-  assert(pool);
-  const size_t block_byte_index = (const uint8_t*)block - pool->blocks;
-  assert(block_byte_index % pool->block_size_bytes == 0);
-  return block_byte_index / pool->block_size_bytes;
-}
diff --git a/listpool/test/listpool_test.c b/listpool/test/listpool_test.c
deleted file mode 100644
index 7a7b0cf..0000000
--- a/listpool/test/listpool_test.c
+++ /dev/null
@@ -1,183 +0,0 @@
-#include "listpool.h"
-
-#include "test.h"
-
-#define NUM_BLOCKS 10
-
-DEF_LISTPOOL(test_pool, int, NUM_BLOCKS);
-
-static int count(test_pool* pool) {
-  int count = 0;
-  listpool_foreach(pool, n, { count++; });
-  return count;
-}
-
-static int sum(test_pool* pool) {
-  int sum = 0;
-  listpool_foreach(pool, n, { sum += *n; });
-  return sum;
-}
-
-// Create a pool.
-TEST_CASE(listpool_create) {
-  test_pool pool;
-  listpool_make(&pool);
-}
-
-// Allocate all N blocks.
-TEST_CASE(listpool_fully_allocate) {
-  test_pool pool;
-  listpool_make(&pool);
-
-  for (int i = 0; i < NUM_BLOCKS; ++i) {
-    const int* block = listpool_alloc(&pool);
-    TEST_TRUE(block != 0);
-  }
-}
-
-// Allocate all N blocks, then free them.
-TEST_CASE(listpool_fill_then_free) {
-  test_pool pool;
-  listpool_make(&pool);
-
-  int* blocks[NUM_BLOCKS] = {0};
-  for (int i = 0; i < NUM_BLOCKS; i++) {
-    blocks[i] = listpool_alloc(&pool);
-    TEST_TRUE(blocks[i] != 0);
-  }
-
-  for (int i = 0; i < NUM_BLOCKS; i++) {
-    listpool_free(&pool, &blocks[i]);
-    TEST_EQUAL(blocks[i], 0); // Pointer should be set to 0 on free.
-  }
-
-  TEST_EQUAL(count(&pool), 0);
-}
-
-// Attempt to allocate blocks past the maximum pool size.
-// The pool should handle the failed allocations gracefully.
-TEST_CASE(listpool_allocate_beyond_max_size) {
-  test_pool pool;
-  listpool_make(&pool);
-
-  // Fully allocate the pool.
-  for (int i = 0; i < NUM_BLOCKS; ++i) {
-    TEST_TRUE(listpool_alloc(&pool) != 0);
-  }
-
-  // Past the end.
-  for (int i = 0; i < NUM_BLOCKS; ++i) {
-    TEST_EQUAL(listpool_alloc(&pool), 0);
-  }
-}
-
-// Free blocks should always remain zeroed out.
-// This tests the invariant right after creating the pool.
-TEST_CASE(listpool_zero_free_blocks_after_creation) {
-  test_pool pool;
-  listpool_make(&pool);
-
-  const int zero = 0;
-  for (int i = 0; i < NUM_BLOCKS; ++i) {
-    const int* block = (const int*)(pool.blocks) + i;
-    TEST_EQUAL(memcmp(block, &zero, sizeof(int)), 0);
-  }
-}
-
-// Free blocks should always remain zeroed out.
-// This tests the invariant after freeing a block.
-TEST_CASE(listpool_zero_free_block_after_free) {
-  test_pool pool;
-  listpool_make(&pool);
-
-  int* val = listpool_alloc(&pool);
-  TEST_TRUE(val != 0);
-  *val = 177;
-
-  int* old_val = val;
-  listpool_free(&pool, &val); // val pointer is set to 0.
-  TEST_EQUAL(*old_val, 0);    // Block is zeroed out after free.
-}
-
-// Traverse an empty pool.
-TEST_CASE(listpool_traverse_empty) {
-  test_pool pool;
-  listpool_make(&pool);
-
-  TEST_EQUAL(count(&pool), 0);
-}
-
-// Traverse a partially full pool.
-TEST_CASE(listpool_traverse_partially_full) {
-  const int N = NUM_BLOCKS / 2;
-
-  test_pool pool;
-  listpool_make(&pool);
-
-  for (int i = 0; i < N; ++i) {
-    int* val = listpool_alloc(&pool);
-    TEST_TRUE(val != 0);
-    *val = i + 1;
-  }
-
-  TEST_EQUAL(sum(&pool), (N) * (N + 1) / 2);
-}
-
-// Traverse a full pool.
-TEST_CASE(listpool_traverse_full) {
-  test_pool pool;
-  listpool_make(&pool);
-
-  for (int i = 0; i < NUM_BLOCKS; ++i) {
-    int* val = listpool_alloc(&pool);
-    TEST_TRUE(val != 0);
-    *val = i + 1;
-  }
-
-  TEST_EQUAL(sum(&pool), (NUM_BLOCKS) * (NUM_BLOCKS + 1) / 2);
-}
-
-// Get the ith (allocated) block.
-TEST_CASE(listpool_get_block) {
-  test_pool pool;
-  listpool_make(&pool);
-
-  for (int i = 0; i < NUM_BLOCKS; ++i) {
-    int* block = listpool_alloc(&pool);
-    TEST_TRUE(block != 0);
-    *block = i;
-    TEST_EQUAL(listpool_get_block_index(&pool, block), (size_t)i);
-  }
-
-  for (int i = 0; i < NUM_BLOCKS; ++i) {
-    TEST_EQUAL(*listpool_get_block(&pool, i), i);
-  }
-}
-
-// Remove a value from the list.
-TEST_CASE(listpool_remove_value) {
-  test_pool pool;
-  listpool_make(&pool);
-
-  int* x = listpool_alloc(&pool);
-  int* y = listpool_alloc(&pool);
-  TEST_TRUE(x != 0);
-  TEST_TRUE(y != 0);
-
-  *x = 155;
-  *y = 177;
-
-  listpool_remove(&pool, 155); // x
-
-  TEST_EQUAL(count(&pool), 1);
-  TEST_EQUAL(sum(&pool), *y);
-}
-
-// Stress test.
-//
-// 1. Allocate the pool, either fully or partially. If fully, attempt to
-//    allocate some items past the end.
-//
-// 2. Free all allocated items in some random order.
-
-int main() { return 0; }
diff --git a/mem/CMakeLists.txt b/mem/CMakeLists.txt
new file mode 100644
index 0000000..233d2be
--- /dev/null
+++ b/mem/CMakeLists.txt
@@ -0,0 +1,26 @@
+cmake_minimum_required(VERSION 3.0)
+
+project(mem)
+
+# Library
+
+add_library(mem
+  src/mem.c)
+
+target_include_directories(mem PUBLIC
+  include)
+
+target_link_libraries(mem
+  list)
+
+target_compile_options(mem PRIVATE -Wall -Wextra)
+
+# Test
+
+add_executable(mem_test
+  test/mem_test.c)
+
+target_link_libraries(mem_test
+  mem)
+
+target_compile_options(mem_test PRIVATE -DUNIT_TEST -DNDEBUG -Wall -Wextra)
diff --git a/mem/include/mem.h b/mem/include/mem.h
new file mode 100644
index 0000000..30c24fc
--- /dev/null
+++ b/mem/include/mem.h
@@ -0,0 +1,149 @@
+/*
+ * Block-based Memory Allocator.
+ *
+ * Clients should use the macros to define and use allocators. They make the API
+ * type-safe.
+ *
+ * Like a pool/block-based allocator, this allocator stores data in fixed-size
+ * blocks. However, this allocator also supports allocation of contiguous chunks
+ * of a variable number of blocks.
+ *
+ * Chunk information is stored in a separate array so that client data is
+ * contiguous in the main pool of memory and better cached.
+ */
+#pragma once
+
+#include <assert.h>
+#include <stdbool.h>
+#include <stddef.h>
+#include <stdint.h>
+
+/// Define a typed memory allocator backed by a statically-allocated array.
+#define DEF_MEM(MEM, TYPE, NUM_BLOCKS) \
+  typedef struct MEM {                 \
+    Memory mem;                        \
+    Chunk  chunks[NUM_BLOCKS];         \
+    TYPE   blocks[NUM_BLOCKS];         \
+  } MEM;
+
+/// Define a typed memory allocator backed by a dynamically-allocated array.
+#define DEF_MEM_DYN(MEM, TYPE) \
+  typedef struct MEM {         \
+    Memory mem;                \
+    Chunk* chunks;             \
+    TYPE*  blocks;             \
+  } MEM;
+
+/// Initialize a statically-backed memory allocator.
+#define mem_make(MEM)                                                       \
+  {                                                                         \
+    assert(MEM);                                                            \
+    const size_t block_size = sizeof((MEM)->blocks[0]);                     \
+    const size_t num_blocks = sizeof((MEM)->blocks) / block_size;           \
+    mem_make_(                                                              \
+        &(MEM)->mem, (MEM)->chunks, (MEM)->blocks, num_blocks, block_size); \
+  }
+
+/// Initialize a dynamically-backed memory allocator.
+#define mem_make_dyn(MEM, num_blocks, block_size) \
+  mem_make_(&(MEM)->mem, 0, 0, num_blocks, block_size)
+
+/// Destroy the allocator.
+///
+/// If the allocator is dynamically-backed, then this function frees the
+/// underlying memory.
+#define mem_del(MEM) mem_del_(&(MEM)->mem)
+
+/// Clear the allocator.
+///
+/// This function frees all of the allocator's blocks. The resulting allocator
+/// is as if it were newly created.
+#define mem_clear(MEM) mem_clear_(&(MEM)->mem)
+
+/// Allocate a new chunk of N blocks.
+/// Return a pointer to the first block of the chunk, or 0 if there is no memory
+/// left.
+/// New chunks are conveniently zeroed out.
+#define mem_alloc(MEM, num_blocks) mem_alloc_(&(MEM)->mem, num_blocks)
+
+/// Free the chunk.
+/// The chunk pointer is conveniently set to 0.
+#define mem_free(MEM, CHUNK) mem_free_(&(MEM)->mem, (void**)CHUNK)
+
+/// Return a pointer to a chunk given the chunk's handle.
+/// The chunk must have been allocated.
+#define mem_get_chunk(MEM, HANDLE) \
+  ((__typeof__((MEM)->blocks[0])*)mem_get_chunk_(&(MEM)->mem, HANDLE))
+
+/// Get the handle to the given chunk.
+#define mem_get_chunk_handle(MEM, CHUNK_PTR) \
+  mem_get_chunk_handle_(&(MEM)->mem, CHUNK_PTR)
+
+/// Iterate over the used chunks of the allocator.
+///
+/// The caller can use 'i' as the index of the current chunk.
+///
+/// It is valid to mem_free() the chunk at each step of the iteration.
+#define mem_foreach(MEM, ITER, BODY)                          \
+  size_t i = 0;                                               \
+  do {                                                        \
+    if ((MEM)->chunks[i].used) {                              \
+      __typeof__((MEM)->blocks[0])* ITER = &(MEM)->blocks[i]; \
+      (void)ITER;                                             \
+      BODY;                                                   \
+    }                                                         \
+    i = (MEM)->chunks[i].next;                                \
+  } while (i);
+
+// -----------------------------------------------------------------------------
+
+/// Chunk information.
+///
+/// Every chunk represents a contiguous array of some number of blocks. The
+/// allocator begins as one big unused chunk.
+///
+/// Allocation looks for a free chunk large enough to hold to requested number
+/// of blocks. If the free chunk is larger than the requested chunk size, then
+/// the requested chunk is carved out of the larger block.
+///
+/// Deallocation frees the chunk back and merges it with free neighbouring
+/// chunks. Two free chunks are never contiguous in memory.
+///
+/// 'next' and 'prev' always point to a valid chunk (e.g., 0). Allocation stops
+/// looking for free chunks when it loops over.
+typedef struct Chunk {
+  size_t num_blocks;
+  size_t prev;
+  size_t next;
+  bool   used;
+} Chunk;
+
+typedef struct Memory {
+  size_t   block_size_bytes;
+  size_t   num_blocks;
+  size_t   next_free_chunk;
+  bool     dynamic; /// True if blocks and chunks are dynamically-allocated.
+  Chunk*   chunks;  /// Array of chunk information.
+  uint8_t* blocks;  /// Array of blocks;
+} Memory;
+
+/// Create a memory allocator.
+///
+/// 'chunks' and 'blocks' may be user-provided (statically-backed allocator) or
+/// null (dynamically-backed allocator).
+/// - If null, the allocator malloc()s the memory for them.
+/// - If given:
+///   - `chunks` must be at least `num_blocks` chunks.
+///   - `blocks` must be at least `num_blocks` * `block_size_bytes` bytes.
+///
+/// All blocks are zeroed out for convenience.
+bool mem_make_(
+    Memory* mem, Chunk* chunks, void* blocks, size_t num_blocks,
+    size_t block_size_bytes);
+
+void   mem_del_(Memory*);
+void   mem_clear_(Memory*);
+void*  mem_alloc_(Memory*, size_t num_blocks);
+void   mem_free_(Memory*, void** chunk_ptr);
+void*  mem_get_chunk_(const Memory*, size_t chunk_handle);
+size_t mem_get_chunk_handle_(const Memory*, const void* chunk);
diff --git a/mem/src/mem.c b/mem/src/mem.c
new file mode 100644
index 0000000..ff97f0f
--- /dev/null
+++ b/mem/src/mem.c
@@ -0,0 +1,183 @@
+#include "mem.h"
+
+#include <stdlib.h>
+#include <string.h>
+
+bool mem_make_(
+    Memory* mem, Chunk* chunks, void* blocks, size_t num_blocks,
+    size_t block_size_bytes) {
+  assert(mem);
+  assert((chunks && blocks) || (!chunks && !blocks));
+  assert(num_blocks >= 1);
+
+  mem->block_size_bytes = block_size_bytes;
+  mem->num_blocks       = num_blocks;
+  mem->next_free_chunk  = 0;
+
+  // Allocate chunks and blocks if necessary and zero them out.
+  if (!chunks) {
+    chunks       = calloc(num_blocks, sizeof(Chunk));
+    blocks       = calloc(num_blocks, block_size_bytes);
+    mem->dynamic = true;
+    if (!chunks || !blocks) {
+      return false;
+    }
+  } else {
+    memset(blocks, 0, num_blocks * block_size_bytes);
+    memset(chunks, 0, num_blocks * sizeof(Chunk));
+    mem->dynamic = false;
+  }
+  mem->chunks = chunks;
+  mem->blocks = blocks;
+
+  // Initialize the head as one large free chunk.
+  Chunk* head      = &mem->chunks[0];
+  head->num_blocks = num_blocks;
+
+  return true;
+}
+
+void mem_del_(Memory* mem) {
+  assert(mem);
+  if (mem->dynamic) {
+    if (mem->chunks) {
+      free(mem->chunks);
+      mem->chunks = 0;
+    }
+    if (mem->blocks) {
+      free(mem->blocks);
+      mem->blocks = 0;
+    }
+  }
+}
+
+void mem_clear_(Memory* mem) {
+  assert(mem);
+  mem->next_free_chunk = 0;
+  memset(mem->blocks, 0, mem->num_blocks * mem->block_size_bytes);
+  memset(mem->chunks, 0, mem->num_blocks * sizeof(Chunk));
+
+  // Initialize the head as one large free chunk.
+  Chunk* head      = &mem->chunks[0];
+  head->num_blocks = mem->num_blocks;
+}
+
+void* mem_alloc_(Memory* mem, size_t num_blocks) {
+  assert(mem);
+  assert(num_blocks >= 1);
+
+  // Search for the first free chunk that can accommodate num_blocks.
+  const size_t start     = mem->next_free_chunk;
+  size_t       chunk_idx = start;
+  bool         found     = false;
+  do {
+    Chunk* chunk = &mem->chunks[chunk_idx];
+    if (!chunk->used) {
+      if (chunk->num_blocks > num_blocks) {
+        // Carve out a smaller chunk when the found chunk is larger than
+        // requested.
+        // [prev] <--> [chunk] <--> [new next] <--> [next]
+        const size_t new_next_idx = chunk_idx + num_blocks;
+        Chunk*       new_next     = &mem->chunks[new_next_idx];
+        if (chunk->next) {
+          mem->chunks[chunk->next].prev = new_next_idx;
+        }
+        new_next->prev = chunk_idx;
+        new_next->next = chunk->next;
+        chunk->next    = new_next_idx;
+
+        new_next->num_blocks = chunk->num_blocks - num_blocks;
+        chunk->num_blocks    = num_blocks;
+
+        chunk->used = true;
+        found       = true;
+        break;
+      } else if (chunk->num_blocks == num_blocks) {
+        chunk->used = true;
+        found       = true;
+        break;
+      }
+    }
+    chunk_idx = chunk->next; // Last chunk points back to 0, which is always the
+                             // start of some chunk. 'next' and 'prev' are
+                             // always valid pointers.
+  } while (chunk_idx != start);
+
+  if (found) {
+    mem->next_free_chunk = mem->chunks[chunk_idx].next;
+    return &mem->blocks[chunk_idx * mem->block_size_bytes];
+  } else {
+    return 0; // Large-enough free chunk not found.
+  }
+}
+
+// The given pointer is a pointer to this first block of the chunk.
+void mem_free_(Memory* mem, void** chunk_ptr) {
+  assert(mem);
+  assert(chunk_ptr);
+
+  const size_t chunk_idx =
+      ((uint8_t*)*chunk_ptr - mem->blocks) / mem->block_size_bytes;
+  assert(chunk_idx < mem->num_blocks);
+  Chunk* chunk = &mem->chunks[chunk_idx];
+
+  // Disallow double-frees.
+  assert(chunk->used);
+
+  // Zero out the chunk so that we don't get stray values the next time it is
+  // allocated.
+  memset(&mem->blocks[chunk_idx], 0, chunk->num_blocks * mem->block_size_bytes);
+
+  // Free the chunk. If it is contiguous with other free chunks, then merge.
+  // We only need to look at the chunk's immediate neighbours because no two
+  // free chunks are left contiguous after merging.
+  chunk->used = false;
+  if (chunk->next) {
+    Chunk* next = &mem->chunks[chunk->next];
+    if (!next->used) {
+      // Pre:  [chunk] <--> [next] <--> [next next]
+      // Post: [  chunk + next   ] <--> [next next]
+      chunk->num_blocks += mem->chunks[chunk->next].num_blocks;
+      chunk->next = next->next;
+      if (next->next) {
+        Chunk* next_next = &mem->chunks[next->next];
+        next_next->prev  = chunk_idx;
+      }
+      next->prev = next->next = next->num_blocks = 0;
+    }
+  }
+  if (chunk->prev) {
+    Chunk* prev = &mem->chunks[chunk->prev];
+    if (!prev->used) {
+      // Pre:  [prev] <--> [chunk] <--> [next]
+      // Post: [  prev + chunk   ] <--> [next]
+      prev->num_blocks += chunk->num_blocks;
+      prev->next = chunk->next;
+      if (chunk->next) {
+        Chunk* next = &mem->chunks[chunk->next];
+        next->prev  = chunk->prev;
+      }
+      chunk->prev = chunk->next = chunk->num_blocks = 0;
+    }
+  }
+
+  *chunk_ptr = 0;
+}
+
+// The handle is the chunk's index. We don't call it an index in the public API
+// because from the user's perspective, two chunks allocated back-to-back need
+// not be +1 away (the offset depends on how large the first chunk is).
+void* mem_get_chunk_(const Memory* mem, size_t chunk_handle) {
+  assert(mem);
+  assert(chunk_handle < mem->num_blocks);
+  assert(mem->chunks[chunk_handle].used);
+  return &mem->blocks[chunk_handle * mem->block_size_bytes];
+}
+
+// The given chunk pointer is a pointer to the blocks array.
+size_t mem_get_chunk_handle_(const Memory* mem, const void* chunk) {
+  assert(mem);
+  const size_t block_byte_index = (const uint8_t*)chunk - mem->blocks;
+  assert(block_byte_index % mem->block_size_bytes == 0);
+  return block_byte_index / mem->block_size_bytes;
+}
diff --git a/mem/test/mem_test.c b/mem/test/mem_test.c
new file mode 100644
index 0000000..6ab4c7c
--- /dev/null
+++ b/mem/test/mem_test.c
@@ -0,0 +1,232 @@
+#include "mem.h"
+
+#include "test.h"
+
+#define NUM_BLOCKS 10
+
+DEF_MEM(test_mem, int, NUM_BLOCKS);
+
+static int count(test_mem* mem) {
+  int count = 0;
+  mem_foreach(mem, n, { count++; });
+  return count;
+}
+
+static int sum(test_mem* mem) {
+  int sum = 0;
+  mem_foreach(mem, n, { sum += *n; });
+  return sum;
+}
+
+// Create a statically-backed allocator.
+TEST_CASE(mem_create) {
+  test_mem mem;
+  mem_make(&mem);
+}
+
+// Create a dynamically-backed allocator.
+TEST_CASE(mem_create_dyn) {
+  DEF_MEM_DYN(dyn_mem, int);
+  
+  dyn_mem mem;
+  mem_make_dyn(&mem, NUM_BLOCKS, sizeof(int));
+}
+
+// Allocate N chunks of 1 block each.
+TEST_CASE(mem_fully_allocate) {
+  test_mem mem;
+  mem_make(&mem);
+
+  for (int i = 0; i < NUM_BLOCKS; ++i) {
+    const int* block = mem_alloc(&mem, 1);
+    TEST_TRUE(block != 0);
+  }
+}
+
+// Allocate N chunks of 1 block each, then free them.
+TEST_CASE(mem_fill_then_free) {
+  test_mem mem;
+  mem_make(&mem);
+
+  int* blocks[NUM_BLOCKS] = {0};
+  for (int i = 0; i < NUM_BLOCKS; i++) {
+    blocks[i] = mem_alloc(&mem, 1);
+    TEST_TRUE(blocks[i] != 0);
+  }
+
+  for (int i = 0; i < NUM_BLOCKS; i++) {
+    mem_free(&mem, &blocks[i]);
+    TEST_EQUAL(blocks[i], 0); // Pointer should be set to 0 on free.
+  }
+
+  TEST_EQUAL(count(&mem), 0);
+}
+
+// Attempt to allocate blocks past the maximum allocator size.
+// The allocator should handle the failed allocations gracefully.
+TEST_CASE(mem_allocate_beyond_max_size) {
+  test_mem mem;
+  mem_make(&mem);
+
+  // Fully allocate the mem.
+  for (int i = 0; i < NUM_BLOCKS; ++i) {
+    TEST_TRUE(mem_alloc(&mem, 1) != 0);
+  }
+
+  // Past the end.
+  for (int i = 0; i < NUM_BLOCKS; ++i) {
+    TEST_EQUAL(mem_alloc(&mem, 1), 0);
+  }
+}
+
+// Free blocks should always remain zeroed out.
+// This tests the invariant right after creating the allocator.
+TEST_CASE(mem_zero_free_blocks_after_creation) {
+  test_mem mem;
+  mem_make(&mem);
+
+  const int zero = 0;
+  for (int i = 0; i < NUM_BLOCKS; ++i) {
+    const int* block = (const int*)(mem.blocks) + i;
+    TEST_EQUAL(memcmp(block, &zero, sizeof(int)), 0);
+  }
+}
+
+// Free blocks should always remain zeroed out.
+// This tests the invariant after freeing a block.
+TEST_CASE(mem_zero_free_block_after_free) {
+  test_mem mem;
+  mem_make(&mem);
+
+  int* val = mem_alloc(&mem, 1);
+  TEST_TRUE(val != 0);
+  *val = 177;
+
+  int* old_val = val;
+  mem_free(&mem, &val);    // val pointer is set to 0.
+  TEST_EQUAL(*old_val, 0); // Block is zeroed out after free.
+}
+
+// Traverse an empty allocator.
+TEST_CASE(mem_traverse_empty) {
+  test_mem mem;
+  mem_make(&mem);
+
+  TEST_EQUAL(count(&mem), 0);
+}
+
+// Traverse a partially full allocator.
+TEST_CASE(mem_traverse_partially_full) {
+  const int N = NUM_BLOCKS / 2;
+
+  test_mem mem;
+  mem_make(&mem);
+
+  for (int i = 0; i < N; ++i) {
+    int* val = mem_alloc(&mem, 1);
+    TEST_TRUE(val != 0);
+    *val = i + 1;
+  }
+
+  TEST_EQUAL(sum(&mem), (N) * (N + 1) / 2);
+}
+
+// Traverse a full allocator.
+TEST_CASE(mem_traverse_full) {
+  test_mem mem;
+  mem_make(&mem);
+
+  for (int i = 0; i < NUM_BLOCKS; ++i) {
+    int* val = mem_alloc(&mem, 1);
+    TEST_TRUE(val != 0);
+    *val = i + 1;
+  }
+
+  TEST_EQUAL(sum(&mem), (NUM_BLOCKS) * (NUM_BLOCKS + 1) / 2);
+}
+
+// Get the ith (allocated) chunk.
+TEST_CASE(mem_get_block) {
+  test_mem mem;
+  mem_make(&mem);
+
+  for (int i = 0; i < NUM_BLOCKS; ++i) {
+    int* block = mem_alloc(&mem, 1);
+    TEST_TRUE(block != 0);
+    *block = i;
+    TEST_EQUAL(mem_get_chunk_handle(&mem, block), (size_t)i);
+  }
+
+  for (int i = 0; i < NUM_BLOCKS; ++i) {
+    TEST_EQUAL(*mem_get_chunk(&mem, i), i);
+  }
+}
+
+// Test merging.
+// 1. Allocate chunks of variable sizes.
+// 2. Free them in a different order.
+// 3. Then we should be able to allocate 1 chunk of N blocks.
+TEST_CASE(mem_fragmentation) {
+  test_mem mem;
+  mem_make(&mem);
+
+  int* blocks[NUM_BLOCKS] = {0};
+  int  next_block         = 0;
+
+#define ALLOC(num_blocks)                           \
+  blocks[next_block] = mem_alloc(&mem, num_blocks); \
+  TEST_TRUE(blocks[next_block] != 0);               \
+  next_block++;
+
+#define FREE(block_idx) mem_free(&mem, &blocks[block_idx])
+
+  // 5 total allocations of variable chunk sizes.
+  ALLOC(2); // 2;  idx = 0
+  ALLOC(3); // 5;  idx = 1
+  ALLOC(1); // 6;  idx = 2
+  ALLOC(3); // 9;  idx = 3
+  ALLOC(1); // 10; idx = 4
+
+  // Free the 5 allocations in a different order.
+  FREE(1);
+  FREE(3);
+  FREE(4);
+  FREE(2);
+  FREE(0);
+
+  // Should be able to allocate 1 chunk of N blocks.
+  const void* chunk = mem_alloc(&mem, NUM_BLOCKS);
+  TEST_TRUE(chunk != 0);
+}
+
+// Clear and re-use an allocator.
+TEST_CASE(mem_clear_then_reuse) {
+  test_mem mem;
+  mem_make(&mem);
+
+  // Allocate chunks, contents not important.
+  for (int i = 0; i < NUM_BLOCKS; ++i) {
+    int* chunk = mem_alloc(&mem, 1);
+    TEST_TRUE(chunk != 0);
+  }
+
+  mem_clear(&mem);
+
+  // Allocate chunks and assign values 0..N.
+  for (int i = 0; i < NUM_BLOCKS; ++i) {
+    int* chunk = mem_alloc(&mem, 1);
+    TEST_TRUE(chunk != 0);
+    *chunk = i + 1;
+  }
+
+  TEST_EQUAL(sum(&mem), NUM_BLOCKS * (NUM_BLOCKS + 1) / 2);
+}
+
+// Stress test.
+//
+// 1. Allocate the mem, either fully or partially. If fully, attempt to
+//    allocate some items past the end.
+//
+// 2. Free all allocated items in some random order.
+
+int main() { return 0; }
diff --git a/listpool/test/test.h b/mem/test/test.h
index fd8dc22..fd8dc22 100644
--- a/listpool/test/test.h
+++ b/mem/test/test.h
diff --git a/mempool/include/mempool.h b/mempool/include/mempool.h
index 2447884..994e25a 100644
--- a/mempool/include/mempool.h
+++ b/mempool/include/mempool.h
@@ -108,7 +108,7 @@ typedef struct mempool {
   size_t     num_blocks;
   size_t     next_free_block;
   bool       full;
-  bool       dynamic; // True if blocks and info are dynamically-allocated.
+  bool       dynamic; /// True if blocks and info are dynamically-allocated.
   BlockInfo* block_info;
   uint8_t*   blocks;
 } mempool;