从list_head到sizeof

在Linux内核中，链表是最常见的数据结构。

一般我们在用户层编程时，使用的链表结构如下：

struct list_node{

          DataType data;

          struct list_node *next;

};

采用这种结构，每个DataType都要定义自己的链表类型，如果用在Linux内核中，那么将充斥这各种各样的链表类型，极不方便。

Linux内核中用了很巧妙的结构。在数据里包含链表，而不是在链表里包含数据。

通用的链表类型

struct list_head{

          struct list_head * next , * pre;

};

struct DataType{

          DataTypeFiled data;

           struct list_head list;

};

list_head使用了typeof，而typeof是编译时处理的，与typeof差不多的函数是sizeof，也是编译时处理的，某些面试题里出现用函数实现sizeof，可以实现一个具有大部分sizeof功能的函数，但是typeof我还没想到好办法用函数实现。

未完待续。。。

sizeof()和typeof()的实现

我们说sizeof()和typeof()是编译时处理的，gcc加上-E选项可以显示预处理后的结果，看看这个例子

1. niuxinli@linux-nxl:~/algrithoms/sizeof> cat test.c 
2. #define NUM  1 
3. int main() 
4. { 
5.     int a = sizeof(int); 
6.     typeof(a) b = 1; 
7.     return 0; 
8. } 
9. niuxinli@linux-nxl:~/algrithoms/sizeof> gcc -E test.c  
10. # 1 "test.c" 
11. # 1 "<built-in>" 
12. # 1 "<command-line>" 
13. # 1 "test.c" 
14.  
15. int main() 
16. { 
17.  int a = sizeof(int); 
18.  typeof(a) b = 1; 
19.  return 0; 
20. } 

可以看到，预处理阶段并没有对sizeof和typeof进行宏替换，说明它们不是用宏实现的。

利用gcc的-S选项可以查看gcc汇编后的汇编文件

1. niuxinli@linux-nxl:~/algrithoms/sizeof> gcc -S test.c  
2. niuxinli@linux-nxl:~/algrithoms/sizeof> cat test.s 
3.     .file   "test.c" 
4.     .text 
5. .globl main 
6.     .type   main, @function 
7. main: 
8. .LFB0: 
9.     .cfi_startproc 
10.     pushq   %rbp 
11.     .cfi_def_cfa_offset 16 
12.     movq    %rsp, %rbp 
13.     .cfi_offset 6, -16 
14.     .cfi_def_cfa_register 6 
15.     movl    $4, -4(%rbp) 
16.     movl    $1, -8(%rbp) 
17.     movl    $0, %eax 
18.     leave 
19.     .cfi_def_cfa 7, 8 
20.     ret 
21.     .cfi_endproc 
22. .LFE0: 
23.     .size   main, .-main 
24.     .ident  "GCC: (SUSE Linux) 4.5.1 20101208 [gcc-4_5-branch revision 167585]" 
25.     .section    .comment.SUSE.OPTs,"MS",@progbits,1 
26.     .string "ospwg" 
27.     .section    .note.GNU-stack,"",@progbits 

可以看到，上面加粗标红的指令就是两个赋值语句，没有调用函数，直接就把4和1赋值给a和b了，说明sizeof()和typeof()不是函数实现的。

编译实际上份好几个过程，预处理只是简单的宏替换，sizeof和typeof应该是在类型检查的时候处理的，在使用它们的时候，可以看作宏。比如下例

1. int main() 
2. { 
3.     int a[sizeof(int)] = {0}; 
4.     return 0; 
5. } 

再看下面的例子

1. niuxinli@linux-nxl:~/algrithoms/sizeof> cat test.c 
2. int main() 
3. { 
4.     int i; 
5.     int a[10]; 
6.     int *b = (int*)malloc(sizeof(int)*10); 
7.     for(i = 0; i < 10; i++) 
8.     { 
9.         a[i] = -1; 
10.         b[i] = -1; 
11.     } 
12.     memset(a,0,sizeof(a)); 
13.     memset(b,0,sizeof(b)); 
14.     printf("sizeof(a)=%d,sizeof(b)=%d\n",sizeof(a),sizeof(b)); 
15.     for(i = 0; i < 10; i++) 
16.         printf("a[%d]=%d,b[%d]=%d\n",i,a[i],i,b[i]); 
17.     return 0; 
18. } 
19. niuxinli@linux-nxl:~/algrithoms/sizeof> make test 
20. make: “test”是最新的。 
21. niuxinli@linux-nxl:~/algrithoms/sizeof> ./test  
22. sizeof(a)=40,sizeof(b)=8 
23. a[0]=0,b[0]=0 
24. a[1]=0,b[1]=0 
25. a[2]=0,b[2]=-1 
26. a[3]=0,b[3]=-1 
27. a[4]=0,b[4]=-1 
28. a[5]=0,b[5]=-1 
29. a[6]=0,b[6]=-1 
30. a[7]=0,b[7]=-1 
31. a[8]=0,b[8]=-1 
32. a[9]=0,b[9]=-1 

a的类型是int [10]，所以它的长度是40,b的类型是int *，64位机器上是8个字节。

我们再来看下怎么用函数实现类似sizeof()的功能

如果用C++，可以用模板

1. niuxinli@linux-nxl:~/algrithoms/sizeof> cat sizeof.cpp 
2. #include <iostream> 
3. #include <stdio.h> 
4. template <typename T> 
5.  
6. size_t my_sizeof(T a) 
7. { 
8.     return (size_t) ((char*)(&a+1) - (char*)(&a)); 
9. } 
10. int main() 
11. { 
12.     int a; 
13.     double b; 
14.     printf("size_of(a) = %d,sizeof(b) = %d\n",my_sizeof(a),my_sizeof(b)); 
15.     return 0; 
16. } 
17. niuxinli@linux-nxl:~/algrithoms/sizeof> make sizeof 
18. make: “sizeof”是最新的。 
19. niuxinli@linux-nxl:~/algrithoms/sizeof> ./sizeof  
20. size_of(a) = 4,sizeof(b) = 8 

如果纯用C语言，可以为每个类型定义一个函数，不过用宏也很方便

1. niuxinli@linux-nxl:~/algrithoms/sizeof> cat sizeof.c 
2. #include <stdio.h> 
3. #define my_sizeof(a)    (size_t)((char*)(&a+1) - (char*)(&a)) 
4. int main() 
5. { 
6.     int a; 
7.     double b; 
8.     printf("sizeof(a) = %d,sizeof(b) = %d\n",my_sizeof(a),my_sizeof(b)); 
9.     return 0; 
10. } 
11. niuxinli@linux-nxl:~/algrithoms/sizeof> gcc sizeof.c 
12. niuxinli@linux-nxl:~/algrithoms/sizeof> ./a.out  
13. sizeof(a) = 4,sizeof(b) = 8 

自己写的sizeof有两个问题，一个是无法计算sizeof(int)这样的，可以通过为每个类型写个宏解决这个问题，如#define sizeof(int)  4

第二个问题是我们写的sizeof不能用作宏，这点没有解决方法。

其实虽说是用函数实现，但也需要在编译时处理，类型检查。

本文转自nxlhero 51CTO博客，原文链接：http://blog.51cto.com/nxlhero/732347，如需转载请自行联系原作者