*/
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.Immutable;
+import org.opendaylight.yangtools.concepts.WritableObjects;
/**
* A class holding an equivalent of {@code Set<UnsignedLong>}. It is geared towards efficiently tracking ranges of
*
* @author Robert Varga
*/
-@Beta
-public final class UnsignedLongSet implements Mutable {
- private static final class Entry implements Comparable<Entry>, Mutable {
- // Note: mutable to allow efficient merges.
- long lowerBits;
- long upperBits;
+abstract class UnsignedLongSet {
+ @Beta
+ @VisibleForTesting
+ public static final class Entry implements Comparable<Entry>, Immutable {
+ public final long lowerBits;
+ public 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);
}
- static Entry of(final Range<UnsignedLong> range) {
- verify(range.lowerBoundType() == BoundType.CLOSED && range.upperBoundType() == BoundType.OPEN,
- "Unexpected range %s", range);
- return of(range.lowerEndpoint().longValue(), range.upperEndpoint().longValue() - 1);
+ @NonNull Entry withLower(final long newLowerBits) {
+ return of(newLowerBits, upperBits);
}
- boolean contains(final long longBits) {
- return Long.compareUnsigned(lowerBits, longBits) <= 0 && Long.compareUnsigned(upperBits, longBits) >= 0;
+ @NonNull Entry withUpper(final long newUpperBits) {
+ return of(lowerBits, newUpperBits);
}
- Entry copy() {
- return new Entry(lowerBits, upperBits);
+ // These two methods provide the same serialization format as the one we've used to serialize
+ // Range<UnsignedLong>
+ 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);
}
- // Provides compatibility with RangeSet<UnsignedLong> using [lower, upper + 1)
- Range<UnsignedLong> toUnsigned() {
- return Range.closedOpen(UnsignedLong.fromLongBits(lowerBits), UnsignedLong.fromLongBits(upperBits + 1));
+ void writeUnsigned(final @NonNull DataOutput out) throws IOException {
+ WritableObjects.writeLongs(out, lowerBits, upperBits + 1);
}
@Override
}
}
- // 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<Entry> 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<Entry> ranges;
- private UnsignedLongSet(final TreeSet<Entry> ranges) {
+ UnsignedLongSet(final NavigableSet<Entry> ranges) {
this.ranges = requireNonNull(ranges);
}
- private UnsignedLongSet(final RangeSet<UnsignedLong> 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
+ && Long.compareUnsigned(head.lowerBits, longBits) <= 0
+ && Long.compareUnsigned(head.upperBits, longBits) >= 0;
}
- public static @NonNull UnsignedLongSet of() {
- return new UnsignedLongSet(new TreeSet<>());
+ public final boolean isEmpty() {
+ return ranges.isEmpty();
}
- public static @NonNull UnsignedLongSet of(final RangeSet<UnsignedLong> rangeSet) {
- return new UnsignedLongSet(rangeSet);
+ public final int rangeSize() {
+ 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;
- }
- }
+ public abstract @NonNull ImmutableUnsignedLongSet immutableCopy();
- 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 final @NonNull MutableUnsignedLongSet mutableCopy() {
+ return new MutableUnsignedLongSet(new TreeSet<>(ranges));
}
- public boolean contains(final long longBits) {
- final var headIt = headIter(Entry.of(longBits));
- return headIt.hasNext() && headIt.next().contains(longBits);
+ public final @NonNull NavigableSet<Entry> ranges() {
+ return Collections.unmodifiableNavigableSet(ranges);
}
- public UnsignedLongSet copy() {
- return new UnsignedLongSet(new TreeSet<>(Collections2.transform(ranges, Entry::copy)));
- }
-
- public ImmutableRangeSet<UnsignedLong> toRangeSet() {
- return ImmutableRangeSet.copyOf(Collections2.transform(ranges, Entry::toUnsigned));
+ final @NonNull NavigableSet<Entry> 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();
return helper.add("size", size).toString();
}
-
- private Iterator<Entry> headIter(final Entry range) {
- return ranges.headSet(range, true).descendingIterator();
- }
}
Code Review / controller.git / blobdiff