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%2FUnsignedLongSet.java;h=daf958a987eece6b262bf1d729ac2ce012d31c45;hb=335a172a0ecf6536a63095620e8229a908960b08;hp=ac599a66240a3469323a6df3925ab227b323f9d4;hpb=760350a21a49693c649205b6db88f2fe8c50e288;p=controller.git 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 ac599a6624..daf958a987 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 @@ -7,21 +7,24 @@ */ package org.opendaylight.controller.cluster.datastore.utils; -import static com.google.common.base.Verify.verify; 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.BoundType; import com.google.common.collect.Collections2; -import com.google.common.collect.ImmutableRangeSet; import com.google.common.collect.Range; import com.google.common.collect.RangeSet; import com.google.common.primitives.UnsignedLong; -import java.util.Iterator; +import java.io.DataInput; +import java.io.DataOutput; +import java.io.IOException; +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.WritableObjects; /** * A class holding an equivalent of {@code Set}. It is geared towards efficiently tracking ranges of @@ -33,9 +36,10 @@ import org.opendaylight.yangtools.concepts.Mutable; * * @author Robert Varga */ -@Beta -public final class UnsignedLongSet implements Mutable { - private static final class Entry implements Comparable, Mutable { +abstract class UnsignedLongSet { + @Beta + @VisibleForTesting + public static final class Entry implements Comparable, Mutable { // Note: mutable to allow efficient merges. long lowerBits; long upperBits; @@ -53,10 +57,14 @@ public final class UnsignedLongSet implements Mutable { return new Entry(lowerBits, upperBits); } - static Entry of(final Range range) { - verify(range.lowerBoundType() == BoundType.CLOSED && range.upperBoundType() == BoundType.OPEN, - "Unexpected range %s", range); - return of(range.lowerEndpoint().longValue(), range.upperEndpoint().longValue() - 1); + @VisibleForTesting + public UnsignedLong lower() { + return UnsignedLong.fromLongBits(lowerBits); + } + + @VisibleForTesting + public UnsignedLong upper() { + return UnsignedLong.fromLongBits(upperBits); } boolean contains(final long longBits) { @@ -72,6 +80,24 @@ public final class UnsignedLongSet implements Mutable { return Range.closedOpen(UnsignedLong.fromLongBits(lowerBits), UnsignedLong.fromLongBits(upperBits + 1)); } + // These two methods provide the same serialization format as the one we've used to serialize + // Range + static @NonNull Entry readUnsigned(final DataInput in) throws IOException { + final byte hdr = WritableObjects.readLongHeader(in); + final long first = WritableObjects.readFirstLong(in, hdr); + final long second = WritableObjects.readSecondLong(in, hdr) - 1; + if (Long.compareUnsigned(first, second) > 0) { + throw new IOException("Lower endpoint " + Long.toUnsignedString(first) + " is greater than upper " + + "endpoint " + Long.toUnsignedString(second)); + } + + return new Entry(first, second); + } + + void writeUnsigned(final @NonNull DataOutput out) throws IOException { + WritableObjects.writeLongs(out, lowerBits, upperBits + 1); + } + @Override @SuppressWarnings("checkstyle:parameterName") public int compareTo(final Entry o) { @@ -101,91 +127,55 @@ public final class UnsignedLongSet implements Mutable { } } - // The idea is rather simple, we track a TreeSet of range entries, ordered by their lower bound. This means that - // for a contains() operation we just need the first headSet() entry. For insert operations we just update either - // the lower bound or the upper bound of an existing entry. When we do, we also look at prev/next entry and if they - // are contiguous with the updated entry, we adjust the entry once more and remove the prev/next entry. - private final TreeSet ranges; + // The idea is rather simple, we track a NavigableSet of range entries, ordered by their lower bound. This means + // that for a contains() operation we just need the first headSet() entry. For insert operations we just update + // either the lower bound or the upper bound of an existing entry. When we do, we also look at prev/next entry and + // if they are contiguous with the updated entry, we adjust the entry once more and remove the prev/next entry. + private final @NonNull NavigableSet ranges; - private UnsignedLongSet(final TreeSet ranges) { + UnsignedLongSet(final NavigableSet ranges) { this.ranges = requireNonNull(ranges); } - private UnsignedLongSet(final RangeSet rangeSet) { - ranges = new TreeSet<>(); - for (var range : rangeSet.asRanges()) { - ranges.add(Entry.of(range)); - } + public final boolean contains(final long longBits) { + final var head = ranges.floor(Entry.of(longBits)); + return head != null && head.contains(longBits); } - public static @NonNull UnsignedLongSet of() { - return new UnsignedLongSet(new TreeSet<>()); + public final boolean isEmpty() { + return ranges.isEmpty(); } - public static @NonNull UnsignedLongSet of(final RangeSet rangeSet) { - return new UnsignedLongSet(rangeSet); + public final int size() { + return ranges.size(); } - public void add(final long longBits) { - final var range = Entry.of(longBits); - - final var headIt = headIter(range); - if (headIt.hasNext()) { - final var head = headIt.next(); - if (head.contains(longBits)) { - return; - } - if (head.upperBits + 1 == longBits) { - head.upperBits = longBits; - final var tailSet = ranges.tailSet(range); - if (!tailSet.isEmpty()) { - final var tail = tailSet.first(); - if (tail.lowerBits - 1 == longBits) { - tail.lowerBits = head.lowerBits; - headIt.remove(); - } - } - return; - } - } - - final var tailSet = ranges.tailSet(range); - if (!tailSet.isEmpty()) { - final var tail = tailSet.first(); - if (tail.lowerBits - 1 == longBits) { - tail.lowerBits = longBits; - return; - } - } - - ranges.add(range); - } + public abstract @NonNull ImmutableUnsignedLongSet immutableCopy(); - public boolean contains(final long longBits) { - final var headIt = headIter(Entry.of(longBits)); - return headIt.hasNext() && headIt.next().contains(longBits); + public final @NonNull MutableUnsignedLongSet mutableCopy() { + return new MutableUnsignedLongSet(new TreeSet<>(Collections2.transform(ranges, Entry::copy))); } - public UnsignedLongSet copy() { - return new UnsignedLongSet(new TreeSet<>(Collections2.transform(ranges, Entry::copy))); + public final @NonNull NavigableSet ranges() { + return Collections.unmodifiableNavigableSet(ranges); } - public ImmutableRangeSet toRangeSet() { - return ImmutableRangeSet.copyOf(Collections2.transform(ranges, Entry::toUnsigned)); + final @NonNull NavigableSet trustedRanges() { + return ranges; } @Override - public int hashCode() { + public final int hashCode() { return ranges.hashCode(); } @Override - public boolean equals(final Object obj) { + public final boolean equals(final Object obj) { return obj == this || obj instanceof UnsignedLongSet && ranges.equals(((UnsignedLongSet) obj).ranges); } @Override - public String toString() { + public final String toString() { final var helper = MoreObjects.toStringHelper(this); final int size = ranges.size(); @@ -201,8 +191,4 @@ public final class UnsignedLongSet implements Mutable { return helper.add("size", size).toString(); } - - private Iterator headIter(final Entry range) { - return ranges.headSet(range, true).descendingIterator(); - } }