[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Qemu-devel] [PATCH v3 29/34] Introduce signed range.
From: |
address@hidden |
Subject: |
[Qemu-devel] [PATCH v3 29/34] Introduce signed range. |
Date: |
Wed, 26 Mar 2014 10:37:02 +0000 |
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
- [Qemu-devel] [PATCH v3 20/34] memory: move RAM_PREALLOC_MASK to exec.c, rename, (continued)
- [Qemu-devel] [PATCH v3 20/34] memory: move RAM_PREALLOC_MASK to exec.c, rename, address@hidden, 2014/03/26
- [Qemu-devel] [PATCH v3 25/34] hostmem: add property to map memory with MAP_SHARED, address@hidden, 2014/03/26
- [Qemu-devel] [PATCH v3 23/34] hostmem: add merge and dump properties, address@hidden, 2014/03/26
- [Qemu-devel] [PATCH v3 34/34] hmp: add info memdev, address@hidden, 2014/03/26
- [Qemu-devel] [PATCH v3 28/34] hw: switch all boards to use memory_region_allocate_system_memory, address@hidden, 2014/03/26
- [Qemu-devel] [PATCH v3 31/34] qapi: make string output visitor parse int list, address@hidden, 2014/03/26
- [Qemu-devel] [PATCH v3 33/34] qmp: add query-memdev, address@hidden, 2014/03/26
- [Qemu-devel] [PATCH v3 06/34] man: improve -numa doc, address@hidden, 2014/03/26
- [Qemu-devel] [PATCH v3 19/34] memory: move preallocation code out of exec.c, address@hidden, 2014/03/26
- [Qemu-devel] [PATCH v3 29/34] Introduce signed range.,
address@hidden <=
- [Qemu-devel] [PATCH v3 13/34] numa: introduce memory_region_allocate_system_memory, address@hidden, 2014/03/26
- [Qemu-devel] [PATCH v3 04/34] NUMA: convert -numa option to use OptsVisitor, address@hidden, 2014/03/26
- [Qemu-devel] [PATCH v3 30/34] qapi: make string input visitor parse int list, address@hidden, 2014/03/26
- [Qemu-devel] [PATCH v3 07/34] qemu-option: introduce qemu_find_opts_singleton, address@hidden, 2014/03/26
- [Qemu-devel] [PATCH v3 17/34] memory: move mem_path handling to memory_region_allocate_system_memory, address@hidden, 2014/03/26