From ced89ff7989fde2f3d1828c9be70600d70d72e3d Mon Sep 17 00:00:00 2001
From: 3gg <3gg@shellblade.net>
Date: Mon, 17 Jul 2023 09:06:14 -0700
Subject: Add used list to mempool; fix mem iteration.

---
 mempool/include/mempool.h | 35 +++++++++++++++++++++++++----------
 mempool/src/mempool.c     | 35 ++++++++++++++++++++---------------
 2 files changed, 45 insertions(+), 25 deletions(-)

(limited to 'mempool')

diff --git a/mempool/include/mempool.h b/mempool/include/mempool.h
index 23786b3..bd4d4dd 100644
--- a/mempool/include/mempool.h
+++ b/mempool/include/mempool.h
@@ -91,28 +91,43 @@
 /// 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 mempool_foreach(POOL, ITER, BODY)                            \
-  for (size_t i = 0; i < (POOL)->pool.num_blocks; ++i) {             \
-    if (!(POOL)->pool.block_info[i].used) {                          \
-      continue;                                                      \
-    }                                                                \
-    __typeof__((POOL)->object[0])* ITER =                            \
-        &(((__typeof__((POOL)->object[0])*)(POOL)->pool.blocks))[i]; \
-    (void)ITER;                                                      \
-    BODY;                                                            \
+#define mempool_foreach(POOL, ITER, BODY)                                \
+  {                                                                      \
+    size_t i = (POOL)->pool.used;                                        \
+    do {                                                                 \
+      if ((POOL)->pool.block_info[i].used) {                             \
+        __typeof__((POOL)->object[0])* ITER =                            \
+            &(((__typeof__((POOL)->object[0])*)(POOL)->pool.blocks))[i]; \
+        (void)ITER;                                                      \
+        BODY;                                                            \
+      }                                                                  \
+      const size_t next = (POOL)->pool.block_info[i].next_used;          \
+      if (next == i) {                                                   \
+        break;                                                           \
+      }                                                                  \
+      i = next;                                                          \
+    } while (true);                                                      \
   }
 
 // -----------------------------------------------------------------------------
 
 typedef struct BlockInfo {
-  size_t next; /// For free blocks, points to the next free block.
+  size_t next_free; /// For free blocks, points to the next free block.
+  size_t next_used; /// For used blocks, points to the next used block.
   bool   used;
 } BlockInfo;
 
+/// Memory pool.
+///
+/// 'head' and 'used' always points to a valid block (e.g., 0).
+/// The implementation must check whether the head of the lists are used/free.
+/// For example, iteration must stop when it finds the first unused block
+/// (BlockInfo.used == 0).
 typedef struct mempool {
   size_t     block_size_bytes;
   size_t     num_blocks;
   size_t     head;    /// Points to the first block in the free list.
+  size_t     used;    /// Points to the first block in the used list.
   bool       dynamic; /// True if blocks and info are dynamically-allocated.
   BlockInfo* block_info;
   uint8_t*   blocks;
diff --git a/mempool/src/mempool.c b/mempool/src/mempool.c
index 679f124..1100dad 100644
--- a/mempool/src/mempool.c
+++ b/mempool/src/mempool.c
@@ -3,18 +3,14 @@
 #include <stdlib.h>
 #include <string.h>
 
-#define NO_BLOCK ((size_t)-1)
-
-static inline size_t min(size_t a, size_t b) { return a < b ? a : b; }
-
 /// Initialize the free list.
 /// All of the blocks in the pool are assumed free.
 static void init_free_list(mempool* pool) {
   assert(pool);
   for (size_t i = 0; i < pool->num_blocks - 1; ++i) {
-    pool->block_info[i].next = i + 1;
+    pool->block_info[i].next_free = i + 1;
   }
-  pool->block_info[pool->num_blocks - 1].next = NO_BLOCK;
+  pool->block_info[pool->num_blocks - 1].next_free = 0;
 }
 
 bool mempool_make_(
@@ -27,6 +23,7 @@ bool mempool_make_(
   pool->block_size_bytes = block_size_bytes;
   pool->num_blocks       = num_blocks;
   pool->head             = 0;
+  pool->used             = 0;
 
   // Initialize blocks and block info.
   if (!block_info) {
@@ -66,6 +63,7 @@ void mempool_del_(mempool* pool) {
 void mempool_clear_(mempool* pool) {
   assert(pool);
   pool->head = 0;
+  pool->used = 0;
   memset(pool->blocks, 0, pool->num_blocks * pool->block_size_bytes);
   memset(pool->block_info, 0, pool->num_blocks * sizeof(BlockInfo));
   init_free_list(pool);
@@ -74,15 +72,18 @@ void mempool_clear_(mempool* pool) {
 void* mempool_alloc_(mempool* pool) {
   assert(pool);
 
-  if (pool->head == NO_BLOCK) {
-    return 0;
+  BlockInfo* head = &pool->block_info[pool->head];
+  if (head->used) {
+    return 0; // Pool is full.
   }
 
   // Allocate the block.
-  BlockInfo* head  = &pool->block_info[pool->head];
-  void*      block = &pool->blocks[pool->head * pool->block_size_bytes];
-  head->used       = true;
-  pool->head       = head->next;
+  void* block     = &pool->blocks[pool->head * pool->block_size_bytes];
+  head->used      = true;
+  head->next_used = pool->used;
+  pool->used      = pool->head;
+  pool->head      = head->next_free;
+  head->next_free = 0;
 
   return block;
 }
@@ -104,9 +105,13 @@ void mempool_free_(mempool* pool, void** block_ptr) {
   memset(*block_ptr, 0, pool->block_size_bytes);
 
   // Free the block and add it to the head of the free list.
-  info->used = false;
-  info->next = pool->head;
-  pool->head = block_index;
+  info->used      = false;
+  info->next_used = 0;
+  info->next_free = pool->head;
+  pool->head      = block_index;
+  if (pool->used == block_index) {
+    pool->used = 0;
+  }
 
   *block_ptr = 0;
 }
-- 
cgit v1.2.3