Nginx erweiterte Datenstruktur-Quellcode-Analyse (1) ----- doppelt verknüpfte Liste

ng_queue_t ist ein von Nginx bereitgestellter sequentieller Container, der Daten in einer doppelt verknüpften Liste zusammenfasst.

Der Vorteil einer verknüpften Liste als sequentieller Container besteht darin, dass sie Vorgänge wie Einfügen, Löschen, Zusammenführen usw. effizient ausführen kann. Beim Verschieben von Elementen in In der verknüpften Liste müssen Sie nur den Zeiger ändern. Daher eignet es sich für Situationen, in denen der Container häufig geändert wird.

Im Vergleich zu anderen sequentiellen Containern bietet es die folgenden drei Vorteile:

( 1) Die Sortierfunktion wird mithilfe der Einfügungssortierung implementiert. Obwohl sie nicht zum Sortieren sehr großer Datenmengen geeignet ist, ist sie einfach und praktisch.

(2) Es ist sehr leichtgewichtig und nicht für die Zuweisung des von verknüpften Listenelementen belegten Speichers verantwortlich. ngx_queue_t verknüpft diese zugewiesenen Speicherelemente einfach mit einer doppelt verknüpften Liste

(3) Unterstützt die Zusammenführung zweier verknüpfter Listen.

Als Nginx diese doppelt verknüpfte Liste entwarf, da der Container und die Elemente die Struktur ngx_queue_t gemeinsam nutzen, um eine Verwechslung der Bedeutung der Mitglieder dieser Struktur zu vermeiden, Nginx kapselt die verknüpfte Liste aller Methoden von Containern und Elementen.

Header-Datei von ngx_queue_t:

In der Implementierungsdatei von gx_queue_t gibt es nur zwei Methoden: Eine besteht darin, das mittlere Element in der verknüpften Liste zurückzugeben, und die andere darin, die verknüpfte Liste zu sortieren.

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_empty(h)                                                    \是否为空
    (h == (h)->prev)


#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_head(h)                                                     \返回第一个结构体指针
    (h)->next


#define ngx_queue_last(h)                                                     \返回最后一个结构体指针
    (h)->prev


#define ngx_queue_sentinel(h)                                                 \返回容器结构体指针
    (h)


#define ngx_queue_next(q)                                                     \返回q的下一个元素
    (q)->next


#define ngx_queue_prev(q)                                                     \返回q的上一个元素
    (q)->prev


#if (NGX_DEBUG)

#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
    (x)->next->prev = (x)->prev;                                              \
    (x)->prev->next = (x)->next

#endif


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


#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)                                         \返回q所属结构体地址
    (type *) ((u_char *) q - offsetof(type, link))

Urheberrechtserklärung: Dieser Artikel ist ein Originalartikel des Bloggers und hat nicht vom Blogger autorisiert. Eine Vervielfältigung ist nicht gestattet.

Das Obige stellt die erweiterte Nginx-Datenstruktur-Quellcode-Analyse vor (1) ----- doppelt verknüpfte Liste, einschließlich Aspekten des Inhalts. Ich hoffe, dass sie für Freunde hilfreich sein wird, die sich für PHP-Tutorials interessieren.

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)) {              //next每走一步都要判断一下的
            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);  //分别保存q的前后节点
        next = ngx_queue_next(q);

        ngx_queue_remove(q);

        do {
            if (cmp(prev, q) <= 0) {  //若prev小于，这个循环结束
                break;
            }

            prev = ngx_queue_prev(prev);//否则跟前面一个元素比

        } while (prev != ngx_queue_sentinel(queue));//这个为结束条件，prev为链表结构体结束

        ngx_queue_insert_after(prev, q);//插入q
    }
}