xref: /unit/src/nxt_queue.c (revision 0:a63ceefd6ab0)
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