表驱动法的理解

http://blog.csdn.net/boyinnju/article/details/6882681#

前言

      为什么想写这篇关于表驱动文章呢？在看到《C标准库》第二章关于的实现后，才很大程度上体会到了什么才是表驱动，对它有了稍微深入的理解，写下文章与大家交流交流，望大家赐教。

什么是表驱动法

     按照《代码大全》的说法，“表驱动法是一种编程模式——从表里面查找信息而不使用逻辑语句（if和case）。在适当的环境下，使用表驱动法，所生成的代码会比复杂的逻辑代码更简单、更容易修改，而且效率更高”。
    好比你要设计一个函数int getMonthDays(int mon);函数的输入为月份，输出为该月份的天数（为简单处理，该函数考虑年份的润平）。用c代码可以这样实现。

int getMonthDays(int mon){
    switch(mon){
        case 1:return 31;break;
        case 2:return 29;break;
        case 3:return 31;break;
        case 4:return 30;break;
        case 5:return 31;break;
        case 6:return 30;break;
        case 7:return 31;break;
        case 8:return 31;break;
        case 9:return 30;break;
        case 10:return 31;break;
        case 11:return 30;break;
        case 12:return 31;break;
        default：return 0;
    }
}

      可以看到，函数case语句很多，显得有点笨拙。若用表驱动法，可以先建一张月份天数表，然后直接从该表中取出月份对应的天数。

int monthDays[12] = {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    int getMonthDays(int mon){
        return monthDays[--mon];
    }

    可以看到，所谓的表就是某种类型的数组而已。我们可以通过设置数组下标直接得到要取的的内容，这也暗示这着下标带有某种含义，上例中的数组下标可以理解为月份数减一。
    我们也可以为函数设置表驱动法。
    shell功能是根据用户的输入命令调用不同的程序。我们可以实现一个简单的shell。简化调用的程序是一个函数。一种简单的方法是if-else判断调用。

void call(char *com){
    if(strcmp(com, "command0"))
        return command0();
    else if(strcmp(com, "command1"))
        return command1();
    else if(strcmp(com, "command2"))
        return command2();
    else if(strcmp(com, "command3"))
        return command3();
    else
        puts("no such command!");
}

    现在我们假设命令只有4个。但如果命令有几十个，那么就会有几十个的if-else判断语句，那样程序就会显得很臃肿。好在表驱动可以解决问题。
 

struct comm{
    char *name;
    void (*com)(void);
};
struct comm table[] = {
    {"command0", command0},
    {"command1", command1},
    {"command2", command2},
    {"command3", command3},
};
void call(char *com){
    int i, n;
    n = sizeof(table)/sizeof(struct comm);
    for(i = 0; i < n; ++i){
        if(strcmp(com, table[i].name))
            return (*table[i].com)();
    }
    puts("no such command!");
}

    新的实现方法显得很简洁。同时，也增加了代码的灵活性。若有新的命令要处理，只要在table里面加上一条新的struct comm即可，函数call无需改变。

Plauger的表驱动

    在阅读实现代码时，本人感觉到Plauger就运用了表驱动法。
    Plauger总共运用了三张转换表：_Ctype,_Toupper,_Tolower;

_Ctype

    _Ctype是一张字符的属性表。
    中包含的大部分函数是对于一个字符类型的检测。例如，isdigit(int c)用来判断c是否是‘0’到‘9’中的一个字符，isupper(int c)用来判断c是否是大写字符。那么如何实现这些函数呢？Plauger在文章开头提到一种简单的方法，即直接if-else逻辑判断。例如为了判断一个数字，可以编写：
    if('0' <= c && c <= '9')...
    判断是否为一个小写字母字母，可以编写：
    if('a' <= c && c <= 'z')...
    然而Plauger并没有采用上面的方法，而是用了看上去更为复杂的方法。他用表来解决。我们先来看看他的实现，至于原因我们稍后分析。
    const short *_Ctype = &ctyp_tab[1];
    _Ctype为short类型的指针，指向ctyp_tab[1]。从ctype_tab[1]开始的每个short型元素，都是对每个ASCII字符的属性描述。Plauger在ctype.h中定义了10个字符属性宏。如_UP表大写属性，_PU表符号属性，_SP表是位空白字符，_XD表16进制字符。Plauger的思想是用这些宏并操作表示每个ASCII字符所拥有的属性，然后将属性写入数组中该ASCII的数值位置。对于字符'a','a'是一个小写字母，同时'a'也可以表示一个16进制的数，如0x1a。那么‘a’的属性可以这样表示(_LO|_XD)，_Ctype['a']=(_LO|_XD)。数字字符‘1’即可表示十进制数，也可以用来表示十六进制数，那么‘1’的属性是（_DI|_XD），_Ctype['1']=(_DI|_XD)。
    所有的这些属性在实现中发挥了关键作用。下面我们来分析isalnum的实现。
    int (isalnum)(int c){
        return (_Ctype[c])&(_DI|_LO|_UP|_XA);
    }
       isalnum用来判断一个字符是否为一个字符或一个数字。_Ctype[c]显示取出c字符的属性，然后与后面的判断掩码与运算，即可判断该属性视为在后面属性集之中。很是巧妙。
       实现原理我们已清楚了。那么回到开头的那个问题，为什么要创建一个属性表，取出属性判断，而不是直接用if-else解决问题呢？而且if-else也很简洁方便啊。我想原因有下面两点。
       一个是为了更好地适应更多的体系结构。我们要注意的是，当前我们执行的字符集市ASCII码。但并不是所有体系结构都是用它。Plauger举例说IBM的EBCDIC也是常用字符集。如果某些字符集的小写字符不是连续的，那么if('a' <= c && c <= 'c')...判断显然是错误的了。若需将移植到使用其他字符集的机器上时，我们可以直接修改_Ctype中的属性值，而无需修改islower里的代码。这样库的灵活性大大增强。
    第二个原因简化了条件判断。正如Plauger所举例子，为了判断空白，可以编写if(c==' '||c=='\t'||c=='\v'||c=='\f'||c=='\n'||c=='\r')，条件判断过长，而用表的方法确实显得简练。

_Toupper和_Tolower

        这两张表的设计是为了标准库中tolower和toupper两个函数的实现而设计的。_Toupper表中存储的值是某个与某字符对应的大写字符。所以实现函数显得很简单，直接return _Toupper[c]。_Tolower亦是同理。

后语

    在大二下学期时，郑涛老师在一门专业课上为我们介绍了表驱动，当时为了应付考试，仅仅是记下了几个例子，并没有体会到表驱动的强悍！如今看到Plauger在用了三张表实现了ctype.h，才对表驱动有了感性的认识，心中对老师和大师敬佩不已。