From nobody Sun Aug 20 05:05:41 2023 X-Original-To: dev-commits-src-main@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 4RT3Td6SDPz4qjWr; Sun, 20 Aug 2023 05:05:41 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "R3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4RT3Td5zQTz4Vny; Sun, 20 Aug 2023 05:05:41 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1692507941; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=PYZlk/jghwd1mWN8JNwzLvPZTR8dcpzE48d1wrEzBSE=; b=GOU8DitKcAXe6jh7ruculQId6tpAoGVAQDu4slpe4ZYsyjAwX0//nIxsYVjU8m2cBesGUl cgFyvK7E+rdOjXKHzTF1WuHMFk61ZesCNyIK3vvKWVGqpzi37rsXupt6kv4fA+IbrMbxNb +nj+a6iawO2dPt/RvLDM9S9El/AFmhPNWl5xSs++IycPcPPuo3vIaJr6NUqW+QqRGGlUh0 0b2YLoDaCKndcCToX880XpquRYXsBJIzK2sDe+oe+lgTsHJRMgejlBE8b66DTRVqu8V/nX sdoPcQ2GSGuoKaJh18T7BVFof22c9ZprBJ30Ek8M7hv7LLKxRAnuHTjAGJKOnw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1692507941; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=PYZlk/jghwd1mWN8JNwzLvPZTR8dcpzE48d1wrEzBSE=; b=APEUFghB2EwjJAF9w64OdAkc+KgM1nGTS9TuKp4+Wg9tok3/4VkwG36RGM2GF5TKjfXIzS np46HD5UHdoWYigv7yH5KKf1S2rJOkzItOt/gADE7s8+aqIKkiQzocfmKA+yybQN9QFtaC P94R1hLIFm0vq5JXnHcSWabVuUlYVQMjW8sKmRlIhw35o4b0sCC2GCGBwlS9ya9Nys0vUM lPbFb8W6xGlckkuOK89GC1jGRTaMQD60ZK1rHCmIsU6nBpu0p6pXvKE/XiUz42jaRz/OUD c3Gbd4bHbv47rU2FXcR0kHVCJaSsmJvKF4XXWhCLNx1m1VZ/7DN8cX8/AQojtA== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1692507941; a=rsa-sha256; cv=none; b=UK5DyfGnyRw0j5tulMdkuJ+2ejsuTP8seCfzMHIv2dqw/e/uvUTl0SUjgHWkZ+cCfzv1Qw dxc8Ughs4uIkrRg3lWpI3staVeAYAoC86D4be/3EYJOAsYJnVRLd5aKKjn6nvNsuGO/DrF cx4fB4qPnKyktl0UMikEaz6GIT/IITgzdlwlb8WCDjVKJqr4yHvAPFuzqQdFGR2GBl6Ffh Xw0SWPTIm3vytCZcol6+0LLiDC0iSQHIK/ZfC3xpeer4EMh20CNcFPZ/niKUmZuTJ9RsCw 1gW3e43osDFyrbbYGYvLtZGogs8dJ7zg2njki1melRsoipsM5l4Rp6jQBUgoOg== ARC-Authentication-Results: i=1; mx1.freebsd.org; none Received: from gitrepo.freebsd.org (gitrepo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:5]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 4RT3Td50gbzBh3; Sun, 20 Aug 2023 05:05:41 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org ([127.0.1.44]) by gitrepo.freebsd.org (8.17.1/8.17.1) with ESMTP id 37K55fju000299; Sun, 20 Aug 2023 05:05:41 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.17.1/8.17.1/Submit) id 37K55fnk000296; Sun, 20 Aug 2023 05:05:41 GMT (envelope-from git) Date: Sun, 20 Aug 2023 05:05:41 GMT Message-Id: <202308200505.37K55fnk000296@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org From: Colin Percival Subject: git: 5f3587169a6d - main - Add List-Id: Commit messages for the main branch of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-main List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-main@freebsd.org X-BeenThere: dev-commits-src-main@freebsd.org MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: cperciva X-Git-Repository: src X-Git-Refname: refs/heads/main X-Git-Reftype: branch X-Git-Commit: 5f3587169a6d17ad1df8c99aea32e8fc27e3195b Auto-Submitted: auto-generated The branch main has been updated by cperciva: URL: https://cgit.FreeBSD.org/src/commit/?id=5f3587169a6d17ad1df8c99aea32e8fc27e3195b commit 5f3587169a6d17ad1df8c99aea32e8fc27e3195b Author: Colin Percival AuthorDate: 2023-07-18 00:07:44 +0000 Commit: Colin Percival CommitDate: 2023-08-20 05:04:55 +0000 Add Thie file provides macros for performing mergesorts and merging two sorted lists implemented by . The mergesort operates in guaranteed O(n log n) time and uses constant additional space: 3 or 4 pointers (depending on list type) and 4 size_t values. The merge operates in guaranteed O(n + m) time and uses constant additional space: 3 pointers. In memoriam: hselasky Reviewed by: jhb (previous version) Sponsored by: https://www.patreon.com/cperciva Differential Revision: https://reviews.freebsd.org/D41073 --- sys/sys/queue_mergesort.h | 217 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 217 insertions(+) diff --git a/sys/sys/queue_mergesort.h b/sys/sys/queue_mergesort.h new file mode 100644 index 000000000000..ea26b9aead46 --- /dev/null +++ b/sys/sys/queue_mergesort.h @@ -0,0 +1,217 @@ +/*- + * 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_ */