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