数据结构的序列化是个很有用的东西。这几天在修改原来的资源管理模块，碰到从前做的几个数据文件解析的子模块，改得很烦，就重新思考序列化的方案了。
Java 和 .Net 等，由于有完整的数据元信息，语言便提供了完善的序列化解决方案。C++ 对此在语言设计上有所缺陷，所以并没有特别好的，被所有人接受的方案。
现存的 C++ serialization 方案多类似于 MFC 在二十年前的做法。而后，boost 提供了一个看起来更完备的方案( boost.serialization )。所谓更完备，我指的是非侵入。 boost 的解决方案用起来感觉更现代，看起来更漂亮。给人一种“不需要修改已有的 C++ 代码，就能把本不支持 serialize 的类加上这个特性”的心理快感。换句话说，就是这件事情我能做的，至于真正做的事情会碰到什么，那就不得而知了。
好吧，老实说，我不喜欢用大量苦力(或是高智慧的结晶？)堆积起来的代码。不管是别人出的力，还是我自己出的。另外，我希望有一个 C 的解决方案，而不是 C++ 的。
所以从昨天开始，就抽了点时间来搞定这件事。
问题来至于 C/C++ 语言未提供类型元信息，那我们从根本上去解决好了。
得到元信息的方案不在于使用奇怪的宏，我这个古板的 C 程序员，也用不起现代的 template 技术。其实自定义一下 C 的结构描述方式(创造个小语言)，写个小程序去解析一下就行了。再用这个程序去生成 .h 文件，而供 serialization 库使用的元数据。
如果暂不考虑让别的动态语言更方便的分析序列化后的数据(留给以后再扩展)，其实，需要做序列化的对象仅仅只有两个数据类型：
值类型和对其它类型的引用。
对于值类型，我们可以简单的做内存拷贝，只需要知道值类型的长度。
而引用，在内存中，则是简单的指针。序列化后则是相对数据块的偏移量。这里使用 base 1 ，这样可以允许 0 依旧表示空引用。
我将引用分成两类，分别称呼为外引用，和内引用。
所谓外引用，指这个引用指向一个不需要被序列化的数据块。在做序列化时，库会把这个外引用翻译成一个原子(通常表现为一个唯一的字符串)。数据展开时，再将原子还原成外引用。
比如：文件或窗口句柄就可以被翻译成携带有文件名信息，或窗口标题信息的原子(这个取决于具体实现)。
内引用：指引用的数据类型也为序列化模块所知。被引用的数据同样需要被加入序列化的数据块中。
如果能正确的处理好所有的内引用关系，被引用的数据其实是内存地址无关的。
在我定义的需求中，序列化模块应该尽可能的合并掉值相同的数据块。比如当字符串的值相同时，在序列化结果中就只应该存在一份。如果需要序列化一颗树，相同值的的叶子节点，或完全相同的子树，都应该被合并掉。
另外，序列化模块应该正确的处理环状结构。比如可以正确的序列化一个循环链表，或是复杂的有向图。
考虑到时间复杂度不能超过多项式时间。不考虑合并值相同且拓扑结构相同的有环图。(尽管理论上是可以合并它们的)
由于有上面两个需求，proto buff 等现成的库是用不了的。
btw, 还有一个小需求：数组类型的长度可以不固定，是由同个结构中另一个整型变量的值决定的。
我花了一天一晚初步实现上面的东西。元信息的定义和处理并不复杂。序列化库的接口也很简洁：
传入数据指针，数据类型的元信息，让库去填充一个数据块即可。其实，序列化的对象就是一个有向有环图。整个实现的难点在于对相同节点的合并。
一开始没太想清楚，本着先做对再优化的原则，使用了个最苯的算法。(最坏情况下，可能有 O(N!) 的时间复杂度)即一开始并不合并相同节点。遍历处理完整个图以后，计算每个节点的 hash 值，然后排序，去掉完全相同的节点，并反向修改引用它们的节点。然后反复这个过程，直到有效节点数不再减少。最后再把所有有效节点放在输出流中，最终调整一下所有的内部引用。
今天和同事讨论了一下，觉得可以改进这个算法。
创建两个集合，一个为有效节点的原子集合，另一个为原始数据块的引用集合。
先在遍历原始数据块，同时把原始数据块的每个节点逐个加入原始数据块集合中(相同的原始指针会在这个步骤被去掉)，并生成临时对象方便我们做进一步处理。这个临时对象上，可以附加遍历状态标记，hash 值，长度，等等信息。
当一个节点上的所有引用均被处理完，这个节点的数据可以转换为一个原子，加入有效节点的原子集合。
当碰到成环的情况，只能是由于当前节点引用了一个先前并没有处理完的节点。这个时候，由于环的存在，那个导致环出现的先前的未处理完的节点，可以肯定不会被公用了。所以，我们可以认为，此节点可以直接被转换为一个原子，加入有效节点集合。还句话说，以后也不会再出现另一个数据块和这个原子完全相同。
用此算法，我们可以只通过一次遍历，找到所有的有效节点，并合并掉一切值相同的节点。
最后，一次性将有效节点拼成一个连续的数据块，并修正引用记录即可。
实现的要点在于，要定义一个内存堆，并从堆中申请序列化过程中使用到的临时内存。然后在序列化完成后直接清除整个堆。如果不这样做，整个过程中的各个零碎而繁杂的数据结构的生命期管理会要命的。
同时，需要定义一个 context 结构，用于记录繁杂的序列化流程中的各种数据。并使用 longjmp 做异常处理(主要用于处理用户提供的 buffer 空间不够的情况)。这会使程序变得很简洁。
至于代码，目前还没完全写完。缺少序列化结果展开的部分，以及数据描述语言的解析器(测试代码暂时用手工解析)。
不过序列化部分基本可用了。加上测试代码，大约用 500 行搞定。看来还算是个小玩意。
写下本文，记录下思路。