xref: /unit/src/nxt_queue.c (revision 0:a63ceefd6ab0)
```/* <![CDATA[ */
function get_sym_list(){return [["Function","xf",[["nxt_queue_middle",17],["nxt_queue_sort",53]]]];} /* ]]> */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
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 {
58
59     link = nxt_queue_first(queue);
60
61     if (link == nxt_queue_last(queue)) {
62         return;
63     }
64
66          link != nxt_queue_tail(queue);
67          link = next)
68     {
69         prev = nxt_queue_prev(link);
70         next = nxt_queue_next(link);
71
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