From nobody Wed Nov 27 11:40:54 2024 Delivered-To: importer@patchew.org Authentication-Results: mx.zohomail.com; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=fail(p=none dis=none) header.from=redhat.com Return-Path: Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) by mx.zohomail.com with SMTPS id 1699282081562881.9605489646832; Mon, 6 Nov 2023 06:48:01 -0800 (PST) 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=20Le=20Goater?= To: qemu-devel@nongnu.org Cc: Alex Williamson , Eric Auger , Yanghang Liu , "Michael S. Tsirkin" , =?UTF-8?q?C=C3=A9dric=20Le=20Goater?= 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 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Received-SPF: pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) client-ip=209.51.188.17; envelope-from=qemu-devel-bounces+importer=patchew.org@nongnu.org; helo=lists.gnu.org; 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+importer=patchew.org@nongnu.org Sender: qemu-devel-bounces+importer=patchew.org@nongnu.org X-ZM-MESSAGEID: 1699282082461100003 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=C3=A9dric 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..205e1da76dc5b29327f590b8293= a826ced63c25d 100644 --- a/include/qemu/range.h +++ b/include/qemu/range.h @@ -225,4 +225,12 @@ int range_compare(Range *a, Range *b); =20 GList *range_list_insert(GList *list, Range *data); =20 +/* + * 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..9605ccfcbed9749dc8c2a665a03= 7300c97981d28 100644 --- a/util/range.c +++ b/util/range.c @@ -66,3 +66,58 @@ GList *range_list_insert(GList *list, Range *data) =20 return list; } + +static inline +GList *append_new_range(GList *list, uint64_t lob, uint64_t upb) +{ + Range *new =3D 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 =3D in, *out =3D *rev; + + for (l =3D in; l && range_upb(l->data) < low; l =3D l->next) { + continue; + } + + if (!l) { + out =3D append_new_range(out, low, high); + goto exit; + } + r =3D (Range *)l->data; + + /* first range lob is greater than min, insert a first range */ + if (range_lob(r) > low) { + out =3D 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 =3D l->next) { + r =3D (Range *)l->data; + rn =3D (Range *)l->next->data; + if (range_lob(r) >=3D high) { + goto exit; + } + if (range_compare(r, rn)) { + out =3D append_new_range(out, range_upb(r) + 1, + MIN(range_lob(rn) - 1, high)); + } + } + + /* last range */ + r =3D (Range *)l->data; + + /* last range upb is less than max, insert a last range */ + if (range_upb(r) < high) { + out =3D append_new_range(out, range_upb(r) + 1, high); + } +exit: + *rev =3D out; +} --=20 2.41.0