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 }
80
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more
information.