X-Git-Url: https://git.opendaylight.org/gerrit/gitweb?a=blobdiff_plain;f=opendaylight%2Fmd-sal%2Fsal-distributed-datastore%2Fsrc%2Fmain%2Fjava%2Forg%2Fopendaylight%2Fcontroller%2Fcluster%2Fdatastore%2Futils%2FMutableUnsignedLongSet.java;h=d225033ebc9b02119cf6e76912666f7a6e174427;hb=99f80f27bee37bb23e345420bf14bb7bb4793c28;hp=2b0dec3d57194c7a88cc262140ee0c50763426df;hpb=824dce54df4b23120461e112574d2ff2effafcf6;p=controller.git 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 2b0dec3d57..d225033ebc 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 @@ -10,6 +10,7 @@ package org.opendaylight.controller.cluster.datastore.utils; import com.google.common.annotations.Beta; import com.google.common.collect.Collections2; import com.google.common.collect.ImmutableRangeSet; +import com.google.common.collect.Range; import com.google.common.primitives.UnsignedLong; import java.util.NavigableSet; import java.util.TreeSet; @@ -40,21 +41,23 @@ public final class MutableUnsignedLongSet extends UnsignedLongSet implements Mut } public void add(final long longBits) { - addOne(trustedRanges(), Entry.of(longBits), 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, range.lowerBits); + addOne(ranges, range); } else { addRange(ranges, range); } } } - private static void addOne(final NavigableSet ranges, final Entry range, final long 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()) { @@ -66,26 +69,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; } } @@ -96,22 +108,31 @@ 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; } @@ -119,14 +140,10 @@ public final class MutableUnsignedLongSet extends UnsignedLongSet implements Mut 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(); @@ -140,26 +157,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) { @@ -168,11 +183,12 @@ public final class MutableUnsignedLongSet extends UnsignedLongSet implements Mut } } - entry.lowerBits = lowerBits; - entry.upperBits = newUpper; + return Entry.of(lowerBits, newUpper); } + // Provides compatibility with RangeSet using [lower, upper + 1) public ImmutableRangeSet toRangeSet() { - return ImmutableRangeSet.copyOf(Collections2.transform(trustedRanges(), Entry::toUnsigned)); + return ImmutableRangeSet.copyOf(Collections2.transform(trustedRanges(), entry -> Range.closedOpen( + UnsignedLong.fromLongBits(entry.lowerBits), UnsignedLong.fromLongBits(entry.upperBits + 1)))); } }