From: Robert Varga Date: Wed, 10 Nov 2021 19:44:05 +0000 (+0100) Subject: Make UnsignedLongSet.Entry immutable X-Git-Tag: v4.0.7~26 X-Git-Url: https://git.opendaylight.org/gerrit/gitweb?p=controller.git;a=commitdiff_plain;h=245165804cb8c11340fa5b225e5cccbe32c01337 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 --- 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 af49065e00..47b8a8b015 100644 --- 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 582193e3c0..b42a945519 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 @@ -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 ranges, final long longBits) { - final var range = Entry.of(longBits); + private static void addOne(final NavigableSet 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 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 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 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 ranges, final Entry entry, final long lowerBits, - final long upperBits) { - if (Long.compareUnsigned(entry.upperBits, upperBits) >= 0) { + private static @NonNull Entry expandCeiling(final NavigableSet 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 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 e3fa6263e6..b9bf8c33f3 100644 --- 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, Mutable { - // Note: mutable to allow efficient merges. - long lowerBits; - long upperBits; + public static final class Entry implements Comparable, 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 using [lower, upper + 1) - Range toUnsigned() { + @NonNull Range 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 ranges() { @@ -163,10 +164,6 @@ abstract class UnsignedLongSet { return ranges; } - final @NonNull Collection copiedRanges() { - return Collections2.transform(ranges, Entry::copy); - } - @Override public final int hashCode() { return ranges.hashCode();