多级指针和链表

如果看到一个声明：type **********************ptr;你会怎么想？估计一半人都疯了，如此声明一个变量的人本身要么是一个高手，要么是一个低能。这样的一排*事实上表示的是一个链表，链表上的每一个元素可以分布在内存的任意一个位置，它们之间每两个通过一个*相联系。*p定义一个指针，p指向一个内存位置，该位置中保存p声明的数据类型，而**p表示一个指针的指针，p指向一个位置，该位置存放一个指针，后者指向p声明的数据类型，类似的***p也一样表示一个指针，****p也没什么区别，这么一大堆指针真的就是一个链表了，以下是一个例子：
void test()
{
int *l1,*l2,*l3,*l4;
int ba = 0x1234;
l4 = &ba;
l3 = &l4;
l2 = &l3;
l1 = &l2;
int *p = l1;
printf("? value:%X\n", (*(int *)p)); //1
printf("? value:%X\n", (**(int **)p)); //2
printf("? value:%X\n", (***(int ***)p)); //3
printf("? value:%X\n", (****(int ****)p)); //4
}
会打印什么呢？l1，l2，l3，l4都在栈上分配，其地址当然也在栈上，1处将打印l2的地址，由于l2指向的也是一个地址，2处将打印l3的地址，同样3处打印l4的地址，4处最终解码出了0x1234这个数字，是这样吗？测试一下就知道了。由此可见**********...确实可以当成链表的next来使用，每增加一个*，链表就往前推进一个元素，相当于引用了当前节点的next节点。由于指针实际上是一个地址，因此构造这个******...链表的时候一定要注意每一个节点都必须是通过&取到的真正的地址，而不能任意赋值，否则就会造成访存违规，程序出错。既然使用了*****...这么一大堆指针，你就要保证使用(*****...)p解码节点元素的时候每一级都是一个地址，上述的例子通过&取到了地址，然后赋值给一个指针，最终的那个l1其实就是一个4级指针，****p最终指向0x1234。
理解了多重指针的本质，下面需要将其构造成一个真正的链表。上面的test函数仅仅将lx声明成int类型的指针，一个int型的数据存放在内存的一个位置，既然通过*相联系的节点没有必要相邻，那么一个int型的指针除了存放指针值之外，该值所在地址下面或者上面的一部分相邻的地址空间也是可以被利用的，比如：
int *p1;
int *p2 = &p1;
int *p3 = &p2;
这里的p1，p2，p3都是指针，也就是一个地址，那么px+/-Y的区域都可以被使用，每一个p将得到一个Y+sizeof(int *)的连续空间范围，这个范围内可以存储自己的数据，最终通过****...可以解码到某个节点，然后再该节点附近大小为Y的范围内就可以找到自己的数据，由此可以设计出以下的数据结构：
struct lst;
struct lst {
struct lst* fuc;
int value;
};
可见，lst是一个结构体，携带了一个value数据，这里不要太在意fuc(?)字段，它的地址其实就是lst的地址，而它的内容则是next的地址，通过该字段可以将几个lst结构体链接在一起，这是c语言的要求，和上述int类型测试时的不断&取地址是一致的。接下来看一下新的test2函数，它演示了***...和链表的同一性：
void test2()
{
struct lst* l1 = (struct lst*)calloc(1, sizeof(struct lst));
struct lst* l2 = (struct lst*)calloc(1, sizeof(struct lst));
struct lst* l3 = (struct lst*)calloc(1, sizeof(struct lst));
struct lst* l4 = (struct lst*)calloc(1, sizeof(struct lst));
l1->fuc = l2;
l1->value = 0x111;
l2->fuc = l3;
l2->value = 0x222;
l3->fuc = l4;
l3->value = 0x333;
l4->fuc = NULL;
l4->value = 0x444;
struct lst *p = (struct lst*)l1;
printf("? value:%X\n", (*(struct lst*)p).value);
printf("? value:%X\n", (struct lst*)(**(struct lst**)p).value);
printf("? value:%X\n", (struct lst*)(***(struct lst***)p).value);
printf("? value:%X\n", (struct lst*)(****(struct lst****)p).value)
}
显然，打印结果如下：
? value:0X111
? value:0X222
? value:0X333
? value:0X444
结构体lst实际上和上述的int类型的指针是一样的，只不过在其指针地址的下面又携带了一个int型的字段value，这样的话一个链表就可以携带数据了。
进一步思考，既然链表现在可以携带数据了，那么携带些什么数据呢？是不是每一个携带有数据的链表都要构造一个结构体呢？这样是不是太浪费了，链表操作API又不能统一。我们反过来想这个问题，既然链表可以携带数据，然后通过链表中的fuc(next)字段或者通过***...找到这个数据，那么数据是不是也可以携带一个链表呢？这是可以的，它们都在连续的内存空间内，对于地址空间而言，谁携带谁是无所谓的，我们需要做的仅仅是管理好链表的next指针即可，比方说一个数据结构data：
struct data {
int other;
struct lst* lt;
int value;
}
由此，value字段进入了data，value就没有必要存在于lst了，由此lst成了以下的样子：
struct lst {
struct lst* fuc;
}
如果我们现在拥有一个data实例，可以在它的首地址下面偏移4字节(other的大小)处取出它的lt字段，也就是一个链表，反过来如果我们拥有一个链表节点实例，也可以在这个上面上面偏移4字节处取到一个data实例。看一下这像什么？是不是linux内核的list_head？只不过list_head是一个双向链表，还有一个prev字段，这个通过list找data的过程也就是linux内核的container_of宏：
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
可以看到，必须指定一个数据类型和该list_head在该数据类型中的字段名。正是虚拟内存空间的连续性使得我们可以抽出list_head这个结构，使嵌入式链表成为可能，这样就可以单独为list_head设计一套api了，而不用关心它携带的是什么数据，实际上它从来不携带数据，而是其它数据结构实例携带了它。
*****...是一个链表，任意的多级指针都是一个链表，理解了这个之后，不但可以单独设计出诸如list_head之类的linux内核的核心数据结构，对于hlist_head的理解也加深了一步：
struct hlist_head {
struct hlist_node *first;
};
struct hlist_node {
struct hlist_node *next, **pprev;
};
hlist_head中只有一个指向hlist_node的指针，而hlist_node中却有一个**类型的指针，也就是一个指针的指针，证明它指向的一个元素是一个指针指向另一个元素，指向谁呢？其实是指向该hlist_node自己的，指向自己？岂不多此一举？事实上它在删除节点的时候十分有用，它可以直接修改前一个节点的next字段，使之指向当前被删除节点的后一个节点，整个过程不用考虑前一个节点到底是hlist_node还是hlist_head，只要它有一个hlist_node类型的指针字段就可以了，这么一来就解放了hlist_head，使得一个和hlist_node截然不同的数据类型可以连接进哈希桶，而这个hlist_head中只有一个字段，大大节省了空间(为何hlist_node不去掉pprev呢，这样不更节省空间？是节省了空间，然而删除的时候就麻烦了，需要遍历操作，找到这个需要删除节点的位置)。
从*******...一路上到达了hlist，事实上全部可以用指针来说话，指针真的是一个了不起的特性，c语言正是因为有了指针才可以访问地址空间任意的地址，正是这种便利性，操作系统内核用c写是最好的，c提供了机器的一个最好的抽象，不多也不少，而这个最好是通过指针来实现的。