Nginx linked list structure

Ngx_list_t is a linked list container packaged by Nginx. The memory allocation of linked list container is based on memory pool, which is easy to operate and efficient. The Nginx container is similar to a regular list. It has a list header and a list node, and the node pointer forms the list. Its structure is defined in core/ngx_list.h as follows:

Chain table structure

typedef struct ngx_list_part_s  ngx_list_part_t;

struct ngx_list_part_s {
    void             *elts; // Point to the first address of the data area of the node
    ngx_uint_t        nelts; // The actual number of elements in the data area of this node
    ngx_list_part_t  *next; // point to the next node in the list
};


typedef struct {
    ngx_list_part_t  *last; // points to the last node in the list
    ngx_list_part_t   part; // The first node contained in the table header of the linked list
    size_t            size; // The size of the element in bytes
    ngx_uint_t        nalloc; // The number of elements each node in the list can hold
    ngx_pool_t       *pool; // The memory pool object of the linked list node space
} ngx_list_t;
Copy the code

So, to understand the basic structure of nginx reencapsulation, you can draw a diagram so that you can easily understand it.

The linked list method

Nginx lists have only two operations: creating lists and adding elements. Since linked list memory allocation is based on the memory pool, all memory destruction is carried out by the memory pool, that is, the linked list has no destruction operation.

Create a list

For the source file, go to core/ngx_list.c. The source file version is 0.5

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

    // Allocate memory for the linked list header
    list = ngx_palloc(pool, sizeof(ngx_list_t));
    if (list= =NULL) {
        return NULL;
    }

    // Allocate memory for the node data area and return the first address of the node data area
    list->part.elts = ngx_palloc(pool, n * size);
    if (list->part.elts == NULL) {
        return NULL;
    }

    // Initializes the node properties
    list->part.nelts = 0;
    list->part.next = NULL;
    list->last = &list->part;
    list->size = size;
    list->nalloc = n;
    list->pool = pool;

    return list;
}
Copy the code

Add elements

void *
ngx_list_push(ngx_list_t *l)
{
    void             *elt;
    ngx_list_part_t  *last;

    // The last pointer points to the last node in the list
    last = l->last;

    // If the last node is full
    if (last->nelts == l->nalloc) {

        /* the last part is full, allocate a new list part */

        // A new node is allocated
        last = ngx_palloc(l->pool, sizeof(ngx_list_part_t));
        if (last == NULL) {
            return NULL;
        }

        // Allocate memory for the node data area and return the first address of the node data area
        last->elts = ngx_palloc(l->pool, l->nalloc * l->size);
        if (last->elts == NULL) {
            return NULL;
        }

        // Initialize the new node structure
        last->nelts = 0;
        last->next = NULL;

        // Connect the new node to the existing list
        l->last->next = last;
        l->last = last;
    }

    // Calculates where to store the new element
    elt = (char *) last->elts + l->size * last->nelts;

    // Add 1 to the actual element
    last->nelts++;

    // Returns the location of the new element
    return elt;
}
Copy the code

When you add an element to a list, you start with the last node:

1. Firstly, the data area of the last node is judged whether the newly added element is stored in memory.
2. If sufficient to store the new element, returns the location of the memory where the new element was stored;
3. If there is not enough memory to store the newly added element, a new node is allocated, the new node is connected to the existing list, and the location of the memory for the new element is returned.

Here’s the difference between lists and arrays:

1. When the array data area is full, expand the data area space; Linked lists allocate nodes and their data areas each time.
2. The added element can be an integer or a structure.

The test program

#include "ngx_config.h"
#include <stdio.h>
#include "ngx_conf_file.h"
#include "nginx.h"
#include "ngx_core.h"
#include "ngx_string.h"
#include "ngx_palloc.h"
#include "ngx_list.h"

volatile ngx_cycle_t  *ngx_cycle;

void ngx_log_error_core(ngx_uint_t level, ngx_log_t *log.ngx_err_t err,
            const char *fmt, ...)
{}void dump_list_part(ngx_list_t* list.ngx_list_part_t* part)
{
    int *ptr = (int*)(part->elts);
    int loop = 0;

    printf(" .part = 0x%x\n", & (list->part));
    printf(" .elts = 0x%x ", part->elts);
    printf("(");
    for (; loop < list->nalloc - 1; loop++)
    {
        printf("%d, ", ptr[loop]);
    }
    printf("%d)\n", ptr[loop]);
    printf(" .nelts = %d\n", part->nelts);
    printf(" .next = 0x%x", part->next);
    if (part->next)
        printf(" -->\n");
    printf(" \n");
}
void dump_list(ngx_list_t* list)
{
    if (list)
    {
        printf("list = 0x%x\n".list);
        printf(" .last = 0x%x\n".list->last);
        printf(" .part = %d\n", & (list->part));
        printf(" .size = %d\n".list->size);
        printf(" .nalloc = %d\n".list->nalloc);
        printf(" .pool = 0x%x\n".list->pool);

        printf("elements: \n");
        ngx_list_part_t *part = &(list->part);
        while(part)
        {
            dump_list_part(list, part);
            part = part->next;
        }
        printf("\n"); }}int main(a)
{
    ngx_pool_t *pool;
    int i;

    printf("--------------------------------\n");
    printf("create a new pool:\n");
    printf("--------------------------------\n");
    pool = ngx_create_pool(1024.NULL);

    printf("--------------------------------\n");
    printf("alloc an list from the pool:\n");
    printf("--------------------------------\n");
    ngx_list_t *list = ngx_list_create(pool, 5.sizeof(int));

    if(NULL= =list)
    {
        return - 1;
    }
    for (i = 0; i < 5; i++)
    {
        int *ptr = ngx_list_push(list);
        *ptr = 2*i;
    }

    dump_list(list);

    ngx_destroy_pool(pool);
    return 0;
}
Copy the code

Write the Makefile for this example:

CXX = GCC CXXFLAGS + = - g - Wall - Wextra NGX_ROOT = / Users/mf/Documents/mysource/nginx - 0.5 the TARGETS = ngx_list_t_test TARGETS_C_FILE= $(TARGETS).c CLEANUP = rm-f $(TARGETS) *.o all:$(TARGETS) clean: $(CLEANUP) CORE_INCS =-I. \ -I$(NGX_ROOT)/src/core \ -I$(NGX_ROOT)/src/event \ -I$(NGX_ROOT)/src/event/modules \ -I$(NGX_ROOT)/src/os/unix \ -I$(NGX_ROOT)/objs \ NGX_PALLOC =$(NGX_ROOT)/objs/src/core/ngx_palloc.o NGX_STRING =$(NGX_ROOT)/objs/src/core/ngx_string.o NGX_ALLOC =$(NGX_ROOT)/objs/src/os/unix/ngx_alloc.o NGX_LIST =$(NGX_ROOT)/objs/src/core/ngx_list.o $(TARGETS):$(TARGETS_C_FILE) $(CXX) $(CXXFLAGS) $(CORE_INCS) $(NGX_PALLOC) $(NGX_STRING) $(NGX_ALLOC) $(NGX_LIST) $^ -o$@
Copy the code

Running results:

↳. / ngx_list_t_test    00:24:13  -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- the create a new pool: -------------------------------- -------------------------------- alloc an list from the pool: -------------------------------- list = 0xa2009840 .last = 0xa2009848 .part = -1577019320 .size = 4 .nalloc = 5 .pool = 0xa2009800 elements: .part = 0xa2009848 .elts = 0xa2009878 (0, 2, 4, 6, 8) .nelts = 5 .next = 0x0Copy the code

reference

• Blog.csdn.net/livelylittl…
• Tc. Dreamcat. Ink/archives / 39…