From patchwork Mon Aug 12 19:35:12 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ezequiel Garcia X-Patchwork-Id: 11090685 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id BB4EB13AC for ; Mon, 12 Aug 2019 19:35:50 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id AB2F72842E for ; Mon, 12 Aug 2019 19:35:50 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 9F4FC28477; Mon, 12 Aug 2019 19:35:50 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-5.2 required=2.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,MAILING_LIST_MULTI,RCVD_IN_DNSWL_MED,UNPARSEABLE_RELAY autolearn=ham version=3.3.1 Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.wl.linuxfoundation.org (Postfix) with ESMTPS id 1A62F2842E for ; Mon, 12 Aug 2019 19:35:50 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=bombadil.20170209; h=Sender: Content-Transfer-Encoding:Content-Type:Cc:List-Subscribe:List-Help:List-Post: List-Archive:List-Unsubscribe:List-Id:MIME-Version:References:In-Reply-To: Message-Id:Date:Subject:To:From:Reply-To:Content-ID:Content-Description: Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID: List-Owner; bh=c3PXDXg+2cxtOi/IRAk1ljf7wBSyl9/Eshz6LR0rZxE=; b=fFaRTwXlq/d+Xe LuQNcvKvGBhd36Y5PDV946p+nmoUIUjZb1BRNPUUf/VxbxWFQ/Jx/bty69aIugv0C0ajZB/bgZyt0 O1THEYvjdZqBlXGmzD9BqfIEmf8vMTuyTjyUWGCNFTQC3R++JaR5xyj+2iulxB2NuBe0CXGpx1WDz xNil3EQyoUnxoeK8Ycu52EQgyNnDSCQuKaXp+n5cKxXcx8hJLRPW/mauQDRzQXz2PmNucnnjAngHY c0Y23ag+eaL4DSU35Oq5w4qcsYyFot+Md2f1VLtTk2wmj0YCmcP4cBs0pYzQ/0S3w3gUDAdyvgrNK ANbIgwKN8WeKazJ9iQFg==; Received: from localhost ([127.0.0.1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.92 #3 (Red Hat Linux)) id 1hxG6d-0005PE-PO; Mon, 12 Aug 2019 19:35:47 +0000 Received: from bhuna.collabora.co.uk ([2a00:1098:0:82:1000:25:2eeb:e3e3]) by bombadil.infradead.org with esmtps (Exim 4.92 #3 (Red Hat Linux)) id 1hxG6a-0005NC-7c for linux-rockchip@lists.infradead.org; Mon, 12 Aug 2019 19:35:45 +0000 Received: from [127.0.0.1] (localhost [127.0.0.1]) (Authenticated sender: ezequiel) with ESMTPSA id 00945283D3D From: Ezequiel Garcia To: linux-media@vger.kernel.org Subject: [PATCH v5 01/11] lib/sort.c: implement sort() variant taking context argument Date: Mon, 12 Aug 2019 16:35:12 -0300 Message-Id: <20190812193522.10911-2-ezequiel@collabora.com> X-Mailer: git-send-email 2.22.0 In-Reply-To: <20190812193522.10911-1-ezequiel@collabora.com> References: <20190812193522.10911-1-ezequiel@collabora.com> MIME-Version: 1.0 X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20190812_123544_542290_B0AB62D6 X-CRM114-Status: GOOD ( 14.40 ) X-BeenThere: linux-rockchip@lists.infradead.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Upstream kernel work for Rockchip platforms List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: fbuergisser@chromium.org, Nicolas Dufresne , Heiko Stuebner , Alexandre Courbot , Jonas Karlman , Rasmus Villemoes , linux-kernel@vger.kernel.org, Tomasz Figa , Paul Kocialkowski , linux-rockchip@lists.infradead.org, Boris Brezillon , Philipp Zabel , Andrew Morton , kernel@collabora.com Sender: "Linux-rockchip" Errors-To: linux-rockchip-bounces+patchwork-linux-rockchip=patchwork.kernel.org@lists.infradead.org X-Virus-Scanned: ClamAV using ClamSMTP From: Rasmus Villemoes Our list_sort() utility has always supported a context argument that is passed through to the comparison routine. Now there's a use case for the similar thing for sort(). This implements sort_r by simply extending the existing sort function in the obvious way. To avoid code duplication, we want to implement sort() in terms of sort_r(). The naive way to do that is static int cmp_wrapper(const void *a, const void *b, const void *ctx) { int (*real_cmp)(const void*, const void*) = ctx; return real_cmp(a, b); } sort(..., cmp) { sort_r(..., cmp_wrapper, cmp) } but this would do two indirect calls for each comparison. Instead, do as is done for the default swap functions - that only adds a cost of a single easily predicted branch to each comparison call. Aside from introducing support for the context argument, this also serves as preparation for patches that will eliminate the indirect comparison calls in common cases. Requested-by: Boris Brezillon Signed-off-by: Rasmus Villemoes Signed-off-by: Boris Brezillon Acked-by: Andrew Morton Tested-by: Philipp Zabel --- include/linux/sort.h | 5 +++++ lib/sort.c | 34 ++++++++++++++++++++++++++++------ 2 files changed, 33 insertions(+), 6 deletions(-) diff --git a/include/linux/sort.h b/include/linux/sort.h index 2b99a5dd073d..61b96d0ebc44 100644 --- a/include/linux/sort.h +++ b/include/linux/sort.h @@ -4,6 +4,11 @@ #include +void sort_r(void *base, size_t num, size_t size, + int (*cmp)(const void *, const void *, const void *), + void (*swap)(void *, void *, int), + const void *priv); + void sort(void *base, size_t num, size_t size, int (*cmp)(const void *, const void *), void (*swap)(void *, void *, int)); diff --git a/lib/sort.c b/lib/sort.c index cf408aec3733..d54cf97e9548 100644 --- a/lib/sort.c +++ b/lib/sort.c @@ -144,6 +144,18 @@ static void do_swap(void *a, void *b, size_t size, swap_func_t swap_func) swap_func(a, b, (int)size); } +typedef int (*cmp_func_t)(const void *, const void *); +typedef int (*cmp_r_func_t)(const void *, const void *, const void *); +#define _CMP_WRAPPER ((cmp_r_func_t)0L) + +static int do_cmp(const void *a, const void *b, + cmp_r_func_t cmp, const void *priv) +{ + if (cmp == _CMP_WRAPPER) + return ((cmp_func_t)(priv))(a, b); + return cmp(a, b, priv); +} + /** * parent - given the offset of the child, find the offset of the parent. * @i: the offset of the heap element whose parent is sought. Non-zero. @@ -171,12 +183,13 @@ static size_t parent(size_t i, unsigned int lsbit, size_t size) } /** - * sort - sort an array of elements + * sort_r - sort an array of elements * @base: pointer to data to sort * @num: number of elements * @size: size of each element * @cmp_func: pointer to comparison function * @swap_func: pointer to swap function or NULL + * @priv: third argument passed to comparison function * * This function does a heapsort on the given array. You may provide * a swap_func function if you need to do something more than a memory @@ -188,9 +201,10 @@ static size_t parent(size_t i, unsigned int lsbit, size_t size) * O(n*n) worst-case behavior and extra memory requirements that make * it less suitable for kernel use. */ -void sort(void *base, size_t num, size_t size, - int (*cmp_func)(const void *, const void *), - void (*swap_func)(void *, void *, int size)) +void sort_r(void *base, size_t num, size_t size, + int (*cmp_func)(const void *, const void *, const void *), + void (*swap_func)(void *, void *, int size), + const void *priv) { /* pre-scale counters for performance */ size_t n = num * size, a = (num/2) * size; @@ -238,12 +252,12 @@ void sort(void *base, size_t num, size_t size, * average, 3/4 worst-case.) */ for (b = a; c = 2*b + size, (d = c + size) < n;) - b = cmp_func(base + c, base + d) >= 0 ? c : d; + b = do_cmp(base + c, base + d, cmp_func, priv) >= 0 ? c : d; if (d == n) /* Special case last leaf with no sibling */ b = c; /* Now backtrack from "b" to the correct location for "a" */ - while (b != a && cmp_func(base + a, base + b) >= 0) + while (b != a && do_cmp(base + a, base + b, cmp_func, priv) >= 0) b = parent(b, lsbit, size); c = b; /* Where "a" belongs */ while (b != a) { /* Shift it into place */ @@ -252,4 +266,12 @@ void sort(void *base, size_t num, size_t size, } } } +EXPORT_SYMBOL(sort_r); + +void sort(void *base, size_t num, size_t size, + int (*cmp_func)(const void *, const void *), + void (*swap_func)(void *, void *, int size)) +{ + return sort_r(base, num, size, _CMP_WRAPPER, swap_func, cmp_func); +} EXPORT_SYMBOL(sort);