You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@mesos.apache.org by be...@apache.org on 2012/03/30 03:17:42 UTC
svn commit: r1307202 - in /incubator/mesos/trunk/src: common/resources.hpp
common/type_utils.hpp common/values.cpp tests/resources_tests.cpp
Author: benh
Date: Fri Mar 30 01:17:42 2012
New Revision: 1307202
URL: http://svn.apache.org/viewvc?rev=1307202&view=rev
Log:
Fixes for Ranges arithmetic (contributed by Vinod Kone).
Modified:
incubator/mesos/trunk/src/common/resources.hpp
incubator/mesos/trunk/src/common/type_utils.hpp
incubator/mesos/trunk/src/common/values.cpp
incubator/mesos/trunk/src/tests/resources_tests.cpp
Modified: incubator/mesos/trunk/src/common/resources.hpp
URL: http://svn.apache.org/viewvc/incubator/mesos/trunk/src/common/resources.hpp?rev=1307202&r1=1307201&r2=1307202&view=diff
==============================================================================
--- incubator/mesos/trunk/src/common/resources.hpp (original)
+++ incubator/mesos/trunk/src/common/resources.hpp Fri Mar 30 01:17:42 2012
@@ -212,7 +212,7 @@ public:
foreach (const Resource& resource, resources) {
if (resource.name() == that.name() &&
- resource.type() == that.type()) {
+ resource.type() == that.type()) {
result.resources.Add()->MergeFrom(resource + that);
added = true;
} else {
@@ -233,7 +233,7 @@ public:
foreach (const Resource& resource, resources) {
if (resource.name() == that.name() &&
- resource.type() == that.type()) {
+ resource.type() == that.type()) {
result.resources.Add()->MergeFrom(resource - that);
} else {
result.resources.Add()->MergeFrom(resource);
Modified: incubator/mesos/trunk/src/common/type_utils.hpp
URL: http://svn.apache.org/viewvc/incubator/mesos/trunk/src/common/type_utils.hpp?rev=1307202&r1=1307201&r2=1307202&view=diff
==============================================================================
--- incubator/mesos/trunk/src/common/type_utils.hpp (original)
+++ incubator/mesos/trunk/src/common/type_utils.hpp Fri Mar 30 01:17:42 2012
@@ -83,6 +83,13 @@ inline std::ostream& operator << (std::o
}
+inline std::ostream& operator << (std::ostream& stream, const Value::Ranges& ranges)
+{
+ stream << ranges.DebugString();
+ return stream;
+}
+
+
inline bool operator == (const FrameworkID& left, const FrameworkID& right)
{
return left.value() == right.value();
Modified: incubator/mesos/trunk/src/common/values.cpp
URL: http://svn.apache.org/viewvc/incubator/mesos/trunk/src/common/values.cpp?rev=1307202&r1=1307201&r2=1307202&view=diff
==============================================================================
--- incubator/mesos/trunk/src/common/values.cpp (original)
+++ incubator/mesos/trunk/src/common/values.cpp Fri Mar 30 01:17:42 2012
@@ -172,43 +172,44 @@ Value::Scalar& operator -= (Value::Scala
return left;
}
+namespace ranges {
+
+static void add(Value::Ranges* result, int64_t begin, int64_t end)
+{
+ if (begin > end) {
+ return;
+ }
+ Value::Range* range = result->add_range();
+ range->set_begin(begin);
+ range->set_end(end);
+}
+
+}
static void coalesce(Value::Ranges* ranges, const Value::Range& range)
{
// Note that we assume that ranges has already been coalesced.
- bool coalesced = false;
+ Value::Ranges result;
+ Value::Range temp = range;
for (int i = 0; i < ranges->range_size(); i++) {
- int64_t begin = ranges->range(i).begin();
- int64_t end = ranges->range(i).end();
+ const Value::Range& current = ranges->range(i);
- if (begin <= range.begin() && range.end() <= end) {
- // Ignore range since it is subsumed by a range in ranges.
- coalesced = true;
- break;
- } else if (begin <= range.begin() && end < range.end()) {
- // Grow the end of the range in ranges.
- ranges->mutable_range(i)->set_end(range.end());
- coalesced = true;
- break;
- } else if (range.begin() < begin && range.end() <= end) {
- // Grow the beginning of the range in ranges.
- ranges->mutable_range(i)->set_begin(range.begin());
- coalesced = true;
- break;
- } else if (range.begin() < begin && end < range.end()) {
- // Replace (grow both the beginning and the end) of the range in ranges.
- ranges->mutable_range(i)->set_begin(range.begin());
- ranges->mutable_range(i)->set_end(range.end());
- coalesced = true;
- break;
+ // Check if current and range overlap. Note, we only need to
+ // compare with range and not with temp to check for overlap
+ // because we expect ranges to be coalesced to begin with!
+ if (current.begin() <= range.end() && current.end() >= range.begin() ) {
+ // Update temp with new boundaries.
+ temp.set_begin(std::min(range.begin(), current.begin()));
+ temp.set_end(std::max(range.end(), current.end()));
+ } else { // No overlap.
+ result.add_range()->MergeFrom(current);
}
}
- if (!coalesced) {
- ranges->add_range()->MergeFrom(range);
- }
+ result.add_range()->MergeFrom(temp);
+ *ranges = result;
}
@@ -219,36 +220,44 @@ static void remove(Value::Ranges* ranges
Value::Ranges result;
for (int i = 0; i < ranges->range_size(); i++) {
- int64_t begin = ranges->range(i).begin();
- int64_t end = ranges->range(i).end();
+ const Value::Range& current = ranges->range(i);
- if (begin == range.begin() && range.end() == end) {
- // Remove range from ranges, but keep everything else.
- for (int j = i + 1; j < ranges->range_size(); j++) {
- result.add_range()->MergeFrom(ranges->range(j));
- }
- break;
- } else if (begin <= range.begin() && range.end() < end) {
- // Shrink range in ranges.
- Value::Range* temp = result.add_range();
- temp->set_begin(range.end() + 1);
- temp->set_end(end);
- break;
- } else if (begin < range.begin() && range.end() >= end) {
- // Shrink end of range in ranges.
- Value::Range* temp = result.add_range();
- temp->set_begin(begin);
- temp->set_end(range.begin() - 1);
- break;
- } else if (begin < range.begin() && range.end() < end) {
- // Split range in ranges.
- Value::Range* temp = result.add_range();
- temp->set_begin(begin);
- temp->set_end(range.begin() - 1);
- temp = result.add_range();
- temp->set_begin(range.end() + 1);
- temp->set_end(end);
- break;
+ // Note that these if/else if conditionals are in a particular
+ // order. In particular, the last two assume that the "subsumes"
+ // checks have already occured.
+ if (range.begin() <= current.begin() && range.end() >= current.end()) {
+ // Range subsumes current.
+ // current: | |
+ // range: | |
+ // range: | |
+ // range: | |
+ // range: | |
+ } else if (range.begin() >= current.begin() && range.end() <= current.end()) {
+ // Range is subsumed by current.
+ // current: | |
+ // range: | |
+ // range: | |
+ // range: | |
+ ranges::add(&result, current.begin(), range.begin() - 1);
+ ranges::add(&result, range.end() + 1, current.end());
+ } else if (range.begin() <= current.begin() && range.end() >= current.begin()) {
+ // Range overlaps to the left.
+ // current: | |
+ // range: | |
+ // range: | |
+ ranges::add(&result, range.end() + 1, current.end());
+ } else if (range.begin() <= current.end() && range.end() >= current.end()) {
+ // Range overlaps to the right.
+ // current: | |
+ // range: | |
+ // range: | |
+ ranges::add(&result, current.begin(), range.begin() - 1);
+ } else {
+ // Range doesn't overlap current.
+ // current: | |
+ // range: | |
+ // range: | |
+ ranges::add(&result, current.begin(), current.end());
}
}
Modified: incubator/mesos/trunk/src/tests/resources_tests.cpp
URL: http://svn.apache.org/viewvc/incubator/mesos/trunk/src/tests/resources_tests.cpp?rev=1307202&r1=1307201&r2=1307202&view=diff
==============================================================================
--- incubator/mesos/trunk/src/tests/resources_tests.cpp (original)
+++ incubator/mesos/trunk/src/tests/resources_tests.cpp Fri Mar 30 01:17:42 2012
@@ -264,9 +264,24 @@ TEST(ResourcesTest, RangesAddition)
const Value::Ranges& ranges = r.get("ports", Value::Ranges());
- EXPECT_EQ(1, ranges.range_size());
- EXPECT_EQ(10000, ranges.range(0).begin());
- EXPECT_EQ(50000, ranges.range(0).end());
+ EXPECT_EQ(values::parse("[10000-50000]").get().ranges(), ranges);
+}
+
+
+TEST(ResourcesTest, RangesAddition2)
+{
+ Resource ports1 = Resources::parse("ports", "[1-10, 5-30, 50-60]");
+ Resource ports2 = Resources::parse("ports", "[1-65, 70-80]");
+
+ Resources r;
+ r += ports1;
+ r += ports2;
+
+ EXPECT_EQ(1, r.size());
+
+ const Value::Ranges& ranges = r.get("ports", Value::Ranges());
+
+ EXPECT_EQ(values::parse("[1-65, 70-80]").get().ranges(), ranges);
}
@@ -283,9 +298,7 @@ TEST(ResourcesTest, RangesSubtraction)
const Value::Ranges& ranges = r.get("ports", Value::Ranges());
- EXPECT_EQ(1, ranges.range_size());
- EXPECT_EQ(20001, ranges.range(0).begin());
- EXPECT_EQ(29999, ranges.range(0).end());
+ EXPECT_EQ(values::parse("[20001-29999]").get().ranges(), ranges);
}
@@ -302,9 +315,7 @@ TEST(ResourcesTest, RangesSubtraction1)
const Value::Ranges& ranges = r.get("ports", Value::Ranges());
- EXPECT_EQ(1, ranges.range_size());
- EXPECT_EQ(50002, ranges.range(0).begin());
- EXPECT_EQ(60000, ranges.range(0).end());
+ EXPECT_EQ(values::parse("[50002-60000]").get().ranges(), ranges);
}
@@ -321,9 +332,7 @@ TEST(ResourcesTest, RangesSubtraction2)
const Value::Ranges& ranges = r.get("ports", Value::Ranges());
- EXPECT_EQ(1, ranges.range_size());
- EXPECT_EQ(50001, ranges.range(0).begin());
- EXPECT_EQ(60000, ranges.range(0).end());
+ EXPECT_EQ(values::parse("[50001-60000]").get().ranges(), ranges);
}
@@ -342,9 +351,7 @@ TEST(ResourcesTest, RangesSubtraction3)
const Value::Ranges& ranges = resourcesFree.get("ports", Value::Ranges());
- EXPECT_EQ(1, ranges.range_size());
- EXPECT_EQ(50002, ranges.range(0).begin());
- EXPECT_EQ(60000, ranges.range(0).end());
+ EXPECT_EQ(values::parse("[50002-60000]").get().ranges(), ranges);
}
@@ -366,6 +373,23 @@ TEST(ResourcesTest, RangesSubtraction4)
}
+TEST(ResourcesTest, RangesSubtraction5)
+{
+ Resource ports1 = Resources::parse("ports", "[1-10, 20-30, 40-50]");
+ Resource ports2 = Resources::parse("ports", "[2-9, 15-45, 48-50]");
+
+ Resources r;
+ r += ports1;
+ r -= ports2;
+
+ EXPECT_EQ(1, r.size());
+
+ const Value::Ranges& ranges = r.get("ports", Value::Ranges());
+
+ EXPECT_EQ(values::parse("[1-1, 10-10, 46-47]").get().ranges(), ranges);
+}
+
+
TEST(ResourcesTest, SetEquals)
{
Resource disks = Resources::parse("disks", "{sda1}");