Annotation of embedaddon/nginx/src/core/ngx_queue.c, revision 1.1.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: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>