利用二级指针管理单向链表

想写这样一篇站在巨人肩上的文章很久了，很久之前在CoolShell上就看到这篇文章：Linus：利用二级指针删除单向链表，当时第一眼看完十分之震惊，大神就是大神！这才是真正的Core Low-level Coding。

长久以来学习我们基础算法和数据结构，但是有多少人真的对基础的数据结构有这么深的钻研，上述链接文章中已经有详细的图解描述一次使用二级指针删除一个节点的实例。

我这里举一个Linux文件系统的例子，我使用linux-2.6.32版本，代码路径linux/fs/filesystems.c。
其中需要讨论的代码，摘要如下：

struct file_system_type {
    const char *name;                   \\看这个
    int fs_flags;
    int (*get_sb) (struct file_system_type *, int,
               const char *, void *, struct vfsmount *);
    void (*kill_sb) (struct super_block *);
    struct module *owner;
    struct file_system_type * next;     \\看这个
    struct list_head fs_supers;

    struct lock_class_key s_lock_key;
    struct lock_class_key s_umount_key;

    struct lock_class_key i_lock_key;
    struct lock_class_key i_mutex_key;
    struct lock_class_key i_mutex_dir_key;
    struct lock_class_key i_alloc_sem_key;
};

static struct file_system_type *file_systems;

static struct file_system_type **find_filesystem(const char *name, unsigned len)
{
    struct file_system_type **p;
    for (p=&file_systems; *p; p=&(*p)->next)
        if (strlen((*p)->name) == len &&
            strncmp((*p)->name, name, len) == 0)
            break;
    return p;
}

int register_filesystem(struct file_system_type * fs)
{
    int res = 0;
    struct file_system_type ** p;

    BUG_ON(strchr(fs->name, '.'));
    if (fs->next)
        return -EBUSY;
    INIT_LIST_HEAD(&fs->fs_supers);
    write_lock(&file_systems_lock);
    p = find_filesystem(fs->name, strlen(fs->name));
    if (*p)
        res = -EBUSY;
    else
        *p = fs;
    write_unlock(&file_systems_lock);
    return res;
}

我要讨论的巧妙利用二级指针的代码就在find_filesystem函数中，其中struct file_system_type结构体可以先不理会，列出来也只是为了方便你看一些细节时候能找到对应的结构成员，不至于迷糊。

还是要从register_filesystem函数讲起，这个函数是将具体的文件系统注册到VFS，Linux中各文件系统初始化函数中都会调用这个函数。函数开始的时候定义了一个二级指针struct file_system_type ** p;，注意find_filesystem函数返回值直接赋值给了二级指针p，秘密都在这个函数里面。

find_filesystem函数中也首先定义了一个二级指针struct file_system_type ** p;在for循环初始化时将p指向了file_systems变量，这个file_systems变量就是VFS管理系统中所有实际文件系统的单向链表头，for循环在这里就是要遍历找到已经注册了VFS的文件系统的信息。for循环的判断条件是*p，即判断p指向是否为空，for循环的增量条件是p指向下一个struct file_system_type *结构。

中间循环就是进行比较判断，判断方法没得说，匹配上则break出来，直接return p，而如果整个链表都匹配不上，则循环结束的时候p=&(*p)->next，由于是最后一个链表了，所以最后链表的next项一定是null，这样返回的也是null。

再回到上层函数，代码贴上来：

if (*p)
        res = -EBUSY;
else
        *p = fs;

已经很明了了，如果*p存在，即表示已经注册了这个文件系统了，则返回错误码；否则的话因为p已经指向最后一个链表的next域，那么*p = fs;表示最后一个链表的next被赋值为fs，即完成增加了单向链表。

后面再补一张图吧

总结

利用二级指针是Linux代码中一个常用trick，虽然有点绕，但是画一画图，人肉跑一跑代码逻辑，还是能搞得懂的，从代码看是简洁的，效率上看是高效的，不需要多余的中间变量和考虑边界条件。

最后编辑于：2018.10.26 16:01:48