第一次听到这个题目的时候，是在某公司的面试时。很遗憾，我当时没有做出来。不
久后，我把这个事就给忘了，直到在另一家公司面试。还好，当时面试官给了我足够
的时间和提示，我才用丑陋的代码将这个问题解决。现在，是时候总结一下了。

首先，我们定义一个节点：

typedef struct node {
    struct node *next;
} Node;

这个 Node 就是我们的单链表的节点，我们可以在次节点的内部嵌入数据，也可将此
节点嵌入到其他结构体中，构成支持其他结构体的骨架（看考linux代码树中的
struct list_head 结构体）。但将此节点用来干什么不是我们讨论的重点，我们关心
的只是如何实现反转单链表这个功能。

方法一：

数据结构以及对其的操作要求我们有一定的空间想想能力。最直观的一种情况就是，
从原始的表头到表尾，依次反转 next 指针：

Node *reverse(Node *Head)
{
    Node *p1, *p2, *p3;

    if (Head == NULL || Head->next == NULL)
        return Head;   // 如果Head为空，或只有一个节点，直接返回 Head

    p1 = Head;
    p2 = p1->next;     // 标定 p1 p2

    p1->next = NULL;
    while (p2 != NULL) {
        p3 = p2->next; // 更新 p3，以记录 p2->next
        p2->next = p1;
        p1 = p2;
        p2 = p3;       // 蠕虫式爬行
    }

    return p1;
}
    

上面的方法中，利用了三个指针 p1, p2 和 p3 来指示我们所要处理的位置，其中关
键的是对于 p3 的更新。因为一旦 p2->next 被更改为指向 p1，则不能找到下一个节
点的位置。因此需要先利用 p3 = p2->next 将下一节点位置记录下来，之后再更新
p2->next 。

方法二：

方法一其实就是一种迭代的方法。下面，我们讨论使用递归来解决这个问题。

Node *reverse_recur(Node *Head)
{
    Node *new_head;
    if (Head == NULL || Head->next == NULL)
        return Head;

    new_head = reverse_recur(Head->next);

    Head->next->next = Head;
    Head->next = NULL;

    return new_head;
}

递归方法隐藏了迭代法要考虑的一些细节。我们认为 reverse_recur() 能够接受一个
表头 Head 作为参数，然后返回反转后链表的新表头 new_head 。

方法三：

这种方法比前两种方法更直观，但是要浪费更多的资源。不提倡使用这种实现方法。

Node *reverse_array(Node *Head)
{
    Node **array;
    Node *p, *new_head;
    int num = 0;
    int i = 0;

    if (Head == NULL)
        return Head;
    
    for (p = Head; p != NULL; p = p->next)
        num++;

    // 动态分配一个 Node 指针的数组，用以存储所有 Node 节点
    array = (Node **)malloc(sizeof(Node *)*num);
    if (array == NULL) {
        printf("Out of memory!\n");
        exit(0);
    }

    for (p = Head; p != NULL; p = p->next) {
        array[i] = p;
        i++;
    }
    for (i=num-1; i > 0; i--)
        array[i]->next = array[i-1];

    array[0]->next = NULL;
    new_head = array[num-1];
    free(array);

    return new_head;
}

本文的中反转单链表的实现和测试代码可以在我的 github 中获得:
[https://github.com/hcyvan/webSiteCode/blob/master/c/
reverse_singly_linked_list.c](https://github.com/hcyvan/webSiteCode/blob/
master/c/reverse_singly_linked_list.c)

双向循环链表

双向循环链表是linux内核中的一个重要的数据结构。

其节点，定义在 linux/types.h 头，文件中：

struct list_head {
    struct list_head *next, *prev;
};

想初始化一个节点，可以用 linux/list.h 头文件中定义的宏LIST_HEAD()，在stack
中由编译器自动分配一个节点，并且将 prev 和 next 的指向节点自身。

#define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)

#define LIST_HEAD_INIT(name) { &(name), &(name) }

如果在已经有了一个节点(这个节点可以是在 heap 中动态分配的)，我们可以用
INIT_LIST_HEAD 进行初始化。初始化的效果和 LIST_HEAD 相同。

static inline void INIT_LIST_HEAD(struct list_head *list)
{
    list->next = list;
    list->prev = list;
}

双向循环链表的操作

这里仅列出一些基本的操作。

1. list_add() 和 list_add_tail
   list_add() 在 head 之后插入节点，list_add_tail 在 head 之前插入节点。

     static inline void list_add(struct list_head *new, struct list_head *head)
     {
        __list_add(new, head, head->next);
     }
   
     static inline void list_add_tail(struct list_head *new,
                  struct list_head *head)
     {
        __list_add(new, head->prev, head);
     }
        
     static inline void __list_add(struct list_head *new,
                  struct list_head *prev,
                  struct list_head *next)
     {
           next->prev = new;
        new->next = next;
        new->prev = prev;
        prev->next = new;
        }
   

2. list_del()

    static inline void list_del(struct list_head *entry)
    {
        __list_del(entry->prev, entry->next);
        entry->next = LIST_POISON1;
        entry->prev = LIST_POISON2;
    }
    
    static inline void __list_del(struct list_head * prev, struct list_head * next)
    {
        next->prev = prev;
        WRITE_ONCE(prev->next, next);
    }
   

3. list_replace()

    static inline void list_replace(struct list_head *old,
                    struct list_head *new)
    {
        new->next = old->next;
        new->next->prev = new;
        new->prev = old->prev;
        new->prev->next = new;
    }
   

4. list_empty()

    static inline int list_empty(const struct list_head *head)
    {
        return head->next == head;
    }
    
    static inline int list_empty_careful(const struct list_head *head)
    {
        struct list_head *next = head->next;
        return (next == head) && (next == head->prev);
    }
   

5. list_for_each()

   从 head 开始，遍历整个循环链表。

    #define list_for_each(pos, head) \
        for (pos = (head)->next; pos != (head); pos = pos->next)
   

节点与数据

双向循环链表的节点并不包含我们所要存储管理的数据，我们通常将 list_head
节点嵌入到一个结构体中。

struct A {
    ...
    struct list_head node;
    ...
}

这样，我们就能够利用 list_entry() 来获得包含数据的结构体。

/**
 * list_entry - get the struct for this entry
 * @ptr:	the &struct list_head pointer.
 * @type:	the type of the struct this is embedded in.
 * @member:	the name of the list_head within the struct.
 */
#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

对于 container_of() 的原理，不是节讨论的重点，可能会在其他的文章讨论。

双向循环链表应用实例

kobject 是 linux 内核中的一个重要的结构体。以 kobject 为节点，搭建起了
linux 内核中的设备驱动模型。kset 是 kobject 的集合。

struct kset {
    struct list_head list;
    struct kobject kobj;
    ...
};

struct kobject {
    const char		*name;
    struct list_head	entry;
    struct kset		*kset;
    ...
};

kobject 与 kset 结构体中的 list 和 entry 域，代表了双向循环列表中的节点。
其中，list 表示双向循环链表中最初的根节点; entry 表示之后要添加/删除的节点。
kobject 中的 kset 域指向将要插入的 kset 结构体。可以通过 kobj_kset_join()
将 kobject 插入到与之关联的 kset 中。

static void kobj_kset_join(struct kobject *kobj)
{
    if (!kobj->kset)
        return;

    kset_get(kobj->kset);
    spin_lock(&kobj->kset->list_lock);
    list_add_tail(&kobj->entry, &kobj->kset->list);
    spin_unlock(&kobj->kset->list_lock);
}

可见，将 kobject 插入到 kset 的实质是向以 kset 中 list 域为表头的双向循环
列表尾部添加节点 entry。也就是对 list_add_tail() 的调用。

好久没有向linux代码树发送补丁了，最近准备继续为linux社区贡献自己的一份力量。同时
也希望能在此过程中学习一下linux的架构和开发过程。大概两个月前，我对于linux内核还
是一无所知。在网上找到了一个网站 Linux Kernel Newbies，之后开始在这个网站
上各种找资料，然后一点一的啃了下来。下面我总结一下如何向linux代码数发送补丁。

linux代码就像一个迷宫，就连找到迷宫的门都是一个难题。下面，我就直接了当的进入这扇
门：”在linux代码树中领取任务“。linux的代码中有一些TODO文件，这些文件中就一些为
准贡献者们提供的任务。对于新手(Kernel Newbies) 而言，dirver/staging/ 中的 TODO 任
务是一个不错的选择。特别是一些代码清理的任务，即使没有linux内核的知识，也能完成。
dirver/staging 的管理者是 Greg HK ，一个很认真、热心的人。如果你订阅了邮件列表
Kernelnewbies 就能发现，Greg HK 是一个积极的问题解决者，并且他讨
论问题的时候总是很有耐心。同时他每天要处理补丁提供者的邮件，虽然有”邮件机器人“
的帮助，但对于格式符合要求的补丁，他每一封都要人工筛选，回复。我想在这里对
Greg HK 表示感谢。如果想在 dirver/staging/ 中领取并完成任务，至少要抄送一份补丁给
Greg HK。

领取任务后，就是对代码的修改了，这里就不展开了。也许以后文章中会有讲述。下面想谈
一下，生成补丁。如果你没有用过 Git ，那么最好先学习一下基本原理和用法，再继续往下
看。

在 git add 之后，可以利用 git diff –cached 来查看 repo 的更改内容。使用
git commit -sv 提交修改。-s 使得 commit 后面会附有你的邮件; -v 能够在输入 commit
内容的时候显示修改内容，方便查阅。git 能为 代码树自动生成补丁：

git format-patch HEAD^

HEAD 指向但前的 commit，^ 表示当前commit的前一个commit。上边的命令根据 HEAD（默认）
和 HEAD^ 来生成 patch。在生成 patch 之后，利用代码书中的脚本检验补丁格式是否正确。

./script/checkpatch <0001-patch-name>

如果补丁格式正确，可以发送补丁。

./scripts/get_maintainer.pl <0001-patch-name>

通过上面的脚本，能够生成几个邮件地址。需要将补丁发送给所修改代码的的维护者并且至
少抄送到一个公共的邮件列表。抄送给公共邮件列表是因为 linux 内核是一个开源软件，她
的开发行为是公开透明的，要受到大家的监督。补丁只能通过纯文本的方式发送，这里只说
一下利用 mutt 的发送方法。

mutt -H <0001-patch-name>

之后，填好 mutt 中的收件人和抄送人地址，就完成了。

领取 driver/staging 的TODO文件中的任务并发送补丁，是新手入门的好方法。从中能了解
linux 内核开发的大概流程，并且能够学习 linux 内核的编码风格。同时，由于发送补丁的
时候或多或少要用到一些内核的知识，通过发现问题并解决问题的方法，能够学习一些
linux 内核的知识。我现在已经进入了 linux内核这个迷宫，如果你是想学习 linux 内核却
不知到从何做起，希望这篇博客对你有所帮助。同时，将发送补丁的流程记录在此，方便自
查阅。

学习 c 语言有一段时间了，以为 c 中的基础知识已经掌握的差不多。直到最近研究了一
下 linux 内核代码，才发现 c 的基础知识没有我想得那么简单。书本中和网站上容易找到
的资料大致覆盖了 c 中 80% 的基础知识，而剩下的 20% 却不容易找到。但这 20% 的基础
知识却对理解源代码十分重要，于是开始补习这 20% 的基础知识。结合网上网友的技术博
客，在 GNU gcc 的网站上下载了一些手册(v4.9.3)，研究了一下。由于一时间看不完全部内
容，只好走一步算一步，将暂时了解到的东西整理出来。其中的逻辑难免有些不明确甚至混
乱，姑且当这仅是读书笔记，之后如果需要的话，还应做进一步的整理。文中所有关于宏的
东西都是关于 GNU gcc 编译器的，其中可能有些不是 c 标准中的东西，对于其他的编译，
器，比如微软的Visual Studio，是否适用我就不知道了。请自行区分。

c 语言中的宏是由 gcc 中的预处理器处理。与其说 gcc 是一个软件，不如说它是一个工具
链，在编译的过程中，gcc 依次调用 cpp、cc1、as 和 ld。其中 cpp 就是 c 语言的预处理
器。这里所说的cpp并不指 c++， 估计 cpp 是 C Preprocessor 的简写。我用的 gcc 版本
中，cpp 被安装在了 /usr/bin/ 中，所以能够直接调用。cpp 的用起来很简单，可以从标准
输入输入，也可以由文件输入。经过 cpp 处理后由标准输出输出结果。如果想观察 cpp 对宏
的处理结果，最好不要在文件中包含头文件，因为头文件中的大量内容会被包含在输出中，
使我们难以快速找到想要的信息。上面的 cpp 调用可以用 gcc -E 代替，只不过 gcc -E 只
支持从文件中输入，而不支持标注输入。下面举个例子:

file: "example.c"
------
#define STR(x) #x

int main()
{
    STR(navy);
    return 0;
}

在命令行中输入 cpp ./example.c 可以在标准输出中找到如下片段

int main()
{
    "navy";
    return 0;
}

不难看出程序中的 STR(navy) 被替换成了 “navy” 。上面讲过，cpp 可以用 gcc -E 代替。
在 gcc 中，经 cpp 处理后的文件拓展名为 .i ，可用 gcc 的 -o 选项指定。知道了如何
验证宏处理的结果，下将讨论宏处理的内容，参考资料主要是GUN gcc 的 The C
Preprocessor 手册，以下简称“手册。

一、两种宏

宏(Macros) 在不同的语境中含义有所不同。c 语言的宏在手册中的定义如下：

A macro is a fragment of code which has been given a name. Whenever the name is
used, it is replaced by the contents of the macro.

在这里，宏其实是一种替换的规则。c 语言中的宏包括两种: Object-like Macros 和
Function-like Macros。从名称中可以大致了解这两种宏所指的内容。但这里还是简单的介绍
一下:

Object-like Macros

下面定义一个宏

#define BUFFER_SIZE 1000

宏的名称可以是大写或小写，但为了与 c 文件中的其他符号区分，宏的名称经常全被写成大
写。cpp 会将 c 文件中的 BUFFER_SIZE 替换为1000。这里的替换是将 BUFFER_SIZE 看成
一个 Object，直接替换。

Function-like Macros

宏函数相对来说复杂一些

#define PLUS(a, b) a+b

cpp 会将PLUS(x, y) 替换成 x+y。记住，直接用宏函数括号中的参数替换后面表达式中
的内容。但是其实这里有一个问题。如果我们想利用PLUS()来计算 (x1+x2)*y 这个表达式，
我们应该怎样做呢？有些人很自然的想到

PLUS(x1, x2)*y

我们按照直接替换的原则，自行推导下

PLUS(x1, x2)*y => x1+x2*y ?!

出错了，为了修复这个bug我们可以将计算表达式改为(PLUS(x1, x2))*y 或者将最开始的宏定
义改为 #define PLUS(a, b) (a+b)。显然后者能方便我门以后对这个宏的使用。其实这次修
还有个问题。例如PLUS(x1+x2, y)这个表达式的会不会产生 (x1+x2)*y这个结果呢？直接替
换试试看，结果如下

(x1+x2*y)

只好再次修改宏定义，这下似乎没什么问题了。

#define PLUS(a, b) ((a)*(b))

其实在Object-like Macros也有类似的问题

#define SIZE SIZE_1 + SIZE_2

如果用SIZE来进行四则运算的话应该不是很安全，不妨改为

#define SIZE (SIZE_1 + SIZE_2)

这下暂时安全了。

二、宏参数

在 Function-like Macros 的括号中能是能接受参数的，这里称为宏参数。说
Function-like Macros 复杂，一个重要的原因就是因为宏参数。

1、字符串化和连接

宏参数能够字符串化和进行符号连接。这里主要介绍两个符号：# 和 ##。# 能够将宏参数字
符串化，## 能够将两个符号连接，产生新的符号。下面分别简要介绍下者两个符号。

#define STR(x) #x
...
printf("%s\n",STR(hello_world));

这个打印 “hello_world” 的方法就是运用了 # 这个符号，将 hello_world 字符串化成
“hello_world”。这里要注意 STR(x) 只能接收一个参数，所以 hello 与 world 之间的下
划线是十分必要的。下一个例子

#define CONS(a,b) a##b
...
int x1 = 1;
int x2 = 2;
...
printf("%d\n",CONS(x,2));

输出结果是2，因为CONS(x,2)会产生x2这个变量符号。

2、可变宏参数

宏参数能接收可变宏参数，GNU CPP 支持 C99 的标准

#define PRINT_1(format, ...) printf(format, __VA_ARGS__)

能够像如下的方式“调用”PRINT_1()

PRINT_1("The result is: %s, %s\n", "hello", "world");

C99 之前的 C 标准不支持可变宏参数(… 和 __VA_ARGS__)，但是 GNU CPP 很早之前就
支持可变宏了，只是格式有所不同。GNU CPP 的可变宏定义方式如下

#define PRINT_1(format, args...) printf(format, args)

其中，符号 args 可以任意指定。如果想保持和其他 C 标准实现的可移植性，就应该使用
__VA_ARGS__ 方式定义可变宏参数；如果想保持和以前版本 GNU GCC 的兼容性，就应该
使用 args… 的方式定义可变宏参数。

问题还没结束，如果可变宏参数部分为空的话，结果是什么呢？ 我们直接替换下

PRINT_1("The result is") => printf("The result is",) ?!

怎么多了个逗号。看来这个宏定义的方式并不支持可变参数为空的情况。问题出现在多出了一
个逗号。这里我们利用 “##” 来修改下宏定义的方式。

#define PRINT_1(format, args...) printf(format ,##args)

如果 args… 部分是 x1 x2 x3，则 args 部分替换为 x1,x2,x3。之后 ## 连接逗号和
args 部分：”,x1,x2,x3”。最终的结果是 printf(“format”,x1,x2,x3)。如果 args… 部分
为空，”,##arg” 的最终部分也是空。最终的结果是 printf(“format”)。问题解决了。对于
__VA_ARGS__ 方式的宏定义，可以采用同样的方式利用 ## 修改。这里有个地方要注意。
宏定义中 format 和逗号直接要有一个空格分开，否则，如果 args 为空，format 会和逗号
一起被“沉默”。

3、参数预扫描(Argument Prescan)

Macro arguments are completely macro-expanded before they are substituted
into a macro body, unless they are stringified or pasted with other tokens.
After substitution, the entire macro body, including the substituted
arguments, is scanned again for macros to be expanded. The result is that the
arguments are scanned twice to expand macro calls in them.

以上是手册中的一段内容。cpp在扩展对宏参数的替换包括的两轮扫描：第一轮替换中，如果
参数中包含宏，则先将参数中的宏替换；第二轮替换包括替换参数后的整个宏。说的有些复
杂，其实就是拓展宏参数，再拓展其他部分。引用用手册中的一个例子：

#define foo a,b
#define bar(x) lose(x)
#define lose(x) (1 + (x))

对于这样的宏定义，如果采用下面的形式调用

bar(foo)

会有什么结果呢？我们期望的是 (1 + (a,b)) ，结果却不是这样的。按照上面对宏参数扫描
(argument prescan) 介绍，宏展开过程如下：

bar(foo) -> bar(a,b) -> lose(a,b) -> ?!

这下出了问题，lose()只能接收一个参数，宏展开出错。要解决这个问题应该将宏定义改成

#define foo (a,b)
#define bar(x) lose(x)
#define lose(x) (1 + (x))

关键是先替换参数，再替换其他。Argument Prescan 另外一个要注意的地方是在宏参数
被字符串化(#)或与其他符号链接(##)的情况下不进行替换。看上去有些复杂，还是举个例子：

#define STR(x) #x
#define NUM 100

以上的宏定义很简单，这里不多解释。STR(NUM) 会被替换成什么呢？答案是 "NUM" (注
意，这里的双引号是结果的一部分，可以自己用前面讲过的方法直接用cpp扫描替换并且验证。
argument prescan

三、复合语句宏定义

下面定义一个能统计字符串中字符个数的宏，统计 str 中的字符数，字符数复制给 n：

#define COUNT(str, n) \
        char *c = str;\
         n = 0;\
        while (*c++ != '\0')\
            n++;

有时，为了使宏定义中的临时变量有自己的作用域，我们可以用 “{}” 将这些语句包围起来。

#define COUNT(str, n) \
        {\
        char *c = str;\
         n = 0;\
        while (*c++ != '\0')\
            n++;\
        }

使用者在使用时并不区分普通函数和宏函数。都在”函数调用”后面添加分号，组成语句

COUNT(str, n);

如果我们用如下的 if 语句结构调用

if (...)
    COUNT(str, n);
else
    ...

直接替代后

if (...)
    {...};    !?
else
    ...

这样就出错了。为了解决这个问题，可将宏定义改为

#define COUNT(str, n) \
        do {\
        char *c = str;\
         n = 0;\
        while (*c++ != '\0')\
            n++;\
        } while (0)

同样采用直接替代的方法可以发现问题解决了。

我接触电脑比较晚，第一次触摸到电脑是在镇上读初中的时候。记得当时学校电脑用
的是国产的清华同方，操作系统是什么现在真的是记不清了。关键是当时根本没有操
作系统这个概念，认为硬件和软件根本就是共生的。现在想起来，课上讲的内容就是
微软的Excel和PPt。之后的5、6年里，我和绝大多数的中国学生一样，读完初中读高
中，之间从没有接触过电脑。读大学后，慢慢的接触到了网络。第一个网络上的帐号
是腾讯的QQ，现在帐号还在，但是基本上都已经不用了，开始被同一个公司的微信替
代。经常登录的博客类网站是人人网，有时还有QQ空间。那个时候觉得网站这类东西
真的是很神奇，虽然大二的时候上了一门叫Dreamweaver的网页制作课，但这门课对
于网站的理解来讲并没有什么实际的帮助。

就这样，大学四年很快就过去了。电脑对于我来讲最大的意义就是它能打游戏、看电
影和上QQ和人人网。我的本科专业是农学专业，读研的时候转到生物学专业，其实两
个专业都差不多，都要在实验室里做实验。研究生一年级的时候我门专业开设了一门
讲授生物统计学的课程，那门课上用到了R语言这个工具。现在在我的印象中，这门课
更像是披着统计学外衣的R语言课。学习R像是在玩儿替换和填空的游戏，将参考书上
的代码抄下来，替换成自己想要的东西，之后在一个可以运行R的软件中运行。这是我
第二次接触到编程这类东西，第一次其实是本科时候计算机选修课上学习了visual
Basic这门语言，体会和学R是差不多，所要做的就是替换、替换和替换。

有了学习R的经历后，自学了Perl和C者两种语言。之后开始学习并且使用GNU/linux
操作系统，学习了C++和Python。在此期间还学习了一些有关数据结构与算法，编译
原理和操作系统之类的知识。于是我鼓起勇气去找了几家IT公司去面试实习生，结果
只有一家做手游的公司同意我的实习申请。但去了一天后，发现这家公司的所用的东
西并不是我感兴趣和想学习的，于是离开了这家公司。后来，我开始接触到linux内核
并且向Greg HK提交了两个linux内核代码树的代码清理补丁。很高兴这些补丁被接收
了，现在我的GitHub主页上可以看到我为linux代码树做了贡献，这真是一
个不错的体验和经历。

现在，我关心的两个软件是linux内核和Gnu Emacs。希望对其有进一步了解并对其作
出自己的贡献。我本身对于Emacs的设计很感兴趣，Emacs有自己的解释器，除了其底
层用C实现外，其他都是由自身的Emacs Lisp实现的，包括Emacs的配置文件都是用
Lisp。这使得Emacs本身有着极强的拓展性。目前，我得为我是否能顺利毕业考虑了。
前面的一年时间，由于兴趣，我几乎将所有的精力都投入到了计算机方面的知识。但
回到现实来看，不管我毕业后向干什么，这个学位对于我找工作都是有帮助的。所以
现在还是应该把精力放到我的毕业课题上来。那计算机的东西呢？谁能一天不吃饭，
谁又能一天总在吃饭呢？