Mercurial > hg > nginx
annotate src/core/ngx_queue.c @ 9331:dbf76fdd109f default tip
release-1.27.4 tag
author | Maxim Dounin <mdounin@mdounin.ru> |
---|---|
date | Tue, 03 Sep 2024 13:11:25 +0300 |
parents | 3038bd4d7816 |
children |
rev | line source |
---|---|
2026 | 1 |
2 /* | |
3 * Copyright (C) Igor Sysoev | |
4412 | 4 * Copyright (C) Nginx, Inc. |
2026 | 5 */ |
6 | |
7 | |
8 #include <ngx_config.h> | |
9 #include <ngx_core.h> | |
10 | |
11 | |
9167
3038bd4d7816
Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
12 static void ngx_queue_merge(ngx_queue_t *queue, ngx_queue_t *tail, |
3038bd4d7816
Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
13 ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *)); |
3038bd4d7816
Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
14 |
3038bd4d7816
Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
15 |
2026 | 16 /* |
17 * find the middle queue element if the queue has odd number of elements | |
18 * or the first element of the queue's second part otherwise | |
19 */ | |
20 | |
21 ngx_queue_t * | |
22 ngx_queue_middle(ngx_queue_t *queue) | |
23 { | |
24 ngx_queue_t *middle, *next; | |
25 | |
26 middle = ngx_queue_head(queue); | |
27 | |
28 if (middle == ngx_queue_last(queue)) { | |
29 return middle; | |
30 } | |
31 | |
32 next = ngx_queue_head(queue); | |
33 | |
34 for ( ;; ) { | |
35 middle = ngx_queue_next(middle); | |
36 | |
37 next = ngx_queue_next(next); | |
38 | |
39 if (next == ngx_queue_last(queue)) { | |
40 return middle; | |
41 } | |
42 | |
43 next = ngx_queue_next(next); | |
44 | |
45 if (next == ngx_queue_last(queue)) { | |
46 return middle; | |
47 } | |
48 } | |
49 } | |
50 | |
51 | |
9167
3038bd4d7816
Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
52 /* the stable merge sort */ |
2026 | 53 |
54 void | |
55 ngx_queue_sort(ngx_queue_t *queue, | |
56 ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *)) | |
57 { | |
9167
3038bd4d7816
Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
58 ngx_queue_t *q, tail; |
2026 | 59 |
60 q = ngx_queue_head(queue); | |
61 | |
62 if (q == ngx_queue_last(queue)) { | |
63 return; | |
64 } | |
65 | |
9167
3038bd4d7816
Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
66 q = ngx_queue_middle(queue); |
3038bd4d7816
Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
67 |
3038bd4d7816
Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
68 ngx_queue_split(queue, q, &tail); |
3038bd4d7816
Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
69 |
3038bd4d7816
Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
70 ngx_queue_sort(queue, cmp); |
3038bd4d7816
Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
71 ngx_queue_sort(&tail, cmp); |
3038bd4d7816
Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
72 |
3038bd4d7816
Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
73 ngx_queue_merge(queue, &tail, cmp); |
3038bd4d7816
Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
74 } |
2026 | 75 |
76 | |
9167
3038bd4d7816
Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
77 static void |
3038bd4d7816
Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
78 ngx_queue_merge(ngx_queue_t *queue, ngx_queue_t *tail, |
3038bd4d7816
Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
79 ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *)) |
3038bd4d7816
Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
80 { |
3038bd4d7816
Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
81 ngx_queue_t *q1, *q2; |
3038bd4d7816
Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
82 |
3038bd4d7816
Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
83 q1 = ngx_queue_head(queue); |
3038bd4d7816
Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
84 q2 = ngx_queue_head(tail); |
2026 | 85 |
9167
3038bd4d7816
Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
86 for ( ;; ) { |
3038bd4d7816
Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
87 if (q1 == ngx_queue_sentinel(queue)) { |
3038bd4d7816
Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
88 ngx_queue_add(queue, tail); |
3038bd4d7816
Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
89 break; |
3038bd4d7816
Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
90 } |
3038bd4d7816
Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
91 |
3038bd4d7816
Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
92 if (q2 == ngx_queue_sentinel(tail)) { |
3038bd4d7816
Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
93 break; |
3038bd4d7816
Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
94 } |
2026 | 95 |
9167
3038bd4d7816
Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
96 if (cmp(q1, q2) <= 0) { |
3038bd4d7816
Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
97 q1 = ngx_queue_next(q1); |
3038bd4d7816
Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
98 continue; |
3038bd4d7816
Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
99 } |
2026 | 100 |
9167
3038bd4d7816
Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
101 ngx_queue_remove(q2); |
3038bd4d7816
Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
102 ngx_queue_insert_before(q1, q2); |
2026 | 103 |
9167
3038bd4d7816
Core: changed ngx_queue_sort() to use merge sort.
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
104 q2 = ngx_queue_head(tail); |
2026 | 105 } |
106 } |