单链表结构 -- ngx_list_t

2015-03-20 21:12:53   最后更新: 2015-03-20 21:12:53   访问数量:1006




单链表是一个较为简单的数据结构,对插入、删除节点具有较高的灵活性

nginx 对该数据结构进行了一层封装

 

// typedef struct ngx_list_t // nginx 链表结构(以数组为节点) {{{ typedef struct { ngx_list_part_t *last; // 最后一个节点 ngx_list_part_t part; // 首个节点 size_t size; // 单个节点占内存大小 ngx_uint_t nalloc; // 每个节点中数组的容量 ngx_pool_t *pool; // 为链表分配的内存池 } ngx_list_t; // }}}

 

// struct ngx_list_part_s // 链表节点 {{{ struct ngx_list_part_s { void *elts; // 节点数组 ngx_uint_t nelts; // 节点元素个数 ngx_list_part_t *next; // 下一节点 }; // }}}

 

 

为了弥补单链表结构的两个不足:

  1. 频繁的内存开辟与占用
  2. 不适合随机访问

 

因此,nginx 单链表结构的每个节点都存储了一个数组

 

这样做不仅克服了以上两个不足,还可以统一管理内存

 

nginx 单链表操作函数
函数操作
ngx_list_create链表创建
ngx_list_init链表初始化(ngx_list_create 调用)
ngx_list_push在单链表尾部添加节点

 

//ngx_list_t * ngx_list_create(ngx_pool_t *pool, ngx_uint_t n, size_t size) // 创建链表结构 {{{ ngx_list_t * ngx_list_create(ngx_pool_t *pool, ngx_uint_t n, size_t size) { ngx_list_t *list; list = ngx_palloc(pool, sizeof(ngx_list_t)); if (list == NULL) { return NULL; } if (ngx_list_init(list, pool, n, size) != NGX_OK) { return NULL; } return list; } // }}}

 

nginx 链表创建过程和数组创建过程非常类似

ngx_list_create 这个函数首先为整个的链表结构在内存池中分配了空间,然后调用 ngx_list_init 创建并初始化了首个节点

// static ngx_inline ngx_int_t ngx_list_init(ngx_list_t *list, ngx_pool_t *pool, ngx_uint_t n, size_t size) // 链表初始化 {{{ static ngx_inline ngx_int_t ngx_list_init(ngx_list_t *list, ngx_pool_t *pool, ngx_uint_t n, size_t size) { list->part.elts = ngx_palloc(pool, n * size); if (list->part.elts == NULL) { return NGX_ERROR; } list->part.nelts = 0; list->part.next = NULL; list->last = &list->part; list->size = size; list->nalloc = n; list->pool = pool; return NGX_OK; } // }}} </codk> <h1>单链表追加节点 <code> // void * ngx_list_push(ngx_list_t *l) // 在单链表后追加节点 {{{ void * ngx_list_push(ngx_list_t *l) { void *elt; ngx_list_part_t *last; last = l->last; // 数组分配已满,需要新建节点 if (last->nelts == l->nalloc) { /* the last part is full, allocate a new list part */ // 为节点分配空间 last = ngx_palloc(l->pool, sizeof(ngx_list_part_t)); if (last == NULL) { return NULL; } // 为数组分配空间 last->elts = ngx_palloc(l->pool, l->nalloc * l->size); if (last->elts == NULL) { return NULL; } last->nelts = 0; last->next = NULL; l->last->next = last; l->last = last; } elt = (char *) last->elts + l->size * last->nelts; last->nelts++; return elt; } // }}}

 

这个函数返回了即将插入元素的地址,保证了内存空间的分配

实现较为简单,不做过多讲解了

 






技术帖      linux      unix      算法      c语言      数据结构      龙潭书斋      nginx      c      链表      ngx_list_t      ngx_list_part_t      ngx_list_s      容器      list      单链表     


京ICP备15018585号