《TCP/IP详解 卷2：实现》 —2.8 Net/3联网数据结构小结

2.8   Net/3联网数据结构小结

本节总结我们在Net/3联网代码中要遇到的数据结构类型。在Net/3内核中会用到其他数据结构(感兴趣的读者可以查看头文件<sys/queue.h>)，但下面这些是我们在本书中要遇到的。

1) 一个mbuf链：一个通过m_next指针链接的mbuf链表。我们已经看过几个这样的例子。

2) 只有一个头指针的mbuf链的链表。mbuf链通过每个链的第一个mbuf中的m_nextpkt指针链接起来。

图2-21所示的就是这种链表。这种数据结构的例子是一个插口发送缓存和接收缓存。

图2-21   只有头指针的mbuf链的链表

顶部的两个mbuf形成这个队列中的第一个记录，底下三个mbuf形成这个队列的第二个记录。对于一个基于记录的协议，如UDP，我们在每个队列中能遇到多个记录。但对于像TCP这样的协议，它没有记录的边界，每个队列我们只能发现一个记录(一个mbuf链可能包含多个mbuf)。

把一个mbuf追加到队列的第一个记录中要遍历所有第一个记录的mbuf，直到遇到m_next为空的mbuf。而追加一个包含新记录的mbuf链到这个队列中，要查找所有记录直到遇到m_nextpkt为空的记录。

3) 一个有头指针和尾指针的mbuf链的链表。

图2-22显示的是这种类型的链表。我们在接口队列中会遇到它(图3-13)，并且在图2-2中已显示过它的一个例子。与图2-21相比仅有一点改变：增加了一个尾指针来简化增加一个新记录的操作。

图2-22   有头指针和尾指针的链表

4) 双向循环链表。

图2-23所示的是这种类型的链表，我们在IP分片与重装(第10章)、协议控制块(第22章)及TCP失序报文段队列(27.9节)中会遇到这种数据结构。

图2-23   双向循环链表

在这个链表中的元素不是mbuf，它们是一些定义了两个相邻的指针的结构：一个next指针跟着一个prev(代表previous)指针。两个指针必须在结构的起始处。如果链表为空，表头的next和prev指针都指向这个表头本身。

在图中我们简单地把向后指针指向另一个向后指针。显然所有的指针应包含它所指向的结构的地址，即向前指针的地址(因为向前和向后指针总是放在结构的起始处)。

这种类型的数据结构能方便地向前向后遍历，并允许方便地在链表中任何位置进行插入与删除。

调用函数insque和remque(图10-20)来对这个链表进行插入和删除。