import com.google.common.base.MoreObjects;
import com.google.common.collect.ImmutableMap;
-import com.google.common.collect.Range;
-import com.google.common.collect.RangeSet;
import com.google.common.primitives.UnsignedLong;
import java.util.HashMap;
import java.util.Map;
import org.opendaylight.controller.cluster.access.concepts.RequestEnvelope;
import org.opendaylight.controller.cluster.access.concepts.RequestException;
import org.opendaylight.controller.cluster.access.concepts.TransactionIdentifier;
+import org.opendaylight.controller.cluster.datastore.utils.UnsignedLongSet;
import org.opendaylight.yangtools.concepts.Identifiable;
import org.opendaylight.yangtools.yang.data.api.schema.tree.DataTreeModification;
import org.slf4j.Logger;
private static final Logger LOG = LoggerFactory.getLogger(AbstractFrontendHistory.class);
private final Map<TransactionIdentifier, FrontendTransaction> transactions = new HashMap<>();
- private final RangeSet<UnsignedLong> purgedTransactions;
+ private final UnsignedLongSet purgedTransactions;
private final String persistenceId;
private final ShardDataTree tree;
private Map<UnsignedLong, Boolean> closedTransactions;
AbstractFrontendHistory(final String persistenceId, final ShardDataTree tree,
- final Map<UnsignedLong, Boolean> closedTransactions, final RangeSet<UnsignedLong> purgedTransactions) {
+ final Map<UnsignedLong, Boolean> closedTransactions, final UnsignedLongSet purgedTransactions) {
this.persistenceId = requireNonNull(persistenceId);
this.tree = requireNonNull(tree);
this.closedTransactions = requireNonNull(closedTransactions);
}
final TransactionIdentifier id = request.getTarget();
- final UnsignedLong ul = UnsignedLong.fromLongBits(id.getTransactionId());
- if (purgedTransactions.contains(ul)) {
+ final long txidBits = id.getTransactionId();
+ if (purgedTransactions.contains(txidBits)) {
LOG.warn("{}: Request {} is contained purged transactions {}", persistenceId, request, purgedTransactions);
- throw new DeadTransactionException(purgedTransactions);
+ throw new DeadTransactionException(purgedTransactions.toRangeSet());
}
- final Boolean closed = closedTransactions.get(ul);
+
+ final Boolean closed = closedTransactions.get(UnsignedLong.fromLongBits(txidBits));
if (closed != null) {
- final boolean successful = closed.booleanValue();
+ final boolean successful = closed;
LOG.debug("{}: Request {} refers to a {} transaction", persistenceId, request, successful ? "successful"
: "failed");
throw new ClosedTransactionException(successful);
private TransactionSuccess<?> handleTransactionPurgeRequest(final TransactionRequest<?> request,
final RequestEnvelope envelope, final long now) {
final TransactionIdentifier id = request.getTarget();
- final UnsignedLong ul = UnsignedLong.fromLongBits(id.getTransactionId());
- if (purgedTransactions.contains(ul)) {
+ final long txidBits = id.getTransactionId();
+ if (purgedTransactions.contains(txidBits)) {
// Retransmitted purge request: nothing to do
LOG.debug("{}: transaction {} already purged", persistenceId, id);
return new TransactionPurgeResponse(id, request.getSequence());
// We perform two lookups instead of a straight remove, because once the map becomes empty we switch it
// to an ImmutableMap, which does not allow remove().
+ final UnsignedLong ul = UnsignedLong.fromLongBits(txidBits);
if (closedTransactions.containsKey(ul)) {
tree.purgeTransaction(id, () -> {
closedTransactions.remove(ul);
closedTransactions = ImmutableMap.of();
}
- purgedTransactions.add(Range.closedOpen(ul, UnsignedLong.ONE.plus(ul)));
+ purgedTransactions.add(txidBits);
LOG.debug("{}: finished purging inherited transaction {}", persistenceId(), id);
envelope.sendSuccess(new TransactionPurgeResponse(id, request.getSequence()), readTime() - now);
});
// purged transactions in one go. If it does, we warn about the situation and
LOG.warn("{}: transaction {} not tracked in {}, but not present in active transactions", persistenceId,
id, purgedTransactions);
- purgedTransactions.add(Range.closedOpen(ul, UnsignedLong.ONE.plus(ul)));
+ purgedTransactions.add(txidBits);
return new TransactionPurgeResponse(id, request.getSequence());
}
tree.purgeTransaction(id, () -> {
- purgedTransactions.add(Range.closedOpen(ul, UnsignedLong.ONE.plus(ul)));
+ purgedTransactions.add(txidBits);
transactions.remove(id);
LOG.debug("{}: finished purging transaction {}", persistenceId(), id);
envelope.sendSuccess(new TransactionPurgeResponse(id, request.getSequence()), readTime() - now);
import org.opendaylight.controller.cluster.access.concepts.TransactionIdentifier;
import org.opendaylight.controller.cluster.datastore.persisted.FrontendClientMetadata;
import org.opendaylight.controller.cluster.datastore.persisted.FrontendHistoryMetadata;
-import org.opendaylight.controller.cluster.datastore.utils.UnsignedLongRangeSet;
+import org.opendaylight.controller.cluster.datastore.utils.UnsignedLongSet;
import org.opendaylight.yangtools.concepts.Builder;
import org.opendaylight.yangtools.concepts.Identifiable;
import org.slf4j.Logger;
}
static final class Enabled extends FrontendClientMetadataBuilder {
-
private final Map<LocalHistoryIdentifier, FrontendHistoryMetadataBuilder> currentHistories = new HashMap<>();
- private final UnsignedLongRangeSet purgedHistories;
private final LocalHistoryIdentifier standaloneId;
+ private final UnsignedLongSet purgedHistories;
Enabled(final String shardName, final ClientIdentifier identifier) {
super(shardName, identifier);
- purgedHistories = UnsignedLongRangeSet.create();
+ purgedHistories = UnsignedLongSet.of();
// History for stand-alone transactions is always present
standaloneId = standaloneHistoryId();
Enabled(final String shardName, final FrontendClientMetadata meta) {
super(shardName, meta.getIdentifier());
- purgedHistories = UnsignedLongRangeSet.create(meta.getPurgedHistories());
+ purgedHistories = UnsignedLongSet.of(meta.getPurgedHistories());
for (FrontendHistoryMetadata h : meta.getCurrentHistories()) {
final FrontendHistoryMetadataBuilder b = new FrontendHistoryMetadataBuilder(getIdentifier(), h);
currentHistories.put(b.getIdentifier(), b);
@Override
public FrontendClientMetadata build() {
- return new FrontendClientMetadata(getIdentifier(), purgedHistories.toImmutable(),
+ return new FrontendClientMetadata(getIdentifier(), purgedHistories.toRangeSet(),
Collections2.transform(currentHistories.values(), FrontendHistoryMetadataBuilder::build));
}
import static com.google.common.base.Preconditions.checkState;
import static java.util.Objects.requireNonNull;
-import com.google.common.collect.Range;
-import com.google.common.collect.RangeSet;
-import com.google.common.collect.TreeRangeSet;
import com.google.common.primitives.UnsignedLong;
import java.util.HashMap;
import java.util.Map;
import org.opendaylight.controller.cluster.access.concepts.LocalHistoryIdentifier;
import org.opendaylight.controller.cluster.access.concepts.TransactionIdentifier;
import org.opendaylight.controller.cluster.datastore.persisted.FrontendHistoryMetadata;
+import org.opendaylight.controller.cluster.datastore.utils.UnsignedLongSet;
import org.opendaylight.yangtools.concepts.Builder;
import org.opendaylight.yangtools.concepts.Identifiable;
final class FrontendHistoryMetadataBuilder implements Builder<FrontendHistoryMetadata>,
Identifiable<LocalHistoryIdentifier> {
- private final Map<UnsignedLong, Boolean> closedTransactions;
- private final RangeSet<UnsignedLong> purgedTransactions;
- private final LocalHistoryIdentifier identifier;
+ private final @NonNull Map<UnsignedLong, Boolean> closedTransactions;
+ private final @NonNull UnsignedLongSet purgedTransactions;
+ private final @NonNull LocalHistoryIdentifier identifier;
private boolean closed;
FrontendHistoryMetadataBuilder(final LocalHistoryIdentifier identifier) {
this.identifier = requireNonNull(identifier);
- this.purgedTransactions = TreeRangeSet.create();
- this.closedTransactions = new HashMap<>(2);
+ purgedTransactions = UnsignedLongSet.of();
+ closedTransactions = new HashMap<>(2);
}
FrontendHistoryMetadataBuilder(final ClientIdentifier clientId, final FrontendHistoryMetadata meta) {
identifier = new LocalHistoryIdentifier(clientId, meta.getHistoryId(), meta.getCookie());
closedTransactions = new HashMap<>(meta.getClosedTransactions());
- purgedTransactions = TreeRangeSet.create(meta.getPurgedTransactions());
+ purgedTransactions = UnsignedLongSet.of(meta.getPurgedTransactions());
closed = meta.isClosed();
}
@Override
public FrontendHistoryMetadata build() {
return new FrontendHistoryMetadata(identifier.getHistoryId(), identifier.getCookie(), closed,
- closedTransactions, purgedTransactions);
+ closedTransactions, purgedTransactions.toRangeSet());
}
void onHistoryClosed() {
}
void onTransactionPurged(final TransactionIdentifier txId) {
- final UnsignedLong id = UnsignedLong.fromLongBits(txId.getTransactionId());
- closedTransactions.remove(id);
- purgedTransactions.add(Range.closedOpen(id, UnsignedLong.ONE.plus(id)));
+ final long txidBits = txId.getTransactionId();
+ closedTransactions.remove(UnsignedLong.fromLongBits(txidBits));
+ purgedTransactions.add(txidBits);
}
/**
import org.opendaylight.controller.cluster.access.concepts.RequestException;
import org.opendaylight.controller.cluster.access.concepts.UnsupportedRequestException;
import org.opendaylight.controller.cluster.datastore.ShardDataTreeCohort.State;
-import org.opendaylight.controller.cluster.datastore.utils.UnsignedLongRangeSet;
+import org.opendaylight.controller.cluster.datastore.utils.UnsignedLongSet;
import org.opendaylight.yangtools.concepts.Identifiable;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
private final Map<LocalHistoryIdentifier, LocalFrontendHistory> localHistories;
// RangeSet performs automatic merging, hence we keep minimal state tracking information
- private final UnsignedLongRangeSet purgedHistories;
+ private final UnsignedLongSet purgedHistories;
// Used for all standalone transactions
private final AbstractFrontendHistory standaloneHistory;
private Long lastSeenHistory = null;
Enabled(final String persistenceId, final ClientIdentifier clientId, final ShardDataTree tree) {
- this(persistenceId, clientId, tree, UnsignedLongRangeSet.create(),
+ this(persistenceId, clientId, tree, UnsignedLongSet.of(),
StandaloneFrontendHistory.create(persistenceId, clientId, tree), new HashMap<>());
}
Enabled(final String persistenceId, final ClientIdentifier clientId, final ShardDataTree tree,
- final UnsignedLongRangeSet purgedHistories, final AbstractFrontendHistory standaloneHistory,
+ final UnsignedLongSet purgedHistories, final AbstractFrontendHistory standaloneHistory,
final Map<LocalHistoryIdentifier, LocalFrontendHistory> localHistories) {
super(persistenceId, clientId, tree);
this.purgedHistories = requireNonNull(purgedHistories);
if (history == null) {
if (purgedHistories.contains(lhId.getHistoryId())) {
LOG.warn("{}: rejecting request {} to purged history", persistenceId(), request);
- throw new DeadHistoryException(purgedHistories.toImmutable());
+ throw new DeadHistoryException(purgedHistories.toRangeSet());
}
LOG.warn("{}: rejecting unknown history request {}", persistenceId(), request);
// not end up resurrecting a purged history.
if (purgedHistories.contains(historyId.getHistoryId())) {
LOG.debug("{}: rejecting purged request {}", persistenceId(), request);
- throw new DeadHistoryException(purgedHistories.toImmutable());
+ throw new DeadHistoryException(purgedHistories.toRangeSet());
}
// Update last history we have seen
this.persistenceId = requireNonNull(persistenceId);
this.clientId = requireNonNull(clientId);
this.tree = requireNonNull(tree);
- this.lastSeenTicks = tree.readTime();
+ lastSeenTicks = tree.readTime();
}
@Override
}
final void touch() {
- this.lastSeenTicks = tree.readTime();
+ lastSeenTicks = tree.readTime();
}
abstract @Nullable LocalHistorySuccess handleLocalHistoryRequest(LocalHistoryRequest<?> request,
import static java.util.Objects.requireNonNull;
import com.google.common.collect.ImmutableMap;
-import com.google.common.collect.RangeSet;
-import com.google.common.collect.TreeRangeSet;
import com.google.common.primitives.UnsignedLong;
import java.util.HashMap;
import java.util.Map;
import java.util.SortedSet;
import org.opendaylight.controller.cluster.access.concepts.LocalHistoryIdentifier;
import org.opendaylight.controller.cluster.access.concepts.TransactionIdentifier;
+import org.opendaylight.controller.cluster.datastore.utils.UnsignedLongSet;
import org.opendaylight.yangtools.yang.data.api.schema.tree.DataTreeModification;
/**
private LocalFrontendHistory(final String persistenceId, final ShardDataTree tree,
final ShardDataTreeTransactionChain chain, final Map<UnsignedLong, Boolean> closedTransactions,
- final RangeSet<UnsignedLong> purgedTransactions) {
+ final UnsignedLongSet purgedTransactions) {
super(persistenceId, tree, closedTransactions, purgedTransactions);
this.chain = requireNonNull(chain);
}
static LocalFrontendHistory create(final String persistenceId, final ShardDataTree tree,
final ShardDataTreeTransactionChain chain) {
- return new LocalFrontendHistory(persistenceId, tree, chain, ImmutableMap.of(), TreeRangeSet.create());
+ return new LocalFrontendHistory(persistenceId, tree, chain, ImmutableMap.of(), UnsignedLongSet.of());
}
static LocalFrontendHistory recreate(final String persistenceId, final ShardDataTree tree,
final ShardDataTreeTransactionChain chain, final Map<UnsignedLong, Boolean> closedTransactions,
- final RangeSet<UnsignedLong> purgedTransactions) {
+ final UnsignedLongSet purgedTransactions) {
return new LocalFrontendHistory(persistenceId, tree, chain, new HashMap<>(closedTransactions),
- TreeRangeSet.create(purgedTransactions));
+ purgedTransactions.copy());
}
@Override
import static java.util.Objects.requireNonNull;
import com.google.common.collect.ImmutableMap;
-import com.google.common.collect.RangeSet;
-import com.google.common.collect.TreeRangeSet;
import com.google.common.primitives.UnsignedLong;
import java.util.HashMap;
import java.util.Map;
import org.opendaylight.controller.cluster.access.concepts.ClientIdentifier;
import org.opendaylight.controller.cluster.access.concepts.LocalHistoryIdentifier;
import org.opendaylight.controller.cluster.access.concepts.TransactionIdentifier;
+import org.opendaylight.controller.cluster.datastore.utils.UnsignedLongSet;
import org.opendaylight.yangtools.yang.data.api.schema.tree.DataTreeModification;
/**
private StandaloneFrontendHistory(final String persistenceId, final ClientIdentifier clientId,
final ShardDataTree tree, final Map<UnsignedLong, Boolean> closedTransactions,
- final RangeSet<UnsignedLong> purgedTransactions) {
+ final UnsignedLongSet purgedTransactions) {
super(persistenceId, tree, closedTransactions, purgedTransactions);
- this.identifier = new LocalHistoryIdentifier(clientId, 0);
+ identifier = new LocalHistoryIdentifier(clientId, 0);
this.tree = requireNonNull(tree);
}
static @NonNull StandaloneFrontendHistory create(final String persistenceId, final ClientIdentifier clientId,
final ShardDataTree tree) {
- return new StandaloneFrontendHistory(persistenceId, clientId, tree, ImmutableMap.of(),
- TreeRangeSet.create());
+ return new StandaloneFrontendHistory(persistenceId, clientId, tree, ImmutableMap.of(), UnsignedLongSet.of());
}
static @NonNull StandaloneFrontendHistory recreate(final String persistenceId, final ClientIdentifier clientId,
final ShardDataTree tree, final Map<UnsignedLong, Boolean> closedTransactions,
- final RangeSet<UnsignedLong> purgedTransactions) {
+ final UnsignedLongSet purgedTransactions) {
return new StandaloneFrontendHistory(persistenceId, clientId, tree, new HashMap<>(closedTransactions),
- purgedTransactions);
+ purgedTransactions.copy());
}
@Override
+++ /dev/null
-/*
- * Copyright (c) 2017 Pantheon Technologies, s.r.o. and others. All rights reserved.
- *
- * This program and the accompanying materials are made available under the
- * terms of the Eclipse Public License v1.0 which accompanies this distribution,
- * and is available at http://www.eclipse.org/legal/epl-v10.html
- */
-package org.opendaylight.controller.cluster.datastore.utils;
-
-import static java.util.Objects.requireNonNull;
-
-import com.google.common.annotations.Beta;
-import com.google.common.base.MoreObjects;
-import com.google.common.collect.ImmutableRangeSet;
-import com.google.common.collect.Range;
-import com.google.common.collect.RangeSet;
-import com.google.common.collect.TreeRangeSet;
-import com.google.common.primitives.UnsignedLong;
-import org.opendaylight.yangtools.concepts.Mutable;
-
-/**
- * Utility {@link RangeSet}-like class, specialized for holding {@link UnsignedLong}. It does not directly implement
- * the {@link RangeSet} interface, but allows converting to and from it. Internal implementation takes advantage of
- * knowing that {@link UnsignedLong} is a discrete type and that it can be stored in a long.
- *
- * @author Robert Varga
- */
-@Beta
-public final class UnsignedLongRangeSet implements Mutable {
- // FIXME: this is just to get us started
- private final RangeSet<UnsignedLong> rangeset;
-
- private UnsignedLongRangeSet(final RangeSet<UnsignedLong> rangeset) {
- this.rangeset = requireNonNull(rangeset);
- }
-
- public static UnsignedLongRangeSet create() {
- return new UnsignedLongRangeSet(TreeRangeSet.create());
- }
-
- public static UnsignedLongRangeSet create(final RangeSet<UnsignedLong> input) {
- return new UnsignedLongRangeSet(TreeRangeSet.create(input));
- }
-
- public RangeSet<UnsignedLong> toImmutable() {
- return ImmutableRangeSet.copyOf(rangeset);
- }
-
- public void add(final long longBits) {
- add(UnsignedLong.fromLongBits(longBits));
- }
-
- public void add(final UnsignedLong value) {
- rangeset.add(Range.closedOpen(value, UnsignedLong.ONE.plus(value)));
- }
-
- public boolean contains(final UnsignedLong value) {
- return rangeset.contains(value);
- }
-
- public boolean contains(final long longBits) {
- return contains(UnsignedLong.fromLongBits(longBits));
- }
-
- public UnsignedLongRangeSet copy() {
- return new UnsignedLongRangeSet(TreeRangeSet.create(rangeset));
- }
-
- @Override
- public String toString() {
- return MoreObjects.toStringHelper(this)
- .omitNullValues()
- .add("span", rangeset.isEmpty() ? null : rangeset.span())
- .add("rangeSize", rangeset.asRanges().size())
- .toString();
- }
-}
--- /dev/null
+/*
+ * Copyright (c) 2021 PANTHEON.tech, s.r.o. and others. All rights reserved.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ * and is available at http://www.eclipse.org/legal/epl-v10.html
+ */
+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.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.util.TreeSet;
+import org.eclipse.jdt.annotation.NonNull;
+import org.opendaylight.yangtools.concepts.Mutable;
+
+/**
+ * A class holding an equivalent of {@code Set<UnsignedLong>}. It is geared towards efficiently tracking ranges of
+ * objects, similar to what a {@link RangeSet} would do.
+ *
+ * <p>
+ * Unlike a {@code RangeSet}, though, this class takes advantage of knowing that an unsigned long is a discrete unit
+ * and can be stored in a simple {@code long}.
+ *
+ * @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;
+
+ private Entry(final long lowerBits, final long upperBits) {
+ this.lowerBits = lowerBits;
+ this.upperBits = upperBits;
+ }
+
+ static Entry of(final long longBits) {
+ return of(longBits, longBits);
+ }
+
+ static 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);
+ }
+
+ 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));
+ }
+
+ @Override
+ @SuppressWarnings("checkstyle:parameterName")
+ public int compareTo(final Entry o) {
+ return Long.compareUnsigned(lowerBits, o.lowerBits);
+ }
+
+ @Override
+ public int hashCode() {
+ return Long.hashCode(lowerBits) * 31 + Long.hashCode(upperBits);
+ }
+
+ @Override
+ public boolean equals(final Object obj) {
+ if (obj == this) {
+ return true;
+ }
+ if (!(obj instanceof Entry)) {
+ return false;
+ }
+ final var other = (Entry) obj;
+ return lowerBits == other.lowerBits && upperBits == other.upperBits;
+ }
+
+ @Override
+ public String toString() {
+ return "[" + Long.toUnsignedString(lowerBits) + ".." + Long.toUnsignedString(upperBits) + "]";
+ }
+ }
+
+ // 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;
+
+ private UnsignedLongSet(final TreeSet<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 static @NonNull UnsignedLongSet of() {
+ return new UnsignedLongSet(new TreeSet<>());
+ }
+
+ public static @NonNull UnsignedLongSet of(final RangeSet<UnsignedLong> rangeSet) {
+ return new UnsignedLongSet(rangeSet);
+ }
+
+ 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 boolean contains(final long longBits) {
+ final var headIt = headIter(Entry.of(longBits));
+ return headIt.hasNext() && headIt.next().contains(longBits);
+ }
+
+ 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));
+ }
+
+ @Override
+ public int hashCode() {
+ return ranges.hashCode();
+ }
+
+ @Override
+ public boolean equals(final Object obj) {
+ return obj == this || obj instanceof UnsignedLongSet && ranges.equals(((UnsignedLongSet) obj).ranges);
+ }
+
+ @Override
+ public String toString() {
+ final var helper = MoreObjects.toStringHelper(this);
+
+ final int size = ranges.size();
+ switch (size) {
+ case 0:
+ break;
+ case 1:
+ helper.add("span", ranges.first());
+ break;
+ default:
+ helper.add("span", Entry.of(ranges.first().lowerBits, ranges.last().upperBits));
+ }
+
+ return helper.add("size", size).toString();
+ }
+
+ private Iterator<Entry> headIter(final Entry range) {
+ return ranges.headSet(range, true).descendingIterator();
+ }
+}
--- /dev/null
+/*
+ * Copyright (c) 2021 PANTHEON.tech, s.r.o. and others. All rights reserved.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ * and is available at http://www.eclipse.org/legal/epl-v10.html
+ */
+package org.opendaylight.controller.cluster.datastore.utils;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+import com.google.common.collect.ImmutableRangeSet;
+import com.google.common.collect.Range;
+import com.google.common.primitives.UnsignedLong;
+import org.junit.Test;
+
+public class UnsignedLongSetTest {
+ @Test
+ public void testOperations() {
+ final var set = UnsignedLongSet.of();
+ assertEquals("UnsignedLongSet{size=0}", set.toString());
+ assertFalse(set.contains(0));
+
+ set.add(0);
+ assertTrue(set.contains(0));
+ assertEquals("UnsignedLongSet{span=[0..0], size=1}", set.toString());
+
+ set.add(1);
+ assertTrue(set.contains(1));
+ assertEquals("UnsignedLongSet{span=[0..1], size=1}", set.toString());
+ set.add(1);
+ assertEquals("UnsignedLongSet{span=[0..1], size=1}", set.toString());
+
+ set.add(4);
+ assertEquals("UnsignedLongSet{span=[0..4], size=2}", set.toString());
+
+ set.add(3);
+ assertEquals("UnsignedLongSet{span=[0..4], size=2}", set.toString());
+
+ set.add(2);
+ assertEquals("UnsignedLongSet{span=[0..4], size=1}", set.toString());
+
+ assertTrue(set.contains(2));
+ assertTrue(set.contains(3));
+ assertTrue(set.contains(4));
+ }
+
+ @Test
+ public void testOfRangeSet() {
+ final var rangeSet = ImmutableRangeSet.<UnsignedLong>builder()
+ .add(Range.closedOpen(UnsignedLong.valueOf(0), UnsignedLong.valueOf(2)))
+ .add(Range.closedOpen(UnsignedLong.valueOf(3), UnsignedLong.valueOf(5)))
+ .build();
+ assertEquals("[[0..2), [3..5)]", rangeSet.toString());
+ assertEquals("UnsignedLongSet{span=[0..4], size=2}", UnsignedLongSet.of(rangeSet).toString());
+ }
+
+ @Test
+ public void testToRangeSet() {
+ final var set = UnsignedLongSet.of();
+ set.add(0);
+ set.add(1);
+ set.add(4);
+ set.add(3);
+ assertEquals("[[0..2), [3..5)]", set.toRangeSet().toString());
+ }
+}
Code Review / controller.git / commitdiff