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_ */
218