Fix UnsignedLongSet entry lifecycle

[controller.git] / opendaylight / md-sal / sal-distributed-datastore / src / main / java / org / opendaylight / controller / cluster / datastore / utils / UnsignedLongSet.java

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
index 4d4b99bbc9bd1fbc6d21a90e56aa41c2b4982382..e3fa6263e634a99078de115f7ba51314b76ebb60 100644 (file)
--- 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
@@ -7,13 +7,11 @@
  */
 package org.opendaylight.controller.cluster.datastore.utils;
 
-import static com.google.common.base.Verify.verify;
 import static java.util.Objects.requireNonNull;
 
 import com.google.common.annotations.Beta;
 import com.google.common.annotations.VisibleForTesting;
 import com.google.common.base.MoreObjects;
-import com.google.common.collect.BoundType;
 import com.google.common.collect.Collections2;
 import com.google.common.collect.Range;
 import com.google.common.collect.RangeSet;
@@ -21,8 +19,8 @@ import com.google.common.primitives.UnsignedLong;
 import java.io.DataInput;
 import java.io.DataOutput;
 import java.io.IOException;
+import java.util.Collection;
 import java.util.Collections;
-import java.util.Iterator;
 import java.util.NavigableSet;
 import java.util.TreeSet;
 import org.eclipse.jdt.annotation.NonNull;
@@ -60,12 +58,6 @@ abstract class UnsignedLongSet {
             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);
-        }
-
         @VisibleForTesting
         public UnsignedLong lower() {
             return UnsignedLong.fromLongBits(lowerBits);
@@ -76,10 +68,6 @@ abstract class UnsignedLongSet {
             return UnsignedLong.fromLongBits(upperBits);
         }
 
-        boolean contains(final long longBits) {
-            return Long.compareUnsigned(lowerBits, longBits) <= 0 && Long.compareUnsigned(upperBits, longBits) >= 0;
-        }
-
         Entry copy() {
             return new Entry(lowerBits, upperBits);
         }
@@ -136,54 +124,21 @@ abstract class UnsignedLongSet {
         }
     }
 
-    // The idea is rather simple, we track a TreeSet of range entries, ordered by their lower bound. This means that
-    // for a contains() operation we just need the first headSet() entry. For insert operations we just update either
-    // the lower bound or the upper bound of an existing entry. When we do, we also look at prev/next entry and if they
-    // are contiguous with the updated entry, we adjust the entry once more and remove the prev/next entry.
-    private final @NonNull TreeSet<Entry> ranges;
+    // The idea is rather simple, we track a NavigableSet of range entries, ordered by their lower bound. This means
+    // that for a contains() operation we just need the first headSet() entry. For insert operations we just update
+    // either the lower bound or the upper bound of an existing entry. When we do, we also look at prev/next entry and
+    // if they are contiguous with the updated entry, we adjust the entry once more and remove the prev/next entry.
+    private final @NonNull NavigableSet<Entry> ranges;
 
-    UnsignedLongSet(final TreeSet<Entry> ranges) {
+    UnsignedLongSet(final NavigableSet<Entry> ranges) {
         this.ranges = requireNonNull(ranges);
     }
 
-    final void addImpl(final long longBits) {
-        final var range = Entry.of(longBits);
-
-        final var headIt = headIter(range);
-        if (headIt.hasNext()) {
-            final var head = headIt.next();
-            if (head.contains(longBits)) {
-                return;
-            }
-            if (head.upperBits + 1 == longBits) {
-                head.upperBits = longBits;
-                final var tailSet = ranges.tailSet(range);
-                if (!tailSet.isEmpty()) {
-                    final var tail = tailSet.first();
-                    if (tail.lowerBits - 1 == longBits) {
-                        tail.lowerBits = head.lowerBits;
-                        headIt.remove();
-                    }
-                }
-                return;
-            }
-        }
-
-        final var tailSet = ranges.tailSet(range);
-        if (!tailSet.isEmpty()) {
-            final var tail = tailSet.first();
-            if (tail.lowerBits - 1 == longBits) {
-                tail.lowerBits = longBits;
-                return;
-            }
-        }
-
-        ranges.add(range);
-    }
-
     public final boolean contains(final long longBits) {
-        final var headIt = headIter(Entry.of(longBits));
-        return headIt.hasNext() && headIt.next().contains(longBits);
+        final var head = ranges.floor(Entry.of(longBits));
+        return head != null
+            && Long.compareUnsigned(head.lowerBits, longBits) <= 0
+            && Long.compareUnsigned(head.upperBits, longBits) >= 0;
     }
 
     public final boolean isEmpty() {
@@ -197,11 +152,7 @@ abstract class UnsignedLongSet {
     public abstract @NonNull ImmutableUnsignedLongSet immutableCopy();
 
     public final @NonNull MutableUnsignedLongSet mutableCopy() {
-        return new MutableUnsignedLongSet(copyRanges());
-    }
-
-    final @NonNull TreeSet<Entry> copyRanges() {
-        return new TreeSet<>(Collections2.transform(ranges, Entry::copy));
+        return new MutableUnsignedLongSet(new TreeSet<>(copiedRanges()));
     }
 
     public final @NonNull NavigableSet<Entry> ranges() {
@@ -212,6 +163,10 @@ abstract class UnsignedLongSet {
         return ranges;
     }
 
+    final @NonNull Collection<Entry> copiedRanges() {
+        return Collections2.transform(ranges, Entry::copy);
+    }
+
     @Override
     public final int hashCode() {
         return ranges.hashCode();
@@ -239,8 +194,4 @@ abstract class UnsignedLongSet {
 
         return helper.add("size", size).toString();
     }
-
-    private Iterator<Entry> headIter(final Entry range) {
-        return ranges.headSet(range, true).descendingIterator();
-    }
 }