1 files changed, 78 insertions, 0 deletions

diff --git a/listpool/src/listpool.c b/listpool/src/listpool.c
new file mode 100644
index 0000000..9c86a3b
--- /dev/null
+++ b/listpool/src/listpool.c
@@ -0,0 +1,78 @@
+#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;
+}