From patchwork Mon Nov 6 14:36:39 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?q?C=C3=A9dric_Le_Goater?= X-Patchwork-Id: 1860238 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=nongnu.org (client-ip=209.51.188.17; helo=lists.gnu.org; envelope-from=qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org; receiver=patchwork.ozlabs.org) Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) (using TLSv1.2 with cipher ECDHE-ECDSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4SPDjZ1m0tz1yQ9 for ; Tue, 7 Nov 2023 01:48:02 +1100 (AEDT) Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1r00jP-0005En-20; Mon, 06 Nov 2023 09:37:35 -0500 Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1r00jI-0004Sw-Pp for qemu-devel@nongnu.org; Mon, 06 Nov 2023 09:37:28 -0500 Received: from mail.ozlabs.org ([2404:9400:2221:ea00::3] helo=gandalf.ozlabs.org) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1r00jG-0000sE-4w for qemu-devel@nongnu.org; Mon, 06 Nov 2023 09:37:28 -0500 Received: from gandalf.ozlabs.org (mail.ozlabs.org [IPv6:2404:9400:2221:ea00::3]) by gandalf.ozlabs.org (Postfix) with ESMTP id 4SPDTG532bz4xkN; Tue, 7 Nov 2023 01:37:22 +1100 (AEDT) Received: from authenticated.ozlabs.org (localhost [127.0.0.1]) (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) (No client certificate requested) by mail.ozlabs.org (Postfix) with ESMTPSA id 4SPDTD0CQlz4xkL; Tue, 7 Nov 2023 01:37:19 +1100 (AEDT) From: =?utf-8?q?C=C3=A9dric_Le_Goater?= To: qemu-devel@nongnu.org Cc: Alex Williamson , Eric Auger , Yanghang Liu , "Michael S. Tsirkin" , =?utf-8?q?C=C3=A9dric_Le_Goater?= Subject: [PULL 08/22] range: Introduce range_inverse_array() Date: Mon, 6 Nov 2023 15:36:39 +0100 Message-ID: <20231106143653.302391-9-clg@redhat.com> X-Mailer: git-send-email 2.41.0 In-Reply-To: <20231106143653.302391-1-clg@redhat.com> References: <20231106143653.302391-1-clg@redhat.com> MIME-Version: 1.0 Received-SPF: pass client-ip=2404:9400:2221:ea00::3; envelope-from=SRS0=Ju2X=GT=redhat.com=clg@ozlabs.org; helo=gandalf.ozlabs.org X-Spam_score_int: -39 X-Spam_score: -4.0 X-Spam_bar: ---- X-Spam_report: (-4.0 / 5.0 requ) BAYES_00=-1.9, HEADER_FROM_DIFFERENT_DOMAINS=0.25, RCVD_IN_DNSWL_MED=-2.3, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org Sender: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org From: Eric Auger This helper reverses a list of regions within a [low, high] span, turning original regions into holes and original holes into actual regions, covering the whole UINT64_MAX span. Signed-off-by: Eric Auger Tested-by: Yanghang Liu Reviewed-by: "Michael S. Tsirkin" Signed-off-by: Cédric Le Goater --- include/qemu/range.h | 8 +++++++ util/range.c | 55 ++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 63 insertions(+) diff --git a/include/qemu/range.h b/include/qemu/range.h index aa671da143cf82470658311599ac473c837b8102..205e1da76dc5b29327f590b8293a826ced63c25d 100644 --- a/include/qemu/range.h +++ b/include/qemu/range.h @@ -225,4 +225,12 @@ int range_compare(Range *a, Range *b); GList *range_list_insert(GList *list, Range *data); +/* + * Inverse an array of sorted ranges over the [low, high] span, ie. + * original ranges becomes holes in the newly allocated inv_ranges + */ +void range_inverse_array(GList *in_ranges, + GList **out_ranges, + uint64_t low, uint64_t high); + #endif diff --git a/util/range.c b/util/range.c index 782cb8b21c77867864a0da1b31a3638f465d1ae6..9605ccfcbed9749dc8c2a665a037300c97981d28 100644 --- a/util/range.c +++ b/util/range.c @@ -66,3 +66,58 @@ GList *range_list_insert(GList *list, Range *data) return list; } + +static inline +GList *append_new_range(GList *list, uint64_t lob, uint64_t upb) +{ + Range *new = g_new0(Range, 1); + + range_set_bounds(new, lob, upb); + return g_list_append(list, new); +} + + +void range_inverse_array(GList *in, GList **rev, + uint64_t low, uint64_t high) +{ + Range *r, *rn; + GList *l = in, *out = *rev; + + for (l = in; l && range_upb(l->data) < low; l = l->next) { + continue; + } + + if (!l) { + out = append_new_range(out, low, high); + goto exit; + } + r = (Range *)l->data; + + /* first range lob is greater than min, insert a first range */ + if (range_lob(r) > low) { + out = append_new_range(out, low, MIN(range_lob(r) - 1, high)); + } + + /* insert a range inbetween each original range until we reach high */ + for (; l->next; l = l->next) { + r = (Range *)l->data; + rn = (Range *)l->next->data; + if (range_lob(r) >= high) { + goto exit; + } + if (range_compare(r, rn)) { + out = append_new_range(out, range_upb(r) + 1, + MIN(range_lob(rn) - 1, high)); + } + } + + /* last range */ + r = (Range *)l->data; + + /* last range upb is less than max, insert a last range */ + if (range_upb(r) < high) { + out = append_new_range(out, range_upb(r) + 1, high); + } +exit: + *rev = out; +}