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