From 824dce54df4b23120461e112574d2ff2effafcf6 Mon Sep 17 00:00:00 2001 From: Robert Varga Date: Tue, 9 Nov 2021 11:23:05 +0100 Subject: [PATCH] Add MutableUnsignedLongSet.addAll() 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 --- .../utils/MutableUnsignedLongSet.java | 101 +++++++++++++++++- ...tendShardDataTreeSnapshotMetadataTest.java | 7 +- .../datastore/utils/UnsignedLongSetTest.java | 99 ++++++++++++++--- 3 files changed, 184 insertions(+), 23 deletions(-) diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/MutableUnsignedLongSet.java b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/MutableUnsignedLongSet.java index 689baad40b..2b0dec3d57 100644 --- a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/MutableUnsignedLongSet.java +++ b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/MutableUnsignedLongSet.java @@ -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 java.util.NavigableSet; 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<>()); } + 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) { + addOne(trustedRanges(), Entry.of(longBits), longBits); + } + + public void addAll(final UnsignedLongSet other) { 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 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()) { @@ -73,6 +94,84 @@ public final class MutableUnsignedLongSet extends UnsignedLongSet implements Mut ranges.add(range); } + private static void addRange(final NavigableSet 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 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 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 toRangeSet() { return ImmutableRangeSet.copyOf(Collections2.transform(trustedRanges(), Entry::toUnsigned)); } diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/persisted/FrontendShardDataTreeSnapshotMetadataTest.java b/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/persisted/FrontendShardDataTreeSnapshotMetadataTest.java index 7daafcd786..d1873f0f4b 100644 --- a/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/persisted/FrontendShardDataTreeSnapshotMetadataTest.java +++ b/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/persisted/FrontendShardDataTreeSnapshotMetadataTest.java @@ -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 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))); } diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongSetTest.java b/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongSetTest.java index af71c42631..dbac4cc5fc 100644 --- a/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongSetTest.java +++ b/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongSetTest.java @@ -37,37 +37,46 @@ public class UnsignedLongSetTest { 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)); - assertEquals("MutableUnsignedLongSet{span=[0..1], size=1}", set.toString()); + assertRanges("[[0..1]]", set); set.add(1); - assertEquals("MutableUnsignedLongSet{span=[0..1], size=1}", set.toString()); + assertRanges("[[0..1]]", set); set.add(4); - assertEquals("MutableUnsignedLongSet{span=[0..4], size=2}", set.toString()); + assertRanges("[[0..1], [4..4]]", set); set.add(3); - assertEquals("MutableUnsignedLongSet{span=[0..4], size=2}", set.toString()); + assertRanges("[[0..1], [3..4]]", set); 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)); + + 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 { - 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)) { @@ -88,11 +97,7 @@ public class UnsignedLongSetTest { @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()); } @@ -133,4 +138,64 @@ public class UnsignedLongSetTest { () -> 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()); + } } -- 2.36.6