1
2 /*
3 * Copyright (C) Igor Sysoev
4 * Copyright (C) NGINX, Inc.
5 */
6
7
8 #include <nxt_main.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 nxt_queue_link_t *
nxt_queue_middle(nxt_queue_t * queue)17 nxt_queue_middle(nxt_queue_t *queue)
18 {
19 nxt_queue_link_t *middle, *next;
20
21 middle = nxt_queue_first(queue);
22
23 if (middle == nxt_queue_last(queue)) {
24 return middle;
25 }
26
27 next = middle;
28
29 for ( ;; ) {
30 middle = nxt_queue_next(middle);
31
32 next = nxt_queue_next(next);
33
34 if (next == nxt_queue_last(queue)) {
35 return middle;
36 }
37
38 next = nxt_queue_next(next);
39
40 if (next == nxt_queue_last(queue)) {
41 return middle;
42 }
43 }
44 }
45
46
47 /*
48 * nxt_queue_sort() provides a stable sort because it uses the insertion
49 * sort algorithm. Its worst and average computational complexity is O^2.
50 */
51
52 void
nxt_queue_sort(nxt_queue_t * queue,nxt_int_t (* cmp)(const void * data,const nxt_queue_link_t *,const nxt_queue_link_t *),const void * data)53 nxt_queue_sort(nxt_queue_t *queue,
54 nxt_int_t (*cmp)(const void *data, const nxt_queue_link_t *,
55 const nxt_queue_link_t *), const void *data)
56 {
57 nxt_queue_link_t *link, *prev, *next;
58
59 link = nxt_queue_first(queue);
60
61 if (link == nxt_queue_last(queue)) {
62 return;
63 }
64
65 for (link = nxt_queue_next(link);
66 link != nxt_queue_tail(queue);
67 link = next)
68 {
69 prev = nxt_queue_prev(link);
70 next = nxt_queue_next(link);
71
72 nxt_queue_remove(link);
73
74 do {
75 if (cmp(data, prev, link) <= 0) {
76 break;
77 }
78
79 prev = nxt_queue_prev(prev);
80
81 } while (prev != nxt_queue_head(queue));
82
83 nxt_queue_insert_after(prev, link);
84 }
85 }
86