Neil Brown精妙的avl实现

最近在复习数据结构，看到avl树，这样比较复杂的数据结构通常都很搞人。于是上网，找到一个实现看，写这代码的老外叫Neil Brown，一个大胡子，我们知道，在国外，开发人员的水平经常和胡子的多少成正比。还看到他在blog中说，这个代码打算用在linux kernel里，自然不会是普通代码了。 
我拿下来，狠看一阵才看懂，不得不说，这个代码很多地方的实现是很精妙的，和教材上只是为了让你理解概念的代码，区别很大。 
这个实现有一个特点，就是没有一般树实现中的left和right指针，作者用一个数组next[2]来表示，next[0]就是左子树，next[1]就是右子树，然后每个节点也不保存当前的层高，这个是教科书的做法，int longer:2，极其省俭的表示了是左子树长（值为0)，还是右子树长(值为1)，或者当前节点上这颗树是平衡的(值了-1)。 

C代码  

1. /* 
2.  * Usage:  avl3  list of integers ... 
3.  * 
4.  * Each integer will be checked to see if it is currently in 
5.  * the AVL tree.  If not, it will be inserted. If so, it will 
6.  * be deleted.  The tree starts out empty and the final tree is 
7.  * printed (on its side) in an ASCII-art style 
8.  */  
9.   
10. #include   
11. typedef int value_t;  
12.   
13. #define LEFT 0  // 表示左节点，或者左子树长  
14. #define RIGHT 1 // 表示右节点，或者右子树长  
15. #define NEITHER -1 // 以当前节点为根的子树是平衡的  
16. typedef int direction; //重定向一个，表示操作是在左子树还是右子树上  
17. // 树节点的定义  
18. typedef struct node_s {  
19.    value_t        value;  
20.    struct node_s *next[2];  
21.    int            longer:2;  
22. } *node;  
23. #define Balanced(n) (n->longer < 0) // 平衡时值了-1  

这里开始精妙了，我们平时的tree查找是怎么写的，target小于当前节点就下到左子树 
继续找，大于就下到右子树继续找，这里就用一个direction next_step = (target > tree->value)得到了接下来操作的方向。next[next_step]就是接下来要查找的节点 

C代码  

1. node avl_find(node tree, value_t target)  
2. {  
3.     while (tree && target != tree->value) {  
4.         direction next_step = (target > tree->value);  
5.         tree = tree->next[next_step];  
6.     }  
7.     return tree;  
8. }  

作者不大喜欢single rotation和double rotation这样的说法，他把旋转分为两种，一种是2旋，就是single rotation，这个时候用数组的优势就出来了，不用把相似的single rotation写两遍，传入的dir值不同就可以了。 

 

C代码  

1. static node avl_rotate_2(node *path_top, direction dir)  
2. {  
3.     node B, C, D, E;  
4.     B = *path_top;  
5.     D = B->next[dir];  
6.     C = D->next[1-dir];  
7.     E = D->next[dir];  
8.   
9.     *path_top = D;  
10.     D->next[1-dir] = B;  
11.     B->next[dir] = C;  
12.     B->longer = NEITHER;  
13.     D->longer = NEITHER;  
14.     return E;  
15. }  

这里是三旋转，也就是double rotation. 
 
注意旋转后面third变量的作用，third表示新入节点在C还是在E上。如果在E上，独立的C的高度必小于A，因为在E上还没有插入新节点时，C只比A高1,而且C上有D，F垫底，所以独立的C的高度要减2,所以独立的C比独立的A高度小1。 

C代码  

1. static node avl_rotate_3(node *path_top, direction dir, direction third)  
2. {  
3.     node B, F, D, C, E;  
4.     B = *path_top;  
5.     F = B->next[dir];  
6.     D = F->next[1-dir];  
7.     /* note: C and E can be NULL */  
8.     C = D->next[1-dir];  
9.     E = D->next[dir];  
10.     *path_top = D;  
11.     D->next[1-dir] = B;  
12.     D->next[dir] = F;  
13.     B->next[dir] = C;  
14.     F->next[1-dir] = E;  
15.     D->longer = NEITHER;  
16.   
17.     /* assume both trees are balanced */  
18.     B->longer = F->longer = NEITHER;  
19.   
20.     if (third == NEITHER)  
21.         return NULL;  
22.     else if (third == dir) {  
23.         /* E holds the insertion so B is unbalanced */   
24.         B->longer = 1-dir;  
25.         return E;  
26.     } else {  
27.         /* C holds the insertion so F is unbalanced */  
28.         F->longer = dir;  
29.         return C;  
30.     }  
31. }  

插入新节点后已经，树已经不平衡了，需要重新计算节点上的longer值。 

C代码  

1. /*************************************************** 
2.  * INSERTION                                       * 
3.  ***************************************************/  
4. static inline void avl_rebalance_path(node path, value_t target)  
5. {  
6.     /* Each node in path is currently balanced. 
7.      * Until we find target, mark each node as longer 
8.      * in the direction of target because we know we have 
9.      * inserted target there 
10.      */  
11.     while (path && target != path->value) {  
12.         direction next_step = (target > path->value);  
13.         path->longer = next_step;  
14.         path = path->next[next_step];  
15.     }  
16. }  

这里是插入新节点后使树重新平衡的全过程，包括旋转节点和更新高度信息。path_top是更新的起点。如果path_top节点是平衡的，不需要旋转，更新高度信息即可。如果在较短和路径上插入，也不需要旋转，还是更新高度信息，path_top变成平衡的，然后对插入的那棵树更新高度信息。如果在较长的路径上插入，就需要旋转了，first和second表示两次的操作方向，如果相同，就是2旋转，否则是3旋转，这时要注意third变量，如果C和E都为空，那么third变量就是NEITHER，不需要特殊处理，否则，third就传入3旋转的函数，用于下面更新高度信息。 

C代码  

1. static inline void avl_rebalance_insert(node *path_top, value_t target)  
2. {  
3.     node path = *path_top;  
4.     direction first, second, third;  
5.     if (Balanced(path))   
6.         ;  
7.     else if (path->longer != (first = (target > path->value))) {  
8.         /* took the shorter path */  
9.         path->longer = NEITHER;  
10.         path = path->next[first];  
11.     } else if (first == (second = (target > path->next[first]->value))) {  
12.         /* just a two-point rotate */  
13.         path = avl_rotate_2(path_top, first);  
14.     } else {  
15.         /* fine details of the 3 point rotate depend on the third step. 
16.          * However there may not be a third step, if the third point of the 
17.          * rotation is the newly inserted point.  In that case we record 
18.          * the third step as NEITHER 
19.          */  
20.         path = path->next[first]->next[second];  
21.         if (target == path->value) third = NEITHER;  
22.         else third = (target > path->value);  
23.         path = avl_rotate_3(path_top, first, third);  
24.     }  
25.     avl_rebalance_path(path, target);  
26. }  

avl_insert是插入接口，这里又有一个技巧，对于avl树，不用从根节点上开始更新高度信息。开始更新高度信息的起点，是path_top。如果查找的一路上下来，每个节点都是平衡的，那么只能从根上开始更新，否则，从第一个不平衡的节点开始更新。插入完成后，再调用avl_rebalance_insert来平衡树。 

C代码  

1. int avl_insert(node *treep, value_t target)  
2. {  
3.     /* insert the target into the tree, returning 1 on success or 0 if it 
4.      * already existed 
5.      */  
6.     node tree = *treep;  
7.     node *path_top = treep;  
8.     while (tree && target != tree->value) {  
9.         direction next_step = (target > tree->value);  
10.         if (!Balanced(tree)) path_top = treep;  
11.         treep = &tree->next[next_step];  
12.         tree = *treep;  
13.     }  
14.     if (tree) return 0;  
15.     tree = malloc(sizeof(*tree));  
16.     tree->next[0] = tree->next[1] = NULL;  
17.     tree->longer = NEITHER;  
18.     tree->value = target;  
19.     *treep = tree;  
20.     avl_rebalance_insert(path_top, target);  
21.     return 1;  
22. }  

明天再写删除的，太晚了。

为什么STL中的string没有实现operator const char*

std::string（我们就默认是std::basic_string吧）没有直接实现operator const char*，而是用一个c_str()函数来实现这个转换，我过去一直对STL这个舍近求远的做法不大理解，不过最近碰到一个应用场景，说明了这个做法的合理性。 

Java代码  

1. const char* foo()  
2. {  
3.     .......  
4.     // 这里正确的写法是str.size()?str.c_str():0;  
5.     return str.size()?str:0;  
6. }  

如果std::string实现了operator const char*,在这个三元运算符内就会产生一个微妙的问题，就是编译器在进行计算的时候，并不是选择自动对str进行const char*的转型操作，而是选择了对所有参与运算的变量进行类型提升，这里类型提升怎么样提？这里自然是把做为构造函数的参数，来构造一个临时的string对象，在效率上用户可能无法接受，在某些特殊的场景还可能引起程序的错误。不明显的隐式转换，这只是一个例子，无数的陷井还程序中，让后期的调试苦不堪言。 

如果对象是用户自定义，最好选择尽量在构造函数前加explicit，来禁掉通过隐式转换来不明不白地调用拷贝构造函数，创建临时对象。我看了basic_string的定义，构造函数没有加explicit关键字，那么就选择了禁掉operator const char*。 

Book review of "Time Management for System Administrators" (1)

"Time Management for System Administrators"是我第一次读时间管理方面的书,应该来讲还是感触比较深.读了也有两个月了,可真正的时间管理一直没有用起来. 虽然用了google日历,感觉也就是做做样子,而且也不太坚持.可见很多时候,并不是求不着道,而是道在那儿,人却不去理会.

此书是写给系统管理员的,不过程序员也可以在中间学到很多东西.作者在前言里说"This book is not for programmers. Beta readers told me that programmers should find this book extremely useful, but I feel that programmers have different issues and therefore deserve their own book."

我大概总结下我觉得书中对于程序员有用的地方,不过想要养成新习惯,重要的不是知道新习惯如何如何好,而是坚持使用新习惯.据说培养一个新习惯只要1个月,但是这一个月一定要坚持,不然就前功尽弃.我们身上的坏习惯都太多了,每天改掉一点,一个月,就会有巨大的提高.

首先,时间管理的原则是:1.一个管理工作(PDA或者纸笔);2.为那些重要的工作节省脑力;3.使用例程,并坚持它们;4.培养习惯和个人原则;5.在"项目时间"里保存专注;6.在工作以外的社会生活也坚持使用.

对于完成工作,专注非常之重要.SA想要专注并不大容易,因为时时有人找.但程序员一般都会有一些个人空间,帮助进入专注状态.工作中的干扰,最好可以完全避免,因为一但手头的工作被打断,你重新上手的时间可能比你完成剩余工作的时间更长.保存专注还有一些小帖士,比如保持桌子和电脑桌面的清洁,消除办公室里让你分心的东西,禁掉IM,邮件通知等等.同时,注意自己在一天的哪个时间段内最容易专注,在那个时间段内做优先级比较高的工作.最后,因为一天的早上人和事都比较少,可以考虑早点去公司,在那一段时间完成工作.

对于分配的任务,不要认为可以就用大脑记着,一定要用时间管理工具记下来.而且只有记录下来,才可以进行方便的计划,而不是被干扰打断.

大部分人每天的工作都是很无聊的,可以说是例行公事,但是如果例行公事都做不好,就不要考虑做别的更有意义的事情了.将那些琐碎的工都编排起来,记录为每日的例行公事,这样你就不会遗漏,而且也不用每天想有哪些琐碎的事要做.

人的生活是个不断的循环,也可以说是螺旋着上升吧.(也可能是原地转圈,或者说干脆是下降).时间管理也是一个管理循环的系统.时间管理的工具有三个特点,方便携带,可靠,和便于管理.因此,具体来说,时间管理系统的组成元素是这几样.日历,人生目标,每日计划,包括Todo list和Schedule.每天早上,用十分钟来计划自己这一天,检查日历,Todo list,置定Schedule.

.NET学习手记(1)-.NET之前的洪荒年代

如果我没有记错，微软是在2002年的2月14号,就是情人节那天，将.NET推到世人面前的，现在2009年了，.NET已经发展了7年，版本已经到3.5，4.0也马上要推出了。这个时候，我才开始学习.NET，作为一个Windows程序员，应该深感羞愧才对。

程序员不管学习什么，有条重要的途径都是看书。我在项目并用不上.NET时，只好先比看书起，陆陆续续开始看相关的书。国人写的＜你必须知道的.NET>，老外写的。现在在看的有<.NET本质论＞和，计划中的有，还有微软的sscli也打算研究。

我计划写这篇笔记很久了，我的计划是首先谈为什么要有.NET，结果刚开始看＜.NET本质论＞时，就发现Don Box非常清楚和深刻地讲了这个问题。Don Box提到.NET Framework从根本上讲提供了两个核心的集成技术：CLR和XML Web Service，后者我不大了解,没有接触。对于CLR，他则指出，CLR is better COM.

就我个人的理解，.NET的出现，是给机器与程序员之间增加了一层抽象形。原来的层次是 机器－＞操作系统API－＞程序员。Windows的API这个集合极大，是不可能完全掌握的怪物，作为补救，微软推出了MFC啊,WinInet啊之类库，但是这些都只是一层薄薄的封装，谈不上抽象层。而.NET，则是插入操作系统API和程序员之间的一个巨大的抽象层。从概念到编程语言，都是全新的。

另一个来源的支柱就是COM，在.NET之前，COM是Windows平台上支柱型的编程模型。但是COM的问题和它的好处一样多。首先就是复杂，COM是一种二进制接口，基于C＋＋的二进制模型，要求使用者至少得非常熟悉C＋＋。即使如此，在学习COM的过程中，依然会有无数的障碍。Joe甚至认为，COM让微软失去了整整一代程序员。

再者，COM没有实现继承，虽然微软认为，COM强制接口与实现分离，且只提供接口继承，是为了程序员好，但是它又提供了包容与聚合两种所谓的对象复用的方法，结果上就有一条，COM aggregation and COM containment are for identity tricks,not code reuse。

COM对象的生命期依赖于引用计数，而非真正的垃圾收集。我个人觉得引用计数总会给人一种资源管理就安全了的错误感觉，从而忽略了循环计数这种常见却难于发现的情况。而对于复杂一点的系统（如果还经常改变的话），想避免这个问题真的很难。

COM的套间，则是一个典型的提供策略非而机制的例子。STA吧，初看起来感觉是很好很强大，但是实际使用中，发现它简直是死锁之源（至少是假死）。

Don Box书中还提到了其它COM的弱点，比如tlb和IDL没有什么关系，COM不能定义依赖关系。其实，COM设计的时候，考虑的效率，而非易用，采取最小原则，需要最少的统一的 C++ 实现方式。这种方式，当时是必须的，现在看起来却不大合适。

总的来讲，CLR出现之前，的确是个洪荒年代，等我再看阵书，再接着谈感想。

怎样在Linux中文环境下使用drScheme

sili@sili-laptop:~$ LANG=C drscheme
这样启动，就可以正常输入了.

Linux&UNIX 程序开发基础教程 笔记1

这本书只要讲一些Linux上一些基础命令和工具,内容很简单。这里的笔记主要是记录一些看着不怎么熟悉的内容。最近打算来个什么“大干XX天，Linux上道“，万一失业了，艺也多了个。

Linux笔记

只记录自己看着不大熟悉的东西

man -k passwd 列出所有可能是查找项

cp -p (-p为保留权限和修改时间)

find /usr/include -name socket.h -print -exec file '{}' \;
;表示有参数, {}为find的结果,\是;的转义符.{}必须放入''中

whereis vs which
whereis强大点，还可以显示man page

grep -n(显示行号) "asdfasd" *.txt

标准输入
catgrep "john"
标准输出
cat>Phones
[your input]
Ctrl+D

标准错误输出
ls -l foo 2> error.log
将标准输出和标准错误输出定向到同一个文件
ls -l foo 2> error.log 1>&2, 如果一个符号依赖于另一个符号，就必须依照从左到右的顺序指定重定向。
＞＞代表追加

命令1|&命令2
将命令1的标准输出和标准错误输出和命令2的标准输入相连

命令1|tee 文件列表|命令2
cat text.cxx text.cxx~|grep "main"|tee file1 file2|wc -l

chmod可以修改的权限位一共有4个3bit,SUID,SGID,粘滞位

SUID位
SUID位的文件被执行时，该文件将以所有者的身份运行，也就是说无论谁来执行这个文件，他都有文件所有者的特权。如果所有者是root的话，那么执行人就有超级用户的特权了。这时该位将变成一个安全漏洞，因此不要轻易设置方位 。
SUID位显示有s和S之分，如果用户本来没有执行权限，用chmod u+s 文件，设置SUID位，用ls -l显示的话是S，如果事先已有了执行权限，显示为s.

SGID与上相同,不过是组ID，命令为chmod g+s 文件.

粘滞位
要求操作系统在可执行程序退出后，仍在内存中保留该程序的映象。这样做是为了节省大型程序的启动时间，不过会占用系统资源。 命令为chmod +t 文件

用&加在命令最后，将命令放入后台
find / -name foo -print>foo.paths 2>/dev/null&

ps a 终端上所有的进程
ps -e 所有进程
ps aux 详细信息
ps auf|more 详细信息,包括进程关系

fg/bg ％进程号
把进程转移到前台/后台

kill -l 列出所有信号编号

Ctrl+Z将程序挂起

tar归档解档
tar -zcf gc.tar.gz ./yfgc/
tar -zxf gc.tar.gz

记录一个bug

最近改的一个bug比较麻烦.症状是一个.NET程序调用我们写的Native code出错,死锁了.用WinDbg观察,发现是死在.NET层中用于垃圾收集的一个线程中,叫Finalize thread,专门用于收集不用的unmanaged的资源.下面这篇文章具体描述Finalize thread的死锁.

http://dotnetdebug.net/2005/06/22/blocked-finalizer-thread/

我对.NET完全是白痴,只用C#写过几个demo程序用来验证API,看着这情形就晕了.不过还是可以看到,一个生存在STA套间的线程(大概是主线程),在等Finalize thread完成,而Finalize thread则在等待一个STA的COM组件的反应.于是死锁发生了.

现在在回忆的时候,觉得这一切再明显不过.不过在调查这个bug过程中,却觉得非常困难,原因有2,首先是不懂.NET,看着这些就有障碍.再者,这个项目是在已有代码的基础上继续开发,对原有的代码不熟悉,还有些程序根本就没有源代码,比如调用我们Native code的.NET程序.

问题在于在使用那个COM组件前后,调用了CoInitialize(NULL)和CoUninitialize(),实际这个是不必要的,因为在每个线程起来时都会调用,这里其实只是重复调用,当时没有多想,只是为了保险写了这样两句.而调用这段的Native Code的线程则是在MTA中的,问题就这样出现了.也有文章说这个事情的.

http://blogs.msdn.com/benkuhn/archive/2006/09/15/756401.aspx

大概是说CoInitialize和CoUninitialize的nest call,如果是进入不同的模式,会引起COM库的引用计数混乱.去掉这一对对CoInitialize/CoUninitialize,程序正常.

非常想研究下.NET的内部架构,这样的错误就不会犯了.