You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@mesos.apache.org by jo...@apache.org on 2016/07/11 23:38:41 UTC
mesos git commit: Refactor Value::Ranges subtraction.
Repository: mesos
Updated Branches:
refs/heads/master 2ed457a06 -> c51d15850
Refactor Value::Ranges subtraction.
This patch reimplements `Value::Ranges` subtraction using the
`IntervalSet` type. `Ranges` are converted to `IntervalSet` before
subtraction and converted back to `Ranges` after subtraction is done.
This changes the runtime of subtractions from O(nm) to O(m log n),
where `n` and `m` are two `Ranges` being subtracted.
Review: https://reviews.apache.org/r/48593/
Project: http://git-wip-us.apache.org/repos/asf/mesos/repo
Commit: http://git-wip-us.apache.org/repos/asf/mesos/commit/c51d1585
Tree: http://git-wip-us.apache.org/repos/asf/mesos/tree/c51d1585
Diff: http://git-wip-us.apache.org/repos/asf/mesos/diff/c51d1585
Branch: refs/heads/master
Commit: c51d15850b3f80db34f1e7734b3e29ce7ef2672f
Parents: 2ed457a
Author: Yanyan Hu <ya...@cn.ibm.com>
Authored: Mon Jul 11 15:33:42 2016 -0700
Committer: Joseph Wu <jo...@apache.org>
Committed: Mon Jul 11 16:01:56 2016 -0700
----------------------------------------------------------------------
src/common/values.cpp | 69 +++++++++++++++++------------------------
src/tests/values_tests.cpp | 67 +++++++++++++++++++++++++++++++++++++++
2 files changed, 96 insertions(+), 40 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/mesos/blob/c51d1585/src/common/values.cpp
----------------------------------------------------------------------
diff --git a/src/common/values.cpp b/src/common/values.cpp
index 587cb68..7b8a8ea 100644
--- a/src/common/values.cpp
+++ b/src/common/values.cpp
@@ -33,6 +33,7 @@
#include <stout/error.hpp>
#include <stout/foreach.hpp>
+#include <stout/interval.hpp>
#include <stout/strings.hpp>
using std::max;
@@ -266,46 +267,32 @@ void coalesce(Value::Ranges* result, const Value::Range& addedRange)
}
-// Removes a range from already coalesced ranges.
-// The algorithms constructs a new vector of ranges which is then
-// coalesced into a Value::Ranges instance.
-static void remove(Value::Ranges* _ranges, const Value::Range& removal)
+// Convert Ranges value to IntervalSet value.
+IntervalSet<uint64_t> rangesToIntervalSet(const Value::Ranges& ranges)
{
- vector<internal::Range> ranges;
- ranges.reserve(_ranges->range_size());
+ IntervalSet<uint64_t> set;
- foreach (const Value::Range& range, _ranges->range()) {
- // Skip if the entire range is subsumed by `removal`.
- if (range.begin() >= removal.begin() && range.end() <= removal.end()) {
- continue;
- }
+ foreach (const Value::Range& range, ranges.range()) {
+ set += (Bound<uint64_t>::closed(range.begin()),
+ Bound<uint64_t>::closed(range.end()));
+ }
- // Divide if the range subsumes the `removal`.
- if (range.begin() < removal.begin() && range.end() > removal.end()) {
- // Front.
- ranges.emplace_back(internal::Range{range.begin(), removal.begin() - 1});
- // Back.
- ranges.emplace_back(internal::Range{removal.end() + 1, range.end()});
- }
+ return set;
+}
- // Fully Emplace if the range doesn't intersect.
- if (range.end() < removal.begin() || range.begin() > removal.end()) {
- ranges.emplace_back(internal::Range{range.begin(), range.end()});
- } else {
- // Trim if the range does intersect.
- if (range.end() > removal.end()) {
- // Trim front.
- ranges.emplace_back(internal::Range{removal.end() + 1, range.end()});
- } else {
- // Trim back.
- CHECK(range.begin() < removal.begin());
- ranges.emplace_back(
- internal::Range{range.begin(), removal.begin() - 1});
- }
- }
+
+// Convert IntervalSet value to Ranges value.
+Value::Ranges intervalSetToRanges(const IntervalSet<uint64_t>& set)
+{
+ Value::Ranges ranges;
+
+ foreach (const Interval<uint64_t>& interval, set) {
+ Value::Range* range = ranges.add_range();
+ range->set_begin(interval.lower());
+ range->set_end(interval.upper() - 1);
}
- internal::coalesce(_ranges, std::move(ranges));
+ return ranges;
}
@@ -405,13 +392,15 @@ Value::Ranges& operator+=(Value::Ranges& left, const Value::Ranges& right)
}
-Value::Ranges& operator-=(Value::Ranges& left, const Value::Ranges& right)
+Value::Ranges& operator-=(Value::Ranges& _left, const Value::Ranges& _right)
{
- coalesce(&left);
- for (int i = 0; i < right.range_size(); ++i) {
- remove(&left, right.range(i));
- }
- return left;
+ IntervalSet<uint64_t> left, right;
+
+ left = rangesToIntervalSet(_left);
+ right = rangesToIntervalSet(_right);
+ _left = intervalSetToRanges(left - right);
+
+ return _left;
}
http://git-wip-us.apache.org/repos/asf/mesos/blob/c51d1585/src/tests/values_tests.cpp
----------------------------------------------------------------------
diff --git a/src/tests/values_tests.cpp b/src/tests/values_tests.cpp
index 9298615..cc17b67 100644
--- a/src/tests/values_tests.cpp
+++ b/src/tests/values_tests.cpp
@@ -21,6 +21,7 @@
#include <mesos/values.hpp>
#include <stout/gtest.hpp>
+#include <stout/interval.hpp>
#include <stout/try.hpp>
#include "master/master.hpp"
@@ -30,6 +31,9 @@ using namespace mesos::internal::values;
namespace mesos {
extern void coalesce(Value::Ranges* ranges);
extern void coalesce(Value::Ranges* ranges, const Value::Range& range);
+
+ extern IntervalSet<uint64_t> rangesToIntervalSet(const Value::Ranges& ranges);
+ extern Value::Ranges intervalSetToRanges(const IntervalSet<uint64_t>& set);
} // namespace mesos {
namespace mesos {
@@ -309,6 +313,69 @@ TEST(ValuesTest, AddRangeCoalesce)
EXPECT_EQ(21U, ranges.range(1).end());
}
+
+// Test converting Ranges to IntervalSet.
+TEST(ValuesTest, RangesToIntervalSet)
+{
+ Value::Ranges ranges;
+ IntervalSet<uint64_t> set;
+ IntervalSet<uint64_t>::iterator interval;
+
+ // Initialize Ranges value as [1-1, 3-5, 7-8].
+ Value::Range* range = ranges.add_range();
+ range->set_begin(1);
+ range->set_end(1);
+ range = ranges.add_range();
+ range->set_begin(3);
+ range->set_end(5);
+ range = ranges.add_range();
+ range->set_begin(7);
+ range->set_end(8);
+
+ // Convert Ranges value to IntervalSet value.
+ set = mesos::rangesToIntervalSet(ranges);
+
+ // Verify converting result which should be {[1,2), [3-6), [7-9)}.
+ ASSERT_EQ(3U, set.intervalCount());
+ interval = set.begin();
+ EXPECT_EQ(1U, interval->lower());
+ EXPECT_EQ(2U, interval->upper());
+ interval++;
+ EXPECT_EQ(3U, interval->lower());
+ EXPECT_EQ(6U, interval->upper());
+ interval++;
+ EXPECT_EQ(7U, interval->lower());
+ EXPECT_EQ(9U, interval->upper());
+ interval++;
+ EXPECT_EQ(set.end(), interval);
+}
+
+
+// Test converting IntervalSet to Ranges.
+TEST(ValuesTest, IntervalSetToRanges)
+{
+ Value::Ranges ranges;
+ IntervalSet<uint64_t> set;
+
+ // Initialize IntervalSet value as {[1-1], [3-4], [7-9]}.
+ set += (Bound<uint64_t>::closed(1), Bound<uint64_t>::closed(1));
+ set += (Bound<uint64_t>::closed(3), Bound<uint64_t>::closed(4));
+ set += (Bound<uint64_t>::closed(7), Bound<uint64_t>::closed(9));
+
+ // Convert IntervalSet value to Ranges value.
+ ranges = mesos::intervalSetToRanges(set);
+
+ // Verify converting result which should be [1-1, 3-4, 7-9].
+ ASSERT_EQ(3, ranges.range_size());
+ EXPECT_EQ(1U, ranges.range(0).begin());
+ EXPECT_EQ(1U, ranges.range(0).end());
+ EXPECT_EQ(3U, ranges.range(1).begin());
+ EXPECT_EQ(4U, ranges.range(1).end());
+ EXPECT_EQ(7U, ranges.range(2).begin());
+ EXPECT_EQ(9U, ranges.range(2).end());
+}
+
+
// Test adding two ranges.
TEST(ValuesTest, RangesAddition)
{