Tips record 二月 20th, 2012
写过的代码还会再写的。
前几天在实现一些链表和树结构，有些地方想记录一下。
有人说在并行程序中链表已经过时了，之前也听人说良好的树形结构比HASH算法更加节省内存，关于这些面向特定场景的讨论，结论不一定对，但比较有启发性。当然我去重新写什么链表或者树形结果的动机并不是这些，仅仅是看到一些丑陋的实现，同时觉得平时这些东西用得比较多，所以就重写一下，写的同时又看到了一些很漂亮的实现技术，同时反过来对整个设计产生了一点反思，整理一下，写在这里。
一般书本上的链表结构大概是这样的：
这种实现往往会和具体问题有冲突。比如，我们之前已经有了一个大的结构，现在我们要将他们链接起来，不能更改名字。一种直观的解决方法是在原有结构里面加上prev和next指针。除去实现上的不自然，还有一个问题，假如我们需要的不仅仅是这种常规的链表，而是需要需要多层次的链表，一个结构可能属于多个不同的链表，这样的话，我要在结构里面加入prev0，next0，prev1，next1……？再比如，我的结构不一样，第一个节点是struct Man，第二个是struct Woman怎么办？显然这么想的话整个设计会越来越不堪。
链表是一种概念，将一连串的Object链接起来的概念，而不是一种实现结构的模式，有一次我看到我妈帮我补裤裆，我便突然想到，链表其实应该想针线一样，小而轻，不管是什么布，插进去拉出来再插到另外一边然后一切都link到一起了。当时虽然想到这个形式，但是不知道怎么实现，“怎么获得结构体的地址？”，这样的问题我也不知道怎么去google，有一次看到C里变参宏的实现，觉得可以通过offset来实现一个获取结构地址的方法，但是又担心结构体对齐各个编译器实现有些不同，还是没有真正的去实现。后来我发现，使用C或者C++写程序的人总会存在各种不兼容，未定义的顾忌，大家觉得要写出移植性好的程序，但是总发现语言本身存在很多未知的地方，所以有了想法也很难第一时间下手实现出来，直到慢慢了解，熟悉如何权衡。
后来我在Linux kernel(linux/list.h)里面看到这样的实现，盯着那段list_entry宏看了很久。这里有对于这个结构的解读。关键的地方是扭转以往对于链表的形式概念，然后搞懂list_entry的意义，其他都很简单了。但仔细看这个实现，就算关于链表的形式实现变了，但是关于API的设计和以往的书本上还是有很大的不同， Linux kernel design patterns - part 2 里面对于这样设计API的原因做了很好的阐述
- Embedded Anchor: A good way to include generic objects in a data structure is to embed an anchor in them and build the data structure around the anchors. The object can be found from the anchor using container_of().
- Broad Interfaces: Don't fall for the trap of thinking that "one size fits all". While having 20 or more macros that all do much the same thing is uncommon, it can be a very appropriate way of dealing with the complexity of finding the optimal solution. Trying to squeeze all possibilities into one narrow interface can be inefficient and choosing not to provide for all possibilities is counter-productive. Having all the permutations available encourages developers to use the right tool for the job and not to compromise. In 2.6.30-rc4, there are nearly 3000 uses of list_for_each_entry(), about 1000 of list_for_each_entry_safe(), nearly 500 of list_for_each(), and less than 1000 of all the rest put together. The fact that some are used rarely in no way reduces their importance.
我们可以以同样的方式来实现树形结构。在实现树形结构之前，要提一下的是，在看到Linux/list.h之后，我总想是否不需要增加额外的类型结构，直接用一个基础数据类型来存储指针类型？我找了找，的确有一个uintptr_t的类型符合要求，有一点要注意的是这个类型并非所有的标准都支持。但在你程序运行的特定平台上，总有一个基础类型是合适的选择，所以你真的有需要这么做的话，可以牺牲一下移植性。把可能出现移植问题的地方尽可能的标注出来，或者统一起来，便于移植。这里有一份代码值得参考一下。
另外说一说二叉搜索树，下面是我以前实现的一个版本
里面有两处比较trick的地方，第一是通过关系运算符的返回值类确定左右指针，第二个是在删除的时候，通过简单编码的方式得到删除节点的位置，这一定程度上缩短了代码的长度。除此之外，我后来意识到整个实现有一种对实际问题的忽视。比如，我并不知道使用这课树的人要进行怎样的操作，频繁的插入？这时可能需要缓存之前插入时候的位置。频繁的全局或者局部搜索？这是可以实现为线索树(threaded tree)。针对这样的情况，怎么设计高效可用的API？这里没法提供一个统一的接口去满足所有的需求，保持一切透明，提供必要的工具箱，让使用者根据自己的情况去快速的构建接口或许是好的方式。上面那篇文章里总结到
Tool Box. Sometimes it is best not to provide a complete solution for a generic service, but rather to provide a suite of tools that can be used to build custom solutions.
另外一句话我觉得很有启示
By providing the basic tools and leaving the details up to the specific situation, users of rbtree find themselves liberated, rather than finding themselves fighting with a library that almost-but-not-quite does what they want.
虽然道理很简单，但是我在写一些接口的时候总是忽视了别的场景，不自觉的按“我觉得应该这样”的思维来过度包装了一些东西。我现在我觉得针对特定的问题域，才能找到最优美的解决方案。
最近看了GoingNative2012这几个视频，觉得值得看一下。关于程序设计，权衡之权衡的问题。
Update：
最近在stackoverflow上看到这么一条讨论《Under what circumstances are linked lists useful?》,这里面有比较丰富的信息（建议移步），其中有几点需要说的：
0， 链表的实现有层次之分，好的实现和坏的实现差距差距较大，在我看到的“好”的实现里，基本上都是以offset来规避指针，并且node本身非常轻量级，不需要调用malloc/free等函数（这在嵌入式应用里是非常重要的）。
1， 链表和数组对比最大的优势之一就是可以在中间进行插入删除，复杂度为O（1），但是这里需要注意一个事实，遍历链表的复杂度往往大于拷贝一个数组的复杂度，在一个“经典”（我个人认为这是坏的实现）中，我们遍历一个链表的操作如下：
while (pnode != NULL) {
/* do something */
pnode = pnode->next;
}
这里会出现（假设这里pnode不被放入寄存器）三次memory access，而相同情况下，遍历一个数组只有一次memory access，所以，如果数据长度为N，假如插入和删除经常发生在(N / 2)的时候，此时选择数组会比链表在复杂度上更合适，比且会有其他好处，比如对链表进行排序通常比对数组进行排序更加耗时。
2，linked list适合用来link大数据块的东西，并且最好是操作位置比较集中，比如在长度未知的情况下，实现栈，队列等。
3，文中我的代码写得太silly了，请忽略。