From patchwork Wed Mar 26 10:37:02 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Hu Tao X-Patchwork-Id: 333825 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from lists.gnu.org (lists.gnu.org [IPv6:2001:4830:134:3::11]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id B4E2914008E for ; Wed, 26 Mar 2014 22:32:24 +1100 (EST) Received: from localhost ([::1]:47099 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WSm4E-0004hn-9P for incoming@patchwork.ozlabs.org; Wed, 26 Mar 2014 07:32:22 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:38070) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WSljU-0002U1-0g for qemu-devel@nongnu.org; Wed, 26 Mar 2014 07:11:00 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WSljP-0003DV-EJ for qemu-devel@nongnu.org; Wed, 26 Mar 2014 07:10:55 -0400 Received: from [59.151.112.132] (port=53275 helo=heian.cn.fujitsu.com) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WSljO-0003CR-9P for qemu-devel@nongnu.org; Wed, 26 Mar 2014 07:10:51 -0400 X-IronPort-AV: E=Sophos;i="4.97,734,1389715200"; d="scan'208";a="28487341" Received: from unknown (HELO edo.cn.fujitsu.com) ([10.167.33.5]) by heian.cn.fujitsu.com with ESMTP; 26 Mar 2014 18:34:35 +0800 Received: from G08CNEXCHPEKD03.g08.fujitsu.local (localhost.localdomain [127.0.0.1]) by edo.cn.fujitsu.com (8.14.3/8.13.1) with ESMTP id s2QAapvN003095; Wed, 26 Mar 2014 18:36:56 +0800 Received: from G08CNEXMBPEKD03.g08.fujitsu.local ([10.167.33.86]) by G08CNEXCHPEKD03.g08.fujitsu.local ([10.167.33.85]) with mapi id 14.03.0146.002; Wed, 26 Mar 2014 18:37:02 +0800 From: "hutao@cn.fujitsu.com" To: "qemu-devel@nongnu.org" Thread-Topic: [PATCH v3 29/34] Introduce signed range. Thread-Index: AQHPSN9Vjh1023TnXEWOW+1RhtD22g== Date: Wed, 26 Mar 2014 10:37:02 +0000 Message-ID: References: In-Reply-To: Accept-Language: zh-CN, en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [10.167.226.102] MIME-Version: 1.0 X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 59.151.112.132 Cc: "ehabkost@redhat.com" , "imammedo@redhat.com" , "mtosatti@redhat.com" , Paolo Bonzini , "a.motakis@virtualopensystems.com" , "gaowanlong@cn.fujitsu.com" Subject: [Qemu-devel] [PATCH v3 29/34] Introduce signed range. X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org Sender: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org Signed-off-by: Hu Tao --- 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 #include +#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