Use ImmutableSortedSet for small ImmutableUnsignedLongSets 07/98307/5
authorRobert Varga <robert.varga@pantheon.tech>
Sat, 6 Nov 2021 13:31:20 +0000 (14:31 +0100)
committerRobert Varga <robert.varga@pantheon.tech>
Sat, 6 Nov 2021 14:04:33 +0000 (15:04 +0100)
This adds a bit of indirection, but for a few entries this ends up
using arrays instead of an RB tree, offering better density.

JIRA: CONTROLLER-2012
Change-Id: I09714c6bf3272946f6cee4360f80a106453d0e61
Signed-off-by: Robert Varga <robert.varga@pantheon.tech>
opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/ImmutableUnsignedLongSet.java
opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/MutableUnsignedLongSet.java
opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongSet.java
opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongSetTest.java

index e6c900b..47b8a8b 100644 (file)
@@ -8,9 +8,12 @@
 package org.opendaylight.controller.cluster.datastore.utils;
 
 import com.google.common.annotations.Beta;
+import com.google.common.collect.ImmutableSortedSet;
 import java.io.DataInput;
 import java.io.DataOutput;
 import java.io.IOException;
+import java.util.ArrayList;
+import java.util.NavigableSet;
 import java.util.TreeSet;
 import org.eclipse.jdt.annotation.NonNull;
 import org.opendaylight.yangtools.concepts.Immutable;
@@ -18,14 +21,24 @@ 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<>());
+    // Do not all
+    private static final int ARRAY_MAX_ELEMENTS = 4096;
 
-    private ImmutableUnsignedLongSet(final TreeSet<Entry> ranges) {
+    private static final @NonNull ImmutableUnsignedLongSet EMPTY =
+        new ImmutableUnsignedLongSet(ImmutableSortedSet.of());
+
+    private ImmutableUnsignedLongSet(final NavigableSet<Entry> ranges) {
         super(ranges);
     }
 
-    static @NonNull ImmutableUnsignedLongSet of(final TreeSet<Entry> ranges) {
-        return ranges.isEmpty() ? EMPTY : new ImmutableUnsignedLongSet(ranges);
+    static @NonNull ImmutableUnsignedLongSet copyOf(final MutableUnsignedLongSet mutable) {
+        if (mutable.isEmpty()) {
+            return of();
+        }
+        if (mutable.size() <= ARRAY_MAX_ELEMENTS) {
+            return new ImmutableUnsignedLongSet(ImmutableSortedSet.copyOfSorted(mutable.trustedRanges()));
+        }
+        return new ImmutableUnsignedLongSet(new TreeSet<>(mutable.trustedRanges()));
     }
 
     public static @NonNull ImmutableUnsignedLongSet of() {
@@ -46,9 +59,18 @@ public final class ImmutableUnsignedLongSet extends UnsignedLongSet implements I
             return EMPTY;
         }
 
-        final var ranges = new TreeSet<Entry>();
-        for (int i = 0; i < size; ++i) {
-            ranges.add(Entry.readUnsigned(in));
+        final NavigableSet<Entry> ranges;
+        if (size <= ARRAY_MAX_ELEMENTS) {
+            final var entries = new ArrayList<Entry>(size);
+            for (int i = 0; i < size; ++i) {
+                entries.add(Entry.readUnsigned(in));
+            }
+            ranges = ImmutableSortedSet.copyOf(entries);
+        } else {
+            ranges = new TreeSet<>();
+            for (int i = 0; i < size; ++i) {
+                ranges.add(Entry.readUnsigned(in));
+            }
         }
         return new ImmutableUnsignedLongSet(ranges);
     }
index e8e479c..e455f90 100644 (file)
@@ -27,7 +27,7 @@ public final class MutableUnsignedLongSet extends UnsignedLongSet implements Mut
 
     @Override
     public ImmutableUnsignedLongSet immutableCopy() {
-        return ImmutableUnsignedLongSet.of(copyRanges());
+        return ImmutableUnsignedLongSet.copyOf(this);
     }
 
     public void add(final long longBits) {
index 4d4b99b..466c027 100644 (file)
@@ -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;
@@ -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);
@@ -136,13 +128,13 @@ 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);
     }
 
@@ -197,11 +189,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<>(Collections2.transform(ranges, Entry::copy)));
     }
 
     public final @NonNull NavigableSet<Entry> ranges() {
index 1a67547..af71c42 100644 (file)
@@ -10,15 +10,24 @@ 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.assertNotEquals;
+import static org.junit.Assert.assertNotSame;
+import static org.junit.Assert.assertSame;
+import static org.junit.Assert.assertThrows;
 import static org.junit.Assert.assertTrue;
+import static org.mockito.Mockito.mock;
 
 import java.io.ByteArrayInputStream;
 import java.io.ByteArrayOutputStream;
 import java.io.DataInputStream;
+import java.io.DataOutput;
 import java.io.DataOutputStream;
 import java.io.IOException;
 import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.mockito.junit.MockitoJUnitRunner;
 
+@RunWith(MockitoJUnitRunner.StrictStubs.class)
 public class UnsignedLongSetTest {
     @Test
     public void testOperations() {
@@ -86,4 +95,42 @@ public class UnsignedLongSetTest {
         set.add(3);
         assertEquals("[[0..2), [3..5)]", set.toRangeSet().toString());
     }
+
+    @Test
+    public void testEmptyCopy() {
+        final var orig = MutableUnsignedLongSet.of();
+        assertSame(ImmutableUnsignedLongSet.of(), orig.immutableCopy());
+        final var copy = orig.mutableCopy();
+        assertEquals(orig, copy);
+        assertNotSame(orig, copy);
+    }
+
+    @Test
+    public void testMutableCopy() {
+        final var orig = MutableUnsignedLongSet.of();
+        orig.add(-1);
+        assertEquals("MutableUnsignedLongSet{span=[18446744073709551615..18446744073709551615], size=1}",
+            orig.toString());
+
+        final var copy = orig.mutableCopy();
+        assertEquals(orig, copy);
+        assertNotSame(orig, copy);
+
+        orig.add(-2);
+        assertNotEquals(orig, copy);
+        assertEquals("MutableUnsignedLongSet{span=[18446744073709551614..18446744073709551615], size=1}",
+            orig.toString());
+    }
+
+    @Test
+    public void testWriteRangesTo() throws IOException {
+        ImmutableUnsignedLongSet.of().writeRangesTo(mock(DataOutput.class), 0);
+    }
+
+    @Test
+    public void testWriteRangesToViolation() {
+        final var ex = assertThrows(IOException.class,
+            () -> ImmutableUnsignedLongSet.of().writeRangesTo(mock(DataOutput.class), 1));
+        assertEquals("Mismatched size: expected 0, got 1", ex.getMessage());
+    }
 }