异想天开

What's the true meaning of light, Could you tell me why

数据结构笔记-nginx源码阅读4

日期:2014-05-27 23:23:12
  
最后更新日期:2014-06-04 14:54:02
记录一下nginx里面的数据结构的知识点,有些也不属于数据结构之列。
1.nginx是用c实现的,调用的方式跟c++顺序是相反的,放一对象进栈,c++里面一般先对该对象赋值,然后将该对象push进去,而nginx的c接口是先push操作,返回对象指针,对该指针赋值。不用考虑将其插入到某个结构,因为其本身源自内部数据结构,如链表,而存储源于内存池。这种接口形式,在nginx的数据结构设计中随处可见,如buf。 2.巧妙利用二级指针的链表遍历接口。
这里用ngx_create_chain_of_bufs函数为例。
[code lang="cpp"]
ngx_chain_t *cl, **ll;
for (i = 0; i < bufs->num; i++) {
b = ngx_calloc_buf(pool);
if (b == NULL) {
return NULL;
}
cl = ngx_alloc_chain_link(pool);
if (cl == NULL) {
return NULL;
}
cl->buf = b;
*ll = cl;
ll = &cl->next;
}
[/code]
这里用二级指针将循环遍历操作的接口写的非常简洁。
3.内存池技术
nginx里面内存池技术实现与其业务相关,nginx内存池的释放是在http request请求结束后,一次释放,中途只有申请操作,不会有释放动态释放。使用内存池目的减少申请和释放操作,不要模块编程过程中的内存管理。另外nginx原始申请内存时,考虑了内存对齐。
4.双向链表的插入
初始情况定义双向链表的表头和表尾,这样做的好处:表头或表尾做哨兵作用,统一了插入了节点的情况-pre节点和next节点总会存在。这种技法使编码变得很简洁,代码优雅。
[code lang="cpp"]
struct list_t list_head,list_tail。
list_head.next = &list_tail;
list_tail.prev = &list_head;
//假设插入node节点,改变四条线即可
struct list_t node ;
node.next = list_head.next;
list_head.next.prev = &node ;
node.prev=&list_head;
list_head.next = &node ;
[/code]
5.nginx里面的单链表
实现类似“二维数组”和“邻接链表”。一小块内存一块块串起来成为一个链。