ZArray、ZList、ZMap — MapleStory 集合型別

概述

MapleStory 沒有使用 STL 容器（std::vector、std::list、std::map），而是自訂了三種集合型別，全部透過 ZAllocEx 管理記憶體，與遊戲的記憶體池整合。

---

ZArray — 動態陣列

對應 STL： std::vector<T>（但記憶體分配走 ZAllocEx）

記憶體版面

ZArray<T> 物件（4 bytes）：
┌──────────┐
│  T* a    │──→ [count][T[0]][T[1]]...[T[n-1]]
└──────────┘

陣列資料區塊：
┌──────────┬────────────────────────────────┐
│ count(4) │ T[0]  T[1]  T[2] ...  T[n-1]  │
└──────────┴────────────────────────────────┘
  ↑ a 指向 count 之後（a - 1 = count）

主要 API

ZArray<int> arr;
arr.Insert(&val);          // 加到末尾（預設 nIdx = -1）
arr.Insert(&val, 0);       // 插入到索引 0
arr.GetAt(i);              // 取得第 i 個元素
arr[i];                    // operator[]（等同 GetAt）
arr.GetCount();            // 元素數量（讀取 *(a-1)）
arr.IsEmpty();             // 是否為空
arr.RemoveAt(i);           // 移除索引 i
arr.RemoveAll();           // 清空（釋放記憶體）

重要限制

// T 必須支援 copy constructor 和 operator=
// 因為 InsertBefore 用的是 new(ptr) T() 和 *result = *e
ZArray<ZXString<char>> names;  // ✅ ZXString 有 operator=
ZArray<int> numbers;           // ✅ 基本型別沒問題

擴容策略

插入時若超過容量，以兩倍大小重新分配（類似 std::vector 的倍增策略）：

// InsertBefore 內部
while (nCap < uCount + 1) {
    nCap *= 2;
}
// 重新 ZAllocEx 分配，複製舊資料，釋放舊記憶體

---

ZList — 雙向鏈結串列

對應 STL： std::list<T>（但節點透過 ZRefCountedDummy 管理）

記憶體版面

ZList<T> 物件：
┌──────────┬──────────┬──────────┬──────────┐
│ gap4[1]  │m_uCount  │ m_pHead* │ m_pTail* │
└──────────┴──────────┴──────────┴──────────┘

節點結構（ZRefCountedDummy<T>）：
┌────────────┬──────────┬────────────────────┐
│ZRefCounted │ padding  │   T (實際資料)     │
│(nRef/next) │          │  含 m_pPrev/m_pNext│
└────────────┴──────────┴────────────────────┘

ZList 的節點是 ZRefCountedDummy

這代表 ZList 的每個節點本身就有引用計數，ZRef<T> 可以直接指向節點裡的 T，而不怕節點被提前釋放。

主要 API

ZList<CItem> items;
items.AddTail(&item);           // 加到串列末端
items.AddTail(&otherList);      // 把另一個 ZList 的所有元素加進來
items.GetHeadPosition();        // 取得頭部指標
items.GetTailPosition();        // 取得尾部指標
items.GetCount();               // 元素數量
items.RemoveAll();              // 清空

迭代方式

T* pNode = items.GetHeadPosition();
while (pNode) {
    // 使用 pNode
    pNode = pNode->m_pNext;  // T 必須有 m_pNext 欄位（ZList 節點規範）
}

---

ZMap — 雜湊 Map

對應 STL： std::unordered_map<T, U>（但使用開放鏈結法）

記憶體版面

ZMap<K, V, Unused> 物件：
┌───────────────┬──────────────┬──────────┬──────────────┬─────────────────┐
│ _PAIR** table │ uTableSize   │ uCount   │ autoGrow/128 │ autoGrowLimit   │
└───────────────┴──────────────┴──────────┴──────────────┴─────────────────┘

table[hash(key)] → _PAIR → _PAIR → nullptr（衝突鏈）

_PAIR 結構（16 bytes）：
┌───────────────┬────────┬──────────┐
│ _PAIR* pNext  │  key   │  value   │
└───────────────┴────────┴──────────┘

雜湊函式

// 使用 _rotr（循環右移）
v3[_rotr(*key, 5) % this->m_uTableSize]

主要 API

ZMap<long, CUser*, void> users;
U* val = users.GetAt(&key);     // 查找（回傳 nullptr 或 &value）
users.Insert();                  // 插入（TODO：實作不完整）
users.RemoveKey();               // 刪除特定 key
users.RemoveAll();               // 清空
users.GetCount();                // 元素數量

ZMap 實作不完整

原始碼中 GetPos()、GetNext()、Insert()、RemoveAll()、RemoveKey() 都有 /* TODO */。Ezorsia 只完整實作了 GetAt() 以滿足最常見的「讀取」需求，其餘操作在 DLL 中較少用到。

自動擴容

當元素數量超過 m_uAutoGrowLimit = m_uAutoGrowEvery128 * m_uTableSize >> 7 時，重新調整 hash table 大小（ResizeHashTable，同樣 TODO）。

---

三種容器選擇指南

場景	推薦容器
快速索引存取、需要連續記憶體	ZArray<T>
頻繁插入/刪除、不需隨機存取	ZList<T>
以 Key 查找物件（如 UID → 玩家）	ZMap<K,V,V>

---

物件回收池（ZRecyclable / ZRecyclableAvBuffer）

ZMap::_PAIR 和 ZRefCountedDummy 都繼承自 ZRecyclable，使用 ZRecyclableAvBuffer 管理節點的 new/delete：

void* operator new(unsigned int uSize) {
    return ZRecyclableAvBuffer<T>::GetInstance()->raw_new();
}
void operator delete(void* p) {
    ZRecyclableAvBuffer<T>::GetInstance()->raw_delete(p);
}

效果類似 ZAllocEx：free 時不真正釋放，而是放回回收池。

---

相關筆記

• ZAllocEx — 集合型別的記憶體後端
• ZRefCountedDummy — ZList 節點型別
• 01 — 目錄概覽