Nginx source code to learn - two-way linked list (ngx_queue_t) analysis and exam

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

The original link:

1 background

Nginx ngx_queue_t is a two-way linked list by " boarding " in the elements including prev and next ngx_queue_s to achieve. Page management in the Linux kernel is also used to this link structure. Linux core scenario analysis describes it: Linux kernel authors prev and next from the "host" abstract data structure into a structure of list_head, so list_head can be connected to the "host" "". (kernel: include/linux/list.h , include/linux/mm.h )

To construct the two-way linked list using ngx_quque_t, the list of links operating data structure related to the abstracted, so as to facilitate the preparation of list manipulation functions. Secondly, with the ngx_queue_t structure of the lists can be connected in series is different data types (as long as the data type that contains the data structure ngx_quque_t). Do not make a proper metaphor, no matter what kind of items (data type), as long as there is a hole items (ngx_quque_t) we can use line (ngx_queue_t chain) of these items together. Furthermore, sort the list, operating mobile elements, only need to modify the ngx_queue_t pointer can be related, so the two-way linked list structure is also called Nginx for lightweight list.

2 ngx_queue_t source code

(main source notes from GitHub), in order to be able to run under the VC6.0 parameter data type definition, part of the source code has been I redefine (source code annotated)


//ngx_queue.h
#ifndef _NGX_QUEUE_H_INCLUDED_
#define _NGX_QUEUE_H_INCLUDED_

//add by ordeder
#define ngx_int_t int
#define u_char unsigned int
	//Custom offsetof
	//http://blog.csdn.net/ordeder/article/details/10226427
#define offsetof(struct_type, member)   ((size_t) &((struct_type *) 0)->member) 
typedef struct ngx_queue_s  ngx_queue_t;
//end of "add by ordeder"

//Reference resources: 
//http://blog.csdn.net/livelylittlefish/article/details/6607324
struct ngx_queue_s {
    ngx_queue_t  *prev;   //Before a
    ngx_queue_t  *next;   //The next
};

//Initialize the queue  
#define ngx_queue_init(q)                                                     \
    (q)->prev = q;                                                            \
    (q)->next = q

//To judge whether the queue is empty
#define ngx_queue_empty(h)                                                    \
    (h == (h)->prev)

//The new node is inserted in the first node after
#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

//The new node is inserted 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

//The head node
#define ngx_queue_head(h)                                                     \
    (h)->next

//Tail node
#define ngx_queue_last(h)                                                     \
    (h)->prev

//Head mark node
#define ngx_queue_sentinel(h)                                                 \
    (h)

//The next node
#define ngx_queue_next(q)                                                     \
    (q)->next

//The last node
#define ngx_queue_prev(q)                                                     \
    (q)->prev


#if (NGX_DEBUG)

//Delete node
#define ngx_queue_remove(x)                                                   \
    (x)->next->prev = (x)->prev;                                              \
    (x)->prev->next = (x)->next;                                              \
    (x)->prev = NULL;                                                         \
    (x)->next = NULL

#else

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

#endif

//Partition 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;

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

//Gets the node data queue, q is a node in the queue, type type, link type element name in the ngx_queue_t queue
#define ngx_queue_data(q, type, link)                                         \
    (type *) ((u_char *) q - offsetof(type, link))

//The intermediate node queue
ngx_queue_t *ngx_queue_middle(ngx_queue_t *queue);
void ngx_queue_sort(ngx_queue_t *queue,
    ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *));


#endif /* _NGX_QUEUE_H_INCLUDED_ */

3 VC6.0 test driver

The following is a test, I will nginx on the ngx_queue_t source code as a.H header file, VC is defined in two different types of body test, test ideas: the definition of the two different types of structures book and journal, they all contain the ngx_queue_t structure. Test the two different types of objects are connected in series with a NGX chain, and then sorted based on the object list in ISBN.


//Ngx_queue.c test cases
#include "ngx_queue.h"
#include <stdio.h>

/////////////////////Two functions from the source code: ngx_quque.c
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)) {
            return middle;
        }
		
        next = ngx_queue_next(next);
		
        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;
            }
			
            prev = ngx_queue_prev(prev);
			
        } while (prev != ngx_queue_sentinel(queue));
		
        ngx_queue_insert_after(prev, q);
    }
}

//The following code for test case

struct Book_s{
	ngx_queue_t qLink;
	int type;
	int ISBN;
};

struct Journal_s{
	ngx_queue_t qLink;
	int type;
	int ISBN;	//The first three elements define the sequence and the same book, in order to ngx_queue_data (Unified) in using Boot_t to get element pointer
	int price;	//Compared to book, an element more, here to book structure and different body and add
};

typedef struct Book_s Boot_t;
typedef struct Journal_s Journal_t;

#define N 3


ngx_int_t book_ISBN_cmp(const ngx_queue_t *a, const ngx_queue_t *b)
{
	Boot_t* pBook_a = ngx_queue_data(a,Boot_t,qLink);
	Boot_t* pBook_b = ngx_queue_data(b,Boot_t,qLink);
	return pBook_a->ISBN > pBook_b->ISBN;
}

int main()
{
	Boot_t book[N];
	Journal_t journal[N];
	int i;

	ngx_queue_t queueContainer;
	ngx_queue_init(&queueContainer);
	
	for (i=0;i<N;i++)
	{
		book[i].ISBN = i;
		book[i].type = 0;

		journal[i].ISBN = i+N;
		journal[i].type = 1;
		journal[i].price = 100 + i;

		ngx_queue_insert_head(&queueContainer,&book[i].qLink);
		ngx_queue_insert_tail(&queueContainer,&journal[i].qLink);
	}
	
	ngx_queue_t *q;
	Boot_t* pBook;
	Journal_t * pJournal;

	for (q = ngx_queue_head(&queueContainer);
		q != ngx_queue_sentinel(&queueContainer);
		q = ngx_queue_next(q))
	{
		pBook = (Boot_t*) (ngx_queue_data(q,Boot_t,qLink));
		if (pBook->type == 0) //Book
		{
			printf("book isbn:%d \n",pBook->ISBN);
		}
		else if(pBook->type == 1) //journal
		{
			pJournal = (Journal_t *) pBook;
			printf("journal isbn:%d price:%d\n",pJournal->ISBN,pJournal->price);
		}
	}

	//QueueContainer will be sorted according to ISBN
	ngx_queue_sort(&queueContainer,book_ISBN_cmp);

	printf("\nAfter sort by ISBN\n");
	for (q = ngx_queue_head(&queueContainer);
	q != ngx_queue_sentinel(&queueContainer);
	q = ngx_queue_next(q))
	{
		pBook = (Boot_t*) (ngx_queue_data(q,Boot_t,qLink));
		if (pBook->type == 0) //Book
		{
			printf("book isbn:%d \n",pBook->ISBN);
		}
		else if(pBook->type == 1) //journal
		{
			pJournal = (Journal_t *) pBook;
			printf("journal isbn:%d price:%d\n",pJournal->ISBN,pJournal->price);
		}
	}

	return 0;
}


4 test results and analysis

The 4.1 test output.:

Content of queue as flows
book isbn:2
book isbn:1
book isbn:0
journal isbn:3 price:100
journal isbn:4 price:101
journal isbn:5 price:102

After sort by ISBN
book isbn:0
book isbn:1
book isbn:2
journal isbn:3 price:100
journal isbn:4 price:101
journal isbn:5 price:102

4.2 analysis

This gives book and journal into the list, ranking of each data object in the list data. Because the book and journal is an array, so the continuous space representation. Different colors in the storage space to the domain block represent different data objects. As can be seen from the picture, the qLink data constitutes a link between host data, it is like a rope, each data object link. QueueContainer as the head, not boarding to data objects, he was as a whole double linked list of the Sentinels, mark the header and footer location.


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

Posted by Jay at January 27, 2014 - 3:04 PM