Return to ngx_queue.c CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / nginx / src / core

Annotation of embedaddon/nginx/src/core/ngx_queue.c, revision 1.1

1.1     ! misho       1: 
        !             2: /*
        !             3:  * Copyright (C) Igor Sysoev
        !             4:  * Copyright (C) Nginx, Inc.
        !             5:  */
        !             6: 
        !             7: 
        !             8: #include <ngx_config.h>
        !             9: #include <ngx_core.h>
        !            10: 
        !            11: 
        !            12: /*
        !            13:  * find the middle queue element if the queue has odd number of elements
        !            14:  * or the first element of the queue's second part otherwise
        !            15:  */
        !            16: 
        !            17: ngx_queue_t *
        !            18: ngx_queue_middle(ngx_queue_t *queue)
        !            19: {
        !            20:     ngx_queue_t  *middle, *next;
        !            21: 
        !            22:     middle = ngx_queue_head(queue);
        !            23: 
        !            24:     if (middle == ngx_queue_last(queue)) {
        !            25:         return middle;
        !            26:     }
        !            27: 
        !            28:     next = ngx_queue_head(queue);
        !            29: 
        !            30:     for ( ;; ) {
        !            31:         middle = ngx_queue_next(middle);
        !            32: 
        !            33:         next = ngx_queue_next(next);
        !            34: 
        !            35:         if (next == ngx_queue_last(queue)) {
        !            36:             return middle;
        !            37:         }
        !            38: 
        !            39:         next = ngx_queue_next(next);
        !            40: 
        !            41:         if (next == ngx_queue_last(queue)) {
        !            42:             return middle;
        !            43:         }
        !            44:     }
        !            45: }
        !            46: 
        !            47: 
        !            48: /* the stable insertion sort */
        !            49: 
        !            50: void
        !            51: ngx_queue_sort(ngx_queue_t *queue,
        !            52:     ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *))
        !            53: {
        !            54:     ngx_queue_t  *q, *prev, *next;
        !            55: 
        !            56:     q = ngx_queue_head(queue);
        !            57: 
        !            58:     if (q == ngx_queue_last(queue)) {
        !            59:         return;
        !            60:     }
        !            61: 
        !            62:     for (q = ngx_queue_next(q); q != ngx_queue_sentinel(queue); q = next) {
        !            63: 
        !            64:         prev = ngx_queue_prev(q);
        !            65:         next = ngx_queue_next(q);
        !            66: 
        !            67:         ngx_queue_remove(q);
        !            68: 
        !            69:         do {
        !            70:             if (cmp(prev, q) <= 0) {
        !            71:                 break;
        !            72:             }
        !            73: 
        !            74:             prev = ngx_queue_prev(prev);
        !            75: 
        !            76:         } while (prev != ngx_queue_sentinel(queue));
        !            77: 
        !            78:         ngx_queue_insert_after(prev, q);
        !            79:     }
        !            80: }