Add MutableUnsignedLongSet.addAll() 72/98372/1
authorRobert Varga <robert.varga@pantheon.tech>
Tue, 9 Nov 2021 10:23:05 +0000 (11:23 +0100)
committerRobert Varga <robert.varga@pantheon.tech>
Tue, 9 Nov 2021 10:29:13 +0000 (11:29 +0100)
Add the ability to merge two UnsignedLongSets. This is useful when
we are using ImmutableUnsignedLongSet as a data interchange format
to communicate changes to a MutableUnsignedLongSet.

JIRA: CONTROLLER-2015
Change-Id: Ia84474b685872586722914f20db8f96a3c172f97
Signed-off-by: Robert Varga <robert.varga@pantheon.tech>
opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/MutableUnsignedLongSet.java
opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/persisted/FrontendShardDataTreeSnapshotMetadataTest.java
opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongSetTest.java

index 689baad..2b0dec3 100644 (file)
@@ -11,6 +11,7 @@ import com.google.common.annotations.Beta;
 import com.google.common.collect.Collections2;
 import com.google.common.collect.ImmutableRangeSet;
 import com.google.common.primitives.UnsignedLong;
 import com.google.common.collect.Collections2;
 import com.google.common.collect.ImmutableRangeSet;
 import com.google.common.primitives.UnsignedLong;
+import java.util.NavigableSet;
 import java.util.TreeSet;
 import org.eclipse.jdt.annotation.NonNull;
 import org.opendaylight.yangtools.concepts.Mutable;
 import java.util.TreeSet;
 import org.eclipse.jdt.annotation.NonNull;
 import org.opendaylight.yangtools.concepts.Mutable;
@@ -25,15 +26,35 @@ public final class MutableUnsignedLongSet extends UnsignedLongSet implements Mut
         return new MutableUnsignedLongSet(new TreeSet<>());
     }
 
         return new MutableUnsignedLongSet(new TreeSet<>());
     }
 
+    public static @NonNull MutableUnsignedLongSet of(final long... ulongs) {
+        final var ret = MutableUnsignedLongSet.of();
+        for (long longBits : ulongs) {
+            ret.add(longBits);
+        }
+        return ret;
+    }
+
     @Override
     public ImmutableUnsignedLongSet immutableCopy() {
         return ImmutableUnsignedLongSet.copyOf(this);
     }
 
     public void add(final long longBits) {
     @Override
     public ImmutableUnsignedLongSet immutableCopy() {
         return ImmutableUnsignedLongSet.copyOf(this);
     }
 
     public void add(final long longBits) {
+        addOne(trustedRanges(), Entry.of(longBits), longBits);
+    }
+
+    public void addAll(final UnsignedLongSet other) {
         final var ranges = trustedRanges();
         final var ranges = trustedRanges();
-        final var range = Entry.of(longBits);
+        for (var range : other.trustedRanges()) {
+            if (range.lowerBits == range.upperBits) {
+                addOne(ranges, range, range.lowerBits);
+            } else {
+                addRange(ranges, range);
+            }
+        }
+    }
 
 
+    private static void addOne(final NavigableSet<Entry> ranges, final Entry range, final long longBits) {
         // We need Iterator.remove() to perform efficient merge below
         final var headIt = ranges.headSet(range, true).descendingIterator();
         if (headIt.hasNext()) {
         // We need Iterator.remove() to perform efficient merge below
         final var headIt = ranges.headSet(range, true).descendingIterator();
         if (headIt.hasNext()) {
@@ -73,6 +94,84 @@ public final class MutableUnsignedLongSet extends UnsignedLongSet implements Mut
         ranges.add(range);
     }
 
         ranges.add(range);
     }
 
+    private static void addRange(final NavigableSet<Entry> ranges, final Entry range) {
+        // If the start of the range is already covered by an existing range, we can expand that
+        final var lower = ranges.floor(range);
+        if (lower != null && Long.compareUnsigned(lower.upperBits + 1, range.lowerBits) >= 0) {
+            expandLower(ranges, lower, range.upperBits);
+            return;
+        }
+
+        // If the end of the range is already covered by an existing range, we can expand that
+        final var upper = ranges.floor(Entry.of(range.upperBits));
+        if (upper != null && Long.compareUnsigned(upper.lowerBits - 1, range.upperBits) <= 0) {
+            // Quick check: if we did not find a lower range at all, we might be expanding the entire span, in which
+            // case upper needs to become the first entry
+            if (lower == null) {
+                ranges.headSet(upper, false).clear();
+            }
+
+            expandUpper(ranges, upper, range.lowerBits, range.upperBits);
+            return;
+        }
+
+        // No luck, insert
+        ranges.add(range);
+    }
+
+    private static void expandLower(final NavigableSet<Entry> ranges, final Entry entry, final long upperBits) {
+        if (Long.compareUnsigned(entry.upperBits, upperBits) >= 0) {
+            // Already contained, this is a no-op
+            return;
+        }
+
+        // Acquire any ranges after floor and clean them up
+        final var tailIt = ranges.tailSet(entry, false).iterator();
+        final long nextLower = upperBits + 1;
+        while (tailIt.hasNext()) {
+            final var tail = tailIt.next();
+            if (Long.compareUnsigned(tail.lowerBits, nextLower) > 0) {
+                // There is gap, nothing more to cleanup
+                break;
+            }
+
+            // We can merge this entry into floor...
+            tailIt.remove();
+
+            if (Long.compareUnsigned(tail.upperBits, nextLower) >= 0) {
+                // ... but we need to expand floor accordingly and after that we are done
+                entry.upperBits = tail.upperBits;
+                return;
+            }
+        }
+
+        // Expand floor to include this range and we are done
+        entry.upperBits = upperBits;
+    }
+
+    private static void expandUpper(final NavigableSet<Entry> ranges, final Entry entry, final long lowerBits,
+            final long upperBits) {
+        if (Long.compareUnsigned(entry.upperBits, upperBits) >= 0) {
+            // Upper end is already covered
+            entry.lowerBits = lowerBits;
+            return;
+        }
+
+        // We are expanding the entry's upper boundary, we need to check if we need to coalesce following entries
+        long newUpper = upperBits;
+        final var tailIt = ranges.tailSet(entry, false).iterator();
+        if (tailIt.hasNext()) {
+            final var tail = tailIt.next();
+            if (Long.compareUnsigned(tail.lowerBits, newUpper + 1) <= 0) {
+                tailIt.remove();
+                newUpper = tail.upperBits;
+            }
+        }
+
+        entry.lowerBits = lowerBits;
+        entry.upperBits = newUpper;
+    }
+
     public ImmutableRangeSet<UnsignedLong> toRangeSet() {
         return ImmutableRangeSet.copyOf(Collections2.transform(trustedRanges(), Entry::toUnsigned));
     }
     public ImmutableRangeSet<UnsignedLong> toRangeSet() {
         return ImmutableRangeSet.copyOf(Collections2.transform(trustedRanges(), Entry::toUnsigned));
     }
index 7daafcd..d1873f0 100644 (file)
@@ -102,12 +102,9 @@ public class FrontendShardDataTreeSnapshotMetadataTest {
         final FrontendIdentifier frontendIdentifier = FrontendIdentifier.create(MemberName.forName(indexName),
                 FrontendType.forName(index));
         final ClientIdentifier clientIdentifier = ClientIdentifier.create(frontendIdentifier, num);
         final FrontendIdentifier frontendIdentifier = FrontendIdentifier.create(MemberName.forName(indexName),
                 FrontendType.forName(index));
         final ClientIdentifier clientIdentifier = ClientIdentifier.create(frontendIdentifier, num);
+        final ImmutableUnsignedLongSet purgedHistories = MutableUnsignedLongSet.of(0).immutableCopy();
 
 
-        final MutableUnsignedLongSet tmp = MutableUnsignedLongSet.of();
-        tmp.add(0);
-        final ImmutableUnsignedLongSet purgedHistories = tmp.immutableCopy();
-
-        return new FrontendClientMetadata(clientIdentifier, purgedHistories.immutableCopy(), List.of(
+        return new FrontendClientMetadata(clientIdentifier, purgedHistories, List.of(
             new FrontendHistoryMetadata(num, num, true,
                 UnsignedLongBitmap.copyOf(Map.of(UnsignedLong.ZERO, Boolean.TRUE)), purgedHistories)));
     }
             new FrontendHistoryMetadata(num, num, true,
                 UnsignedLongBitmap.copyOf(Map.of(UnsignedLong.ZERO, Boolean.TRUE)), purgedHistories)));
     }
index af71c42..dbac4cc 100644 (file)
@@ -37,37 +37,46 @@ public class UnsignedLongSetTest {
 
         set.add(0);
         assertTrue(set.contains(0));
 
         set.add(0);
         assertTrue(set.contains(0));
-        assertEquals("MutableUnsignedLongSet{span=[0..0], size=1}", set.toString());
+        assertRanges("[[0..0]]", set);
 
         set.add(1);
         assertTrue(set.contains(1));
 
         set.add(1);
         assertTrue(set.contains(1));
-        assertEquals("MutableUnsignedLongSet{span=[0..1], size=1}", set.toString());
+        assertRanges("[[0..1]]", set);
         set.add(1);
         set.add(1);
-        assertEquals("MutableUnsignedLongSet{span=[0..1], size=1}", set.toString());
+        assertRanges("[[0..1]]", set);
 
         set.add(4);
 
         set.add(4);
-        assertEquals("MutableUnsignedLongSet{span=[0..4], size=2}", set.toString());
+        assertRanges("[[0..1], [4..4]]", set);
 
         set.add(3);
 
         set.add(3);
-        assertEquals("MutableUnsignedLongSet{span=[0..4], size=2}", set.toString());
+        assertRanges("[[0..1], [3..4]]", set);
 
         set.add(2);
 
         set.add(2);
-        assertEquals("MutableUnsignedLongSet{span=[0..4], size=1}", set.toString());
+        assertRanges("[[0..4]]", set);
 
         assertTrue(set.contains(2));
         assertTrue(set.contains(3));
         assertTrue(set.contains(4));
 
         assertTrue(set.contains(2));
         assertTrue(set.contains(3));
         assertTrue(set.contains(4));
+
+        set.add(8);
+        assertRanges("[[0..4], [8..8]]", set);
+        set.add(6);
+        assertRanges("[[0..4], [6..6], [8..8]]", set);
+        set.add(7);
+        assertRanges("[[0..4], [6..8]]", set);
+        set.add(5);
+        assertRanges("[[0..8]]", set);
+
+        set.add(11);
+        assertRanges("[[0..8], [11..11]]", set);
+        set.add(9);
+        assertRanges("[[0..9], [11..11]]", set);
     }
 
     @Test
     public void testSerialization() throws IOException {
     }
 
     @Test
     public void testSerialization() throws IOException {
-        final var tmp = MutableUnsignedLongSet.of();
-        tmp.add(0);
-        tmp.add(1);
-        tmp.add(4);
-        tmp.add(3);
 
 
-        final var set = tmp.immutableCopy();
+        final var set = MutableUnsignedLongSet.of(0, 1, 4, 3).immutableCopy();
 
         final var bos = new ByteArrayOutputStream();
         try (var out = new DataOutputStream(bos)) {
 
         final var bos = new ByteArrayOutputStream();
         try (var out = new DataOutputStream(bos)) {
@@ -88,11 +97,7 @@ public class UnsignedLongSetTest {
 
     @Test
     public void testToRangeSet() {
 
     @Test
     public void testToRangeSet() {
-        final var set = MutableUnsignedLongSet.of();
-        set.add(0);
-        set.add(1);
-        set.add(4);
-        set.add(3);
+        final var set = MutableUnsignedLongSet.of(0, 1, 4, 3);
         assertEquals("[[0..2), [3..5)]", set.toRangeSet().toString());
     }
 
         assertEquals("[[0..2), [3..5)]", set.toRangeSet().toString());
     }
 
@@ -133,4 +138,64 @@ public class UnsignedLongSetTest {
             () -> ImmutableUnsignedLongSet.of().writeRangesTo(mock(DataOutput.class), 1));
         assertEquals("Mismatched size: expected 0, got 1", ex.getMessage());
     }
             () -> ImmutableUnsignedLongSet.of().writeRangesTo(mock(DataOutput.class), 1));
         assertEquals("Mismatched size: expected 0, got 1", ex.getMessage());
     }
+
+    @Test
+    public void testAddRange() {
+        var set = sparseSet();
+        set.addAll(MutableUnsignedLongSet.of(1, 2));
+        assertRanges("[[1..2], [5..6], [9..10], [13..14]]", set);
+        set.addAll(MutableUnsignedLongSet.of(3, 4));
+        assertRanges("[[1..6], [9..10], [13..14]]", set);
+        set.addAll(MutableUnsignedLongSet.of(4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15));
+        assertRanges("[[1..15]]", set);
+
+        set = sparseSet();
+        set.addAll(MutableUnsignedLongSet.of(2, 3, 4, 5));
+        assertRanges("[[1..6], [9..10], [13..14]]", set);
+
+        set.addAll(MutableUnsignedLongSet.of(6, 7));
+        assertRanges("[[1..7], [9..10], [13..14]]", set);
+
+        set.addAll(MutableUnsignedLongSet.of(8));
+        assertRanges("[[1..10], [13..14]]", set);
+
+        set = MutableUnsignedLongSet.of();
+        set.addAll(MutableUnsignedLongSet.of(1, 2));
+        assertRanges("[[1..2]]", set);
+
+        set = sparseSet();
+        set.addAll(MutableUnsignedLongSet.of(4, 5));
+        assertRanges("[[1..2], [4..6], [9..10], [13..14]]", set);
+
+        set.addAll(MutableUnsignedLongSet.of(12, 13, 14, 15));
+        assertRanges("[[1..2], [4..6], [9..10], [12..15]]", set);
+
+        set.addAll(MutableUnsignedLongSet.of(8, 9, 10, 11));
+        assertRanges("[[1..2], [4..6], [8..15]]", set);
+
+        set.addAll(MutableUnsignedLongSet.of(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16));
+        assertRanges("[[0..16]]", set);
+
+        set = sparseSet();
+        set.addAll(MutableUnsignedLongSet.of(0, 1, 2, 3));
+        assertRanges("[[0..3], [5..6], [9..10], [13..14]]", set);
+
+        set = sparseSet();
+        set.addAll(MutableUnsignedLongSet.of(0, 1, 2, 3, 4, 5, 6, 7, 8));
+        assertRanges("[[0..10], [13..14]]", set);
+
+        set = sparseSet();
+        set.addAll(MutableUnsignedLongSet.of(0, 1, 2, 3, 4, 5, 6, 7, 8, 9));
+        assertRanges("[[0..10], [13..14]]", set);
+    }
+
+    private static MutableUnsignedLongSet sparseSet() {
+        final var ret = MutableUnsignedLongSet.of(1, 2, 5, 6, 9, 10, 13, 14);
+        assertRanges("[[1..2], [5..6], [9..10], [13..14]]", ret);
+        return ret;
+    }
+
+    private static void assertRanges(final String expected, final UnsignedLongSet set) {
+        assertEquals(expected, set.ranges().toString());
+    }
 }
 }