[PATCH v2 06/12] range: Introduce range_inverse_array()

[Eric Auger <eric.auger@redhat.com>]

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 <eric.auger@redhat.com>

---

v1 -> v2:
- Move range_inverse_array description comment in the header
- Take low/high params
---
 include/qemu/range.h |  8 ++++++++
 util/range.c         | 45 ++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 53 insertions(+)

diff --git a/include/qemu/range.h b/include/qemu/range.h
index 7e2b1cc447..2b59e3bf0c 100644
--- a/include/qemu/range.h
+++ b/include/qemu/range.h
@@ -219,4 +219,12 @@ static inline int ranges_overlap(uint64_t first1, uint64_t len1,
 
 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(uint32_t nr_ranges, Range *ranges,
+                         uint32_t *nr_inv_ranges, Range **inv_ranges,
+                         uint64_t low, uint64_t high);
+
 #endif
diff --git a/util/range.c b/util/range.c
index 098d9d2dc0..4baeb588cc 100644
--- a/util/range.c
+++ b/util/range.c
@@ -70,3 +70,48 @@ GList *range_list_insert(GList *list, Range *data)
 
     return list;
 }
+
+void range_inverse_array(uint32_t nr_ranges, Range *ranges,
+                         uint32_t *nr_inv_ranges, Range **inv_ranges,
+                         uint64_t low, uint64_t high)
+{
+    Range *resv;
+    int i = 0, j = 0;
+
+    resv = g_malloc0_n(nr_ranges + 1, sizeof(Range));
+
+    for (; j < nr_ranges  && (range_upb(&ranges[j]) < low); j++) {
+        continue; /* skip all ranges below mon */
+    }
+
+    if (j == nr_ranges) {
+        range_set_bounds(&resv[i++], low, high);
+        goto realloc;
+    }
+
+    /* first range lob is greater than min, insert a first range */
+    if (range_lob(&ranges[j]) > low) {
+        range_set_bounds(&resv[i++], low,
+                         MIN(range_lob(&ranges[j]) - 1, high));
+    }
+
+    /* insert a range inbetween each original range until we reach max */
+    for (; j < nr_ranges - 1; j++) {
+        if (range_lob(&ranges[j]) >= high) {
+            goto realloc;
+        }
+        if (range_compare(&ranges[j], &ranges[j + 1])) {
+            range_set_bounds(&resv[i++], range_upb(&ranges[j]) + 1,
+                             MIN(range_lob(&ranges[j + 1]) - 1, high));
+        }
+    }
+    /* last range upb is less than max, insert a last range */
+    if (range_upb(&ranges[j]) <  high) {
+        range_set_bounds(&resv[i++],
+                          range_upb(&ranges[j]) + 1, high);
+    }
+realloc:
+    *nr_inv_ranges = i;
+    resv = g_realloc(resv, i * sizeof(Range));
+    *inv_ranges = resv;
+}
-- 
2.41.0