Repository: cassandra
Updated Branches:
  refs/heads/cassandra-3.0 60a8cfe11 -> c6f822c2a
  refs/heads/cassandra-3.11 2ed7c6a6b -> 78c7d57eb
  refs/heads/trunk 521542ff2 -> 131080371


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.0
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

Reply via email to