Golony

Golony 是一个高性能的 Go 容器库，提供以下特性：

特性

• O(1) 时间复杂度的插入操作
• O(1) 时间复杂度的删除操作
• O(1) 时间复杂度的元素引用
• 高效的元素遍历（跳过已删除元素）
• 引用失效检测

技术实现

• 采用了类似 C++ 库 plf::colony (std::hive) 中的 low complexity jump-counting pattern 来实现高效遍历
• 使用 check pattern 机制来检测引用失效
• 通过跳表优化遍历性能，避免遍历已删除的元素位置

使用约束

• check 由调用方提供，并且必须保证不会与仍可能被持有的旧 Index 重复。推荐使用单调递增的 generation/check 值。
• group 索引使用 uint16 存储，因此最多支持 65536 个 group（索引范围 0..65535）。
• 当 group 数超过 uint16 可表示范围时，后续 Insert 会 panic。

安全模型与已知限制

1. 零值 Index 可能意外匹配存活元素

Index[T]{} 在 Go 中的自然零值为 check=0, group=0, offset=0。若以 check=0 插入了第一个元素，对零值 Index 调用 Get 会成功返回该元素，这意味着未经初始化的 Index 变量可能意外解析为真实对象。

建议：始终以非零 check 值插入元素（例如单调递增的 generation 计数器从 1 开始），使零值 Index 永远无法通过 Get 校验。

2. FatIndex.Pointer() 返回的原始指针绕过 generation 校验

Golony 的元素内存不会因 Insert/Erase 发生移动，因此只要元素仍存活，Pointer() 返回的 *T 始终有效——这是 Golony 的指针稳定性保证，与 plf::colony/std::hive 的设计一致。

ABA 危险：*T 完全绕过 check/generation 机制。若持有者在元素被 Erase 后（该 slot 可能已被新元素复用）仍通过旧指针写入，会静默修改新元素的值，而 Index.check 校验对此无任何感知。

建议：不要将 Pointer() 返回的指针持久化超出当前作用域（例如存入结构体字段、跨帧保存）。若需要跨操作引用元素，请保存 Index 并通过 Get 重新获取指针。

3. Iterate 期间调用 Insert 行为未定义

在 Iterate 的回调中调用 Insert 不会损坏数据结构（skipfield 与 free list 的结构完整性在所有情形下均得到维持），但新插入元素是否会在本次遍历中被访问到是未定义的：

• 若新元素被分配到当前 group 中当前迭代位置之后的空槽，它会被本次遍历访问到；
• 若被分配到当前位置之前的空槽，或触发了新 group 的分配，它不会被访问到。

具体行为取决于容器内部的碎片状态与分配路径，不应在代码中依赖此行为。

建议：如需在遍历中产生新元素，将待插入数据收集到临时切片，在 Iterate 返回后再批量 Insert。在回调中 Erase 非当前元素是允许的；Erase 当前元素请通过回调返回 erase=true 完成，而非直接调用 Erase。

4. Size() / Capacity() 在 32 位平台上可能溢出

Size() 和 Capacity() 返回 int。Golony 的最大理论容量为 65536 × 32768 = 2,147,483,648，恰好超过 math.MaxInt32。在 32 位平台上若容量达到上限，int 转换结果将溢出为负数。

建议：若需要在 32 位平台支持极大容量，请限制 group 数量以确保总容量不超过 math.MaxInt32，或在使用返回值前自行做上限检查。

使用场景

适用于需要频繁插入删除，同时要求保持元素引用稳定性的场景，例如：

• 游戏开发中的实体管理
• 大规模对象池
• 需要频繁更新的数据结构

性能优势

• 插入/删除操作不会导致其他元素的内存移动
• 遍历时可以高效跳过已删除的元素
• 通过引用失效检测机制确保内存安全

许可证

MIT License