Make UnsignedLongSet.Entry immutable

Having entries mutable is just a drag when transferring them to
mutable, as we need to perform deep copies. Let's turn them into
immutables and be done with it.

JIRA: CONTROLLER-2015
Change-Id: I3be807cbdf71a51e6b9506e0932857a230924986
Signed-off-by: Robert Varga <robert.varga@pantheon.tech>

diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/ImmutableUnsignedLongSet.java b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/ImmutableUnsignedLongSet.java
index af49065e00e8192693df1036600623ee2573d5c9..47b8a8b01552dc3fee3c7ad34a2fd5783b395e03 100644 (file)
--- a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/ImmutableUnsignedLongSet.java
+++ b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/ImmutableUnsignedLongSet.java
@@ -36,9 +36,9 @@ public final class ImmutableUnsignedLongSet extends UnsignedLongSet implements I
             return of();
         }
         if (mutable.size() <= ARRAY_MAX_ELEMENTS) {
-            return new ImmutableUnsignedLongSet(ImmutableSortedSet.copyOf(mutable.copiedRanges()));
+            return new ImmutableUnsignedLongSet(ImmutableSortedSet.copyOfSorted(mutable.trustedRanges()));
         }
-        return new ImmutableUnsignedLongSet(new TreeSet<>(mutable.copiedRanges()));
+        return new ImmutableUnsignedLongSet(new TreeSet<>(mutable.trustedRanges()));
     }
 
     public static @NonNull ImmutableUnsignedLongSet of() {

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 582193e3c0be91cefd5d658f98c8859742d9f4f9..b42a945519b97204352bb1afbd9c0fc34940c110 100644 (file)
--- 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
@@ -40,22 +40,23 @@ public final class MutableUnsignedLongSet extends UnsignedLongSet implements Mut
     }
 
     public void add(final long longBits) {
-        addOne(trustedRanges(), longBits);
+        addOne(trustedRanges(), Entry.of(longBits));
     }
 
     public void addAll(final UnsignedLongSet other) {
         final var ranges = trustedRanges();
         for (var range : other.trustedRanges()) {
             if (range.lowerBits == range.upperBits) {
-                addOne(ranges, range.lowerBits);
+                addOne(ranges, range);
             } else {
                 addRange(ranges, range);
             }
         }
     }
 
-    private static void addOne(final NavigableSet<Entry> ranges, final long longBits) {
-        final var range = Entry.of(longBits);
+    private static void addOne(final NavigableSet<Entry> ranges, final Entry range) {
+        final long longBits = range.lowerBits;
+
         // We need Iterator.remove() to perform efficient merge below
         final var headIt = ranges.headSet(range, true).descendingIterator();
         if (headIt.hasNext()) {
@@ -67,26 +68,35 @@ public final class MutableUnsignedLongSet extends UnsignedLongSet implements Mut
 
             // Merge into head entry if possible
             if (head.upperBits + 1 == longBits) {
-                head.upperBits = longBits;
+                // We will be replacing head
+                headIt.remove();
 
                 // Potentially merge head entry and tail entry
-                final var tail = ranges.higher(range);
-                if (tail != null) {
+                final var tailIt = ranges.tailSet(range, false).iterator();
+                if (tailIt.hasNext()) {
+                    final var tail = tailIt.next();
                     if (tail.lowerBits - 1 == longBits) {
-                        // Expand tail, remove head
-                        tail.lowerBits = head.lowerBits;
-                        headIt.remove();
+                        // Update tail.lowerBits to include contents of head
+                        tailIt.remove();
+                        ranges.add(tail.withLower(head.lowerBits));
+                        return;
                     }
                 }
+
+                // Update head.upperBits
+                ranges.add(head.withUpper(longBits));
                 return;
             }
         }
 
-        final var tail = ranges.higher(range);
-        if (tail != null) {
+        final var tailIt = ranges.tailSet(range, false).iterator();
+        if (tailIt.hasNext()) {
+            final var tail = tailIt.next();
             // Merge into tail entry if possible
             if (tail.lowerBits - 1 == longBits) {
-                tail.lowerBits = longBits;
+                // Update tail.lowerBits
+                tailIt.remove();
+                ranges.add(tail.withLower(longBits));
                 return;
             }
         }
@@ -97,37 +107,42 @@ public final class MutableUnsignedLongSet extends UnsignedLongSet implements Mut
 
     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;
+        final var headIt = ranges.headSet(range, true).descendingIterator();
+        final boolean hasFloor = headIt.hasNext();
+        if (hasFloor) {
+            final var floor = headIt.next();
+            if (Long.compareUnsigned(floor.upperBits, range.upperBits) < 0
+                && Long.compareUnsigned(floor.upperBits + 1, range.lowerBits) >= 0) {
+                headIt.remove();
+                ranges.add(expandFloor(ranges, floor, 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) {
+        final var tailIt = ranges.headSet(Entry.of(range.upperBits), true).descendingIterator();
+        if (tailIt.hasNext()) {
+            final var upper = tailIt.next();
+            tailIt.remove();
+
             // 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) {
+            if (!hasFloor) {
                 ranges.headSet(upper, false).clear();
             }
 
-            expandUpper(ranges, upper, range.lowerBits, range.upperBits);
+            ranges.add(expandCeiling(ranges, upper, range.lowerBits, range.upperBits));
             return;
         }
 
         // No luck, insert
-        ranges.add(range.copy());
+        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;
-        }
-
+    private static @NonNull Entry expandFloor(final NavigableSet<Entry> ranges, final Entry floor,
+            final long upperBits) {
         // Acquire any ranges after floor and clean them up
-        final var tailIt = ranges.tailSet(entry, false).iterator();
+        final var tailIt = ranges.tailSet(floor, false).iterator();
         final long nextLower = upperBits + 1;
         while (tailIt.hasNext()) {
             final var tail = tailIt.next();
@@ -141,26 +156,24 @@ public final class MutableUnsignedLongSet extends UnsignedLongSet implements Mut
 
             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;
+                return floor.withUpper(tail.upperBits);
             }
         }
 
         // Expand floor to include this range and we are done
-        entry.upperBits = upperBits;
+        return floor.withUpper(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) {
+    private static @NonNull Entry expandCeiling(final NavigableSet<Entry> ranges, final Entry ceiling,
+            final long lowerBits, final long upperBits) {
+        if (Long.compareUnsigned(ceiling.upperBits, upperBits) >= 0) {
             // Upper end is already covered
-            entry.lowerBits = lowerBits;
-            return;
+            return ceiling.withLower(lowerBits);
         }
 
         // 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();
+        final var tailIt = ranges.tailSet(ceiling, false).iterator();
         if (tailIt.hasNext()) {
             final var tail = tailIt.next();
             if (Long.compareUnsigned(tail.lowerBits, newUpper + 1) <= 0) {
@@ -169,8 +182,7 @@ public final class MutableUnsignedLongSet extends UnsignedLongSet implements Mut
             }
         }
 
-        entry.lowerBits = lowerBits;
-        entry.upperBits = newUpper;
+        return Entry.of(lowerBits, newUpper);
     }
 
     public ImmutableRangeSet<UnsignedLong> toRangeSet() {

diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongSet.java b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongSet.java
index e3fa6263e634a99078de115f7ba51314b76ebb60..b9bf8c33f3df8c889c9a3bc293a7179f9e8c0aa2 100644 (file)
--- a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongSet.java
+++ b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongSet.java
@@ -12,19 +12,17 @@ import static java.util.Objects.requireNonNull;
 import com.google.common.annotations.Beta;
 import com.google.common.annotations.VisibleForTesting;
 import com.google.common.base.MoreObjects;
-import com.google.common.collect.Collections2;
 import com.google.common.collect.Range;
 import com.google.common.collect.RangeSet;
 import com.google.common.primitives.UnsignedLong;
 import java.io.DataInput;
 import java.io.DataOutput;
 import java.io.IOException;
-import java.util.Collection;
 import java.util.Collections;
 import java.util.NavigableSet;
 import java.util.TreeSet;
 import org.eclipse.jdt.annotation.NonNull;
-import org.opendaylight.yangtools.concepts.Mutable;
+import org.opendaylight.yangtools.concepts.Immutable;
 import org.opendaylight.yangtools.concepts.WritableObjects;
 
 /**
@@ -40,40 +38,43 @@ import org.opendaylight.yangtools.concepts.WritableObjects;
 abstract class UnsignedLongSet {
     @Beta
     @VisibleForTesting
-    public static final class Entry implements Comparable<Entry>, Mutable {
-        // Note: mutable to allow efficient merges.
-        long lowerBits;
-        long upperBits;
+    public static final class Entry implements Comparable<Entry>, Immutable {
+        final long lowerBits;
+        final long upperBits;
 
         private Entry(final long lowerBits, final long upperBits) {
             this.lowerBits = lowerBits;
             this.upperBits = upperBits;
         }
 
-        static Entry of(final long longBits) {
+        static @NonNull Entry of(final long longBits) {
             return of(longBits, longBits);
         }
 
-        static Entry of(final long lowerBits, final long upperBits) {
+        static @NonNull Entry of(final long lowerBits, final long upperBits) {
             return new Entry(lowerBits, upperBits);
         }
 
         @VisibleForTesting
-        public UnsignedLong lower() {
+        public @NonNull UnsignedLong lower() {
             return UnsignedLong.fromLongBits(lowerBits);
         }
 
         @VisibleForTesting
-        public UnsignedLong upper() {
+        public @NonNull UnsignedLong upper() {
             return UnsignedLong.fromLongBits(upperBits);
         }
 
-        Entry copy() {
-            return new Entry(lowerBits, upperBits);
+        @NonNull Entry withLower(final long newLowerBits) {
+            return of(newLowerBits, upperBits);
+        }
+
+        @NonNull Entry withUpper(final long newUpperBits) {
+            return of(lowerBits, newUpperBits);
         }
 
         // Provides compatibility with RangeSet<UnsignedLong> using [lower, upper + 1)
-        Range<UnsignedLong> toUnsigned() {
+        @NonNull Range<UnsignedLong> toUnsigned() {
             return Range.closedOpen(UnsignedLong.fromLongBits(lowerBits), UnsignedLong.fromLongBits(upperBits + 1));
         }
 
@@ -152,7 +153,7 @@ abstract class UnsignedLongSet {
     public abstract @NonNull ImmutableUnsignedLongSet immutableCopy();
 
     public final @NonNull MutableUnsignedLongSet mutableCopy() {
-        return new MutableUnsignedLongSet(new TreeSet<>(copiedRanges()));
+        return new MutableUnsignedLongSet(new TreeSet<>(ranges));
     }
 
     public final @NonNull NavigableSet<Entry> ranges() {
@@ -163,10 +164,6 @@ abstract class UnsignedLongSet {
         return ranges;
     }
 
-    final @NonNull Collection<Entry> copiedRanges() {
-        return Collections2.transform(ranges, Entry::copy);
-    }
-
     @Override
     public final int hashCode() {
         return ranges.hashCode();