1/*-
2 * SPDX-License-Identifier: BSD-2-Clause
3 *
4 * Copyright (c) 2023 Colin Percival
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
21 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
22 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
23 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
24 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
25 * SUCH DAMAGE.
26 */
27
28#ifndef _SYS_QUEUE_MERGESORT_H_
29#define _SYS_QUEUE_MERGESORT_H_
30
31/*
32 * This file defines macros for performing mergesorts on singly-linked lists,
33 * single-linked tail queues, lists, and tail queues as implemented in
34 * <sys/queue.h>.
35 */
36
37/*
38 * Shims to work around _CONCAT and _INSERT_AFTER taking different numbers of
39 * arguments for different types of linked lists.
40 */
41#define STAILQ_CONCAT_4(head1, head2, type, field) \
42 STAILQ_CONCAT(head1, head2)
43#define TAILQ_CONCAT_4(head1, head2, type, field) \
44 TAILQ_CONCAT(head1, head2, field)
45#define SLIST_INSERT_AFTER_4(head, slistelm, elm, field) \
46 SLIST_INSERT_AFTER(slistelm, elm, field)
47#define LIST_INSERT_AFTER_4(head, slistelm, elm, field) \
48 LIST_INSERT_AFTER(slistelm, elm, field)
49
50/*
51 * Generic macros which apply to all types of lists.
52 */
53#define SYSQUEUE_MERGE(sqms_list1, sqms_list2, thunk, sqms_cmp, TYPE, NAME, \
54 M_FIRST, M_INSERT_AFTER, M_INSERT_HEAD, M_NEXT, M_REMOVE_HEAD) \
55do { \
56 struct TYPE *sqms_elm1; \
57 struct TYPE *sqms_elm1_prev; \
58 struct TYPE *sqms_elm2; \
59 \
60 /* Start at the beginning of list1; _prev is the previous node. */ \
61 sqms_elm1_prev = NULL; \
62 sqms_elm1 = M_FIRST(sqms_list1); \
63 \
64 /* Pull entries from list2 and insert them into list1. */ \
65 while ((sqms_elm2 = M_FIRST(sqms_list2)) != NULL) { \
66 /* Remove from list2. */ \
67 M_REMOVE_HEAD(sqms_list2, NAME); \
68 \
69 /* Advance until we find the right place to insert it. */ \
70 while ((sqms_elm1 != NULL) && \
71 (sqms_cmp)(sqms_elm2, sqms_elm1, thunk) >= 0) { \
72 sqms_elm1_prev = sqms_elm1; \
73 sqms_elm1 = M_NEXT(sqms_elm1, NAME); \
74 } \
75 \
76 /* Insert into list1. */ \
77 if (sqms_elm1_prev == NULL) \
78 M_INSERT_HEAD(sqms_list1, sqms_elm2, NAME); \
79 else \
80 M_INSERT_AFTER(sqms_list1, sqms_elm1_prev, \
81 sqms_elm2, NAME); \
82 sqms_elm1_prev = sqms_elm2; \
83 } \
84} while (0)
85
86#define SYSQUEUE_MERGE_SUBL(sqms_sorted, sqms_len1, sqms_len2, sqms_melm, \
87 sqms_mpos, thunk, sqms_cmp, TYPE, NAME, \
88 M_FIRST, M_NEXT, M_REMOVE_HEAD, M_INSERT_AFTER) \
89do { \
90 struct TYPE *sqms_curelm; \
91 size_t sqms_i; \
92 \
93 /* Find the element before the start of the second sorted region. */ \
94 while ((sqms_mpos) < (sqms_len1)) { \
95 (sqms_melm) = M_NEXT((sqms_melm), NAME); \
96 (sqms_mpos)++; \
97 } \
98 \
99 /* Pull len1 entries off the list and insert in the right place. */ \
100 for (sqms_i = 0; sqms_i < (sqms_len1); sqms_i++) { \
101 /* Grab the first element. */ \
102 sqms_curelm = M_FIRST(&(sqms_sorted)); \
103 \
104 /* Advance until we find the right place to insert it. */ \
105 while (((sqms_mpos) < (sqms_len1) + (sqms_len2)) && \
106 ((sqms_cmp)(sqms_curelm, M_NEXT((sqms_melm), NAME), \
107 thunk) >= 0)) { \
108 (sqms_melm) = M_NEXT((sqms_melm), NAME); \
109 (sqms_mpos)++; \
110 } \
111 \
112 /* Move the element in the right place if not already there. */ \
113 if (sqms_curelm != (sqms_melm)) { \
114 M_REMOVE_HEAD(&(sqms_sorted), NAME); \
115 M_INSERT_AFTER(&(sqms_sorted), (sqms_melm), \
116 sqms_curelm, NAME); \
117 (sqms_melm) = sqms_curelm; \
118 } \
119 } \
120} while (0)
121
122#define SYSQUEUE_MERGESORT(sqms_head, thunk, sqms_cmp, TYPE, NAME, M_HEAD, \
123 M_HEAD_INITIALIZER, M_EMPTY, M_FIRST, M_NEXT, M_INSERT_HEAD, \
124 M_INSERT_AFTER, M_CONCAT, M_REMOVE_HEAD) \
125do { \
126 /* \
127 * Invariant: If sqms_slen = 2^a + 2^b + ... + 2^z with a < b < ... < z \
128 * then sqms_sorted is a sequence of 2^a sorted entries followed by a \
129 * list of 2^b sorted entries ... followed by a list of 2^z sorted \
130 * entries. \
131 */ \
132 M_HEAD(, TYPE) sqms_sorted = M_HEAD_INITIALIZER(sqms_sorted); \
133 struct TYPE *sqms_elm; \
134 size_t sqms_slen = 0; \
135 size_t sqms_sortmask; \
136 size_t sqms_mpos; \
137 \
138 /* Move everything from the input list to sqms_sorted. */ \
139 while (!M_EMPTY(sqms_head)) { \
140 /* Pull the head off the input list. */ \
141 sqms_elm = M_FIRST(sqms_head); \
142 M_REMOVE_HEAD(sqms_head, NAME); \
143 \
144 /* Push it onto sqms_sorted. */ \
145 M_INSERT_HEAD(&sqms_sorted, sqms_elm, NAME); \
146 sqms_slen++; \
147 \
148 /* Restore sorting invariant. */ \
149 sqms_mpos = 1; \
150 for (sqms_sortmask = 1; \
151 sqms_sortmask & ~sqms_slen; \
152 sqms_sortmask <<= 1) \
153 SYSQUEUE_MERGE_SUBL(sqms_sorted, sqms_sortmask, \
154 sqms_sortmask, sqms_elm, sqms_mpos, thunk, sqms_cmp,\
155 TYPE, NAME, M_FIRST, M_NEXT, M_REMOVE_HEAD, \
156 M_INSERT_AFTER); \
157 } \
158 \
159 /* Merge the remaining sublists. */ \
160 sqms_elm = M_FIRST(&sqms_sorted); \
161 sqms_mpos = 1; \
162 for (sqms_sortmask = 2; \
163 sqms_sortmask < sqms_slen; \
164 sqms_sortmask <<= 1) \
165 if (sqms_slen & sqms_sortmask) \
166 SYSQUEUE_MERGE_SUBL(sqms_sorted, \
167 sqms_slen & (sqms_sortmask - 1), sqms_sortmask, \
168 sqms_elm, sqms_mpos, thunk, sqms_cmp, \
169 TYPE, NAME, M_FIRST, M_NEXT, M_REMOVE_HEAD, \
170 M_INSERT_AFTER); \
171 \
172 /* Move the sorted list back to the input list. */ \
173 M_CONCAT(sqms_head, &sqms_sorted, TYPE, NAME); \
174} while (0)
175
176/**
177 * Macros for each of the individual data types. They are all invoked as
178 * FOO_MERGESORT(head, thunk, compar, TYPE, NAME)
179 * and
180 * FOO_MERGE(list1, list2, thunk, compar, TYPE, NAME)
181 * where the compar function operates as in qsort_r, i.e. compar(a, b, thunk)
182 * returns an integer less than, equal to, or greater than zero if a is
183 * considered to be respectively less than, equal to, or greater than b.
184 */
185#define SLIST_MERGESORT(head, thunk, cmp, TYPE, NAME) \
186 SYSQUEUE_MERGESORT((head), (thunk), (cmp), TYPE, NAME, SLIST_HEAD, \
187 SLIST_HEAD_INITIALIZER, SLIST_EMPTY, SLIST_FIRST, SLIST_NEXT, \
188 SLIST_INSERT_HEAD, SLIST_INSERT_AFTER_4, SLIST_CONCAT, SLIST_REMOVE_HEAD)
189#define SLIST_MERGE(list1, list2, thunk, cmp, TYPE, NAME) \
190 SYSQUEUE_MERGE((list1), (list2), (thunk), (cmp), TYPE, NAME, SLIST_FIRST, \
191 SLIST_INSERT_AFTER_4, SLIST_INSERT_HEAD, SLIST_NEXT, SLIST_REMOVE_HEAD)
192
193#define LIST_MERGESORT(head, thunk, cmp, TYPE, NAME) \
194 SYSQUEUE_MERGESORT((head), (thunk), (cmp), TYPE, NAME, LIST_HEAD, \
195 LIST_HEAD_INITIALIZER, LIST_EMPTY, LIST_FIRST, LIST_NEXT, \
196 LIST_INSERT_HEAD, LIST_INSERT_AFTER_4, LIST_CONCAT, LIST_REMOVE_HEAD)
197#define LIST_MERGE(list1, list2, thunk, cmp, TYPE, NAME) \
198 SYSQUEUE_MERGE((list1), (list2), (thunk), (cmp), TYPE, NAME, LIST_FIRST, \
199 LIST_INSERT_AFTER_4, LIST_INSERT_HEAD, LIST_NEXT, LIST_REMOVE_HEAD)
200
201#define STAILQ_MERGESORT(head, thunk, cmp, TYPE, NAME) \
202 SYSQUEUE_MERGESORT((head), (thunk), (cmp), TYPE, NAME, STAILQ_HEAD, \
203 STAILQ_HEAD_INITIALIZER, STAILQ_EMPTY, STAILQ_FIRST, STAILQ_NEXT, \
204 STAILQ_INSERT_HEAD, STAILQ_INSERT_AFTER, STAILQ_CONCAT_4, STAILQ_REMOVE_HEAD)
205#define STAILQ_MERGE(list1, list2, thunk, cmp, TYPE, NAME) \
206 SYSQUEUE_MERGE((list1), (list2), (thunk), (cmp), TYPE, NAME, STAILQ_FIRST, \
207 STAILQ_INSERT_AFTER, STAILQ_INSERT_HEAD, STAILQ_NEXT, STAILQ_REMOVE_HEAD)
208
209#define TAILQ_MERGESORT(head, thunk, cmp, TYPE, NAME) \
210 SYSQUEUE_MERGESORT((head), (thunk), (cmp), TYPE, NAME, TAILQ_HEAD, \
211 TAILQ_HEAD_INITIALIZER, TAILQ_EMPTY, TAILQ_FIRST, TAILQ_NEXT, \
212 TAILQ_INSERT_HEAD, TAILQ_INSERT_AFTER, TAILQ_CONCAT_4, TAILQ_REMOVE_HEAD)
213#define TAILQ_MERGE(list1, list2, thunk, cmp, TYPE, NAME) \
214 SYSQUEUE_MERGE((list1), (list2), (thunk), (cmp), TYPE, NAME, TAILQ_FIRST, \
215 TAILQ_INSERT_AFTER, TAILQ_INSERT_HEAD, TAILQ_NEXT, TAILQ_REMOVE_HEAD)
216
217#endif /* !_SYS_QUEUE_MERGESORT_H_ */