blob: fb32316cd72f388b194c7daf99dc9ad5456b804f (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
/*
* Copyright (C) Igor Sysoev
* Copyright (C) NGINX, Inc.
*/
#include <njs_main.h>
/*
* Find the middle queue element if the queue has odd number of elements,
* or the first element of the queue's second part otherwise.
*/
njs_queue_link_t *
njs_queue_middle(njs_queue_t *queue)
{
njs_queue_link_t *middle, *next;
middle = njs_queue_first(queue);
if (middle == njs_queue_last(queue)) {
return middle;
}
next = middle;
for ( ;; ) {
middle = njs_queue_next(middle);
next = njs_queue_next(next);
if (next == njs_queue_last(queue)) {
return middle;
}
next = njs_queue_next(next);
if (next == njs_queue_last(queue)) {
return middle;
}
}
}
/*
* njs_queue_sort() provides a stable sort because it uses the insertion
* sort algorithm. Its worst and average computational complexity is O^2.
*/
void
njs_queue_sort(njs_queue_t *queue,
njs_int_t (*compare)(const void *data, const njs_queue_link_t *,
const njs_queue_link_t *), const void *data)
{
njs_queue_link_t *link, *prev, *next;
link = njs_queue_first(queue);
if (link == njs_queue_last(queue)) {
return;
}
for (link = njs_queue_next(link);
link != njs_queue_tail(queue);
link = next)
{
prev = njs_queue_prev(link);
next = njs_queue_next(link);
njs_queue_remove(link);
do {
if (compare(data, prev, link) <= 0) {
break;
}
prev = njs_queue_prev(prev);
} while (prev != njs_queue_head(queue));
njs_queue_insert_after(prev, link);
}
}
|
