筆者在 C 的世界第一站，選擇先把地基打好：memory pool
因為在 C 裡要 hash 沒有、陣列也無法自動擴容
要物件需要自己 malloc/free，一不小心就記憶體外洩 memory leak
只要 memory pool 先到位，後面的 value/array/table/matcher 都能「有秩序地長大」

為什麼要 memory pool

• C 的 malloc/free 成本高、碎片化嚴重，小物件大量分配很快就失控
• matcher tree 充滿微小物件（節點、字串、臨時緩衝），需要一個「一次性回收」的容器
• 生命週期清楚：建樹期用一個固定 pool，匹配期可用 temp pool，比對完一筆資料一鍵 reset 或 free
• O(1) 回收：不用逐一 free，整池無腦回收，一個不漏
• 錯誤傳遞簡單：把錯誤掛在 pool->error，上層每次呼叫後只要檢查一個地方
• 跨模組一致：value/array/table/matcher 都統一走 pool->alloc，記憶體統一列管，介面單純
• 為 bridge 打地基：Ruby/Go 的 finalizer 可以直接綁 pool 的 reset/free，淺包裝（shallow wrap）也能安全依賴 pool

設計目標

• 分配便宜：pool->alloc(pool, size) 接近「指標往前推」的成本
• 擴容穩定：當一個 chunk 用完，自動長下一塊，chunk 大小採倍增，讓 chunk 數量維持 O(log n)
• 生命週期清楚：reset 持有記憶體但指標歸零，一秒回到解放前，free 一次收工
• 友善錯誤：把錯誤掛在 pool->error，上層統一檢查
• 追蹤外部分配：trace(ptr, size) 把外部記憶體跟 pool 綁一起，free 時能一併處理（或至少集中紀錄）

模型：單向串列 + 倍增策略

最小模型是「一條 chunk 的 linked list」
每個 chunk 長這樣：

typedef struct mongory_memory_node {
  void *ptr;      // 這塊記憶體的起點
  size_t size;    // 總大小
  size_t used;    // 已用位元組
  struct mongory_memory_node *next; // 下一塊 chunk
} mongory_memory_node;

typedef struct mongory_memory_pool_ctx {
  size_t chunk_size;            // 下一塊 chunk 預設大小（會倍增）
  mongory_memory_node *head;    // 第一塊
  mongory_memory_node *current; // 正在使用的那一塊
  mongory_memory_node *extra;   // 追蹤外部分配用的清單
} mongory_memory_pool_ctx;

倍增策略的好處是：當需求從 2KB → 4KB → 8KB… 成長時，chunk 數量是對數級（O(log n)），減少系統呼叫與碎片化
這點在長時間跑 matcher 的情境，穩定性差很多

為什麼用 chunk

• 減少系統呼叫：一次向系統要一大塊，後續小分配都在使用者空間完成，malloc/free 次數驟降
• 改善區域性：同一輪建樹產生的小物件會落在相近位址，上層遍歷時快取命中率更好
• 彈性擴容：用完一塊 chunk，自動再向系統 malloc 下一個，夠無腦
• 降低碎片：小物件不會與系統 allocator 的其他需求互相穿插，碎片化顯著下降
• 簡化 reset：只要把每個 chunk 的 used 歸零，指標回到 head，下一輪直接重用
• 易於追蹤：chunk 是明確的邊界，debug/profiler 觀察與統計更直觀

為什麼要倍增

• 阿嬤邏輯：你吃不夠飽（不夠用）啊？給你雙倍份量，不夠飽再告訴我
• O(log n) 擴容：總 chunk 數隨需求量成長為對數級，擴容次數與成本被攤平
• 避免抖動：線性加法（+k）容易在臨界點頻繁 grow，倍增可迅速跨越需求峰
• 保持區域性：更少、更大的 chunk 讓資料更集中，迴圈與樹遍歷受益
• 心智負擔低：實作簡單、預測容易，比起動態估算「應該加多少」更穩定

綜合上面兩個考量，筆者使用倍增策略的 chunk pool，開發體驗簡直像在寫高階語言一樣簡單

介面：alloc/reset/trace/free

struct mongory_memory_pool {
  void *(*alloc)(mongory_memory_pool *pool, size_t size);
  void  (*trace)(mongory_memory_pool *pool, void *ptr, size_t size);
  void  (*reset)(mongory_memory_pool *pool);
  void  (*free)(mongory_memory_pool *pool);
  void *ctx;               // 指向 mongory_memory_pool_ctx
  mongory_error *error;    // 發生錯誤時掛在這裡
};

• alloc：若 current 不夠，呼叫 grow，成功就回傳對齊後的位址，used += size
• trace：把外部 ptr 串到 extra 清單（視設計決定 reset/free 的處理策略）
• reset：把 current 指回 head，每塊的 used 歸零（chunk 還在，下次可重用）
• free：釋放整條 head 串列與 extra 清單

抽象化的優點

把所有的 function 通通抽象成 function pointer ，核心的分配 ctx 又做成抽象的 void，有什麼好處？
好處是如果未來某一天，有別的專案要引用 mongory core，但記憶體分配策略想要配合他自己的方式，這時候

mongory_memory_pool *my_pool = {
  .alloc = my_custom_alloc
  .trace = my_custom_trace
  .reset = my_custom_reset
  .free = my_custom_free
  .ctx = my_custom_context
  .error = NULL             // 乖一點，一開始不要亂塞 error
}

像這樣定義好你自己的記憶體分配策略，然後送進 Mongory core 系統，一樣可以配合使用！
這做法很適合用在效能敏感或嵌入式設備等場景

核心片段（概念化）

static inline mongory_memory_node *
mongory_memory_chunk_new(size_t size) { /* malloc + 初始化 used=0 */ }

static inline bool
mongory_memory_pool_grow(mongory_memory_pool_ctx *ctx, size_t need) {
  size_t newsz = ctx->chunk_size;
  while (newsz < need) newsz <<= 1;      // 倍增到能裝下
  mongory_memory_node *node = mongory_memory_chunk_new(newsz);
  if (!node) return false;
  ctx->chunk_size = newsz << 1;          // 下一次預估再加倍
  ctx->current->next = node;
  ctx->current = node;
  return true;
}

static inline void *
mongory_memory_pool_alloc(mongory_memory_pool *pool, size_t size) {
  mongory_memory_pool_ctx *ctx = pool->ctx;
  // 對齊略
  if (ctx->current->size - ctx->current->used < size) {
    if (!mongory_memory_pool_grow(ctx, size)) {
      // 掛錯誤，回傳 NULL
      return NULL;
    }
  }
  void *ptr = (char*)ctx->current->ptr + ctx->current->used;
  ctx->current->used += size;
  return ptr;
}

Reset 與 Free 的語意

• reset：視為「把所有小物件一次性回收，但保留大塊記憶體」，下次再 alloc 直接從 head 開始，成本非常低
• free：整個 pool 壽終正寢，所有 chunk 與追蹤記憶體一起釋放
• 追蹤記憶體（trace）：常見用在外部函式回傳的 buffer，需要與 pool 同生命周期管理

帶著 pool 的物件

為了讓上層方便、也能在錯誤時回到 pool：筆者讓所有高階物件（value/array/table/matcher）都帶有 pool* 欄位
這讓：

• 物件內部再分配可以直接走 obj->pool->alloc
• 上層要查錯誤，直接看 obj->pool->error
• 在 bridge（Ruby/Go）中，也能把 pool 的 reset/free 綁到語言的生命週期（GC）

邊界與踩雷

• 別在 reset/free 後繼續使用舊指標，特別是 free，那是未定義行為
• 錯誤一定掛 pool->error，不要直接 fprintf(stderr, ...) 後就結束，上層需要可預期的錯誤型別

微小基準與體感

在 1e5 次固定大小分配的情境下，memory pool 的 alloc 幾乎是 pointer bump 的等級，搭配倍增，chunk 次數落在對數級，整體分配時間相當穩定
這讓後續的 matcher tree 建構能放心從大塊 chunk 上高效分配出大量小物件，不怕碎片化拖垮效能

測試要點（Unity）

void test_initial_pool_size(void) {
  mongory_memory_pool *pool = mongory_memory_pool_new();
  mongory_memory_pool_ctx *ctx = pool->ctx;
  TEST_ASSERT_EQUAL(2048, ctx->chunk_size); // 例如預設 2KB
  pool->free(pool);
}

void test_reset_reuse(void) {
  mongory_memory_pool *pool = mongory_memory_pool_new();
  void *p1 = pool->alloc(pool, 256);
  pool->reset(pool);
  void *p2 = pool->alloc(pool, 256);
  TEST_ASSERT_NOT_NULL(p1);
  TEST_ASSERT_NOT_NULL(p2); // reset 後仍可分配且從頭開始
  pool->free(pool);
}

結論

第一步就實作 memory pool ，並把「分配/釋放/擴容/錯誤/追蹤」一次想清楚，後面才有底氣一路寫到 value、array、table、matcher
這套 pool 讓筆者在 C 裡用「內部無腦 alloc，交給外部統一 free」的工作流，寫 matcher 幾乎跟寫高階語言一樣自然，完全沒有「我是不是忘了 free」的心理負擔

下一篇 Day 11，筆者會把「值的世界」整理成一個統一的 mongory_value：型別標籤、比較函式、字串化、與 function pointer dispatch，讓 matcher 能在 C 裡輕鬆說話

專案（C Core）