From nobody Thu Nov 28 08:35:23 2024 Delivered-To: importer@patchew.org Authentication-Results: mx.zohomail.com; dkim=pass; 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=pass(p=none dis=none) header.from=redhat.com ARC-Seal: i=1; a=rsa-sha256; t=1693814910; cv=none; d=zohomail.com; s=zohoarc; b=HAg0al9tHxt3CTBfwXYwviX9W7RXl2O+HXFktW6GPAya/o3kXY4o+vEUxWUn7OvTVhJZZlQR8GCzNSsUWBgQ0n4/3xQTLFR20MZgWskS6JK3oU6xtmYpEHOjRmy3CPDGLuR54nr3j4CvPfelNidF4XHGcjhNjRTZbPdyKyPy1fQ= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1693814910; h=Content-Transfer-Encoding:Cc:Date:From:In-Reply-To:List-Subscribe:List-Post:List-Id:List-Archive:List-Help:List-Unsubscribe:MIME-Version:Message-ID:References:Sender:Subject:To; bh=Um6REkjCwNMOmEMDVW18psduw0V2ZAPmFC4IdpStheA=; b=WwjQVmKeAD82/EhYb5MFI5uhXmwAyQDiHeG5R7VHW/7AEulyd28hltwPCTurWRCHgGdnjnFx2ezaeqjBp9nAVBYNkaJs96OieTpjDQle/LTP95FgnnPzxRBtV0N+dYTMgpb/dq0g+7gjwZjqi/R1jn5GUgy8CN7b7llcSonqGg8= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=pass; 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=pass header.from= (p=none dis=none) Return-Path: Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) by mx.zohomail.com with SMTPS id 1693814910522599.9178817268729; Mon, 4 Sep 2023 01:08:30 -0700 (PDT) Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1qd4bc-00018S-Na; Mon, 04 Sep 2023 04:06:44 -0400 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 1qd4bV-00013S-La for qemu-devel@nongnu.org; Mon, 04 Sep 2023 04:06:37 -0400 Received: from us-smtp-delivery-124.mimecast.com ([170.10.133.124]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1qd4bR-0006Js-Bt for qemu-devel@nongnu.org; Mon, 04 Sep 2023 04:06:37 -0400 Received: from mimecast-mx02.redhat.com (mx-ext.redhat.com [66.187.233.73]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-146-RgijNkkRMfySp58HyT5o3Q-1; Mon, 04 Sep 2023 04:05:15 -0400 Received: from smtp.corp.redhat.com (int-mx02.intmail.prod.int.rdu2.redhat.com [10.11.54.2]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx02.redhat.com (Postfix) with ESMTPS id EA5291E441D4; Mon, 4 Sep 2023 08:05:14 +0000 (UTC) Received: from laptop.redhat.com (unknown [10.39.192.53]) by smtp.corp.redhat.com (Postfix) with ESMTP id DEF1940ED412; Mon, 4 Sep 2023 08:05:10 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1693814781; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=Um6REkjCwNMOmEMDVW18psduw0V2ZAPmFC4IdpStheA=; b=Iox/4fZAPpBsJLMT2tvO4yrbqqDJXGY1io0sUDSUEP/4Xn0qdN+faN4idcKNml9DWW1Bzc zKcHW66f7uE7M56dh87Jkvc18RW7IASB7GpZx1MaVaYLuhOj72xswcIBAjegoJHpBYs1E5 BBeaaaLHjommgPV3bIDLaHtYJgKVsPo= X-MC-Unique: RgijNkkRMfySp58HyT5o3Q-1 From: Eric Auger To: eric.auger.pro@gmail.com, eric.auger@redhat.com, qemu-devel@nongnu.org, qemu-arm@nongnu.org, alex.williamson@redhat.com, clg@redhat.com, jean-philippe@linaro.org, mst@redhat.com, pbonzini@redhat.com Cc: peter.maydell@linaro.org, peterx@redhat.com, david@redhat.com, philmd@linaro.org Subject: [PATCH 06/13] range: Introduce range_inverse_array() Date: Mon, 4 Sep 2023 10:03:49 +0200 Message-ID: <20230904080451.424731-7-eric.auger@redhat.com> In-Reply-To: <20230904080451.424731-1-eric.auger@redhat.com> References: <20230904080451.424731-1-eric.auger@redhat.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable X-Scanned-By: MIMEDefang 3.1 on 10.11.54.2 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=170.10.133.124; envelope-from=eric.auger@redhat.com; helo=us-smtp-delivery-124.mimecast.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIMWL_WL_HIGH=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_MSPIKE_H4=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=unavailable 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-ZohoMail-DKIM: pass (identity @redhat.com) X-ZM-MESSAGEID: 1693814912434100005 Content-Type: text/plain; charset="utf-8" This helper reverses an array of regions, turning original regions into holes and original holes into actual regions, covering the whole UINT64_MAX span. Signed-off-by: Eric Auger --- include/qemu/range.h | 3 +++ util/range.c | 35 +++++++++++++++++++++++++++++++++++ 2 files changed, 38 insertions(+) diff --git a/include/qemu/range.h b/include/qemu/range.h index 7e2b1cc447..fc1d3dabe6 100644 --- a/include/qemu/range.h +++ b/include/qemu/range.h @@ -219,4 +219,7 @@ static inline int ranges_overlap(uint64_t first1, uint6= 4_t len1, =20 GList *range_list_insert(GList *list, Range *data); =20 +void range_inverse_array(uint32_t nr_ranges, Range *ranges, + uint32_t *nr_inv_ranges, Range **inv_ranges); + #endif diff --git a/util/range.c b/util/range.c index 098d9d2dc0..11c4ff0b78 100644 --- a/util/range.c +++ b/util/range.c @@ -70,3 +70,38 @@ GList *range_list_insert(GList *list, Range *data) =20 return list; } + +/* + * Inverse an array of sorted ranges over the UINT64_MAX span, ie. + * original ranges becomes holes in the newly allocated inv_ranges + */ +void range_inverse_array(uint32_t nr_ranges, Range *ranges, + uint32_t *nr_inv_ranges, Range **inv_ranges) +{ + Range *resv; + int i =3D 0, j =3D 0; + + resv =3D g_malloc0_n(nr_ranges + 1, sizeof(Range)); + + /* first range lob is greater than 0, insert a first range */ + if (range_lob(&ranges[0]) > 0) { + range_set_bounds(&resv[i++], 0, + range_lob(&ranges[0]) - 1); + } + + /* insert a range inbetween each original range */ + for (; j < nr_ranges - 1; j++) { + if (range_compare(&ranges[j], &ranges[j + 1])) { + range_set_bounds(&resv[i++], range_upb(&ranges[j]) + 1, + range_lob(&ranges[j + 1]) - 1); + } + } + /* last range upb is less than UINT64_MAX, insert a last range */ + if (range_upb(&ranges[nr_ranges - 1]) < UINT64_MAX) { + range_set_bounds(&resv[i++], + range_upb(&ranges[nr_ranges - 1]) + 1, UINT64_MA= X); + } + *nr_inv_ranges =3D i; + resv =3D g_realloc(resv, i * sizeof(Range)); + *inv_ranges =3D resv; +} --=20 2.41.0