基础数据结构单向链表

  • Z时代
  • 2024-01-10
  • 分类：综合

编程

单向链表

ngx_list_t，nginx的list为单向链表，和一般的list不一样的地方，元素对象并不是单个对象，而是一个对象数组。在新增元素操作是获取对象指针，在对指针进行操作

代码

ngx_list.c/ngx_list.h

数据结构

  • ngx_list_t

  • ngx_list_part_t

typedef struct ngx_list_part_s  ngx_list_part_t;
struct ngx_list_part_s {
    void             *elts; // void *指针，对象数组，对于part使用的是数组，而不是单一对象
    ngx_uint_t        nelts; // 已使用对象个数
    ngx_list_part_t  *next; // 指向下一个对象
};
typedef struct {
    ngx_list_part_t  *last; // 指向尾部
    ngx_list_part_t   part; // 指向首部
    size_t            size; // 元素大小，需要注意不是总的个数，而是part中的数组
    ngx_uint_t        nalloc; // 元素个数，需要注意不是总的个数，而是part中的数据
    ngx_pool_t       *pool; // 内存池
} ngx_list_t;

操作

  • ngx_list_create 创建链表

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) { // 初始化列表，即初始化第一个part
        return NULL;
    }
    return list;
}
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;  // 设置last
    list->size = size; // 设置元素大小
    list->nalloc = n; // 设置元素个数
    list->pool = pool;
    return NGX_OK;
}

  • ngx_list_push 插入一个新的元素

void *
ngx_list_push(ngx_list_t *l)
{
    void             *elt;
    ngx_list_part_t  *last;
    last = l->last; // 指向最新的part
    if (last->nelts == l->nalloc) { // part已满，则分配新的part
        /* the last part is full, allocate a new list part */
        last = ngx_palloc(l->pool, sizeof(ngx_list_part_t)); // 分配part内存
        if (last == NULL) {
            return NULL;
        }
        last->elts = ngx_palloc(l->pool, l->nalloc * l->size); // 分配void *数组
        if (last->elts == NULL) {
            return NULL;
        }
        last->nelts = 0;
        last->next = NULL;
        l->last->next = last; // 指向新的part
        l->last = last;
    }
    elt = (char *) last->elts + l->size * last->nelts;  // elts初始指针 加上 元素 个数* size 计算目标指针地址
    last->nelts++;
    return elt;
}

  • 遍历list

/*
 *
 *  the iteration through the list:
 *
 *  part = &list.part;
 *  data = part->elts;
 *
 *  for (i = 0 ;; i++) {
 *
 *      if (i >= part->nelts) {
 *          if (part->next == NULL) {
 *              break;
 *          }
 *
 *          part = part->next;
 *          data = part->elts;
 *          i = 0;
 *      }
 *
 *      ...  data[i] ...
 *
 *  }
 */

以上是 基础数据结构单向链表 的全部内容， 来源链接： utcz.com/z/512109.html

回到顶部