云风的 BLOG

问题来至于 C/C++ 语言未提供类型元信息，那我们从根本上去解决好了。

得到元信息的方案不在于使用奇怪的宏，我这个古板的 C 程序员，也用不起现代的 template 技术。其实自定义一下 C 的结构描述方式（创造个小语言），写个小程序去解析一下就行了。 再用这个程序去生成 .h 文件，而供 serialization 库使用的元数据。

如果暂不考虑让别的动态语言更方便的分析序列化后的数据（留给以后再扩展），其实，需要做序列化的对象仅仅只有两个数据类型：

值类型和对其它类型的引用。

对于值类型，我们可以简单的做内存拷贝，只需要知道值类型的长度。

而引用，在内存中，则是简单的指针。序列化后则是相对数据块的偏移量。这里使用 base 1 ，这样可以允许 0 依旧表示空引用。

我将引用分成两类，分别称呼为外引用，和内引用。

所谓外引用，指这个引用指向一个不需要被序列化的数据块。在做序列化时，库会把这个外引用翻译成一个原子（通常表现为一个唯一的字符串）。数据展开时，再将原子还原成外引用。

比如：文件或窗口句柄就可以被翻译成携带有文件名信息，或窗口标题信息的原子（这个取决于具体实现）。

内引用：指引用的数据类型也为序列化模块所知。被引用的数据同样需要被加入序列化的数据块中。

如果能正确的处理好所有的内引用关系，被引用的数据其实是内存地址无关的。

在我定义的需求中，序列化模块应该尽可能的合并掉值相同的数据块。比如当字符串的值相同时，在序列化结果中就只应该存在一份。如果需要序列化一颗树，相同值的的叶子节点， 或完全相同的子树，都应该被合并掉。

另外，序列化模块应该正确的处理环状结构。比如可以正确的序列化一个循环链表，或是复杂的有向图。

考虑到时间复杂度不能超过多项式时间。不考虑合并值相同且拓扑结构相同的有环图。（尽管理论上是可以合并它们的）

由于有上面两个需求，proto buff 等现成的库是用不了的。

btw, 还有一个小需求：数组类型的长度可以不固定，是由同个结构中另一个整型变量的值决定的。

我花了一天一晚初步实现上面的东西。元信息的定义和处理并不复杂。序列化库的接口也很简洁：

传入数据指针，数据类型的元信息，让库去填充一个数据块即可。其实，序列化的对象就是一个有向有环图。整个实现的难点在于对相同节点的合并。

一开始没太想清楚，本着先做对再优化的原则，使用了个最苯的算法。（最坏情况下，可能有 O(N!) 的时间复杂度）即一开始并不合并相同节点。遍历处理完整个图以后， 计算每个节点的 hash 值，然后排序，去掉完全相同的节点，并反向修改引用它们的节点。然后反复这个过程，直到有效节点数不再减少。最后再把所有有效节点放在输出流中， 最终调整一下所有的内部引用。

今天和同事讨论了一下，觉得可以改进这个算法。

创建两个集合，一个为有效节点的原子集合，另一个为原始数据块的引用集合。

先在遍历原始数据块，同时把原始数据块的每个节点逐个加入原始数据块集合中（相同的原始指针会在这个步骤被去掉），并生成临时对象方便我们做进一步处理。这个临时对象上， 可以附加遍历状态标记，hash 值，长度，等等信息。

当一个节点上的所有引用均被处理完，这个节点的数据可以转换为一个原子，加入有效节点的原子集合。

当碰到成环的情况，只能是由于当前节点引用了一个先前并没有处理完的节点。这个时候，由于环的存在，那个导致环出现的先前的未处理完的节点，可以肯定不会被公用了。 所以，我们可以认为，此节点可以直接被转换为一个原子，加入有效节点集合。换句话说，以后也不会再出现另一个数据块和这个原子完全相同。

用此算法，我们可以只通过一次遍历，找到所有的有效节点，并合并掉一切值相同的节点。

最后，一次性将有效节点拼成一个连续的数据块，并修正引用记录即可。

实现的要点在于，要定义一个内存堆，并从堆中申请序列化过程中使用到的临时内存。然后在序列化完成后直接清除整个堆。如果不这样做，整个过程中的各个零碎而繁杂的数据结构 的生命期管理会要命的。

同时，需要定义一个 context 结构，用于记录繁杂的序列化流程中的各种数据。并使用 longjmp 做异常处理（主要用于处理用户提供的 buffer 空间不够的情况）。这会使程序变得很简洁。

至于代码，目前还没完全写完。缺少序列化结果展开的部分，以及数据描述语言的解析器（测试代码暂时用手工解析）。

不过序列化部分基本可用了。加上测试代码，大约用 500 行搞定。看来还算是个小玩意。

写下本文，记录下思路。

31 号 补充：

以上对图的相同节点合并算法，是有缺陷的。在处理环问题时，不能做最大可能的合并。

比如：

       +--------------+
       V              |
A ---> B ---> C ----> D
|             ^
+-------------+

在此种情况下，虽然 A 和 D 节点的拓扑结构类似，如果值相等，是可以被合并的。但此算法对此无能为力。

不过考虑到实现的简洁和不错的时间性能，可以容忍这个缺陷。