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 <aleksandr.sorokou...@gmail.com> Authored: Tue Nov 6 21:47:03 2018 +0100 Committer: Alex Petrov <oleksandr.pet...@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-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
