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:
- Firstly, the data area of the last node is judged whether the newly added element is stored in memory.
- If sufficient to store the new element, returns the location of the memory where the new element was stored;
- 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:
- When the array data area is full, expand the data area space; Linked lists allocate nodes and their data areas each time.
- 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…