链表(3)

链表(2)简单讲述了一种Linux通用的链表结构，准确的说一个双向链表描述的双端队列，其实nginx中单向链表ngx_list_t和双向链表ngx_queue_t是分开定义的。我们在这里只讲双向队列的原因是因为实际项目中只用到了双向链表。

nginx中关于ngx_queue_t的典型应用是在其连接池中.作为Web服务器,nginx会处理大量的socket连接，为了提高并发处理链接的能力，nginx引入了连接池（参见ngx_connections.h和ngx_connection.c），其实现这个连接池也用到了一个技巧—-静态链表.

我们知道线性表分为顺序分配和链接分配，典型的简单的例子就是数组和链表。数组是顺序分配，连续的在内存中排列着有限个结点。链表是链接分配的，相对与数组，链表意味着离散，无限个结点。

静态链表是既是链表也是数组，其实现就是将一个数组中的元素串成链表中的节点。其继承了链表和数组的优点，也继承了链表和数组的缺点。首先说优点，不管链表的串链顺序是怎样的，其结点在物理上是连续的，因为其本身就是数组，内存分配上不会出现碎片化，而且涉及到队列的push和pop操作不会设计到资源的申请与释放，只是一个链表操作而已，所以非常的高效。而缺点就是其长度是固定的，在初始化的时候就要充分考虑到资源的大小。所以这种链表结构特别适合于像连接池这样的需要频繁高效的得到资源与释放资源的情况。

如果对静态链表应用敢兴趣，可以看看nginx的连接池实现，我在这里就不准备Demo了，只是讲到链表多啰嗦几句。
nginx之所以能处理高并发，高性能，不光其应用了epoll模式这么简单，其代码中用到了很多的技巧，建议Linux下从事C语言应用编程的程序员都可以学习一下高手的代码，无论是架构，项目的模块化，还是编程技巧，都会很有收获的。

参考文献:

1. <<计算机程序设计艺术>> 卷一 基本算法 （第三版）

2. 《深入理解Nginx》模块化开发与架构解析

3. 《算法导论》

generated by haroopad

链表3