5.6 降低判定树的高度（1）
5.5节讲述了对非线性索引表的优化，讨论了最大case值和最小case值之差在255以内的情况。当最大case值与最小case值之差大于255，超出索引1字节的表达范围时，上述优化方案同样会造成空间的浪费，此时采用另一种优化方案—判定树：将每个case值作为一个节点，从这些节点中找到一个中间值作为根节点，以此形成一棵二叉平衡树，以每个节点为判定值，大于和小于关系分别对应左子树和右子树，这样可以提高效率。
如果打开O1选项—体积优先，由于有序线性优化和索引表优化都需要消耗额外的空间，因此在体积优先的情况下，这两种优化方案是不被允许的。编译器尽量以二叉判定树的方式来降低程序占用的体积，如代码清单5-17所示。
代码清单5-17 switch树的C++(www.cppentry.com)源码
- int nIndex = 0;
- scanf("%d", &nIndex);
- switch(nIndex){
- case 2: printf("nIndex == 2\n"); break;
- case 3: printf("nIndex == 3\n"); break;
- case 8: printf("nIndex == 8\n"); break;
- case 10: printf("nIndex == 10\n"); break;
- case 35: printf("nIndex == 35\n"); break;
- case 37: printf("nIndex == 37\n"); break;
- case 666: printf("nIndex == 666\n"); break;
- default: printf("default\n"); break;
- }
如果代码清单5-17中没有case 666这句代码，可以采用非线性索引表方式进行优化。有了case 666这句代码后，便无法使用仿造if else优化、有序线性优化、非线性索引表优化等方式。需要使用更强大的解决方案，将switch做成树，Debug版代码见代码清单5-18。
代码清单5-18 树结构switch片段—Debug版
- switch(nIndex){ // 源码对比
- 00401490 mov ecx,dword ptr [ebp-4]
- 00401493 mov dword ptr [ebp-8],ecx
- ; 取出变量nIndex进行比较
- 00401496 cmp dword ptr [ebp-8],0Ah
- ; 条件跳转，大于10跳转到地址0x004014B9处
- 0040149A jg SwitchTree+59h (004014b9)
- 0040149C cmp dword ptr [ebp-8],0Ah
- ; 条件跳转，等于10跳转到地址0x004014FD处
- 004014A0 je SwitchTree+9Dh (004014fd)
- 004014A2 cmp dword ptr [ebp-8],2
- ; 条件跳转，等于2跳转到地址0x004014D0处
- 004014A6 je SwitchTree+70h (004014d0)
- 004014A8 cmp dword ptr [ebp-8],3
- ; 条件跳转，等于3跳转到地址0x004014DF处
- 004014AC je SwitchTree+7Fh (004014df)
- 004014AE cmp dword ptr [ebp-8],8
- ; 条件跳转，等于8跳转到地址0x004014EE处
- 004014B2 je SwitchTree+8Eh (004014ee)
- ; JE跳转失败，直接跳转到地址0x00401539（default块首地址）处
- 004014B4 jmp SwitchTree+0D9h (00401539)
- 004014B9 cmp dword ptr [ebp-8],23h
- ; 条件跳转，等于35跳转到地址0x0040150C处
- 004014BD je SwitchTree+0ACh (0040150c)
- 004014BF cmp dword ptr [ebp-8],25h
- ; 条件跳转，等于37跳转到地址0x0040151B处
- 004014C3 je SwitchTree+0BBh (0040151b)
- 004014C5 cmp dword ptr [ebp-8],29Ah
- ; 条件跳转，等于666跳转到地址0x0040152A处
- 004014CC je SwitchTree+0CAh (0040152a)
- ; JE跳转失败，直接跳转到地址0x00401539（default块首地址）处
- 004014CE jmp SwitchTree+0D9h (00401539)
-
- …… // case 语句块部分略
-
- // default 语句块
- default:printf("default\n");break; // 源码对比
- 00401539 push offset string "default\n" (004230b0)
- 0040153E call printf (004015e0)
- 00401543 add esp,4
分析代码清单5-18得出，在switch的处理代码中，比较判断的次数非常之多。首先与10进行了比较，大于10跳转到地址0x004014B9处，这个地址对应的代码又是条件跳转操作，比较的数值为35。如果不等于35，则与37比较；不等于37又再次与666进行比较；与666比较失败后会跳转到switch结尾或default块的首地址处。到此为止，大于10的比较就全部结束了。从这几处比较可以发现，这类似一个if 分支结构。
继续分析，第一次与10进行比较，小于10则顺序向下执行。再次与2进行比较，如果不等于2，就继续与3比较；如果不等于3，再继续与8进行比较。小于10的比较操作到此就都结束了，很明显，条件跳转指令后，没有语句块，这是一个仿造if else的switch分支结构。大于10的比较情况与小于10的类似，也是一个仿造的if else分支结构。如果每一次比较都以失败告终，最后将只能够执行JMP指令，跳转到地址0x00401539处，即default块首地址。将这两段比较组合后的结构图如图5-9所示。
 |
| 图5-9 二叉判定树 |