Split UnsignedLongSet into two implementations, mutable and immutable.
Use the mutable implementation in runtime tracking of identifiers and
use the immutable implementation for tracking identifiers in metadata.
The serialization format is kept compatible with RangeSets, although
that implies a minor penalty in serdes.
This switch ends up potentially using more objects for small sets, but
that is offset by not having Cut indirections and most notably being
resistent to allocation of huge arrays.
JIRA: CONTROLLER-2011
Change-Id: I0c84ffaaa4ce39299cef9006784b8aff78dd0f83
Signed-off-by: Robert Varga <robert.varga@pantheon.tech>
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.controller.cluster.datastore.utils.MutableUnsignedLongSet;
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 UnsignedLongSet purgedTransactions;
+ private final MutableUnsignedLongSet 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 UnsignedLongSet purgedTransactions) {
+ final Map<UnsignedLong, Boolean> closedTransactions, final MutableUnsignedLongSet purgedTransactions) {
this.persistenceId = requireNonNull(persistenceId);
this.tree = requireNonNull(tree);
this.closedTransactions = requireNonNull(closedTransactions);
import com.google.common.base.MoreObjects.ToStringHelper;
import com.google.common.collect.Collections2;
import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableRangeSet;
-import com.google.common.collect.RangeSet;
-import com.google.common.primitives.UnsignedLong;
-import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import org.eclipse.jdt.annotation.NonNull;
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.UnsignedLongSet;
+import org.opendaylight.controller.cluster.datastore.utils.ImmutableUnsignedLongSet;
+import org.opendaylight.controller.cluster.datastore.utils.MutableUnsignedLongSet;
import org.opendaylight.yangtools.concepts.Builder;
import org.opendaylight.yangtools.concepts.Identifiable;
import org.slf4j.Logger;
@Override
public FrontendClientMetadata build() {
- return new FrontendClientMetadata(getIdentifier(), ImmutableRangeSet.of(), ImmutableList.of());
+ return new FrontendClientMetadata(getIdentifier(), ImmutableUnsignedLongSet.of(), ImmutableList.of());
}
@Override
static final class Enabled extends FrontendClientMetadataBuilder {
private final Map<LocalHistoryIdentifier, FrontendHistoryMetadataBuilder> currentHistories = new HashMap<>();
+ private final MutableUnsignedLongSet purgedHistories;
private final LocalHistoryIdentifier standaloneId;
- private final UnsignedLongSet purgedHistories;
Enabled(final String shardName, final ClientIdentifier identifier) {
super(shardName, identifier);
- purgedHistories = UnsignedLongSet.of();
+ purgedHistories = MutableUnsignedLongSet.of();
// History for stand-alone transactions is always present
standaloneId = standaloneHistoryId();
Enabled(final String shardName, final FrontendClientMetadata meta) {
super(shardName, meta.getIdentifier());
- purgedHistories = UnsignedLongSet.of(meta.getPurgedHistories());
+ purgedHistories = meta.getPurgedHistories().mutableCopy();
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.toRangeSet(),
+ return new FrontendClientMetadata(getIdentifier(), purgedHistories.immutableCopy(),
Collections2.transform(currentHistories.values(), FrontendHistoryMetadataBuilder::build));
}
}
return new LeaderFrontendState.Enabled(shard.persistenceId(), getIdentifier(), shard.getDataStore(),
- purgedHistories.copy(), singleHistory, histories);
+ purgedHistories.mutableCopy(), singleHistory, histories);
}
@Override
}
static FrontendClientMetadataBuilder of(final String shardName, final FrontendClientMetadata meta) {
- final Collection<FrontendHistoryMetadata> current = meta.getCurrentHistories();
- final RangeSet<UnsignedLong> purged = meta.getPurgedHistories();
-
// Completely empty histories imply disabled state, as otherwise we'd have a record of the single history --
// either purged or active
- return current.isEmpty() && purged.isEmpty() ? new Disabled(shardName, meta.getIdentifier())
- : new Enabled(shardName, meta);
+ return meta.getCurrentHistories().isEmpty() && meta.getPurgedHistories().isEmpty()
+ ? new Disabled(shardName, meta.getIdentifier()) : new Enabled(shardName, meta);
}
@Override
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.controller.cluster.datastore.utils.MutableUnsignedLongSet;
import org.opendaylight.yangtools.concepts.Builder;
import org.opendaylight.yangtools.concepts.Identifiable;
Identifiable<LocalHistoryIdentifier> {
private final @NonNull Map<UnsignedLong, Boolean> closedTransactions;
- private final @NonNull UnsignedLongSet purgedTransactions;
+ private final @NonNull MutableUnsignedLongSet purgedTransactions;
private final @NonNull LocalHistoryIdentifier identifier;
private boolean closed;
FrontendHistoryMetadataBuilder(final LocalHistoryIdentifier identifier) {
this.identifier = requireNonNull(identifier);
- purgedTransactions = UnsignedLongSet.of();
+ purgedTransactions = MutableUnsignedLongSet.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 = UnsignedLongSet.of(meta.getPurgedTransactions());
+ purgedTransactions = meta.getPurgedTransactions().mutableCopy();
closed = meta.isClosed();
}
@Override
public FrontendHistoryMetadata build() {
return new FrontendHistoryMetadata(identifier.getHistoryId(), identifier.getCookie(), closed,
- closedTransactions, purgedTransactions.toRangeSet());
+ closedTransactions, purgedTransactions.immutableCopy());
}
void onHistoryClosed() {
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.UnsignedLongSet;
+import org.opendaylight.controller.cluster.datastore.utils.MutableUnsignedLongSet;
import org.opendaylight.yangtools.concepts.Identifiable;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
// Histories which have not been purged
private final Map<LocalHistoryIdentifier, LocalFrontendHistory> localHistories;
- // RangeSet performs automatic merging, hence we keep minimal state tracking information
- private final UnsignedLongSet purgedHistories;
+ // UnsignedLongSet performs automatic merging, hence we keep minimal state tracking information
+ private final MutableUnsignedLongSet 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, UnsignedLongSet.of(),
+ this(persistenceId, clientId, tree, MutableUnsignedLongSet.of(),
StandaloneFrontendHistory.create(persistenceId, clientId, tree), new HashMap<>());
}
Enabled(final String persistenceId, final ClientIdentifier clientId, final ShardDataTree tree,
- final UnsignedLongSet purgedHistories, final AbstractFrontendHistory standaloneHistory,
+ final MutableUnsignedLongSet purgedHistories, final AbstractFrontendHistory standaloneHistory,
final Map<LocalHistoryIdentifier, LocalFrontendHistory> localHistories) {
super(persistenceId, clientId, tree);
this.purgedHistories = requireNonNull(purgedHistories);
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.controller.cluster.datastore.utils.MutableUnsignedLongSet;
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 UnsignedLongSet purgedTransactions) {
+ final MutableUnsignedLongSet 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(), UnsignedLongSet.of());
+ return new LocalFrontendHistory(persistenceId, tree, chain, ImmutableMap.of(), MutableUnsignedLongSet.of());
}
static LocalFrontendHistory recreate(final String persistenceId, final ShardDataTree tree,
final ShardDataTreeTransactionChain chain, final Map<UnsignedLong, Boolean> closedTransactions,
- final UnsignedLongSet purgedTransactions) {
+ final MutableUnsignedLongSet purgedTransactions) {
return new LocalFrontendHistory(persistenceId, tree, chain, new HashMap<>(closedTransactions),
- purgedTransactions.copy());
+ purgedTransactions.mutableCopy());
}
@Override
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.controller.cluster.datastore.utils.MutableUnsignedLongSet;
import org.opendaylight.yangtools.yang.data.api.schema.tree.DataTreeModification;
/**
* @author Robert Varga
*/
final class StandaloneFrontendHistory extends AbstractFrontendHistory {
- private final LocalHistoryIdentifier identifier;
- private final ShardDataTree tree;
+ private final @NonNull LocalHistoryIdentifier identifier;
+ private final @NonNull ShardDataTree tree;
private StandaloneFrontendHistory(final String persistenceId, final ClientIdentifier clientId,
final ShardDataTree tree, final Map<UnsignedLong, Boolean> closedTransactions,
- final UnsignedLongSet purgedTransactions) {
+ final MutableUnsignedLongSet purgedTransactions) {
super(persistenceId, tree, closedTransactions, purgedTransactions);
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(), UnsignedLongSet.of());
+ return new StandaloneFrontendHistory(persistenceId, clientId, tree, ImmutableMap.of(),
+ MutableUnsignedLongSet.of());
}
static @NonNull StandaloneFrontendHistory recreate(final String persistenceId, final ClientIdentifier clientId,
final ShardDataTree tree, final Map<UnsignedLong, Boolean> closedTransactions,
- final UnsignedLongSet purgedTransactions) {
+ final MutableUnsignedLongSet purgedTransactions) {
return new StandaloneFrontendHistory(persistenceId, clientId, tree, new HashMap<>(closedTransactions),
- purgedTransactions.copy());
+ purgedTransactions.mutableCopy());
}
@Override
import com.google.common.base.MoreObjects;
import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableRangeSet;
-import com.google.common.collect.ImmutableRangeSet.Builder;
-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.ArrayList;
import java.util.Collection;
-import java.util.Set;
import org.eclipse.jdt.annotation.NonNull;
import org.opendaylight.controller.cluster.access.concepts.ClientIdentifier;
+import org.opendaylight.controller.cluster.datastore.utils.ImmutableUnsignedLongSet;
import org.opendaylight.yangtools.concepts.Identifiable;
import org.opendaylight.yangtools.concepts.WritableObject;
-import org.opendaylight.yangtools.concepts.WritableObjects;
public final class FrontendClientMetadata implements Identifiable<ClientIdentifier>, WritableObject {
private final @NonNull ImmutableList<FrontendHistoryMetadata> currentHistories;
- private final @NonNull ImmutableRangeSet<UnsignedLong> purgedHistories;
+ private final @NonNull ImmutableUnsignedLongSet purgedHistories;
private final @NonNull ClientIdentifier identifier;
- public FrontendClientMetadata(final ClientIdentifier identifier, final RangeSet<UnsignedLong> purgedHistories,
+ public FrontendClientMetadata(final ClientIdentifier identifier, final ImmutableUnsignedLongSet purgedHistories,
final Collection<FrontendHistoryMetadata> currentHistories) {
this.identifier = requireNonNull(identifier);
- this.purgedHistories = ImmutableRangeSet.copyOf(purgedHistories);
+ this.purgedHistories = requireNonNull(purgedHistories);
this.currentHistories = ImmutableList.copyOf(currentHistories);
}
return currentHistories;
}
- public RangeSet<UnsignedLong> getPurgedHistories() {
+ public ImmutableUnsignedLongSet getPurgedHistories() {
return purgedHistories;
}
@Override
public void writeTo(final DataOutput out) throws IOException {
identifier.writeTo(out);
-
- final Set<Range<UnsignedLong>> ranges = purgedHistories.asRanges();
- out.writeInt(ranges.size());
- for (final Range<UnsignedLong> r : ranges) {
- WritableObjects.writeLongs(out, r.lowerEndpoint().longValue(), r.upperEndpoint().longValue());
- }
+ purgedHistories.writeTo(out);
out.writeInt(currentHistories.size());
for (final FrontendHistoryMetadata h : currentHistories) {
public static FrontendClientMetadata readFrom(final DataInput in) throws IOException {
final ClientIdentifier id = ClientIdentifier.readFrom(in);
-
- final int purgedSize = in.readInt();
- final Builder<UnsignedLong> b = ImmutableRangeSet.builder();
- for (int i = 0; i < purgedSize; ++i) {
- final byte header = WritableObjects.readLongHeader(in);
- final UnsignedLong lower = UnsignedLong.fromLongBits(WritableObjects.readFirstLong(in, header));
- final UnsignedLong upper = UnsignedLong.fromLongBits(WritableObjects.readSecondLong(in, header));
-
- b.add(Range.closedOpen(lower, upper));
- }
+ final var purgedHistories = ImmutableUnsignedLongSet.readFrom(in);
final int currentSize = in.readInt();
- final Collection<FrontendHistoryMetadata> currentHistories = new ArrayList<>(currentSize);
+ // FIXME: ImmutableList.builder()
+ final var currentHistories = new ArrayList<FrontendHistoryMetadata>(currentSize);
for (int i = 0; i < currentSize; ++i) {
currentHistories.add(FrontendHistoryMetadata.readFrom(in));
}
- return new FrontendClientMetadata(id, b.build(), currentHistories);
+ return new FrontendClientMetadata(id, purgedHistories, currentHistories);
}
@Override
*/
package org.opendaylight.controller.cluster.datastore.persisted;
+import static java.util.Objects.requireNonNull;
+
import com.google.common.base.MoreObjects;
import com.google.common.base.Verify;
import com.google.common.collect.ImmutableMap;
-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 java.io.DataInput;
import java.io.DataOutput;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
-import java.util.Set;
import org.eclipse.jdt.annotation.NonNull;
+import org.opendaylight.controller.cluster.datastore.utils.ImmutableUnsignedLongSet;
import org.opendaylight.yangtools.concepts.WritableObject;
import org.opendaylight.yangtools.concepts.WritableObjects;
public final class FrontendHistoryMetadata implements WritableObject {
- private final @NonNull ImmutableRangeSet<UnsignedLong> purgedTransactions;
+ private final @NonNull ImmutableUnsignedLongSet purgedTransactions;
private final @NonNull ImmutableMap<UnsignedLong, Boolean> closedTransactions;
private final long historyId;
private final long cookie;
private final boolean closed;
public FrontendHistoryMetadata(final long historyId, final long cookie, final boolean closed,
- final Map<UnsignedLong, Boolean> closedTransactions, final RangeSet<UnsignedLong> purgedTransactions) {
+ final Map<UnsignedLong, Boolean> closedTransactions, final ImmutableUnsignedLongSet purgedTransactions) {
this.historyId = historyId;
this.cookie = cookie;
this.closed = closed;
this.closedTransactions = ImmutableMap.copyOf(closedTransactions);
- this.purgedTransactions = ImmutableRangeSet.copyOf(purgedTransactions);
+ this.purgedTransactions = requireNonNull(purgedTransactions);
}
public long getHistoryId() {
return closed;
}
- public Map<UnsignedLong, Boolean> getClosedTransactions() {
+ public ImmutableMap<UnsignedLong, Boolean> getClosedTransactions() {
return closedTransactions;
}
- public RangeSet<UnsignedLong> getPurgedTransactions() {
+ public ImmutableUnsignedLongSet getPurgedTransactions() {
return purgedTransactions;
}
WritableObjects.writeLongs(out, historyId, cookie);
out.writeBoolean(closed);
- final Set<Range<UnsignedLong>> purgedRanges = purgedTransactions.asRanges();
- WritableObjects.writeLongs(out, closedTransactions.size(), purgedRanges.size());
+ final int purgedSize = purgedTransactions.size();
+ WritableObjects.writeLongs(out, closedTransactions.size(), purgedSize);
for (Entry<UnsignedLong, Boolean> e : closedTransactions.entrySet()) {
WritableObjects.writeLong(out, e.getKey().longValue());
out.writeBoolean(e.getValue());
}
- for (Range<UnsignedLong> r : purgedRanges) {
- WritableObjects.writeLongs(out, r.lowerEndpoint().longValue(), r.upperEndpoint().longValue());
- }
+ purgedTransactions.writeRangesTo(out, purgedSize);
}
public static FrontendHistoryMetadata readFrom(final DataInput in) throws IOException {
final Boolean value = in.readBoolean();
closedTransactions.put(key, value);
}
- final RangeSet<UnsignedLong> purgedTransactions = TreeRangeSet.create();
- for (int i = 0; i < psize; ++i) {
- final byte h = WritableObjects.readLongHeader(in);
- final UnsignedLong l = UnsignedLong.fromLongBits(WritableObjects.readFirstLong(in, h));
- final UnsignedLong u = UnsignedLong.fromLongBits(WritableObjects.readSecondLong(in, h));
- purgedTransactions.add(Range.closedOpen(l, u));
- }
+ final var purgedTransactions = ImmutableUnsignedLongSet.readFrom(in, psize);
return new FrontendHistoryMetadata(historyId, cookie, closed, closedTransactions, purgedTransactions);
}
--- /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 com.google.common.annotations.Beta;
+import java.io.DataInput;
+import java.io.DataOutput;
+import java.io.IOException;
+import java.util.TreeSet;
+import org.eclipse.jdt.annotation.NonNull;
+import org.opendaylight.yangtools.concepts.Immutable;
+import org.opendaylight.yangtools.concepts.WritableObject;
+
+@Beta
+public final class ImmutableUnsignedLongSet extends UnsignedLongSet implements Immutable, WritableObject {
+ private static final @NonNull ImmutableUnsignedLongSet EMPTY = new ImmutableUnsignedLongSet(new TreeSet<>());
+
+ private ImmutableUnsignedLongSet(final TreeSet<Entry> ranges) {
+ super(ranges);
+ }
+
+ static @NonNull ImmutableUnsignedLongSet of(final TreeSet<Entry> ranges) {
+ return ranges.isEmpty() ? EMPTY : new ImmutableUnsignedLongSet(ranges);
+ }
+
+ public static @NonNull ImmutableUnsignedLongSet of() {
+ return EMPTY;
+ }
+
+ @Override
+ public ImmutableUnsignedLongSet immutableCopy() {
+ return this;
+ }
+
+ public static @NonNull ImmutableUnsignedLongSet readFrom(final DataInput in) throws IOException {
+ return readFrom(in, in.readInt());
+ }
+
+ public static @NonNull ImmutableUnsignedLongSet readFrom(final DataInput in, final int size) throws IOException {
+ if (size == 0) {
+ return EMPTY;
+ }
+
+ final var ranges = new TreeSet<Entry>();
+ for (int i = 0; i < size; ++i) {
+ ranges.add(Entry.readUnsigned(in));
+ }
+ return new ImmutableUnsignedLongSet(ranges);
+ }
+
+ @Override
+ public void writeTo(final DataOutput out) throws IOException {
+ out.writeInt(size());
+ writeRanges(out);
+ }
+
+ public void writeRangesTo(final @NonNull DataOutput out, final int size) throws IOException {
+ if (size != size()) {
+ throw new IOException("Mismatched size: expected " + size() + ", got " + size);
+ }
+ writeRanges(out);
+ }
+
+ private void writeRanges(final @NonNull DataOutput out) throws IOException {
+ for (var range : trustedRanges()) {
+ range.writeUnsigned(out);
+ }
+ }
+}
--- /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 com.google.common.annotations.Beta;
+import com.google.common.collect.Collections2;
+import com.google.common.collect.ImmutableRangeSet;
+import com.google.common.primitives.UnsignedLong;
+import java.util.TreeSet;
+import org.eclipse.jdt.annotation.NonNull;
+import org.opendaylight.yangtools.concepts.Mutable;
+
+@Beta
+public final class MutableUnsignedLongSet extends UnsignedLongSet implements Mutable {
+ MutableUnsignedLongSet(final TreeSet<Entry> ranges) {
+ super(ranges);
+ }
+
+ public static @NonNull MutableUnsignedLongSet of() {
+ return new MutableUnsignedLongSet(new TreeSet<>());
+ }
+
+ @Override
+ public ImmutableUnsignedLongSet immutableCopy() {
+ return ImmutableUnsignedLongSet.of(copyRanges());
+ }
+
+ public void add(final long longBits) {
+ addImpl(longBits);
+ }
+
+ public ImmutableRangeSet<UnsignedLong> toRangeSet() {
+ return ImmutableRangeSet.copyOf(Collections2.transform(trustedRanges(), Entry::toUnsigned));
+ }
+}
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.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.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 {
+abstract class UnsignedLongSet {
+ @Beta
+ @VisibleForTesting
+ public static final class Entry implements Comparable<Entry>, Mutable {
// Note: mutable to allow efficient merges.
long lowerBits;
long upperBits;
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) {
return Long.compareUnsigned(lowerBits, longBits) <= 0 && Long.compareUnsigned(upperBits, longBits) >= 0;
}
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<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);
+ }
+
+ void writeUnsigned(final @NonNull DataOutput out) throws IOException {
+ WritableObjects.writeLongs(out, lowerBits, upperBits + 1);
+ }
+
@Override
@SuppressWarnings("checkstyle:parameterName")
public int compareTo(final Entry o) {
// 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 final @NonNull TreeSet<Entry> ranges;
- private UnsignedLongSet(final TreeSet<Entry> ranges) {
+ 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 void addImpl(final long longBits) {
final var range = Entry.of(longBits);
final var headIt = headIter(range);
ranges.add(range);
}
- public boolean contains(final long longBits) {
+ public final 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 final boolean isEmpty() {
+ return ranges.isEmpty();
+ }
+
+ public final int size() {
+ 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));
+ }
+
+ public final @NonNull NavigableSet<Entry> ranges() {
+ return Collections.unmodifiableNavigableSet(ranges);
}
- 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();
import akka.actor.ActorSystem;
import com.google.common.base.Throwables;
import com.google.common.collect.ImmutableMap;
-import com.google.common.collect.Range;
-import com.google.common.primitives.UnsignedLong;
import com.google.common.util.concurrent.FluentFuture;
import com.google.common.util.concurrent.ListenableFuture;
import com.google.common.util.concurrent.MoreExecutors;
import java.util.Iterator;
import java.util.List;
import java.util.Optional;
-import java.util.Set;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.TimeUnit;
while (iterator.hasNext() && metadata.getHistoryId() != 1) {
metadata = iterator.next();
}
- Set<Range<UnsignedLong>> ranges = metadata.getPurgedTransactions().asRanges();
-
- assertEquals(1, ranges.size());
+ assertEquals(1, metadata.getPurgedTransactions().size());
} else {
// ask based should track no metadata
assertTrue(frontendMetadata.getClients().get(0).getCurrentHistories().isEmpty());
import com.google.common.base.Stopwatch;
import com.google.common.base.Throwables;
import com.google.common.collect.ImmutableMap;
-import com.google.common.collect.Range;
import com.google.common.primitives.UnsignedLong;
import com.google.common.util.concurrent.ListenableFuture;
import com.google.common.util.concurrent.MoreExecutors;
import java.util.LinkedList;
import java.util.List;
import java.util.Optional;
-import java.util.Set;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
}
assertEquals(0, metadata.getClosedTransactions().size());
- assertEquals(Range.closedOpen(UnsignedLong.valueOf(0), UnsignedLong.valueOf(11)),
- metadata.getPurgedTransactions().asRanges().iterator().next());
+
+ final var purgedRanges = metadata.getPurgedTransactions().ranges();
+ assertEquals(1, purgedRanges.size());
+ final var purgedRange = purgedRanges.first();
+ assertEquals(UnsignedLong.ZERO, purgedRange.lower());
+ assertEquals(UnsignedLong.valueOf(10), purgedRange.upper());
} else {
// ask based should track no metadata
assertTrue(frontendMetadata.getClients().get(0).getCurrentHistories().isEmpty());
metadata = iterator.next();
}
- Set<Range<UnsignedLong>> ranges = metadata.getPurgedTransactions().asRanges();
-
assertEquals(0, metadata.getClosedTransactions().size());
- assertEquals(1, ranges.size());
+ assertEquals(1, metadata.getPurgedTransactions().size());
} else {
// ask based should track no metadata
assertTrue(frontendMetadata.getClients().get(0).getCurrentHistories().isEmpty());
import static org.junit.Assert.assertTrue;
import com.google.common.collect.ImmutableMap;
-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.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import org.opendaylight.controller.cluster.access.concepts.FrontendIdentifier;
import org.opendaylight.controller.cluster.access.concepts.FrontendType;
import org.opendaylight.controller.cluster.access.concepts.MemberName;
+import org.opendaylight.controller.cluster.datastore.utils.ImmutableUnsignedLongSet;
+import org.opendaylight.controller.cluster.datastore.utils.MutableUnsignedLongSet;
public class FrontendShardDataTreeSnapshotMetadataTest {
FrontendType.forName(index));
final ClientIdentifier clientIdentifier = ClientIdentifier.create(frontendIdentifier, num);
- final RangeSet<UnsignedLong> purgedHistories = TreeRangeSet.create();
- purgedHistories.add(Range.closedOpen(UnsignedLong.ZERO, UnsignedLong.ONE));
+ final MutableUnsignedLongSet tmp = MutableUnsignedLongSet.of();
+ tmp.add(0);
+ final ImmutableUnsignedLongSet purgedHistories = tmp.immutableCopy();
final Set<FrontendHistoryMetadata> currentHistories = Set.of(
new FrontendHistoryMetadata(num, num, true, ImmutableMap.of(UnsignedLong.ZERO, Boolean.TRUE),
purgedHistories));
- return new FrontendClientMetadata(clientIdentifier, purgedHistories, currentHistories);
+ return new FrontendClientMetadata(clientIdentifier, purgedHistories.immutableCopy(), currentHistories);
}
private static <T> void testObject(final T object, final T equalObject) {
*/
package org.opendaylight.controller.cluster.datastore.utils;
+import static org.junit.Assert.assertArrayEquals;
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 java.io.ByteArrayInputStream;
+import java.io.ByteArrayOutputStream;
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.IOException;
import org.junit.Test;
public class UnsignedLongSetTest {
@Test
public void testOperations() {
- final var set = UnsignedLongSet.of();
- assertEquals("UnsignedLongSet{size=0}", set.toString());
+ final var set = MutableUnsignedLongSet.of();
+ assertEquals("MutableUnsignedLongSet{size=0}", set.toString());
assertFalse(set.contains(0));
set.add(0);
assertTrue(set.contains(0));
- assertEquals("UnsignedLongSet{span=[0..0], size=1}", set.toString());
+ assertEquals("MutableUnsignedLongSet{span=[0..0], size=1}", set.toString());
set.add(1);
assertTrue(set.contains(1));
- assertEquals("UnsignedLongSet{span=[0..1], size=1}", set.toString());
+ assertEquals("MutableUnsignedLongSet{span=[0..1], size=1}", set.toString());
set.add(1);
- assertEquals("UnsignedLongSet{span=[0..1], size=1}", set.toString());
+ assertEquals("MutableUnsignedLongSet{span=[0..1], size=1}", set.toString());
set.add(4);
- assertEquals("UnsignedLongSet{span=[0..4], size=2}", set.toString());
+ assertEquals("MutableUnsignedLongSet{span=[0..4], size=2}", set.toString());
set.add(3);
- assertEquals("UnsignedLongSet{span=[0..4], size=2}", set.toString());
+ assertEquals("MutableUnsignedLongSet{span=[0..4], size=2}", set.toString());
set.add(2);
- assertEquals("UnsignedLongSet{span=[0..4], size=1}", set.toString());
+ assertEquals("MutableUnsignedLongSet{span=[0..4], size=1}", set.toString());
assertTrue(set.contains(2));
assertTrue(set.contains(3));
}
@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());
+ public void testSerialization() throws IOException {
+ final var tmp = MutableUnsignedLongSet.of();
+ tmp.add(0);
+ tmp.add(1);
+ tmp.add(4);
+ tmp.add(3);
+
+ final var set = tmp.immutableCopy();
+
+ final var bos = new ByteArrayOutputStream();
+ try (var out = new DataOutputStream(bos)) {
+ set.writeTo(out);
+ }
+
+ final var bytes = bos.toByteArray();
+ assertArrayEquals(new byte[] { 0, 0, 0, 2, 16, 2, 17, 3, 5 }, bytes);
+
+ final ImmutableUnsignedLongSet read;
+ try (var in = new DataInputStream(new ByteArrayInputStream(bytes))) {
+ read = ImmutableUnsignedLongSet.readFrom(in);
+ assertEquals(0, in.available());
+ }
+
+ assertEquals(set, read);
}
@Test
public void testToRangeSet() {
- final var set = UnsignedLongSet.of();
+ final var set = MutableUnsignedLongSet.of();
set.add(0);
set.add(1);
set.add(4);
Code Review / controller.git / commitdiff