循环双向链表结构 -- ngx_queue_t

2015-03-19 00:10:53   最后更新: 2015-03-19 00:13:42   访问数量:1025




nginx 实现了六个基本容器,分别是:

  1. 循环双向链表 -- ngx_queue_t
  2. 动态数组 -- ngx_array_t
  3. 单向链表 -- ngx_list_t
  4. 红黑树 -- ngx_rbtree_t
  5. 基数树 -- ngx_radix_tree_t
  6. 哈希表 -- ngx_hash_t

 

接下来我们首先介绍一下 nginx 封装的双向链表

 

nginx 的双向链表的声明和定义在 ngx_queue.h 和 ngx_queue.c 两个文件中

 

因为双向链表结构的灵活性与高效性,非常适合频繁修改容器的场合,他在 nginx 中使用相当频繁

 

nginx 双向链表的结构非常简单:

 

// struct ngx_queue_s // nginx 双向链表结构 {{{ struct ngx_queue_s { ngx_queue_t *prev; ngx_queue_t *next; }; // }}}

 

 

由于双向链表结构较为简单,同时考虑执行效率,nginx 将大量操作封装成了宏函数

主要有以下操作:

操作意义
ngx_queue_init双向链表初始化(置空)
ngx_queue_empty判断双向链表是否为空链表
ngx_queue_insert_head在指定元素前插入新节点
ngx_queue_insert_after在指定元素前插入新节点
ngx_queue_insert_tail在指定元素后插入新节点
ngx_queue_head返回指定元素的后继
ngx_queue_last返回指定元素的前驱
ngx_queue_sentinel返回指定元素
ngx_queue_next返回指定元素的后继
ngx_queue_prev返回指定元素的前驱
ngx_queue_remove删除指定元素
ngx_queue_split拆分双向链表
ngx_queue_add合并链表
ngx_queue_data返回指定元素所属结构体变量
ngx_queue_middle返回双向链表中位元素
ngx_queue_sort双向链表排序 (插入排序)

 

由于所有实现代码较为简单,所以将所有宏和代码直接贴到这里,不做过多说明了

// struct ngx_queue_s // nginx 双向链表结构 {{{ struct ngx_queue_s { ngx_queue_t *prev; ngx_queue_t *next; }; // }}} // #define ngx_queue_init(q) // 双线链表初始化 {{{ #define ngx_queue_init(q) \ (q)->prev = q; \ (q)->next = q // }}} // #define ngx_queue_empty(h) // 判断双向链表是否为空 {{{ #define ngx_queue_empty(h) \ (h == (h)->prev) // }}} // #define ngx_queue_insert_head(h, x) // 在指定元素前插入新节点 {{{ #define ngx_queue_insert_head(h, x) \ (x)->next = (h)->next; \ (x)->next->prev = x; \ (x)->prev = h; \ (h)->next = x #define ngx_queue_insert_after ngx_queue_insert_head // }}} // #define ngx_queue_insert_tail(h, x) // 在指定元素后插入新节点 {{{ #define ngx_queue_insert_tail(h, x) \ (x)->prev = (h)->prev; \ (x)->prev->next = x; \ (x)->next = h; \ (h)->prev = x // }}} // #define ngx_queue_head(h) // 返回指定元素的后继 {{{ #define ngx_queue_head(h) \ (h)->next // }}} // #define ngx_queue_last(h) // 返回指定元素的前驱 {{{ #define ngx_queue_last(h) \ (h)->prev // }}} // #define ngx_queue_sentinel(h) // 返回指定元素 {{{ #define ngx_queue_sentinel(h) \ (h) // }}} // #define ngx_queue_next(q) // 返回指定元素的后继 {{{ #define ngx_queue_next(q) \ (q)->next // }}} // #define ngx_queue_prev(q) // 返回指定元素的前驱 {{{ #define ngx_queue_prev(q) \ (q)->prev // }}} // #define ngx_queue_remove(x) // 删除指定元素 {{{ #define ngx_queue_remove(x) \ (x)->next->prev = (x)->prev; \ (x)->prev->next = (x)->next // }}} // #define ngx_queue_split(h, q, n) // 拆分双向链表 {{{ #define ngx_queue_split(h, q, n) \ (n)->prev = (h)->prev; \ (n)->prev->next = n; \ (n)->next = q; \ (h)->prev = (q)->prev; \ (h)->prev->next = h; \ (q)->prev = n; // }}} // #define ngx_queue_add(h, n) // 合并链表 {{{ #define ngx_queue_add(h, n) \ (h)->prev->next = (n)->next; \ (n)->next->prev = (h)->prev; \ (h)->prev = (n)->prev; \ (h)->prev->next = h; // }}} // #define ngx_queue_data(q, type, link) // 返回指定元素所属结构体变量 {{{ #define ngx_queue_data(q, type, link) \ (type *) ((u_char *) q - offsetof(type, link)) // }}}

 

 

// ngx_queue_t * ngx_queue_middle(ngx_queue_t *queue) // 通过双向遍历的方式,找到双向链表中位元素 {{{ ngx_queue_t * ngx_queue_middle(ngx_queue_t *queue) { ngx_queue_t *middle, *next; middle = ngx_queue_head(queue); if (middle == ngx_queue_last(queue)) { return middle; } next = ngx_queue_head(queue); for ( ;; ) { middle = ngx_queue_next(middle); next = ngx_queue_next(next); if (next == ngx_queue_last(queue)) { return middle; } next = ngx_queue_next(next); if (next == ngx_queue_last(queue)) { return middle; } } } // }}} /* the stable insertion sort */ // void ngx_queue_sort(ngx_queue_t *queue, // ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *)) // 双向链表排序 (插入排序) {{{ void ngx_queue_sort(ngx_queue_t *queue, ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *)) { ngx_queue_t *q, *prev, *next; q = ngx_queue_head(queue); if (q == ngx_queue_last(queue)) { return; } for (q = ngx_queue_next(q); q != ngx_queue_sentinel(queue); q = next) { prev = ngx_queue_prev(q); next = ngx_queue_next(q); ngx_queue_remove(q); do { if (cmp(prev, q) <= 0) { break; } prev = ngx_queue_prev(prev); } while (prev != ngx_queue_sentinel(queue)); ngx_queue_insert_after(prev, q); } } // }}}

 

 

关于插入排序,可参考:

插入排序

 

也许在很多人的概念中,双向链表结构应该是包含实际的值域的,但是这里的双向链表却仅仅只有前驱和后继两个域,究竟要怎样使用呢?

下面是一个例子:

typedef struct { u_char *str; ngx_queue_t qEle; int num; } TestNode;

 

 

形成的结构如下图:

 

 

这样做的好处在于:

  1. 双向链表结构无需关注具体实现的数据类型
  2. 与内存分配完全无关
  3. 简化链表的合并等操作

 






技术帖      算法      数据结构      struct      龙潭书斋      插入排序      排序      nginx      链表      ngx_queue_t      双向链表      循环双向链表      循环链表      二分查找      查找     


京ICP备15018585号