nginx高级数据结构源码分析(一)-----双向链表
程序员文章站
2022-06-02 20:52:01
...
ng_queue_t是Nginx提供的一个顺序容器,它以双向链表的方式将数据组织在一起。
链表作为顺序容器的优势在于,它可以高效的执行插入、删除、合并等操作,在移动链表中的元素时只需要修改指针的指向,因此,它很适合频繁修改容器的场合。
相对于其他顺序容器,它的优势有以下三点:
(1) 实现了排序功能,采用额是插入排序,虽然不太适合超大规模数据的排序,但是简单实用。
(2) 它非常轻量级,不负责链表元素所占内存的分配。ngx_queue_t只是把这些分配号内存的元素用双向链表链接起来
(3) 支持两个链表的合并。
Nginx在设计这个双向链表时,由于容器与元素共用了ngx_queue_t结构体,为了避免此结构体成员的意义混乱,Nginx封装了链表容器与元素的所有方法。
ngx_queue_t的头文件:
typedef struct ngx_queue_s ngx_queue_t; struct ngx_queue_s { ngx_queue_t *prev; ngx_queue_t *next; }; #define ngx_queue_init(q) \初始化,为空,都指向容器结构体 (q)->prev = q; \ (q)->next = q #define ngx_queue_empty(h) \是否为空 (h == (h)->prev) #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) \插入链表容器尾部 (x)->prev = (h)->prev; \ (x)->prev->next = x; \ (x)->next = h; \ (h)->prev = x #define ngx_queue_head(h) \返回第一个结构体指针 (h)->next #define ngx_queue_last(h) \返回最后一个结构体指针 (h)->prev #define ngx_queue_sentinel(h) \返回容器结构体指针 (h) #define ngx_queue_next(q) \返回q的下一个元素 (q)->next #define ngx_queue_prev(q) \返回q的上一个元素 (q)->prev #if (NGX_DEBUG) #define ngx_queue_remove(x) \ (x)->next->prev = (x)->prev; \ (x)->prev->next = (x)->next; \ (x)->prev = NULL; \ (x)->next = NULL #else #define ngx_queue_remove(x) \删除x (x)->next->prev = (x)->prev; \ (x)->prev->next = (x)->next #endif #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) \合并链表 (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) \返回q所属结构体地址 (type *) ((u_char *) q - offsetof(type, link))
ngx_queue_t的实现文件中只有两个方法:一个是返回链表中的中心元素,还有一个是对链表排序。
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)) { //next每走一步都要判断一下的 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 *)) //用插入法排序 { 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); //分别保存q的前后节点 next = ngx_queue_next(q); ngx_queue_remove(q); do { if (cmp(prev, q)版权声明:本文为博主原创文章,未经博主允许不得转载。
以上就介绍了nginx高级数据结构源码分析(一)-----双向链表,包括了方面的内容,希望对PHP教程有兴趣的朋友有所帮助。
声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn核实处理。
相关文章
相关视频
上一篇: svn 无法打开根进行编辑操作
下一篇: php 归并排序 数组交集_PHP