Add MutableUnsignedLongSet.addAll()

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

diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/MutableUnsignedLongSet.java b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/MutableUnsignedLongSet.java
index 689baad40b8225a5c2bb2f53145ca54dd2d07801..2b0dec3d57194c7a88cc262140ee0c50763426df 100644 (file)
--- a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/MutableUnsignedLongSet.java
+++ b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/MutableUnsignedLongSet.java
@@ -11,6 +11,7 @@ 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.NavigableSet;
 import java.util.TreeSet;
 import org.eclipse.jdt.annotation.NonNull;
 import org.opendaylight.yangtools.concepts.Mutable;
@@ -25,15 +26,35 @@ public final class MutableUnsignedLongSet extends UnsignedLongSet implements Mut
         return new MutableUnsignedLongSet(new TreeSet<>());
     }
 
+    public static @NonNull MutableUnsignedLongSet of(final long... ulongs) {
+        final var ret = MutableUnsignedLongSet.of();
+        for (long longBits : ulongs) {
+            ret.add(longBits);
+        }
+        return ret;
+    }
+
     @Override
     public ImmutableUnsignedLongSet immutableCopy() {
         return ImmutableUnsignedLongSet.copyOf(this);
     }
 
     public void add(final long longBits) {
+        addOne(trustedRanges(), Entry.of(longBits), longBits);
+    }
+
+    public void addAll(final UnsignedLongSet other) {
         final var ranges = trustedRanges();
-        final var range = Entry.of(longBits);
+        for (var range : other.trustedRanges()) {
+            if (range.lowerBits == range.upperBits) {
+                addOne(ranges, range, range.lowerBits);
+            } else {
+                addRange(ranges, range);
+            }
+        }
+    }
 
+    private static void addOne(final NavigableSet<Entry> ranges, final Entry range, final long longBits) {
         // We need Iterator.remove() to perform efficient merge below
         final var headIt = ranges.headSet(range, true).descendingIterator();
         if (headIt.hasNext()) {
@@ -73,6 +94,84 @@ public final class MutableUnsignedLongSet extends UnsignedLongSet implements Mut
         ranges.add(range);
     }
 
+    private static void addRange(final NavigableSet<Entry> ranges, final Entry range) {
+        // If the start of the range is already covered by an existing range, we can expand that
+        final var lower = ranges.floor(range);
+        if (lower != null && Long.compareUnsigned(lower.upperBits + 1, range.lowerBits) >= 0) {
+            expandLower(ranges, lower, range.upperBits);
+            return;
+        }
+
+        // If the end of the range is already covered by an existing range, we can expand that
+        final var upper = ranges.floor(Entry.of(range.upperBits));
+        if (upper != null && Long.compareUnsigned(upper.lowerBits - 1, range.upperBits) <= 0) {
+            // Quick check: if we did not find a lower range at all, we might be expanding the entire span, in which
+            // case upper needs to become the first entry
+            if (lower == null) {
+                ranges.headSet(upper, false).clear();
+            }
+
+            expandUpper(ranges, upper, range.lowerBits, range.upperBits);
+            return;
+        }
+
+        // No luck, insert
+        ranges.add(range);
+    }
+
+    private static void expandLower(final NavigableSet<Entry> ranges, final Entry entry, final long upperBits) {
+        if (Long.compareUnsigned(entry.upperBits, upperBits) >= 0) {
+            // Already contained, this is a no-op
+            return;
+        }
+
+        // Acquire any ranges after floor and clean them up
+        final var tailIt = ranges.tailSet(entry, false).iterator();
+        final long nextLower = upperBits + 1;
+        while (tailIt.hasNext()) {
+            final var tail = tailIt.next();
+            if (Long.compareUnsigned(tail.lowerBits, nextLower) > 0) {
+                // There is gap, nothing more to cleanup
+                break;
+            }
+
+            // We can merge this entry into floor...
+            tailIt.remove();
+
+            if (Long.compareUnsigned(tail.upperBits, nextLower) >= 0) {
+                // ... but we need to expand floor accordingly and after that we are done
+                entry.upperBits = tail.upperBits;
+                return;
+            }
+        }
+
+        // Expand floor to include this range and we are done
+        entry.upperBits = upperBits;
+    }
+
+    private static void expandUpper(final NavigableSet<Entry> ranges, final Entry entry, final long lowerBits,
+            final long upperBits) {
+        if (Long.compareUnsigned(entry.upperBits, upperBits) >= 0) {
+            // Upper end is already covered
+            entry.lowerBits = lowerBits;
+            return;
+        }
+
+        // We are expanding the entry's upper boundary, we need to check if we need to coalesce following entries
+        long newUpper = upperBits;
+        final var tailIt = ranges.tailSet(entry, false).iterator();
+        if (tailIt.hasNext()) {
+            final var tail = tailIt.next();
+            if (Long.compareUnsigned(tail.lowerBits, newUpper + 1) <= 0) {
+                tailIt.remove();
+                newUpper = tail.upperBits;
+            }
+        }
+
+        entry.lowerBits = lowerBits;
+        entry.upperBits = newUpper;
+    }
+
     public ImmutableRangeSet<UnsignedLong> toRangeSet() {
         return ImmutableRangeSet.copyOf(Collections2.transform(trustedRanges(), Entry::toUnsigned));
     }