【数据结构】动态数组，数组链表，双向链表

本节介绍Nginx中的动态数组，数组链表，以及双向链表；

动态数组

说明几点

（1）Nginx中数组和STL中的vector类似，当达到数组的已分配内存的上限时，会自动扩充数组的大小；

（2）数组只支持添加，不支持删除；

动态数组结构体声明

typedef struct {
    void        *elts;      //数组的起始地址
    ngx_uint_t   nelts;     //当前的已经使用元素的个数
    size_t       size;      //一个元素的字节大小
    ngx_uint_t   nalloc;    //最大可容纳元素的个数
    ngx_pool_t  *pool;      //内存池对象
} ngx_array_t;

动态数组初始化

static ngx_inline ngx_int_t
ngx_array_init(ngx_array_t *array,ngx_pool_t *pool,ngx_uint_t n,size_t size)
{
    /*
     * set "array->nelts" before "array->elts",otherwise MSVC thinks
     * that "array->nelts" may be used without having been initialized
     */

    array->nelts = 0;     //当前的已经使用元素的个数，刚开始为0
    array->size = size;		//元素的字节大小
    array->nalloc = n;    //最大可容纳元素的个数
    array->pool = pool;

    array->elts = ngx_palloc(pool,n * size); //分配内存为n*size，其实是整个数据元素的大小
    if (array->elts == NULL) {
        return NGX_ERROR;
    }

    return NGX_OK;
}

动态数组创建

ngx_array_t *
ngx_array_create(ngx_pool_t *p,size_t size)
{
    ngx_array_t *a;

    a = ngx_palloc(p,sizeof(ngx_array_t));   //创建一个数组
    if (a == NULL) {
        return NULL;
    }

    if (ngx_array_init(a,p,n,size) != NGX_OK) {  //数组初始化
        return NULL;
    }

    return a;
}

动态数组销毁

void
ngx_array_destroy(ngx_array_t *a)
{
    ngx_pool_t  *p;

    p = a->pool;

    if ((u_char *) a->elts + a->size * a->nalloc == p->d.last) {  //当此时地址正好等于p->d.last时才会释放
    //任何在数组内存申请后调整d.last，会使得数组内存不可以释放
    
        p->d.last -= a->size * a->nalloc;   //释放可用的内存，主要是调整d.last
    }

    if ((u_char *) a + sizeof(ngx_array_t) == p->d.last) {         //当此时地址正好等于p->d.last时才会释放
     //任何在数组内存申请后调整d.last，会使得数组内存不可以释放
     
        p->d.last = (u_char *) a;           //释放可用的内存，主要是调整d.last
    }
}

申请1个元素内存

void *
ngx_array_push(ngx_array_t *a)
{
    void        *elt,*new;
    size_t       size;
    ngx_pool_t  *p;

    if (a->nelts == a->nalloc) {    //相等时，说明内存已经使用完

        /* the array is full */

        size = a->size * a->nalloc;   //整个内存的大小

        p = a->pool;

        if ((u_char *) a->elts + size == p->d.last    //等于最后一个地址，而且内存池还有新的内存
            && p->d.last + a->size <= p->d.end)
        {
            /*
             * the array allocation is the last in the pool
             * and there is space for new allocation
             */

            p->d.last += a->size;   //更新内存的使用量
            a->nalloc++;            //更新nalloc的容量
  
        } else {
            /* allocate a new array */

            new = ngx_palloc(p,2 * size);    //创建一个两倍的内存
            if (new == NULL) {
                return NULL;
            }

            ngx_memcpy(new,a->elts,size);   //拷贝原数据到新的内存
            a->elts = new;
            a->nalloc *= 2;   //更新nalloc的容量
        }
    }

    elt = (u_char *) a->elts + a->size * a->nelts;    //指向添加元素的地址
    a->nelts++;   //已使用的个数加1

    return elt;
}

申请n个元素内存

void *
ngx_array_push_n(ngx_array_t *a,ngx_uint_t n)
{
    void        *elt,*new;
    size_t       size;
    ngx_uint_t   nalloc;
    ngx_pool_t  *p;

    size = n * a->size;   //申请元素的总大小

    //大于时，说明内存将要使用完
    if (a->nelts + n > a->nalloc) {

        /* the array is full */

        p = a->pool;

        if ((u_char *) a->elts + a->size * a->nalloc == p->d.last    //等于最后一个地址，而且内存池还有新的内存够申请元素的总大小
            && p->d.last + size <= p->d.end)
        {
            /*
             * the array allocation is the last in the pool
             * and there is space for new allocation
             */

            p->d.last += size;   //更新内存的使用量
            a->nalloc += n;      //更新nalloc的容量

        } else {
            /* allocate a new array */

            nalloc = 2 * ((n >= a->nalloc) ? n : a->nalloc);  

            new = ngx_palloc(p,nalloc * a->size);  //创建一个两倍的内存
            if (new == NULL) {
                return NULL;
            }

            ngx_memcpy(new,a->nelts * a->size); //拷贝原内存数据到新的内存
            a->elts = new;      //更新新的地址
            a->nalloc = nalloc;  //更新nalloc的容量
        }
    }

    elt = (u_char *) a->elts + a->size * a->nelts;    //指向添加元素的地址
    a->nelts += n;   //已使用的个数加n

    return elt;
}

数组链表

说明几点

（1）nginx中的数组链表，整体元素为一个链表元素，而一个链表元素分为一个数组和一些控制信息，当一个链表元素使用完后，申请另一个链表元素和数组内存，并用控制信息来连接起来；

链表元素声明

//链表元素节点
struct ngx_list_part_s {
    void             *elts;     //指向数组元素的起始地址
    ngx_uint_t        nelts;    //表示该链表节点已经使用了多少个元素
    ngx_list_part_t  *next;     //指向链表的下一个链表元素
};


//整体管理结构，相当于链表头
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;

链表头初始化

static ngx_inline ngx_int_t
ngx_list_init(ngx_list_t *list,size_t size)
{
    list->part.elts = ngx_palloc(pool,n * size);   //链表元素节点申请的数据内存大小为n * size
    if (list->part.elts == NULL) {
        return NGX_ERROR;
    }

    list->part.nelts = 0;   //表示该链表节点数组已经使用了多少个元素，初始为0
    list->part.next = NULL;    //指向链表的下一个链表元素为NULL
    
    list->last = &list->part;   //指向最后一个链表元素，初始化为第一个
    list->size = size;      //一个元素大小
    list->nalloc = n;     //数组中存放的元素个数
    list->pool = pool;

    return NGX_OK;
}

链表创建

ngx_list_t *
ngx_list_create(ngx_pool_t *pool,size_t size)
{
    ngx_list_t  *list;

    list = ngx_palloc(pool,sizeof(ngx_list_t));    //申请一个ngx_list_t（管理）
    if (list == NULL) {
        return NULL;
    }

    if (ngx_list_init(list,pool,size) != NGX_OK) { //链表头初始化
        return NULL;
    }

    return list;
}

申请1个数据元素的内存

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;    //分配元素的起始地址，通过l->size * last->nelts来定位存放的地址
    last->nelts++;   

    return elt;
}

双向链表

说明几点

（1）Nginx的双向链表提供排序的功能，也支持两个链表的合并

双向链表声明

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_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_empty(h)                                                    
    (h == (h)->prev)

其他操作

//获得链表头
#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)->next

//获得某节点上一个节点
#define ngx_queue_prev(q)                                                     
    (q)->prev

删除节点

#define ngx_queue_remove(x)                                                   
    (x)->next->prev = (x)->prev;                                              
    (x)->prev->next = (x)->next;                                              
    (x)->prev = NULL;                                                         
    (x)->next = NULL

#else

//删除节点x
#define ngx_queue_remove(x)                                                   
    (x)->next->prev = (x)->prev;                                              
    (x)->prev->next = (x)->next

#endif

拆分链表

//拆分链表，分为h和n(q为首元素，q和n形成一个双向链表)
#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;

合并链表

//两个链表连接成一个链表，将n添加到h后面
#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)                                         
    (type *) ((u_char *) q - offsetof(type,link))

（1）q为链表所在的地址，如果真正的结构体地址为a，那么有 q - a =offsetof(type,link))；则a = q -offsetof(type,link))；

寻找中间节点

/*
 * find the middle queue element if the queue has odd number of elements
 * or the first element of the queue's second part otherwise
 */


//找到中间节点
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);     //走1步

        if (next == ngx_queue_last(queue)) {
            return middle;
        }

        next = ngx_queue_next(next);   //走2步

        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);
        next = ngx_queue_next(q);

        ngx_queue_remove(q);  //删除

        do {
            if (cmp(prev,q) <= 0) {    //比前面的节点元素大，就break;
                break;
            }

            prev = ngx_queue_prev(prev);    //否则就一直往前走

        } while (prev != ngx_queue_sentinel(queue));

        ngx_queue_insert_after(prev,q);  //插入到指定的位置
    }
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!