我倾向于在 C 程序里使用整数 handle ,而不是指针。尤其是需要做弱引用的时候。
我认为,一个好的 handle 生成算法,应该满足:
如是长期运行的程序,第一和第四个需求不能同时成立。但对于非长期程序,理论上 32bit 的数字应该是够用了。
比较简单的实现方案是用一个自增 id ,然后用一张 hash 表来保存 id 到指针的映射。但 hash 表不是严格的 O(1) 复杂度。在 skynet 中,我使用了一个简单的方法:自增 id 后,如果发现 hash 冲突,就再加一,直到不冲突为止。这个方法不能满足第 4 点需求。
当然,同时满足 5 点需求未必有多大的意义,但我最近想到一个有趣的方案,稍微实现了一下,感觉可以做到。
前提是:为了让 32bit 数字就够用,同时有效的 handle 不能太多(大多数场景是这样的)或是在同时有效的 handle 很多时,不要过于频繁销毁和创建很少的几个 handle 。
我们用一个固定 size 为 2^n 的整数数组来管理所有的 handle 。handle 对 size 取模,就是它在这个数组所在的 slot 。然后,我们只需要维护一个完美 hash 表,所有分配出去有效的 handle 都不在这张 hash 表中发生碰撞。这是可以用 O(1) 时间做到的:方法是,每次回收 handle ,都把该 slot 的高 (32-n) bits 加一,这个新的待分配的 id 绝对不会和已分配过的 id 重复。
和简单的循环自增 id 检查冲突的算法相比较,不仅仅是时间上更稳定。最主要的好处是,这个算法更难耗尽 32bit 的空间(发生回绕)。尤其在有效 handle 数量较多时,一旦发生碰撞,自增 id 的方式一下子就会跳过很多数字,而这些数字中大部分是从来没有使用过,本可以安全的分配出去的。
在 handle 销毁(回收时),同时把 handle 串在该数组里的 free list 即可保证下次 O(1) 时间就能完成新 handle 的分配。
举个例子:
如果我们限制最大有效 handle 数为 4 ,如果把 0 保留为无效 id ,那么分配四次后,handle 分别为 1 2 3 4 。
这时,如果我们把 2 销毁,重新分配的话,新的 handle 是 6 而不是 5 (因为 5 和 1 会发生 hash 碰撞)。这时,再销毁 6 然后分配一个新 handle ,这个新的 handle 会是 6+4 = 10 。
在这个算法中,是不是之后所有新增 handle 都比 10 大呢?并不是。如果销毁 1 ,再分配的话,会得到 5 ,5 比 10 小。
这个算法获得的 handle 的数值并非单调递增的,它比自增方案更节省全部的数字空间。
如果这个数组满了怎么办?一般我们不用考虑这种情况,应该一开始规划好上限(例如 posix 的同时打开文件数就有上限)。但若是想解决,也可以倍增 size 。只不过 rehash 的过程比较复杂:不光是要把已有的有效 handle 重新填在新数组中,还需要额外标记那些可能过于用过的 slots 。
我写了一个简单的实现:https://gist.github.com/cloudwu/dcbf583f7034ef6c0f8adec3f76860f0
借助这个数据结构,我们就可以把同类对象分配在一个大数组中,然后用 handle 索引它们,和指针相比,几乎没有额外的开销。并且有如下好处: