我的桌面游戏吧快开张了
最近投了点钱，打算在杭州开一个桌面游戏吧。就是纯粹好玩儿。希望在钱花完前，可以多招待一些朋友来玩。
不过工作太忙，这个事情其实都是合伙人在操心。我临时架了个 blog ，记录下点滴吧。
有兴趣的同学可以关注一下哦。
很临时的东西，希望可以慢慢完善起来。
将来有时间，想多写点程序，利用 web 2.0 和客人多做互动。
« February 2010 | Main | April 2010 »
最近投了点钱，打算在杭州开一个桌面游戏吧。就是纯粹好玩儿。希望在钱花完前，可以多招待一些朋友来玩。
不过工作太忙，这个事情其实都是合伙人在操心。我临时架了个 blog ，记录下点滴吧。
有兴趣的同学可以关注一下哦。
很临时的东西，希望可以慢慢完善起来。
将来有时间，想多写点程序，利用 web 2.0 和客人多做互动。
数据结构的序列化是个很有用的东西。这几天在修改原来的资源管理模块，碰到从前做的几个数据文件解析的子模块，改得很烦，就重新思考序列化的方案了。
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 行搞定。看来还算是个小玩意。
写下本文，记录下思路。
31 号 补充：
以上对图的相同节点合并算法，是有缺陷的。在处理环问题时，不能做最大可能的合并。
比如：
+--------------+
V |
A ---> B ---> C ----> D
| ^
+-------------+
在此种情况下，虽然 A 和 D 节点的拓扑结构类似，如果值相等，是可以被合并的。但此算法对此无能为力。
不过考虑到实现的简洁和不错的时间性能，可以容忍这个缺陷。
当我还在用 C++ 做主要开发语言的最后几年，我已经不大用 protected 了。从箱底翻出曾经钟爱的一本书：《C++语言的设计和演化》，中文版 235 页这样记录:
“ ... Mark Linton 顺便到我的办公室来了一下，提出了一个使人印象深刻的请求，要求提供第三个控制层次，以便能支持斯坦福大学正在开发的 Interviews 库中所使用的风格。我们一起揣测，创造出单词 protected 以表示类里的一些成员，...”
“... Mark 是 Interviews 的主要设计师。他的有说服力的争辩是基于实际经验和来自真实代码的实例。...”
“...大约五年之后，Mark 在 Interviews 里禁止了 protected 数据成员，因为它们已经变成许多程序错误的根源...”
我不喜欢 protected ，但是今天，我偶尔用一下 C++ 时，不再有那么多洁癖。反正很难用 C++ 做出稳定的设计，那么，爱怎么用就怎么用吧。关键是别用 C++ 做特别核心的东西就成了。
今天，碰到一个跟 protected 有关的问题，小郁闷了一下。觉得可以写写。这个倒是个基本问题，貌似以前很熟悉。毕竟很多年不碰了，对 C++ 语法有点生疏。
小时候，我一度以为这样的代码是不合法的。
因为我担心在 foo::foobar 中不能访问 f 的私有成员变量 a。
后来我明白了，所谓私有，是针对类的，而不是具体的对象。
但是今天碰到另一个问题，让我愣了一下。
这次，在 foobar::bar 里，访问 this 的 a 成员允许，但 f 的 a 成员却被禁止了。
因为 foo::a 对 foobar 是 protected 的，foobar 的成员函数可以访问自己的 a ，但是对于 foo 指针，就禁止了。
想了一下，解决方案是。
很坏味道。不过也不太所谓了。
据说公司的 OA 系统是买来的。不知道是谁做的，反正一刹那，我想把这帮人拖出来打一顿。好吧，我不够淡定。
一直以来，这套 OA 系统只支持 IE ，还需要装个 ActiveX 控件才能得到完整的特性。怨声载道啊。这也就忍了。https 的证书没配置好，每次都要求确认一下。我觉得吧，公司还不至于花不了这点钱弄个正式的安全证书。罢了，这也忍忍。
这两天做招聘面试的流程。我的面试记录是写在纸上的。辛辛苦苦的把几份都录入到 OA 系统里。然后电子流程走了一圈。因为到某个环节的流程错误，被退回了。
结果，我输入的面试记录全部被清空了 ！现在要重新敲一遍。
然后 popo 、打电话跟人抱怨这个事情，花得精力已经比重敲一次多了。明天等人从数据库里把原来输入的数据找回来。
怪不得杭州这边分公司报销还在用纸的单子，不走电子的 OA 。尽管不那么环保。
面向对象编程不是银弹。大部分场合，我对面向对象的使用非常谨慎，能不用则不用。相关的讨论就不展开了。
但是，某些场合下，采用面向对象的确是比较好的方案。比如 UI 框架，又比如 3d 渲染引擎中的场景管理。C 语言对面向对象编程并没有原生支持，但没有原生支持并不等于不适合用 C 写面向对象程序。反而，我们对具体实现方式有更多的选择。
大部分用 C 写面向对象程序的程序员受 C++ 影响颇深。企图用宏模拟出一个常见 C++ 编译器已经实现的对象模型。于我愚见，这并不是一个好的方向。C++ 的对象模型，本质上是为了追求实现层的性能，并直接体现出来。就有如在 C++ 中被滥用的 inline ，的确有效，却破坏了分离原则。C++ 的继承是过紧的耦合。
我所理解的面向对象，是让不同的数据元有共同的操作方式，适合成组的处理。根据操作方式的不同，我们会对数据元做不同的分组。一个数据可能出现在这个组里，也可以出现在那个组里。这取决于你从不同的方面提取的共性。这些可供统一操作的共性称之为接口（Interface），接口在 C 语言中，表现为一组函数指针的集合。放在 C++ 中，即为虚表。
我所偏爱的面向对象实现方式（使用 C 语言）是这样的：
若有一组数据，我们需要让他们看起来都有一种叫作 foo 的共性。把符合这样的数据都称为 foo_object 。通常，我们会有如下 api 去操控 foo_object 。
在具体实现时，会在一个叫 foo.c 的实现文件中，定义出 foo_object 结构，里面有一些 foo_dosomething 所需的数据成员。
但是，以上还不能满足要求。因为，我们会有不同的数据，他们只是表现出 foo_object 某些方面的特性。对于不同的数据，它们在 dosomething 时，实际所做的操作也有所区别。这时，我们需要定义出一个接口，供 foo.c 内部使用。那么，以上的头文件就需要做一些修改，把接口 i_foo 的定义加进去，并修改 create 函数。
这里稍做解释。i_foo 是供 foo_dosomething 内部使用的一组接口。构造 foo_object 时，我们把一个外部数据 data 和为 foo_object 相关特性定义出的 i_foo 接口捆绑在一起，传入构造函数 foo_create 。一般，我还会会每个符合 foo_object 特性的对象实现一个方法来得到对应的 i_foo ，如：
创建一个 foo_object 对象的代码看起来是这样：
struct foo_object 的定义中，必然要记录 i_foo 的接口指针和 data 数据指针。从 C++ 的观点看，foo_object 是基类，它也会有一些基类成员和非虚的成员函数。具体的派生类在实现时，改写了虚表 i_foo 的内容（重载了虚函数）。data 数据是在对基类 foo_object 继承时扩展的数据成员。但，在这里，我们使用了组合的方式来扩展成员。这增加了一层间接性，但提供了更低的耦合。其中的优劣暂且不讨论了。
通常看起来会是这样：
此处还有另一个问题：data 的生命期该由谁来负责？
生命期管理是个很大的课题。也是大多数使用 C/C++ 开发的软件的复杂度重要来源。我个人倾向于把生命期管理独立出来解决。所以 foo_object 模块一般并不负责 data 的生命期管理。它只负责 struct foo_object 的资源释放。
自己经营自己，是我的 C 语言软件开发的观点之一。我倾向于采用混合语言编程来更好的解决这个问题。比如 C 和 Lua ，或者 C 和 C++ 。如果不采用混合语言编程，那么也可以在之后，增加一个同样用 C 语言编写的层次来管理。这个话题，留到下次来讲。
剥离出生命期管理，代码量可以减少很多，也不容易犯错误。
ps. C 语言是一个弱类型的语言。至少比 C++ 要弱一些。这表现在：
void * 在 C 语言中可以指代任意数据指针。你可以把任意数据指针赋值给一个 void * 变量，也可以把一个 void * 变量赋给特定的指针类型变量。（这在 C++ 中不推荐，并会被编译器警告）
C 语言中的函数指针也比较有趣。通常，不同类型的函数指针相互赋值是会引起编译器警告的（类型不同）。当然，我们可以用一个 void * 来解决问题。但有时候，我们期望让类型检查严格一些，至少我们不希望把一个数据指针赋值给一个函数指针。但希望编译器不要理会函数参数的差异。
在 C 语言中，void (*foo)() 可以被赋予任意返回 void 的函数指针。即，你可以把 void foobar(int) 的地址赋予前面的 foo 变量（这是由 C 标准的参数传递规则保证的）。
所以，在 C 语言编程中需要注意。如果你想定义一个不接受参数的函数，并让编译器帮你检查出那些错误的多传递了参数的语句。你必须在 .h 文件中严格定义 void foo(void) 以示 foo 函数不接受参数。
在传统的 C 语言中，对结构初始化需要非常小心。这里，我们的 i_foo 接口定义就使用了 C 里的结构。这需要非常谨慎小心。（没有 C++ 编译器帮你做这件事）
C99 新增加的语法增强了这点（在初始化结构时，可以不依赖次序，而写出成员的名字）。值得采用。
昨天，我们工作室这次的编辑器一职的程序招聘工作结束了。
比我预期的时间和人选上都超过了预期。谢谢大家的支持。
原来我的计划是找到两个合适的人来做这些事情，但实际上，这次来面试的数十位同学中达到我们心目中要求的人远远超过了这个数字。我想我也是非常细致的做了这一系列面试工作的，每个来我们办公室面试的同学，都做了一个半小时到两个半小时的沟通交流。
直到最后，依旧纠结于在五六个合适人选中该如何选择。虽然我们最终多安排了一个职位，但还是很遗憾不能与各位想来我们这里的朋友在未来一起共事。
之前有些地理位置上比较远的同学，过年时曾经去 email 说安排一次面试。之后考虑到路途遥远，而我们已经收到了很多附近的同学的面试请求。这段时间又的确找到了合适的人选。顾而没能有机会邀请你们来杭州一叙，很是抱歉。
另，我们在北京和广州的工作室也在招聘。如果愿意，我可以代为转交简历。
我已经给所有参加面试的和投递简历的同学回复了邮件。但还是有可能遗漏。在此致歉。希望能够谅解。
btw, gameres 上有一则招聘帖”杭州网易风云诚聘各类游戏人才“ ，最近几天好多人问起。其实跟我这里没有关系的 :)