第7章　Nginx提供的高级数据结构

任何复杂的程序都需要用到数组、链表、树等数据结构，这些容器可以让用户忽略底层细节，快速开发出各种高级数据结构、实现复杂的业务功能。在开发Nginx模块时，同样也需要这样的高级通用容器。然而，Nginx有两个特点：跨平台、使用C语言实现，这两个特点导致Nginx不宜使用一些第三方中间件提供的容器和算法。跨平台意味着Nginx必须可以运行在Windows、Linux等许多主流操作系统上，因此，Nginx的所有代码都必须可以跨平台编译、运行。另外，Nginx是由C语言开发的。虽然所有的操作系统都支持C语言，但是C语言与每一个操作系统都是强相关的，且C库对操作系统的某些系统调用封装的方法并不是跨平台的。

对于这种情况，Nginx的解决方法很简单，在这些必须特殊化处理的地方，对每个操作系统都给一份特异化的实现，因此，用户在下载Nginx源码包时会发现有Windows版本和UNIX版本。而对于基础的数据结构和算法，Nginx则完全从头实现了一遍，如动态数组、链表、二叉排序树、散列表等。当开发功能复杂的模块时，如果需要使用这些数据结构，不妨使用它们来加快开发速度，这些数据结构的好处是完全使用C语言从头实现，运行效率非常高，而且它们是可以跨平台使用的，在主流操作系统上都可以正常的工作。

当然，由于这些基础数据结构的跨平台特性、C语言面向过程的特点、不统一的使用风格以及几乎没有注释的Nginx源代码，造成了它们并不容易使用，本章将会详细阐述它们的设计目的、思想、使用方法，并通过例子形象地展示这些容器的使用方式。

7.1　Nginx提供的高级数据结构概述

本章将介绍Nginx实现的6个基本容器，熟练使用这6个基本容器，将会大大提高开发Nginx模块的效率，也可以更加方便地实现复杂的功能。

ngx_queue_t双向链表是Nginx提供的轻量级链表容器，它与Nginx的内存池无关，因此，这个链表将不会负责分配内存来存放链表元素。这意味着，任何链表元素都需要通过其他方式来分配它所需要的内存空间，不要指望ngx_queue_t帮助存储元素。ngx_queue_t只是把这些已经分配好内存的元素用双向链表连接起来。ngx_queue_t的功能虽然很简单，但它非常轻量级，对每个用户数据而言，只需要增加两个指针的空间即可，消耗的内存很少。同时，ngx_queue_t还提供了一个非常简易的插入排序法，虽然不太适合超大规模数据的排序，但它胜在简单实用。ngx_queue_t作为C语言提供的通用双向链表，其设计思路值得用户参考。

ngx_array_t动态数组类似于C++语言STL库的vector容器，它用连续的内存存放着大小相同的元素（就像数组），这使得它按照下标检索数据的效率非常高，可以用O（1）的时间来访问随机元素。相比数组，它的优势在于，数组通常是固定大小的，而ngx_array_t可以在达到容量最大值时自动扩容（扩容算法与常见的vector容器不同）。ngx_array_t与ngx_queue_t的一个显著不同点在于，ngx_queue_t并不负责为容器元素分配内存，而ngx_array_t是负责容器元素的内存分配的。ngx_array_t也是Nginx中应用非常广泛的数据结构，本章介绍的支持通配符的散列表中就有使用它的例子。

ngx_list_t单向链表与ngx_queue_t双向链表是完全不同的，它是负责容器内元素内存分配的，因此，这两个容器在通用性的设计思路上是完全不同的。同时它与ngx_array_t也不一样，它不是用完全连续的内存来存储元素，而是用单链表将多段内存块连接起来，每段内存块也存储了多个元素，有点像“数组+单链表”。在3.2.3节中已经详细介绍过ngx_list_t单向链表，本章不再赘述。

ngx_rbtree_t（红黑树）是一种非常有效的高级数据结构，它在许多系统中都作为核心数据结构存在。它在检索特定关键字时不再需要像以上容器那样遍历容器，同时，ngx_rbtree_t容器在检索、插入、删除元素方面非常高效，且其针对各种类型的数据的平均时间都很优异。与散列表相比，ngx_rbtree_t还支持范围查询，也支持高效地遍历所有元素，因此，Nginx的核心模块是离不开ngx_rbtree_t容器的。同时，一些较复杂的Nginx模块也都用到了ngx_rbtree_t容器。用户在需要用到快速检索的容器时，应该首先考虑是不是使用ngx_rbtree_t。

ngx_radix_tree_t基数树与ngx_rbtree_t红黑树一样都是二叉查找树，ngx_rbtree_t红黑树具备的优点，ngx_radix_tree_t基数树同样也有，但ngx_radix_tree_t基数树的应用范围要比ngx_rbtree_t红黑树小，因为ngx_radix_tree_t要求元素必须以整型数据作为关键字，所以大大减少了它的应用场景。然而，由于ngx_radix_tree_t基数树在插入、删除元素时不需要做旋转操作，因此它的插入、删除效率一般要比ngx_rbtree_t红黑树高。选择使用哪种二叉查找树取决于实际的应用场景。不过，ngx_radix_tree_t基数树的用法要比ngx_rbtree_t红黑树简单许多。

支持通配符的散列表是Nginx独创的。Nginx首先实现了基础的常用散列表，在这个基础上，它又根据Web服务器的特点，对于URI域名这种场景设计了支持通配符的散列表，当然，只支持前置通配符和后置通配符，如www.test.和.test.com。Nginx对于这种散列表做了非常多的优化设计，它的实现较为复杂。在7.7节中，将会非常详细地描述它的实现，当然，如果只是使用这种散列表，并不需要完全看懂7.7节，可以只看一下7.7.3节的例子，这将会简单许多。不过，要想能够灵活地修改Nginx的各种使用散列表的代码，还是建议读者仔细阅读一下7.7节的内容。