我不得不承认,在编程的世界,无奇不有,码农的创造力是无穷的,也是妙不可言的!只要涉及到效率,永远是没有最快,只有更快!
我们知道,在标准C中,有函数int isdigit(int c)可以用来判断字符c是否为0~9之间的数字。比如:
知道了isdigit的用途,我们可以抛出问题了:
你会怎样实现isdigit(int c)呢?
我想,绝大多数人的第一反应和最终想法都是使用宏定义去实现这个简单的函数,如下所示:
1 |
#define isdigit(c) ((c) >= '0' && (c) <= '9') |
简洁又美观,使用宏连函数调用的开销都省掉了,效率也不差,这就是最完美的了吗?让我们看看linux内核中是怎样实现这个函数的:
01 |
#define _U 0x01 /* upper */ |
02 |
#define _L 0x02 /* lower */ |
03 |
#define _D 0x04 /* digit */ |
04 |
#define _C 0x08 /* cntrl */ |
05 |
#define _P 0x10 /* punct */ |
06 |
#define _S 0x20 /* white space (space/lf/tab) */ |
07 |
#define _X 0x40 /* hex digit */ |
08 |
#define _SP 0x80 /* hard space (0x20) */ |
10 |
extern
unsigned char _ctype[]; |
12 |
#define isdigit(c) ((_ctype+1)[c]&(_D)) |
14 |
unsigned char
_ctype[] = {0x00, |
15 |
_C,_C,_C,_C,_C,_C,_C,_C,
|
16 |
_C,_C|_S,_C|_S,_C|_S,_C|_S,_C|_S,_C,_C,
|
17 |
_C,_C,_C,_C,_C,_C,_C,_C,
|
18 |
_C,_C,_C,_C,_C,_C,_C,_C,
|
19 |
_S|_SP,_P,_P,_P,_P,_P,_P,_P,
|
20 |
_P,_P,_P,_P,_P,_P,_P,_P,
|
21 |
_D,_D,_D,_D,_D,_D,_D,_D,
|
22 |
_D,_D,_P,_P,_P,_P,_P,_P,
|
23 |
_P,_U|_X,_U|_X,_U|_X,_U|_X,_U|_X,_U|_X,_U,
|
24 |
_U,_U,_U,_U,_U,_U,_U,_U,
|
25 |
_U,_U,_U,_U,_U,_U,_U,_U,
|
26 |
_U,_U,_U,_P,_P,_P,_P,_P,
|
27 |
_P,_L|_X,_L|_X,_L|_X,_L|_X,_L|_X,_L|_X,_L,
|
28 |
_L,_L,_L,_L,_L,_L,_L,_L,
|
29 |
_L,_L,_L,_L,_L,_L,_L,_L,
|
30 |
_L,_L,_L,_P,_P,_P,_P,_C,
|
31 |
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
|
32 |
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
|
33 |
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
|
34 |
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
|
35 |
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
|
36 |
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
|
37 |
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
|
38 |
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
|
很神奇吧,典型的空间换时间的做法。在这里进行简单的解释:我们知道字符'0'~'9'对应的ASCII码为48~57,映射到上面的_ctype数组相应的位置全是_D,_D&_D为真,因此可以对'0'~'9'进行正确的判断。剩下的就是要对此范围外的字符判断为false就OK了。这里的做法精华之处也就在于此,对不同种类的字符进行了分类,并使用唯一的二进制来进行标识,使用&和|保证了不同类别的字符不会同时满足两种分类的条件。
文末说一句,有时间多看看linux内核的代码,毕竟都是经过千锤百炼的。也许很多代码诡异的让你头大,但是hack出其思想后,获得的喜悦也是无法言表的。
;