[Qemu-devel] [PATCH v3 29/34] Introduce signed range.

[address@hidden]

Signed-off-by: Hu Tao <address@hidden>
---
 include/qemu/range.h | 119 +++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 119 insertions(+)

diff --git a/include/qemu/range.h b/include/qemu/range.h
index aae9720..d2dd49d 100644
--- a/include/qemu/range.h
+++ b/include/qemu/range.h
@@ -3,6 +3,7 @@
 
 #include <inttypes.h>
 #include <qemu/typedefs.h>
+#include "qemu/queue.h"
 
 /*
  * Operations on 64 bit address ranges.
@@ -60,4 +61,122 @@ static inline int ranges_overlap(uint64_t first1, uint64_t 
len1,
     return !(last2 < first1 || last1 < first2);
 }
 
+typedef struct SignedRangeList SignedRangeList;
+
+typedef struct SignedRange {
+    int64_t start;
+    int64_t length;
+
+    QTAILQ_ENTRY(SignedRange) entry;
+} SignedRange;
+
+QTAILQ_HEAD(SignedRangeList, SignedRange);
+
+static inline SignedRange *s_range_new(int64_t start, int64_t length)
+{
+    SignedRange *range = NULL;
+
+    if (start + length - 1 < start) {
+        /* negative length or overflow */
+        return NULL;
+    }
+
+    range = g_malloc0(sizeof(*range));
+    range->start = start;
+    range->length = length;
+
+    return range;
+}
+
+static inline void s_range_free(SignedRange *range)
+{
+    g_free(range);
+}
+
+static inline bool s_range_overlap(int64_t start1, int64_t length1,
+                                   int64_t start2, int64_t length2)
+{
+    return !((start1 + length1) < start2 || (start2 + length2) < start1);
+}
+
+static inline int64_t s_range_end(int64_t start, int64_t length)
+{
+    return start + length - 1;
+}
+
+static inline bool s_range_overflow(int64_t start, int64_t length)
+{
+    return s_range_end(start, length) < start;
+}
+
+static inline int s_range_join(SignedRange *range,
+                               int64_t start, int64_t length)
+{
+    if (s_range_overflow(start, length)) {
+        return -1;
+    }
+
+    if (s_range_overlap(range->start, range->length, start, length)) {
+        int64_t end = s_range_end(range->start, range->length);
+        if (end < s_range_end(start, length)) {
+            end = s_range_end(start, length);
+        }
+        if (range->start > start) {
+            range->start = start;
+        }
+        range->length = end - range->start + 1;
+        return 0;
+    }
+
+    return -1;
+}
+
+static inline int s_range_compare(int64_t start1, int64_t length1,
+                                  int64_t start2, int64_t length2)
+{
+    if (start1 == start2 && length1 == length2) {
+        return 0;
+    } else if (s_range_end(start1, length1) <
+               s_range_end(start2, length2)) {
+        return -1;
+    } else {
+        return 1;
+    }
+}
+
+/* Add range to list. Keep them sorted, and merge ranges whenever possible */
+static inline void range_list_add(SignedRangeList *list,
+                                  int64_t start, int64_t length)
+{
+    SignedRange *r, *next, *new = NULL;
+    SignedRange *cur = NULL;
+
+    QTAILQ_FOREACH_SAFE(r, list, entry, next) {
+        if (s_range_overlap(r->start, r->length, start, length)) {
+            s_range_join(r, start, length);
+            break;
+        } else if (s_range_compare(start, length, r->start, r->length) < 0) {
+            cur = r;
+            break;
+        }
+    }
+
+    new = s_range_new(start, length);
+    if (!r) {
+        QTAILQ_INSERT_TAIL(list, new, entry);
+    } else if (cur) {
+        QTAILQ_INSERT_BEFORE(cur, new, entry);
+    } else {
+        s_range_free(new);
+        SignedRange *next = QTAILQ_NEXT(r, entry);
+        while (next && s_range_overlap(r->start, r->length,
+                                       next->start, next->length)) {
+            s_range_join(r, next->start, next->length);
+            QTAILQ_REMOVE(list, next, entry);
+            s_range_free(next);
+            next = QTAILQ_NEXT(r, entry);
+        }
+    }
+}
+
 #endif
-- 
1.8.5.2.229.g4448466