/*- * SPDX-License-Identifier: BSD-2-Clause * * Copyright (c) 2023 Colin Percival * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. */ #ifndef _SYS_QUEUE_MERGESORT_H_ #define _SYS_QUEUE_MERGESORT_H_ /* * This file defines macros for performing mergesorts on singly-linked lists, * single-linked tail queues, lists, and tail queues as implemented in * . */ /* * Shims to work around _CONCAT and _INSERT_AFTER taking different numbers of * arguments for different types of linked lists. */ #define STAILQ_CONCAT_4(head1, head2, type, field) \ STAILQ_CONCAT(head1, head2) #define TAILQ_CONCAT_4(head1, head2, type, field) \ TAILQ_CONCAT(head1, head2, field) #define SLIST_INSERT_AFTER_4(head, slistelm, elm, field) \ SLIST_INSERT_AFTER(slistelm, elm, field) #define LIST_INSERT_AFTER_4(head, slistelm, elm, field) \ LIST_INSERT_AFTER(slistelm, elm, field) /* * Generic macros which apply to all types of lists. */ #define SYSQUEUE_MERGE(sqms_list1, sqms_list2, thunk, sqms_cmp, TYPE, NAME, \ M_FIRST, M_INSERT_AFTER, M_INSERT_HEAD, M_NEXT, M_REMOVE_HEAD) \ do { \ struct TYPE *sqms_elm1; \ struct TYPE *sqms_elm1_prev; \ struct TYPE *sqms_elm2; \ \ /* Start at the beginning of list1; _prev is the previous node. */ \ sqms_elm1_prev = NULL; \ sqms_elm1 = M_FIRST(sqms_list1); \ \ /* Pull entries from list2 and insert them into list1. */ \ while ((sqms_elm2 = M_FIRST(sqms_list2)) != NULL) { \ /* Remove from list2. */ \ M_REMOVE_HEAD(sqms_list2, NAME); \ \ /* Advance until we find the right place to insert it. */ \ while ((sqms_elm1 != NULL) && \ (sqms_cmp)(sqms_elm2, sqms_elm1, thunk) >= 0) { \ sqms_elm1_prev = sqms_elm1; \ sqms_elm1 = M_NEXT(sqms_elm1, NAME); \ } \ \ /* Insert into list1. */ \ if (sqms_elm1_prev == NULL) \ M_INSERT_HEAD(sqms_list1, sqms_elm2, NAME); \ else \ M_INSERT_AFTER(sqms_list1, sqms_elm1_prev, \ sqms_elm2, NAME); \ sqms_elm1_prev = sqms_elm2; \ } \ } while (0) #define SYSQUEUE_MERGE_SUBL(sqms_sorted, sqms_len1, sqms_len2, sqms_melm, \ sqms_mpos, thunk, sqms_cmp, TYPE, NAME, \ M_FIRST, M_NEXT, M_REMOVE_HEAD, M_INSERT_AFTER) \ do { \ struct TYPE *sqms_curelm; \ size_t sqms_i; \ \ /* Find the element before the start of the second sorted region. */ \ while ((sqms_mpos) < (sqms_len1)) { \ (sqms_melm) = M_NEXT((sqms_melm), NAME); \ (sqms_mpos)++; \ } \ \ /* Pull len1 entries off the list and insert in the right place. */ \ for (sqms_i = 0; sqms_i < (sqms_len1); sqms_i++) { \ /* Grab the first element. */ \ sqms_curelm = M_FIRST(&(sqms_sorted)); \ \ /* Advance until we find the right place to insert it. */ \ while (((sqms_mpos) < (sqms_len1) + (sqms_len2)) && \ ((sqms_cmp)(sqms_curelm, M_NEXT((sqms_melm), NAME), \ thunk) >= 0)) { \ (sqms_melm) = M_NEXT((sqms_melm), NAME); \ (sqms_mpos)++; \ } \ \ /* Move the element in the right place if not already there. */ \ if (sqms_curelm != (sqms_melm)) { \ M_REMOVE_HEAD(&(sqms_sorted), NAME); \ M_INSERT_AFTER(&(sqms_sorted), (sqms_melm), \ sqms_curelm, NAME); \ (sqms_melm) = sqms_curelm; \ } \ } \ } while (0) #define SYSQUEUE_MERGESORT(sqms_head, thunk, sqms_cmp, TYPE, NAME, M_HEAD, \ M_HEAD_INITIALIZER, M_EMPTY, M_FIRST, M_NEXT, M_INSERT_HEAD, \ M_INSERT_AFTER, M_CONCAT, M_REMOVE_HEAD) \ do { \ /* \ * Invariant: If sqms_slen = 2^a + 2^b + ... + 2^z with a < b < ... < z \ * then sqms_sorted is a sequence of 2^a sorted entries followed by a \ * list of 2^b sorted entries ... followed by a list of 2^z sorted \ * entries. \ */ \ M_HEAD(, TYPE) sqms_sorted = M_HEAD_INITIALIZER(sqms_sorted); \ struct TYPE *sqms_elm; \ size_t sqms_slen = 0; \ size_t sqms_sortmask; \ size_t sqms_mpos; \ \ /* Move everything from the input list to sqms_sorted. */ \ while (!M_EMPTY(sqms_head)) { \ /* Pull the head off the input list. */ \ sqms_elm = M_FIRST(sqms_head); \ M_REMOVE_HEAD(sqms_head, NAME); \ \ /* Push it onto sqms_sorted. */ \ M_INSERT_HEAD(&sqms_sorted, sqms_elm, NAME); \ sqms_slen++; \ \ /* Restore sorting invariant. */ \ sqms_mpos = 1; \ for (sqms_sortmask = 1; \ sqms_sortmask & ~sqms_slen; \ sqms_sortmask <<= 1) \ SYSQUEUE_MERGE_SUBL(sqms_sorted, sqms_sortmask, \ sqms_sortmask, sqms_elm, sqms_mpos, thunk, sqms_cmp,\ TYPE, NAME, M_FIRST, M_NEXT, M_REMOVE_HEAD, \ M_INSERT_AFTER); \ } \ \ /* Merge the remaining sublists. */ \ sqms_elm = M_FIRST(&sqms_sorted); \ sqms_mpos = 1; \ for (sqms_sortmask = 2; \ sqms_sortmask < sqms_slen; \ sqms_sortmask <<= 1) \ if (sqms_slen & sqms_sortmask) \ SYSQUEUE_MERGE_SUBL(sqms_sorted, \ sqms_slen & (sqms_sortmask - 1), sqms_sortmask, \ sqms_elm, sqms_mpos, thunk, sqms_cmp, \ TYPE, NAME, M_FIRST, M_NEXT, M_REMOVE_HEAD, \ M_INSERT_AFTER); \ \ /* Move the sorted list back to the input list. */ \ M_CONCAT(sqms_head, &sqms_sorted, TYPE, NAME); \ } while (0) /** * Macros for each of the individual data types. They are all invoked as * FOO_MERGESORT(head, thunk, compar, TYPE, NAME) * and * FOO_MERGE(list1, list2, thunk, compar, TYPE, NAME) * where the compar function operates as in qsort_r, i.e. compar(a, b, thunk) * returns an integer less than, equal to, or greater than zero if a is * considered to be respectively less than, equal to, or greater than b. */ #define SLIST_MERGESORT(head, thunk, cmp, TYPE, NAME) \ SYSQUEUE_MERGESORT((head), (thunk), (cmp), TYPE, NAME, SLIST_HEAD, \ SLIST_HEAD_INITIALIZER, SLIST_EMPTY, SLIST_FIRST, SLIST_NEXT, \ SLIST_INSERT_HEAD, SLIST_INSERT_AFTER_4, SLIST_CONCAT, SLIST_REMOVE_HEAD) #define SLIST_MERGE(list1, list2, thunk, cmp, TYPE, NAME) \ SYSQUEUE_MERGE((list1), (list2), (thunk), (cmp), TYPE, NAME, SLIST_FIRST, \ SLIST_INSERT_AFTER_4, SLIST_INSERT_HEAD, SLIST_NEXT, SLIST_REMOVE_HEAD) #define LIST_MERGESORT(head, thunk, cmp, TYPE, NAME) \ SYSQUEUE_MERGESORT((head), (thunk), (cmp), TYPE, NAME, LIST_HEAD, \ LIST_HEAD_INITIALIZER, LIST_EMPTY, LIST_FIRST, LIST_NEXT, \ LIST_INSERT_HEAD, LIST_INSERT_AFTER_4, LIST_CONCAT, LIST_REMOVE_HEAD) #define LIST_MERGE(list1, list2, thunk, cmp, TYPE, NAME) \ SYSQUEUE_MERGE((list1), (list2), (thunk), (cmp), TYPE, NAME, LIST_FIRST, \ LIST_INSERT_AFTER_4, LIST_INSERT_HEAD, LIST_NEXT, LIST_REMOVE_HEAD) #define STAILQ_MERGESORT(head, thunk, cmp, TYPE, NAME) \ SYSQUEUE_MERGESORT((head), (thunk), (cmp), TYPE, NAME, STAILQ_HEAD, \ STAILQ_HEAD_INITIALIZER, STAILQ_EMPTY, STAILQ_FIRST, STAILQ_NEXT, \ STAILQ_INSERT_HEAD, STAILQ_INSERT_AFTER, STAILQ_CONCAT_4, STAILQ_REMOVE_HEAD) #define STAILQ_MERGE(list1, list2, thunk, cmp, TYPE, NAME) \ SYSQUEUE_MERGE((list1), (list2), (thunk), (cmp), TYPE, NAME, STAILQ_FIRST, \ STAILQ_INSERT_AFTER, STAILQ_INSERT_HEAD, STAILQ_NEXT, STAILQ_REMOVE_HEAD) #define TAILQ_MERGESORT(head, thunk, cmp, TYPE, NAME) \ SYSQUEUE_MERGESORT((head), (thunk), (cmp), TYPE, NAME, TAILQ_HEAD, \ TAILQ_HEAD_INITIALIZER, TAILQ_EMPTY, TAILQ_FIRST, TAILQ_NEXT, \ TAILQ_INSERT_HEAD, TAILQ_INSERT_AFTER, TAILQ_CONCAT_4, TAILQ_REMOVE_HEAD) #define TAILQ_MERGE(list1, list2, thunk, cmp, TYPE, NAME) \ SYSQUEUE_MERGE((list1), (list2), (thunk), (cmp), TYPE, NAME, TAILQ_FIRST, \ TAILQ_INSERT_AFTER, TAILQ_INSERT_HEAD, TAILQ_NEXT, TAILQ_REMOVE_HEAD) #endif /* !_SYS_QUEUE_MERGESORT_H_ */