view src/core/ngx_queue.c @ 544:f7ec98e3caeb NGINX_0_8_18

nginx 0.8.18 *) Feature: the "read_ahead" directive. *) Feature: now several "perl_modules" directive may be used. *) Feature: the "limit_req_log_level" and "limit_conn_log_level" directives. *) Bugfix: now "limit_req" directive conforms to the leaky bucket algorithm. Thanks to Maxim Dounin. *) Bugfix: nginx did not work on Linux/sparc. Thanks to Marcus Ramberg. *) Bugfix: nginx sent '\0' in a "Location" response header line on MKCOL request. Thanks to Xie Zhenye. *) Bugfix: zero status code was logged instead of 499 status code; the bug had appeared in 0.8.11. *) Bugfix: socket leak; the bug had appeared in 0.8.11.
author Igor Sysoev <http://sysoev.ru>
date Tue, 06 Oct 2009 00:00:00 +0400
parents 820f6378fc00
children
line wrap: on
line source


/*
 * Copyright (C) Igor Sysoev
 */


#include <ngx_config.h>
#include <ngx_core.h>


/*
 * find the middle queue element if the queue has odd number of elements
 * or the first element of the queue's second part otherwise
 */

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);
    }
}