Reimplement UnsignedLongRangeSet 98/98298/6
authorRobert Varga <robert.varga@pantheon.tech>
Sat, 6 Nov 2021 01:15:46 +0000 (02:15 +0100)
committerRobert Varga <robert.varga@pantheon.tech>
Sat, 6 Nov 2021 12:37:00 +0000 (13:37 +0100)
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 <robert.varga@pantheon.tech>
opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/AbstractFrontendHistory.java
opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/FrontendClientMetadataBuilder.java
opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/FrontendHistoryMetadataBuilder.java
opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/LeaderFrontendState.java
opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/LocalFrontendHistory.java
opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/StandaloneFrontendHistory.java
opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongRangeSet.java [deleted file]
opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongSet.java [new file with mode: 0644]
opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongSetTest.java [new file with mode: 0644]

index 01fc35c..e437b07 100644 (file)
@@ -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<LocalHistoryIdent
     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;
 
@@ -60,7 +59,7 @@ abstract class AbstractFrontendHistory implements Identifiable<LocalHistoryIdent
     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);
@@ -82,14 +81,15 @@ abstract class AbstractFrontendHistory implements Identifiable<LocalHistoryIdent
         }
 
         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);
@@ -120,8 +120,8 @@ abstract class AbstractFrontendHistory implements Identifiable<LocalHistoryIdent
     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());
@@ -129,6 +129,7 @@ abstract class AbstractFrontendHistory implements Identifiable<LocalHistoryIdent
 
         // 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);
@@ -136,7 +137,7 @@ abstract class AbstractFrontendHistory implements Identifiable<LocalHistoryIdent
                     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);
             });
@@ -149,12 +150,12 @@ abstract class AbstractFrontendHistory implements Identifiable<LocalHistoryIdent
             // 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);
index 475d2e6..d4befae 100644 (file)
@@ -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<FrontendClientMe
     }
 
     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();
@@ -102,7 +101,7 @@ abstract class FrontendClientMetadataBuilder implements Builder<FrontendClientMe
         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);
@@ -119,7 +118,7 @@ abstract class FrontendClientMetadataBuilder implements Builder<FrontendClientMe
 
         @Override
         public FrontendClientMetadata build() {
-            return new FrontendClientMetadata(getIdentifier(), purgedHistories.toImmutable(),
+            return new FrontendClientMetadata(getIdentifier(), purgedHistories.toRangeSet(),
                 Collections2.transform(currentHistories.values(), FrontendHistoryMetadataBuilder::build));
         }
 
index eedabdd..0dd3c48 100644 (file)
@@ -10,9 +10,6 @@ package org.opendaylight.controller.cluster.datastore;
 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;
@@ -21,28 +18,29 @@ 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.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();
     }
 
@@ -54,7 +52,7 @@ final class FrontendHistoryMetadataBuilder implements Builder<FrontendHistoryMet
     @Override
     public FrontendHistoryMetadata build() {
         return new FrontendHistoryMetadata(identifier.getHistoryId(), identifier.getCookie(), closed,
-            closedTransactions, purgedTransactions);
+            closedTransactions, purgedTransactions.toRangeSet());
     }
 
     void onHistoryClosed() {
@@ -71,9 +69,9 @@ final class FrontendHistoryMetadataBuilder implements Builder<FrontendHistoryMet
     }
 
     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);
     }
 
     /**
index 295dbdc..ea2ef2f 100644 (file)
@@ -31,7 +31,7 @@ import org.opendaylight.controller.cluster.access.concepts.RequestEnvelope;
 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;
@@ -66,7 +66,7 @@ abstract class LeaderFrontendState implements Identifiable<ClientIdentifier> {
         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;
@@ -75,12 +75,12 @@ abstract class LeaderFrontendState implements Identifiable<ClientIdentifier> {
         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);
@@ -123,7 +123,7 @@ abstract class LeaderFrontendState implements Identifiable<ClientIdentifier> {
                     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<ClientIdentifier> {
             // 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<ClientIdentifier> {
         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<ClientIdentifier> {
     }
 
     final void touch() {
-        this.lastSeenTicks = tree.readTime();
+        lastSeenTicks = tree.readTime();
     }
 
     abstract @Nullable LocalHistorySuccess handleLocalHistoryRequest(LocalHistoryRequest<?> request,
index b723903..129ef3a 100644 (file)
@@ -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<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
index 4ac3f9c..be85f68 100644 (file)
@@ -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<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
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 (file)
index 9ea92d0..0000000
+++ /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<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();
-    }
-}
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 (file)
index 0000000..ac599a6
--- /dev/null
@@ -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<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();
+    }
+}
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 (file)
index 0000000..7742cf3
--- /dev/null
@@ -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.<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());
+    }
+}