*/
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.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.Collections;
-import java.util.Iterator;
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;
/**
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 {
+ 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);
}
- @VisibleForTesting
- public UnsignedLong lower() {
- return UnsignedLong.fromLongBits(lowerBits);
- }
-
- @VisibleForTesting
- public UnsignedLong upper() {
- return UnsignedLong.fromLongBits(upperBits);
- }
-
- boolean contains(final long longBits) {
- return Long.compareUnsigned(lowerBits, longBits) <= 0 && Long.compareUnsigned(upperBits, longBits) >= 0;
- }
-
- Entry copy() {
- return new Entry(lowerBits, upperBits);
- }
-
- // Provides compatibility with RangeSet<UnsignedLong> using [lower, upper + 1)
- Range<UnsignedLong> toUnsigned() {
- return Range.closedOpen(UnsignedLong.fromLongBits(lowerBits), UnsignedLong.fromLongBits(upperBits + 1));
+ @NonNull Entry withUpper(final long newUpperBits) {
+ return of(lowerBits, newUpperBits);
}
// These two methods provide the same serialization format as the one we've used to serialize
}
}
- // 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 @NonNull 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;
- UnsignedLongSet(final TreeSet<Entry> ranges) {
+ UnsignedLongSet(final NavigableSet<Entry> ranges) {
this.ranges = requireNonNull(ranges);
}
- final void addImpl(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 final boolean contains(final long longBits) {
- final var headIt = headIter(Entry.of(longBits));
- return headIt.hasNext() && headIt.next().contains(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 final boolean isEmpty() {
return ranges.isEmpty();
}
- public final int size() {
+ public final int rangeSize() {
return ranges.size();
}
public abstract @NonNull ImmutableUnsignedLongSet immutableCopy();
public final @NonNull MutableUnsignedLongSet mutableCopy() {
- return new MutableUnsignedLongSet(copyRanges());
- }
-
- final @NonNull TreeSet<Entry> copyRanges() {
- return new TreeSet<>(Collections2.transform(ranges, Entry::copy));
+ return new MutableUnsignedLongSet(new TreeSet<>(ranges));
}
public final @NonNull NavigableSet<Entry> ranges() {
return helper.add("size", size).toString();
}
-
- private Iterator<Entry> headIter(final Entry range) {
- return ranges.headSet(range, true).descendingIterator();
- }
}
Code Review / controller.git / blobdiff