@@ -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
@@ -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;
+}
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 <eric.auger@redhat.com> --- v2 -> v3: - now operate on GList's. Fix the commit msg by mentionning low/high params v1 -> v2: - Move range_inverse_array description comment in the header - Take low/high params --- include/qemu/range.h | 8 +++++++ util/range.c | 55 ++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 63 insertions(+)