linux内核存储管理中单链表操作

最近在看《LINUX内核源代码情景分析》存储管理方面的内容，大量涉及到链表方面的操作，其中有一段代码挺有意思，是从__insert_vm_struct函数中截取的关于单链表操作的，代码如下：

    struct vm_area_struct **pprev;

    pprev = &mm->mmap;
    while (*pprev && (*pprev)->vm_start <= vmp->vm_start)
        pprev = &(*pprev)->vm_next;

    vmp->vm_next = *pprev;
    *pprev = vmp;

大意就是向一个升序单链表中插入一个节点，但是采用的操作方法很特别。为便于描述该机理，写了如下简化代码：

#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>

static struct node_t {
    struct data *head;
}node, *pnode = &node;

struct data {
    struct data *next;
    int n;
};

void _insert(struct data *pdata)
{
    struct data **ppdata = &pnode->head;
    while (*ppdata && (*ppdata)->n < pdata->n)
        ppdata = &(*ppdata)->next;
    pdata->next = *ppdata;
    *ppdata = pdata;
}

void insert(int n)
{
    struct data *t = calloc(1, sizeof *t);
    t->n = n;
    _insert(t);
}

void var_insert(int n, ...)
{
    va_list ap;
    va_start(ap, n);
    if (n != -1) insert(n);
    else return;
    while (1) {
        int i = va_arg(ap, int);
        if (i == -1) break;
        insert(i);
    }
    va_end(ap);
}

void show(void)
{
    struct data *t = pnode->head;
    for ( ; t; t = t->next) {
        printf("%d\t", t->n);
    }
    printf("\n");
}

int main(void)
{
    var_insert(5,9,3,12,1,16,4,7,-1);
    show();
    return 0;
}

关键在于_insert函数，定义了一个二级指针，可以通过该变量同时获取三个结点，

#define list_entry(ptr, type, member) \
    ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

获取上一个结点：list_entry(ppdata, struct data, next);

获取当前结点： *ppdata

获取下一个结点: (*ppdata)->next

可见该二级指针的运用相当灵活，从链表中删除一个结点操作如下：

void delete(int n)
{
    struct data **ppdata = &pnode->head;
    while (*ppdata && (*ppdata)->n != n)
        ppdata = &(*ppdata)->next;
    *ppdata = (*ppdata)->next;
    ppdata = &(*ppdata)->next;
}