Nginx source code to learn the basic data structure of ngx_queue_t (four)

Recommended for you: Get network issues from WhatsUp Gold. Not end users.

Nginx ngx_queue_t the queue structure

Because nginx has the characteristics of cross platform and C language, the containers and algorithms that nginx should not use some third party middleware, cross platform (Linux, windows) features,

Therefore the nginx code must be compiled to run cross platform, data structure and algorithm nginx choice completely from scratch again based implementation of two-way linked list, for example, dynamic arrays, the red black tree,

Hash table data structure and algorithm, it is self-evident that foundation for our benefit.

src/core/ngx_queue.{c|h} The implementation of basic sequential container a two-way linked list.

Nginx_queue_t is a lightweight container two-way linked list list provided by nginx, it has nothing to do with the nginx memory pool, so this list container is not responsible for the allocation of memory to store the list element.

The characteristics, list as the sequential containers: can the efficient implementation of insert, delete, merge operation.

In the ngx_queue_t container advantage:

A pure two-way linked list, it is not responsible for distribution list elements occupied memory, has nothing to do with the ngx_pool_t Nginx memory pool package,

Sort function,

Support the merger between two list,


The basic structure of a Nginx queue


Nginx queue is realized by a double circular linked list with head node, each node structure for ngx_queue_t

typedef struct ngx_queue_s  ngx_queue_t;

struct ngx_queue_s {

   ngx_queue_t  *prev;   //Before a

   ngx_queue_t  *next;   //The next

};

In a 32 bit operating system, obviously sizeof(ngx_queue_t)=8.

From the ngx_queue_t structure definition can be seen, and no data content node queue structure of nginx (page management in the Linux kernel is also used to this link structure),

This is different from the books will be linked list nodes data member declarations in the structure of linked list nodes in the body, a technique that is C programming abstraction.

Queue operation and structure of nginx only pointer operation, is not responsible for the distribution and node content space, so when defining a queue node itself, it needs its own definition of the data structure

And the distribution of space, and contains a ngx_queue_t pointer or objects in them, need to get data node of the original, need to use the ngx_queue_data macro:

#definengx_queue_data(q, type, link) (type*) ((u_char *) q – offsetof(type, link))

Uses for this macro, in a blog before I also used, please go here. The goal here is how through a variable of a struct structure to obtain

The whole structure of the variable? Defined by ngx_queue_data can be seen, the general definition of queue node structure (the structure of type type), need to define a structure of type type

Members of the ngx_queue_t type, wherein offsetof is mainly used for a member for the structure of offset in the structure, the first parameter to type is the structure of the name, second

Link is the number of members of the structure name, pay attention to the starting address calculation node structure (the need for a type conversion).


Basic operation


The basic operation in nginx ngx_queue_t.

The queue structure defines a sentinel (sentinel) node, he pointed to the head of the queue, which is defined as follows:

#define ngx_queue_sentinel(h) (h)


Some of the most basic operations are as follows (easier to understand, no longer apply the):

Ngx_queue_head was the head node

#define ngx_queue_head(h) (h)->next

Ngx_queue_last tail node

#define ngx_queue_last(h) (h)->prev

Ngx_queue_next node of a node

#define ngx_queue_next(q) (q)->next

Ngx_queue_prev is the last node node

#define ngx_queue_prev(q) (q)->prev

Here are some relatively complex operation:

Ngx_queue_init initialization queue

#define ngx_queue_init(q)                                                    \
   (q)->prev = q;                                                           \
   (q)->next = q

Ngx_queue_empty judging whether the queue is empty

#define ngx_queue_empty(h) (h == (h)->prev)

Ngx_queue_insert_head inserts a new node in the head node after

#define ngx_queue_insert_head(h, x)                                           \

   (x)->next = (h)->next;                                                   \

   (x)->next->prev = x;                                                      \

   (x)->prev = h;                                                           \

   (h)->next = x

Logic as shown below:


Ngx_queue_insert_after inserts a new node in the specified node after

#define ngx_queue_insert_after ngx_queue_insert_head

Ngx_queue_insert_tail inserts a new node in the tail node after.

#define ngx_queue_insert_tail(h, x) \

(x)->prev = (h)->prev; \

(x)->prev->next = x; \

(x)->next = h; \

(h)->prev = x

Drawing understanding tail and head interpolation interpolation different approaches but equally satisfactory results.

Ngx_queue_remove to delete a node in the queue

#define ngx_queue_remove(x)                                                   \
    (x)->next->prev = (x)->prev;                                              \
    (x)->prev->next = (x)->next;                                              \
    (x)->prev = NULL;                                                         \
    (x)->next = NULL
Logic as shown below:


Ngx_queue_split segmentation queue

#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;

Ngx_queue_split has 3 parameters, h as the head of the queue (i.e. chain table pointer), the queue from the Q node queue is divided into two queues, head node of the new queue node after Q of N, graphics and presentation are as follows.


The ngx_queue_add link queue

#define ngx_queue_add(h, n)                                                   \
    (h)->prev->next = (n)->next;                                              \
    (n)->next->prev = (h)->prev;                                              \
    (h)->prev = (n)->prev;                                                    \
    (h)->prev->next = h;

This is not to apply the, can own drawing understanding.

The intermediate node ngx_queue_middle to obtain the queue

If the queue with an odd number of nodes(In addition to head node), Returns the intermediate nodes, if the queue has an even number of nodes, the first node is returned to the queue.

The basic idea of the algorithm: middle pointer after every move a node, while the next pointer after each shift two nodes.

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);
        if (next == ngx_queue_last(queue)) {   //An odd number of nodes
            return middle;
        }
        next = ngx_queue_next(next);
        if (next == ngx_queue_last(queue)) {   //An even number of nodes
            return middle;
        }
   }
}

Ngx_queue_sort queue (stable insertion sort)

From the first node traversal, turn to the current node q is inserted into the front line of order in the queue list.

Function declarations are as follows:

Void ngx_queue_sort(ngx_queue_t *queue, ngx_int_t(*cmp)(const ngx_queue_t *, const ngx_queue_t *))

The function parameter contains a callback function, the callback function used to list two element size comparison. Familiar with insertion sort should be easy to understand this list sorting algorithm.

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) {//Comparison of node
                break;
            }
            prev = ngx_queue_prev(prev);
        } while (prev != ngx_queue_sentinel(queue));// The sentinel node
        ngx_queue_insert_after(prev, q);//In order to insert a node into a line list order in the queue
    }
}

Test

Through the above analysis, we know that if we want to use the nginx ngx_queue_t basic data structure, then we structure must be structure follows the form of the body.

That contains the variable ngx_queue_t, as shown in Fig.


We define a structure, form as follows:


typedef struct
{
    int key;
    char name[32];
    ngx_queue_t link;
}ngx_qTest_t;
The number, names defined in the structure

Then according to the callback function order function structure in the custom ngx_queue.


// From big to small order
ngx_int_t cmp(const ngx_queue_t *a, const ngx_queue_t *b)
{
    ngx_qTest_t *aTest = ngx_queue_data(a, ngx_qTest_t, link);
    ngx_qTest_t *bTest = ngx_queue_data(b, ngx_qTest_t, link);
    return aTest->key <bTest->key;
}
Main functions are as follows:

int main()
{
    ngx_qTest_t arr[5];
    ngx_queue_t head;
    ngx_queue_init(&head);
    int i=0;
    for( ; i<5; ++i)//Initialize the queue
    {
        arr[i].key = i;
        sprintf(arr[i].name, "\"My key is:%d.\"", arr[i].key);
        if(i%2)
        {
            ngx_queue_insert_head(&head, &arr[i].link);
        }
        else
        {
            ngx_queue_insert_tail(&head, &arr[i].link);
        }
    }
    printf("*******************************\n");
    printf("Before sort:\n");
    print_queue(&head);
    ngx_queue_sort(&head, cmp);
    printf("*******************************\n");
    printf("After sort:\n");
    print_queue(&head);

    ngx_queue_t * midq = ngx_queue_middle(&head);
    ngx_qTest_t *mid_data = ngx_queue_data(midq, ngx_qTest_t, link);
    printf("*******************************\n");
    // To obtain the intermediate node
    printf("%The middle key is %d.\n", mid_data->key);
    return 0;
}
The test results as shown in Fig.:


The complete code of GitHub to me

Reference resources:

In depth understanding of nginx

http://blog.csdn.net/livelylittlefish/article/details/6607324

http://blog.csdn.net/ordeder/article/details/17058399

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download

Posted by Blair at February 11, 2014 - 8:16 AM