Mercurial > hg > nginx-vendor-0-8
diff src/core/ngx_queue.c @ 378:820f6378fc00 NGINX_0_7_1
nginx 0.7.1
*) Change: now locations are searched in a tree.
*) Change: the "optimize_server_names" directive was canceled due to
the "server_name_in_redirect" directive introduction.
*) Change: some long deprecated directives are not supported anymore.
*) Change: the "none" parameter in the "ssl_session_cache" directive;
now this is default parameter.
Thanks to Rob Mueller.
*) Bugfix: worker processes might not catch reconfiguration and log
rotation signals.
*) Bugfix: nginx could not be built on latest Fedora 9 Linux.
Thanks to Roxis.
author | Igor Sysoev <http://sysoev.ru> |
---|---|
date | Mon, 26 May 2008 00:00:00 +0400 |
parents | |
children |
line wrap: on
line diff
new file mode 100644 --- /dev/null +++ b/src/core/ngx_queue.c @@ -0,0 +1,79 @@ + +/* + * 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); + } +}