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) \ 55 do { \ 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) \ 89 do { \ 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) \ 125 do { \ 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