Mercurial > hg > nginx-vendor-current

comparison src/core/ngx_queue.c @ 378:820f6378fc00 NGINX_0_7_1

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