You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cassandra.apache.org by if...@apache.org on 2018/11/19 07:59:08 UTC
[2/6] cassandra git commit: Fix full ring range subtraction
Fix full ring range subtraction
Patch by Aleksandr Sorokoumov; reviewed by Alex Petrov for CASSANDRA-14869
Project: http://git-wip-us.apache.org/repos/asf/cassandra/repo
Commit: http://git-wip-us.apache.org/repos/asf/cassandra/commit/c6f822c2
Tree: http://git-wip-us.apache.org/repos/asf/cassandra/tree/c6f822c2
Diff: http://git-wip-us.apache.org/repos/asf/cassandra/diff/c6f822c2
Branch: refs/heads/cassandra-3.11
Commit: c6f822c2a07e0e7c8e4af72523fe62d181c71e56
Parents: 60a8cfe
Author: Aleksandr Sorokoumov <al...@gmail.com>
Authored: Tue Nov 6 21:47:03 2018 +0100
Committer: Alex Petrov <ol...@gmail.com>
Committed: Mon Nov 19 08:51:56 2018 +0100
----------------------------------------------------------------------
src/java/org/apache/cassandra/dht/Range.java | 27 +++++++++++--
.../org/apache/cassandra/dht/RangeTest.java | 40 ++++++++++++++++++++
2 files changed, 63 insertions(+), 4 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/cassandra/blob/c6f822c2/src/java/org/apache/cassandra/dht/Range.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/dht/Range.java b/src/java/org/apache/cassandra/dht/Range.java
index ba6854e..3cf292a 100644
--- a/src/java/org/apache/cassandra/dht/Range.java
+++ b/src/java/org/apache/cassandra/dht/Range.java
@@ -256,6 +256,14 @@ public class Range<T extends RingPosition<T>> extends AbstractBounds<T> implemen
}
/**
+ * Tells if the given range covers the entire ring
+ */
+ private static <T extends RingPosition<T>> boolean isFull(T left, T right)
+ {
+ return left.equals(right);
+ }
+
+ /**
* Note: this class has a natural ordering that is inconsistent with equals
*/
public int compareTo(Range<T> rhs)
@@ -274,13 +282,24 @@ public class Range<T extends RingPosition<T>> extends AbstractBounds<T> implemen
* Subtracts a portion of this range.
* @param contained The range to subtract from this. It must be totally
* contained by this range.
- * @return An ArrayList of the Ranges left after subtracting contained
+ * @return A List of the Ranges left after subtracting contained
* from this.
*/
- private ArrayList<Range<T>> subtractContained(Range<T> contained)
+ private List<Range<T>> subtractContained(Range<T> contained)
{
- ArrayList<Range<T>> difference = new ArrayList<Range<T>>(2);
+ // both ranges cover the entire ring, their difference is an empty set
+ if(isFull(left, right) && isFull(contained.left, contained.right))
+ {
+ return Collections.emptyList();
+ }
+
+ // a range is subtracted from another range that covers the entire ring
+ if(isFull(left, right))
+ {
+ return Collections.singletonList(new Range<>(contained.right, contained.left));
+ }
+ List<Range<T>> difference = new ArrayList<>(2);
if (!left.equals(contained.left))
difference.add(new Range<T>(left, contained.left));
if (!right.equals(contained.right))
@@ -346,7 +365,7 @@ public class Range<T extends RingPosition<T>> extends AbstractBounds<T> implemen
// intersections.length must be 2
Range<T> first = intersections[0];
Range<T> second = intersections[1];
- ArrayList<Range<T>> temp = rhs.subtractContained(first);
+ List<Range<T>> temp = rhs.subtractContained(first);
// Because there are two intersections, subtracting only one of them
// will yield a single Range.
http://git-wip-us.apache.org/repos/asf/cassandra/blob/c6f822c2/test/unit/org/apache/cassandra/dht/RangeTest.java
----------------------------------------------------------------------
diff --git a/test/unit/org/apache/cassandra/dht/RangeTest.java b/test/unit/org/apache/cassandra/dht/RangeTest.java
index 5cd94e2..627253d 100644
--- a/test/unit/org/apache/cassandra/dht/RangeTest.java
+++ b/test/unit/org/apache/cassandra/dht/RangeTest.java
@@ -362,6 +362,8 @@ public class RangeTest
assertRanges(range.subtractAll(collection), 10L, 54L, 60L, 90L);
collection.add(makeRange(80L, 95L));
assertRanges(range.subtractAll(collection), 10L, 54L, 60L, 80L);
+
+ assertEquals(Collections.emptySet(), range.subtractAll(Collections.singleton(range)));
}
@Test
@@ -380,6 +382,44 @@ public class RangeTest
assertRanges(range.subtractAll(collection), 100L, 200L, 500L, 0L);
collection.add(makeRange(1000L, 0));
assertRanges(range.subtractAll(collection), 100L, 200L, 500L, 1000L);
+
+ assertEquals(Collections.emptySet(), range.subtractAll(Collections.singleton(range)));
+ }
+
+ @Test
+ public void testSubtractAllFromFullRingRange()
+ {
+ Range<Token> ring1 = makeRange(50L, 50L);
+ Range<Token> ring2 = makeRange(0L, 0L);
+
+ Set<Range<Token>> contained1 = Collections.singleton(makeRange(10L, 100L));
+ Set<Range<Token>> contained2 = Collections.singleton(makeRange(100L, 10L));
+
+ assertEquals(contained2, ring1.subtractAll(contained1));
+ assertEquals(contained2, ring2.subtractAll(contained1));
+ assertEquals(contained1, ring1.subtractAll(contained2));
+ assertEquals(contained1, ring2.subtractAll(contained2));
+ assertEquals(Collections.emptySet(), ring1.subtractAll(Collections.singleton(ring1)));
+ assertEquals(Collections.emptySet(), ring2.subtractAll(Collections.singleton(ring2)));
+ assertEquals(Collections.emptySet(), ring1.subtractAll(Collections.singleton(ring2)));
+ }
+
+ @Test
+ public void testSubtractFromFullRingRange()
+ {
+ Range<Token> ring1 = makeRange(50L, 50L);
+ Range<Token> ring2 = makeRange(0L, 0L);
+
+ Range<Token> contained1 = makeRange(10L, 100L);
+ Range<Token> contained2 = makeRange(100L, 10L);
+
+ assertEquals(Collections.singleton(contained2), ring1.subtract(contained1));
+ assertEquals(Collections.singleton(contained2), ring2.subtract(contained1));
+ assertEquals(Collections.singleton(contained1), ring1.subtract(contained2));
+ assertEquals(Collections.singleton(contained1), ring2.subtract(contained2));
+ assertEquals(Collections.emptySet(), ring1.subtract(ring1));
+ assertEquals(Collections.emptySet(), ring2.subtract(ring2));
+ assertEquals(Collections.emptySet(), ring1.subtract(ring2));
}
private Range<Token> makeRange(String token1, String token2)
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@cassandra.apache.org
For additional commands, e-mail: commits-help@cassandra.apache.org