|
378
|
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 }
|
