[原理分析]linux内核中的链表原理实践

浏览数：25 / 时间：2015年06月20日

摘要：

本文根据linux内核的链表定义，尝试自己来完成相关的接口设计，并且构建测试用例，来体会下链表接口的用法。

正文：

首先来看下linux内核提供的链表接口大致如下：

struct head_node{
	struct head_node* pre;
	struct head_node* next;
};

即节点中只有两个指针：一个指向前一个元素，一个指向后一个元素；假设我们现在要使用该接口，跟一个int值联合在一起形成数据节点，那么存在两种可能的方式：

case1:

typedef struct data_node{
	head_node h;
	int value;
}data_node;

case2:

typedef struct data{
	head_node* head; //此处是否应该用指针?
	int value;
}data_node;

上述两种结构设计的区别主要在于:head_node是否应该以指针形式出现？因为本人的系统能力有限，不能一开始就从高度上审视，所以只能实证的方式来看。

接下来主要的任务是：1.创建多个data_node的数据节点；2.将这些节点通过head_node接口串接起来；3.通过head_node接口遍历这些data_node，并且将value的值输出；我首先以case1的结构进行相关函数的设计，

void node_add(head_node* head, head_node* a)
{
	head->next->prev = a;
	a->next = head->next;

	head->next = a;
	a->prev = head;
}

void node_del(head_node* a)
{
	a->prev->next = a->next;
	a->next->prev = a->prev;
}

void list_value(data_node* d)
{
   data_node* dn = d;
   do{
     printf("%d ", dn->value);
     dn = (data_node*)dn->h.next;
   }while(dn!=d);
}

上述是主要的接口设计，涉及到的主要是指针的操作，下面是调用端的代码：

int _tmain(int argc, _TCHAR* argv[])
{
    data_node* d1 = (data_node*)malloc(sizeof(data_node));
    d1->h.next = &(d1->h);
    d1->h.prev  = &(d1->h);
    d1->value = 2;


    data_node* d2 = (data_node*)malloc(sizeof(data_node));
    d2->h.next = &(d2->h);
    d2->h.prev  = &(d2->h);
    d2->value = 3;

    data_node* d3 = (data_node*)malloc(sizeof(data_node));
    d3->h.next = &(d3->h);
    h.prev  = &(d3->h);
    d3->value = 4;

    node_add(&(d1->h), &(d2->h));
    node_add(&(d1->h), &(d3->h));

    list_value(d1);
    node_del(&(d2->h));
    list_value(d1);

    getchar();
    return 0;
}

功能性上基本完成预定的设计。那么我们再来看看基于case2的设计，其中的node_add()，node_del()接口与case1相同，但是list_value()的接口在此处就不能实现了，因为通过head_node->next的接口到达下一个head_node时，其value数据还在上一层结构中，无法通过地址偏移找到，具体的示例图如下：

上图中的上半部分就是case2的设计，其中标注的“不可逆”就说明很难从head_node退回到data_node，从而获得value的值；而下半部分是case1的设计，value的值可以直接通过地址偏移获得。由此，我们可以明白为什么在数据节点设计过程中不采用链表节点的指针形式。