From 19a6bcd20358c883478ee3b82e67cb147113f1c0 Mon Sep 17 00:00:00 2001 From: Robert Varga Date: Sat, 6 Nov 2021 02:15:46 +0100 Subject: [PATCH] Reimplement UnsignedLongRangeSet We are tracking simple discrete values, for which a RangeSet is an overkill due to it being generalized utility working with all possible ranges. Reimplement UnsignedLongRangeSet as UnsignedLongSet, tracking discrete closed ranges of longs, which improves both memory footprint and speed of contains()/add() operations. This also spots a failure to disconnect purged histories during FrontendHistoryMetadataBuilder.toLeaderState(). JIRA: CONTROLLER-1720 Change-Id: I24fae4174201fd133a282f27589d6c274c06c8dc Signed-off-by: Robert Varga --- .../datastore/AbstractFrontendHistory.java | 29 +-- .../FrontendClientMetadataBuilder.java | 11 +- .../FrontendHistoryMetadataBuilder.java | 24 +- .../datastore/LeaderFrontendState.java | 16 +- .../datastore/LocalFrontendHistory.java | 11 +- .../datastore/StandaloneFrontendHistory.java | 14 +- .../datastore/utils/UnsignedLongRangeSet.java | 77 ------- .../datastore/utils/UnsignedLongSet.java | 208 ++++++++++++++++++ .../datastore/utils/UnsignedLongSetTest.java | 69 ++++++ 9 files changed, 327 insertions(+), 132 deletions(-) delete mode 100644 opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongRangeSet.java create mode 100644 opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongSet.java create mode 100644 opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongSetTest.java diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/AbstractFrontendHistory.java b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/AbstractFrontendHistory.java index 01fc35c395..e437b07c64 100644 --- a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/AbstractFrontendHistory.java +++ b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/AbstractFrontendHistory.java @@ -11,8 +11,6 @@ import static java.util.Objects.requireNonNull; 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; @@ -34,6 +32,7 @@ import org.opendaylight.controller.cluster.access.concepts.LocalHistoryIdentifie 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; @@ -49,7 +48,7 @@ abstract class AbstractFrontendHistory implements Identifiable transactions = new HashMap<>(); - private final RangeSet purgedTransactions; + private final UnsignedLongSet purgedTransactions; private final String persistenceId; private final ShardDataTree tree; @@ -60,7 +59,7 @@ abstract class AbstractFrontendHistory implements Identifiable closedTransactions; AbstractFrontendHistory(final String persistenceId, final ShardDataTree tree, - final Map closedTransactions, final RangeSet purgedTransactions) { + final Map closedTransactions, final UnsignedLongSet purgedTransactions) { this.persistenceId = requireNonNull(persistenceId); this.tree = requireNonNull(tree); this.closedTransactions = requireNonNull(closedTransactions); @@ -82,14 +81,15 @@ abstract class AbstractFrontendHistory implements Identifiable 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()); @@ -129,6 +129,7 @@ abstract class AbstractFrontendHistory implements Identifiable { closedTransactions.remove(ul); @@ -136,7 +137,7 @@ abstract class AbstractFrontendHistory implements Identifiable { - 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); diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/FrontendClientMetadataBuilder.java b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/FrontendClientMetadataBuilder.java index 475d2e62f2..d4befae83e 100644 --- a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/FrontendClientMetadataBuilder.java +++ b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/FrontendClientMetadataBuilder.java @@ -26,7 +26,7 @@ import org.opendaylight.controller.cluster.access.concepts.LocalHistoryIdentifie 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; @@ -84,15 +84,14 @@ abstract class FrontendClientMetadataBuilder implements Builder 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(); @@ -102,7 +101,7 @@ abstract class FrontendClientMetadataBuilder implements Builder, Identifiable { - private final Map closedTransactions; - private final RangeSet purgedTransactions; - private final LocalHistoryIdentifier identifier; + private final @NonNull Map 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(); } @@ -54,7 +52,7 @@ final class FrontendHistoryMetadataBuilder implements Builder { private final Map 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; @@ -75,12 +75,12 @@ abstract class LeaderFrontendState implements Identifiable { 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 localHistories) { super(persistenceId, clientId, tree); this.purgedHistories = requireNonNull(purgedHistories); @@ -123,7 +123,7 @@ abstract class LeaderFrontendState implements Identifiable { 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); @@ -174,7 +174,7 @@ abstract class LeaderFrontendState implements Identifiable { // 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 @@ -256,7 +256,7 @@ abstract class LeaderFrontendState implements Identifiable { this.persistenceId = requireNonNull(persistenceId); this.clientId = requireNonNull(clientId); this.tree = requireNonNull(tree); - this.lastSeenTicks = tree.readTime(); + lastSeenTicks = tree.readTime(); } @Override @@ -281,7 +281,7 @@ abstract class LeaderFrontendState implements Identifiable { } final void touch() { - this.lastSeenTicks = tree.readTime(); + lastSeenTicks = tree.readTime(); } abstract @Nullable LocalHistorySuccess handleLocalHistoryRequest(LocalHistoryRequest request, diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/LocalFrontendHistory.java b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/LocalFrontendHistory.java index b7239032b5..129ef3a5eb 100644 --- a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/LocalFrontendHistory.java +++ b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/LocalFrontendHistory.java @@ -10,8 +10,6 @@ package org.opendaylight.controller.cluster.datastore; 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; @@ -19,6 +17,7 @@ import java.util.Optional; 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; /** @@ -31,21 +30,21 @@ final class LocalFrontendHistory extends AbstractFrontendHistory { private LocalFrontendHistory(final String persistenceId, final ShardDataTree tree, final ShardDataTreeTransactionChain chain, final Map closedTransactions, - final RangeSet 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 closedTransactions, - final RangeSet purgedTransactions) { + final UnsignedLongSet purgedTransactions) { return new LocalFrontendHistory(persistenceId, tree, chain, new HashMap<>(closedTransactions), - TreeRangeSet.create(purgedTransactions)); + purgedTransactions.copy()); } @Override diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/StandaloneFrontendHistory.java b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/StandaloneFrontendHistory.java index 4ac3f9c1ed..be85f689eb 100644 --- a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/StandaloneFrontendHistory.java +++ b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/StandaloneFrontendHistory.java @@ -10,8 +10,6 @@ package org.opendaylight.controller.cluster.datastore; 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; @@ -21,6 +19,7 @@ import org.eclipse.jdt.annotation.NonNull; 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; /** @@ -35,23 +34,22 @@ final class StandaloneFrontendHistory extends AbstractFrontendHistory { private StandaloneFrontendHistory(final String persistenceId, final ClientIdentifier clientId, final ShardDataTree tree, final Map closedTransactions, - final RangeSet 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 closedTransactions, - final RangeSet purgedTransactions) { + final UnsignedLongSet purgedTransactions) { return new StandaloneFrontendHistory(persistenceId, clientId, tree, new HashMap<>(closedTransactions), - purgedTransactions); + purgedTransactions.copy()); } @Override diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongRangeSet.java b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongRangeSet.java deleted file mode 100644 index 9ea92d0b9e..0000000000 --- a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongRangeSet.java +++ /dev/null @@ -1,77 +0,0 @@ -/* - * 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 rangeset; - - private UnsignedLongRangeSet(final RangeSet rangeset) { - this.rangeset = requireNonNull(rangeset); - } - - public static UnsignedLongRangeSet create() { - return new UnsignedLongRangeSet(TreeRangeSet.create()); - } - - public static UnsignedLongRangeSet create(final RangeSet input) { - return new UnsignedLongRangeSet(TreeRangeSet.create(input)); - } - - public RangeSet 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(); - } -} 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 new file mode 100644 index 0000000000..ac599a6624 --- /dev/null +++ b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongSet.java @@ -0,0 +1,208 @@ +/* + * 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}. It is geared towards efficiently tracking ranges of + * objects, similar to what a {@link RangeSet} would do. + * + *

+ * 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, 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 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 using [lower, upper + 1) + Range 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 ranges; + + private UnsignedLongSet(final TreeSet ranges) { + this.ranges = requireNonNull(ranges); + } + + private UnsignedLongSet(final RangeSet 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 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 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 headIter(final Entry range) { + return ranges.headSet(range, true).descendingIterator(); + } +} diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongSetTest.java b/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongSetTest.java new file mode 100644 index 0000000000..7742cf3b75 --- /dev/null +++ b/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongSetTest.java @@ -0,0 +1,69 @@ +/* + * 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.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()); + } +} -- 2.36.6