链表与队列
链表和队列是生产中用的非常频繁的数据结构，变种也非常多。这里介绍的是最基本结构。
为了避免重复造轮子，了解系统已有的一些数据结构的实现不仅对理解网络子系统的代码非常有帮助，也能提升自身编码的效率。
本节介绍就是系统自带的queue.h中实现的基础数据结构。对于Linux系统而言，该文件的目录一般为:/usr/include/sys/queue.h
在介绍相关的数据结构前，根据queue.h实现中采用的命名规则，对以下两个名字进行适当的解释。
- 链表(lists)：只仅维持HEAD指针的链式数据结构
- 队列(queue)：同时维持HEAD和LAST指针的链式数据结构
在queue.h中共实现了以下几种数据结构。
- 单链表（Single-linked Lists)
单链表只维持一个HEAD指针，而且只能正序遍历，因此仅适用于LIFO类型的场景。 它的好处就是，空间开销最小。 - 双链表（Lists)
双链表在单链表的基础上，增加prev指针。从而可以以O(1)的时间复杂度删除一个指定的element。相比于单链表来说，仅增加了一点点空间开销，因此比单链表更实用一些。 - 简单队列（Simple Queue)
简单队列本质上就是具有尾指针的单链表，因此它相对于单链表的优势也非常明显：能够以O(1)的时间复杂度进行尾部插入操作。 但是它并不能执行尾部删除操作，所以用的也不是非常多。 - 尾队列（Tail Queue)
尾队列本质上就是具有尾指针的双链表。它相对于双链表的优势也非常明显：能够快速执行尾插入、尾删除操作。 吐槽一下：干嘛非得叫个尾队列呢，直接叫队列不更好么。:( - 循环队列 (Circular Queue)
循环队列本质上就是首尾相连的尾队列。它的优势就是能够从任意element开始遍历整个队列。
虽然这些数据结构本身都比较简单，但却十分实用。这些数据结构体就像是一个个钩子，可以内嵌到自定义的复杂结构体中发挥功效。用好这些数据结构能大大的提高开发效率。
下面就以TAILQ为例，实现TCP中发送队列的基本雏形。
#include <stdio.h>
#include <sys/queue.h>
// sk_buff是网络系统中，管理数据包的重要数据结构体
struct sk_buff {
int data;
// 内嵌“钩子”tailq到sk_buff中，进而可以把sk_buff加入到队列中管理
TAILQ_ENTRY(sk_buff) tailq;
};
struct sk_buff alloc_skb(int data)
{
struct sk_buff skb = { data, {NULL, NULL} };
return skb;
}
/* 用于管理sk_buff的链表结构体，相当于
* struct skb_queue {
* sk_buff *tqh_first; /* first element */
* sk_buff *qual *tqh_last; /* addr of last next element */
* }
*/
TAILQ_HEAD(skb_queue, sk_buff);
int main()
{
// 声明使用sndbuf作为发送队列，管理一个个sk_buff数据包
struct skb_queue sndbuf;
struct sk_buff *tmp_skb;
// 对发送队列进行初始化
TAILQ_INIT(&sndbuf);
/* Alloc three test skb */
struct sk_buff skb_1 = alloc_skb(11);
struct sk_buff skb_2 = alloc_skb(22);
struct sk_buff skb_3 = alloc_skb(33);
// 将skb_1插入到sndbuf的头部，tailq表示在sk_buff中的"钩子"
TAILQ_INSERT_HEAD(&sndbuf, &skb_1, tailq);
// 将skb_2插入到skb_1位置之前
TAILQ_INSERT_AFTER(&sndbuf, &skb_1, &skb_2, tailq);
// 将skb_3插入到sndbuf的尾部
TAILQ_INSERT_TAIL(&sndbuf, &skb_3, tailq);
// 顺序遍历发送队列sndbuf
TAILQ_FOREACH(tmp_skb, &sndbuf, tailq) {
printf(" %d", tmp_skb->data);
}
printf("\n");
// 逆序遍历发送队列sndbuf
TAILQ_FOREACH_REVERSE(tmp_skb, &sndbuf, skb_queue, tailq) {
printf(" %d", tmp_skb->data);
}
printf("\n");
// 依次删除sndbuf的头部element
while (!TAILQ_EMPTY(&sndbuf)) {
tmp_skb = TAILQ_FIRST(&sndbuf);
TAILQ_REMOVE(&sndbuf, tmp_skb, tailq);
}
if (TAILQ_EMPTY(&sndbuf)) {
printf("Empty sndbuf.\n");
}
return 0;
}
在使用queue.h中的结构体之前，建议看一下它的源码实现，不到600行代码。
之后也可以根据自己的需要，在这些结构体的基础上实现更复杂、更酷的功能。参考资料中三篇资料对queue.h中结构体的介绍非常到位，推荐阅读。
Minimal example of TAILQ usage out of
TAILQ example on ideone
queue.h之尾队列