链表(2)
我们在中探讨了链表的一些最基本最简单的一些用法，只能用来讲讲链表操作的基本原理，不具有通用性。
事实上，我们在实际的项目中用的是在nginx内核中的一种通用的循环链表，其完全是由C语言的宏来定义的，设计非常的简洁巧妙，用在生产环境非常的健壮稳固。
在讲通用链表之前先讲一个宏:offsetof()
size_t offsetof(structName, memberName);
其表示为某结构体成员相对于其所在结构体的中偏移量。通用链表的实现就依赖于这个宏实现的。
下面来介绍nginx通用双向链表的结构体定义typedef struct ngx_queue_s ngx_queue_t;struct ngx_queue_s { ngx_queue_t *prev; ngx_queue_t *next;}; 其定义非常的简单，仅仅是两个指向前节点和后节点的指针。ngx_queue_t 作为结构体的子成员，如：
struct userinfo{ char * firstname; char * lastname; int age; int sex; ngx_queue_t queue;} 所有关于链表的操作，都是对ngx_queue_t的操作，当我们要取得userinfo结构体地址时，就可以用上面的offsetof宏,根据queue的地址来取得了，理论上来说,一个ngx_queue_t的链表可以串起包含有ngx_queue_t的任意结构体类型，但是建议还是像C++或者java,csharp的泛型一样，一个链表中只包含一种结构体类型。
实际项目中，我们对其进行重新命名，并进行了封装，详见源码目录下的core/na_queue.h
其具体代码如下:/* * Copyright(C) Neo * Thu Mar 28 11:30:44 2013 * 对列定义（双向队列,环形队列） 参考nigix队列定义，以及Linux内核队列定义 */#ifndef _NA_QUEUE_H_#define _NA_QUEUE_H_#include "na_core.h"typedef struct na_queue_s na_queue_t;struct na_queue_s { na_queue_t * prev; na_queue_t * next;};/* 初始化队列 */#define na_queue_init(q) \ (q)->prev = (q); \ (q)->next = (q)/* 判断队列是否为空 */#define na_queue_empty(h) \ ((h) == (h)->prev)/* 从头插入节点 */#define na_queue_insert_head(h,x) \ (x)->next = (h)->next; \ (x)->next->prev = (x); \ (x)->prev = (h); \ (h)->next = (x)#define na_queue_insert_after na_queue_insert_head/* 从末尾插入节点 */#define na_queue_insert_tail(h,x) \ (x)->prev = (h)->prev; \ (x)->prev->next = x; \ (x)->next = h; \ (h)->prev = x /* 头指针对应的头节点 */#define na_queue_head(h) (h)->next/* 最后一个节点 */#define na_queue_last(h) (h)->prev#define na_queue_sentinel(h) (h)/*下一个节点*/#define na_queue_next(q) (q)->next/* 前一个节点 */#define na_queue_prev(q) (q)->prev/* 移除一个节点 */#define na_queue_remove(x) \ (x)->next->prev = (x)->prev; \ (x)->prev->next = (x)->next; \ (x)->prev = NULL; \ (x)->next = NULL/* 切分一个队列 * h 头指针 * q 需要拆分的头指针 * n 拆分完成后另外一个队列的头指针 */#define na_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 na_queue_add(h,n) \ (h)->prev->next = (n)->next; \ (n)->next->prev = (h)->prev; \ (h)->prev = (n)->prev; \ (h)->prev->next = (h);/* 根据队列指针，得到包涵此队列指针的结构体 * q 队列指针 * type 返回的数据类型 * link 数据项中对应的队列项名字 */#define na_queue_data(q, type, link) \ (type *) ((u_char *) q - offsetof(type, link))/* 查找中间节点 */na_queue_t *na_queue_middle(na_queue_t * queue);/* 对队列排序 */void na_queue_sort(na_queue_t *queue,int (*cmp)(const na_queue_t *, const na_queue_t *));/*遍历队列中节点的数据 *q:传入的包含队列类型的结构体指针 *s:队列的哨兵指针 *type:包含队列的结构体类型 *link:队列在结构体中的名字*/#define na_queue_foreach(q,s,type,link) \ na_queue_t * _head_ =NULL; \ for(_head_=na_queue_head(s),q=na_queue_data(_head_,type,link);_head_!=s;_head_=na_queue_next(_head_),q=na_queue_data(_head_,type,link))// add by hc#define NA_QUEUE_INIT(name) {&(name),&(name)}#define na_queue_is_last(head,node) ((node)->next == (head))#define na_queue_for_each(pos,head) \ for(pos = (head)->next;pos != head;pos = pos->next)#define na_queue_for_each_safe(pos,n,head) \ for(pos = (head)->next,n = pos->next;pos != (head);pos = n,n = pos->next)#endif /* _NA_QUEUE_H_ */ 其链表的操作
| 函数名 | 参数说明 | 函数执行意义 |
|---|---|---|
| na_queue_init | 哨兵节点 | 初始化链表的哨兵节点 |
| na_queue_empty | 同上 | 判断链表是否为空 |
| na_queue_insert_head | 在表头插入节点 | |
| na_queue_insert_after | 在表尾插入节点 | |
| na_queue_head | 取得链表表头 | |
| na_queue_last | 取得表尾 | |
| na_queue_sentinel | 取得哨兵节点 | |
| na_queue_next | 取得下一个节点 | |
| na_queue_prev | 取得前一个节点 | |
| na_queue_remove | 移除一个节点 | |
| na_queue_split | 拆分一个链表 | |
| na_queue_add | 合并一个链表 | |
| na_queue_data | q 队列指针 type 返回的数据类型 link 数据项中对应的队列项名字 | 根据队列指针，得到包涵此队列指针的结构体 |
| na_queue_middle | 查找中间节点 | |
| na_queue_sort | 对队列排序 | |
| na_queue_foreach | q:传入的包含队列类型的结构体指针 s:队列的哨兵指针 type:包含队列的结构体类型 link:队列在结构体中的名字 | 遍历队列中节点的数据 |
| na_queue_for_each_safe | 安全遍历队列中节点的数据 |
其他参数说明见源码说明,
这里重点讲两个宏 na_queue_date 和 na_queue_foreachna_queue_date 是最上面offsetof宏的应用，功能是取得包含链表指针的结构体的地址。
na_queue_foreach 是遍历队列中的所有的节点下面通过一个简单的插入排序来展示链表的用法:
#include#include #include "na_queue.h"#include typedef struct number_s number_t;typedef unsigned char u_char;struct number_s{ int value; na_queue_t queue;};//根据一个int值新建一个节点number_t *new_number_t(int v){ number_t * n = calloc(sizeof(number_t),1); n->value = v; return n;}//释放一个number_t的链表中所有节点void free_number_t(na_queue_t * h){ na_queue_t * p = h->next; while(p!=h){ na_queue_remove(p); number_t* q =na_queue_data(p,number_t,queue); free(q); p = h->next; }}//打印一个链表的所有节点值voidprint_queue(na_queue_t * h){ na_queue_t * p = h->next; while(p!=h){ number_t * q = na_queue_data(p,number_t,queue); printf("%d ",q->value); p=p->next; } printf("\n");}//在链表中插入一个值，使其按照从小到大顺序排列voidinsert_node(na_queue_t * h,int v){ number_t * n= new_number_t(v); if(na_queue_empty(h)){ na_queue_insert_tail(h,&n->queue); return; } na_queue_t * p = h->next; while(p!=h){ number_t * num = na_queue_data(p,number_t,queue); if(num->value > v){ na_queue_t* q = na_queue_prev(p); na_queue_t* c = &n->queue; na_queue_next(q) = c; na_queue_next(c) = p; na_queue_prev(c) = q; na_queue_prev(p) = c; return; } p = na_queue_next(p); } na_queue_insert_tail(h,&n->queue);}//得到一个随机数int get_random(){ srand(time(0)); return rand()/100000000;}int main(int argc, char *argv[]){ na_queue_t h; na_queue_init(&h); int i; for (i = 0; i < 10; i++) { int r = get_random(); printf("add number:%d\n",r); insert_node(&h,r); print_queue(&h); sleep(1); } free_number_t(&h); return 0;}
测试时一段插入排序程序,输出如下:
add number:10 10 add number:18 10 18 add number:4 4 10 18 add number:1 1 4 10 18 add number:20 1 4 10 18 20 add number:17 1 4 10 17 18 20 add number:3 1 3 4 10 17 18 20 add number:0 0 1 3 4 10 17 18 20 add number:18 0 1 3 4 10 17 18 18 20 add number:5 0 1 3 4 5 10 17 18 18 20
事实上最开始见到这个链表结构是从Linux内核代码中，位于<linux/list.h>
参考文献:
- 《Linux内核设计与实现》(Linux Kernel Development Third Edition) Robert Love
- 《深入理解Nginx》模块化开发与架构解析
- 《算法导论》
generated by