Stone's Note
0%

Nginx 高级数据结构

发表于 更新于

overview

ngx_list_t 链表容器

  • 存储数组的链表
  • 每个链表元素 ngx_list_part_t 又是一个数组，拥有连续的内存
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef struct ngx_list_part_s ngx_list_part_t;

struct ngx_list_part_s {
  void              *elts;          // 数组的起始地址
  ngx_unit_t        nelts;          // 数组中已使用了多少个元素，即使同一个数组中也可存储不同类型变量
  ngx_list_part_t   *next;
}

typedef struct {
  ngx_list_part_t   *last;          // 链表最后一个数组元素
  ngx_list_part_t   part;           // 链表首个数组元素，也就是说链表最少会有一个元素
  size_t            size;           // 限制每个数组元素占用空间大小， <= size
  ngx_unit_t        nalloc;         // ngx_list_part_t 数组的容量，最多可存储多少个数据
  ngx_pool_t        *pool;          // 内存池
} ngx_list_t;

ngx_queue_t 双向链表

  • 实现了排序功能
  • 非常轻量级，是一个纯粹的双向链表
  • 支持两个链表间的合并
1
2
3
4
5
6
typedef struct ngx_queue_s ngx_queue_t;

struct ngx_queue_s {
  ngx_queue_t       *prev;          // 第一个节点的 prev 指向容器
  ngx_queue_t       *next;          // 最后一个节点的 next 指向容器
};

双向链表的容器和节点本身全用 ngx_queue_t 表示，很难区分某个 ngx_queue_t 是节点还是容器。所以Nginx将所有容器和节点的方法全部列出来，在不同的意义上用不同的方法。

链表容器方法：

1
2
3
4
5
6
7
8
9
10
11
12
ngx_queue_init()
ngx_queue_empty()
ngx_queue_insert_head()
ngx_queue_insert_tail()
ngx_queue_head()
ngx_queue_last()
ngx_queue_sentinel()
ngx_queue_remove()
ngx_queue_split()
ngx_queue_add()
ngx_queue_middle()
ngx_queue_sort()                    // 插入排序，并不适合大量数据排序

链表节点方法：

1
2
3
4
ngx_queue_next()
ngx_queue_prev()
ngx_queue_data()
ngx_queue_insert_after()

除 ngx_queue_middle 和 ngx_queue_sort ，其他全部宏实现

例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct {
    u_char*     str;
    ngx_queue_t qElel;
    int num;
}TestNode;


ngx_init_t compTestNode(const ngx_queue_t* a, const ngx_queue_t* b)
{
    TestNode* aNode = ngx_queue_data(a, TestNode, qElel);
    TestNode* bNode = ngx_queue_data(b, TestNode, qElel);

    return aNode->num > bNode->num;
}

双向链表能通用的关键在这：

1
2
3
4
#define ngx_queue_data(q, type, link)
  (type*) ((u_char*)q - offsetof(type, link))

#define offsetof(s, m)  (size_t)&(((s *)0)->m)

通过内部成员 ngx_queue_t 可以找到所属的数据结构 TestNode, 进而找到数据结构中的其他成员

ngx_array_t 动态数组

  • 顺序容器
  • 数组的形式存储元素
  • 数组容量达到上限时动态改变数组的大小

与 C++ STL vector 容器扩容的区别

STL vector 扩容方式

1
2
3
// n 为当前新申请空间，若n大于剩余空间，则重新分配空间
const size_type len = old_size + max(old_size, n);    
// 引用自《STL源码分析》，P125
ngx_array_t 扩容方式
1
2
3
4
5
6
ngx_array_push(...);      // 扩容到 2×size
ngx_array_push_n(...);    // 扩容到size和最大值的2倍
// 若内存池对象，资源不足，需先申请内存池空间。
// 扩容之后，旧空间没有释放？
// 等后续看 ngx_palloc 再看
// TODO
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef struct ngx_array_s ngx_array_t;

struct ngx_array_s {
  void  *elts;            // 数组首地址
  ngx_uint_t nelts;       // 数组中已使用元素的个数
  size_t size;            // 每个数组元素占用的内存大小
  ngx_uint_t nalloc;      // 当前数组容量
  ngx_pool_t *pool;       // 内存池对象
}

ngx_array_create()
ngx_array_init()          // 内联
ngx_array_destroy()
ngx_array_push()          // 自动扩容
ngx_array_push_n()        // 自动扩容

ngx_rbtree_t 红黑树

  • 关联容器

Nginx应用场景：支持快速检索，插入，删除操作，也支持范围查询，遍历。

  • 定时器管理
  • 文件缓存

红黑树：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct ngx_rbtree_s ngx_rbtree_t;

typedef void (*ngx_rbtree_insert_pt) (ngx_rbtree_node_t *root,
ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);

struct ngx_rbtree_s {
  ngx_rbtree_node_t   *root;
  ngx_rbtree_node_t   *sentinel;  // 指向NIL哨兵节点
  ngx_rbtree_insert_pt insert;    // 自定义比较函数，当两个节点key相同时，通过这个函数进行区分
}

ngx_rbtree_init(...);
ngx_rbtree_insert(...);
ngx_rbtree_delete(...);

红黑树的一个节点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

typedef ngx_uint_t ngx_rbtree_key_t;
typedef struct ngx_rbtree_node_s ngx_rbtree_node_t;

struct ngx_rbtree_node_s {
  ngx_rbtree_key_t    key;        // 无符号整型关键字
  ngx_rbtree_node_t   *left;
  ngx_rbtree_node_t   *right;
  ngx_rbtree_node_t   *parent;
  u_char              color;      // 0 黑色，1红色
  u_char              data;       // 空间太小，很少使用
  //TODO 看看size，为什么此处加一个，data，为了空间充分利用吗？
}

ngx_rbt_red(...);
ngx_rbt_black(...);
ngx_rbt_is_red(...);
ngx_rbt_is_black(...);
ngx_rbt_copy_color(...);
ngx_rbtree_min(...);                // 找到当前节点及其子树中的最小节点
ngx_rbtree_sentinel_init(...);

1
2
3
4
typedef struct {
  ngx_rbtree_node_t node; // 第一个位置方便转化
  ngx_uint_t num;
} TestRBTreeNode;

ngx_radix_tree_t 基数树

与ngx_rbtree 区别：

  • 存储的每个节点都必须以32位整型作为区别任意两个节点的唯一标识。
  • 负责分配每个节点占用的内存
  • 没有红黑树所谓的子平衡
1
2
3
4
5
6
7
8
typedef struct ngx_radix_node_s ngx_radix_node_t;

struct ngx_radix_node_s {
  ngx_radix_node_t    *left;        // 指向左子树，为空则为null
  ngx_radix_node_t    *right;
  ngx_radix_node_t    *parent;      // 指向父节点，为空则为null
  uintptr_t           value;        // 指针，指向用户自定义的数据结构
}
1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct {
  ngx_radix_node_t    *root;
  ngx_pool_t          *pool;
  ngx_radis_node_t    *free;        // 已分配未使用的节点的单链表
  char                *start;       // 已分配还未使用的内存的首地址
  size_t              size;         // 已分配还未使用的内存的大小
} ngx_radix_tree_t;


ngx_radix_tree_create(...);
ngx_radix32tree_insert(...);
ngx_radix32tree_delete(...);
ngx_radix32tree_find(...);

支持通配符的散列表

解决碰撞方法：

  • 分离链表法：
    同义词的所有元素，放在散列表外的链表中。当找到散列表的位置后，需遍历链表再去找到元素
  • 开放寻址法：所有元素都存在散列表中，依次检查其后连续的槽（此为nginx中用到的方法）
1
2
3
4
5
typedef struct {
  void      *value;                 // 指向自定义元素数据的指针，当前槽为空，则为null
  u_short   len;
  u_char    name[1];                // 元素关键字的长度
} ngx_hash_elt_t;                   // 元素关键字首地址
1
2
3
typedef struct {
  ngx_hash_elt_t      **buckets;    // 指向散列表的首地址，也是第一个槽的地址
  ngx_uint_t          size;         // 散列表中槽的总数

支持通配符的散列表

1
2
3
4
5
6
7
typedef struct {
  ngx_hash_t hash;                  // 基本散列表
  void *value;                      // 指向用户数据
} ngx_hash_wildcard_t;

ngx_hash_find_wc_head(...);
ngx_hash_find_wc_tail(...);

1
2
3
4
5
typedef struct {
  ngx_hash_t hash;                  // 用于精确匹配的基本散列表
  ngx_hash_wildcard_t *wc_head;     // 用于查询前置通配符的散列表
  ngx_hash_wildcard_t *wc_tail;     // 用于查询后置通配符的散列表
} ngx_hash_combined_t;

引用并感谢作者

《深入理解Nginx-模块开发及架构解析》(陶辉著)