Add UnsignedLongBitmap 10/98310/13
authorRobert Varga <robert.varga@pantheon.tech>
Sat, 6 Nov 2021 15:04:48 +0000 (16:04 +0100)
committerRobert Varga <robert.varga@pantheon.tech>
Mon, 8 Nov 2021 20:34:31 +0000 (21:34 +0100)
Rather than using a ImmutableMap<UnsignedLong, Boolean>, we can do
have a much denser representation with a specialized class. Here we
are introducing an explicit UnsignedLongBitmap, which stores an array
of longs and an array of booleans, ditching the intermediate objects.

Also clean up error reporting, throwing an IOException instead of a
VerifyException when things should go south unexpectedly.

JIRA: CONTROLLER-2013
Change-Id: Ie64da0af68ea2898dc77368afd4fce8abd2cccea
Signed-off-by: Robert Varga <robert.varga@pantheon.tech>
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/persisted/FrontendHistoryMetadata.java
opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongBitmap.java [new file with mode: 0644]
opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/persisted/FrontendShardDataTreeSnapshotMetadataTest.java
opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongBitmapTest.java [new file with mode: 0644]

index 72bab44..b00d25d 100644 (file)
@@ -19,6 +19,7 @@ import org.opendaylight.controller.cluster.access.concepts.LocalHistoryIdentifie
 import org.opendaylight.controller.cluster.access.concepts.TransactionIdentifier;
 import org.opendaylight.controller.cluster.datastore.persisted.FrontendHistoryMetadata;
 import org.opendaylight.controller.cluster.datastore.utils.MutableUnsignedLongSet;
 import org.opendaylight.controller.cluster.access.concepts.TransactionIdentifier;
 import org.opendaylight.controller.cluster.datastore.persisted.FrontendHistoryMetadata;
 import org.opendaylight.controller.cluster.datastore.utils.MutableUnsignedLongSet;
+import org.opendaylight.controller.cluster.datastore.utils.UnsignedLongBitmap;
 import org.opendaylight.yangtools.concepts.Builder;
 import org.opendaylight.yangtools.concepts.Identifiable;
 
 import org.opendaylight.yangtools.concepts.Builder;
 import org.opendaylight.yangtools.concepts.Identifiable;
 
@@ -39,7 +40,7 @@ final class FrontendHistoryMetadataBuilder implements Builder<FrontendHistoryMet
 
     FrontendHistoryMetadataBuilder(final ClientIdentifier clientId, final FrontendHistoryMetadata meta) {
         identifier = new LocalHistoryIdentifier(clientId, meta.getHistoryId(), meta.getCookie());
 
     FrontendHistoryMetadataBuilder(final ClientIdentifier clientId, final FrontendHistoryMetadata meta) {
         identifier = new LocalHistoryIdentifier(clientId, meta.getHistoryId(), meta.getCookie());
-        closedTransactions = new HashMap<>(meta.getClosedTransactions());
+        closedTransactions = meta.getClosedTransactions().mutableCopy();
         purgedTransactions = meta.getPurgedTransactions().mutableCopy();
         closed = meta.isClosed();
     }
         purgedTransactions = meta.getPurgedTransactions().mutableCopy();
         closed = meta.isClosed();
     }
@@ -52,7 +53,7 @@ final class FrontendHistoryMetadataBuilder implements Builder<FrontendHistoryMet
     @Override
     public FrontendHistoryMetadata build() {
         return new FrontendHistoryMetadata(identifier.getHistoryId(), identifier.getCookie(), closed,
     @Override
     public FrontendHistoryMetadata build() {
         return new FrontendHistoryMetadata(identifier.getHistoryId(), identifier.getCookie(), closed,
-            closedTransactions, purgedTransactions.immutableCopy());
+            UnsignedLongBitmap.copyOf(closedTransactions), purgedTransactions.immutableCopy());
     }
 
     void onHistoryClosed() {
     }
 
     void onHistoryClosed() {
index 7e27f86..c698ccf 100644 (file)
@@ -10,33 +10,28 @@ package org.opendaylight.controller.cluster.datastore.persisted;
 import static java.util.Objects.requireNonNull;
 
 import com.google.common.base.MoreObjects;
 import static java.util.Objects.requireNonNull;
 
 import com.google.common.base.MoreObjects;
-import com.google.common.base.Verify;
-import com.google.common.collect.ImmutableMap;
-import com.google.common.primitives.UnsignedLong;
 import java.io.DataInput;
 import java.io.DataOutput;
 import java.io.IOException;
 import java.io.DataInput;
 import java.io.DataOutput;
 import java.io.IOException;
-import java.util.HashMap;
-import java.util.Map;
-import java.util.Map.Entry;
 import org.eclipse.jdt.annotation.NonNull;
 import org.opendaylight.controller.cluster.datastore.utils.ImmutableUnsignedLongSet;
 import org.eclipse.jdt.annotation.NonNull;
 import org.opendaylight.controller.cluster.datastore.utils.ImmutableUnsignedLongSet;
+import org.opendaylight.controller.cluster.datastore.utils.UnsignedLongBitmap;
 import org.opendaylight.yangtools.concepts.WritableObject;
 import org.opendaylight.yangtools.concepts.WritableObjects;
 
 public final class FrontendHistoryMetadata implements WritableObject {
     private final @NonNull ImmutableUnsignedLongSet purgedTransactions;
 import org.opendaylight.yangtools.concepts.WritableObject;
 import org.opendaylight.yangtools.concepts.WritableObjects;
 
 public final class FrontendHistoryMetadata implements WritableObject {
     private final @NonNull ImmutableUnsignedLongSet purgedTransactions;
-    private final @NonNull ImmutableMap<UnsignedLong, Boolean> closedTransactions;
+    private final @NonNull UnsignedLongBitmap closedTransactions;
     private final long historyId;
     private final long cookie;
     private final boolean closed;
 
     public FrontendHistoryMetadata(final long historyId, final long cookie, final boolean closed,
     private final long historyId;
     private final long cookie;
     private final boolean closed;
 
     public FrontendHistoryMetadata(final long historyId, final long cookie, final boolean closed,
-            final Map<UnsignedLong, Boolean> closedTransactions, final ImmutableUnsignedLongSet purgedTransactions) {
+            final UnsignedLongBitmap closedTransactions, final ImmutableUnsignedLongSet purgedTransactions) {
         this.historyId = historyId;
         this.cookie = cookie;
         this.closed = closed;
         this.historyId = historyId;
         this.cookie = cookie;
         this.closed = closed;
-        this.closedTransactions = ImmutableMap.copyOf(closedTransactions);
+        this.closedTransactions = requireNonNull(closedTransactions);
         this.purgedTransactions = requireNonNull(purgedTransactions);
     }
 
         this.purgedTransactions = requireNonNull(purgedTransactions);
     }
 
@@ -52,7 +47,7 @@ public final class FrontendHistoryMetadata implements WritableObject {
         return closed;
     }
 
         return closed;
     }
 
-    public ImmutableMap<UnsignedLong, Boolean> getClosedTransactions() {
+    public UnsignedLongBitmap getClosedTransactions() {
         return closedTransactions;
     }
 
         return closedTransactions;
     }
 
@@ -65,45 +60,43 @@ public final class FrontendHistoryMetadata implements WritableObject {
         WritableObjects.writeLongs(out, historyId, cookie);
         out.writeBoolean(closed);
 
         WritableObjects.writeLongs(out, historyId, cookie);
         out.writeBoolean(closed);
 
+        final int closedSize = closedTransactions.size();
         final int purgedSize = purgedTransactions.size();
         final int purgedSize = purgedTransactions.size();
-        WritableObjects.writeLongs(out, closedTransactions.size(), purgedSize);
-        for (Entry<UnsignedLong, Boolean> e : closedTransactions.entrySet()) {
-            WritableObjects.writeLong(out, e.getKey().longValue());
-            out.writeBoolean(e.getValue());
-        }
+        WritableObjects.writeLongs(out, closedSize, purgedSize);
+        closedTransactions.writeEntriesTo(out, closedSize);
         purgedTransactions.writeRangesTo(out, purgedSize);
     }
 
     public static FrontendHistoryMetadata readFrom(final DataInput in) throws IOException {
         purgedTransactions.writeRangesTo(out, purgedSize);
     }
 
     public static FrontendHistoryMetadata readFrom(final DataInput in) throws IOException {
-        byte header = WritableObjects.readLongHeader(in);
-        final long historyId = WritableObjects.readFirstLong(in, header);
-        final long cookie = WritableObjects.readSecondLong(in, header);
+        final byte firstHdr = WritableObjects.readLongHeader(in);
+        final long historyId = WritableObjects.readFirstLong(in, firstHdr);
+        final long cookie = WritableObjects.readSecondLong(in, firstHdr);
         final boolean closed = in.readBoolean();
 
         final boolean closed = in.readBoolean();
 
-        header = WritableObjects.readLongHeader(in);
-        long ls = WritableObjects.readFirstLong(in, header);
-        Verify.verify(ls >= 0 && ls <= Integer.MAX_VALUE);
-        final int csize = (int) ls;
-
-        ls = WritableObjects.readSecondLong(in, header);
-        Verify.verify(ls >= 0 && ls <= Integer.MAX_VALUE);
-        final int psize = (int) ls;
-
-        final Map<UnsignedLong, Boolean> closedTransactions = new HashMap<>(csize);
-        for (int i = 0; i < csize; ++i) {
-            final UnsignedLong key = UnsignedLong.fromLongBits(WritableObjects.readLong(in));
-            final Boolean value = in.readBoolean();
-            closedTransactions.put(key, value);
-        }
-        final var purgedTransactions = ImmutableUnsignedLongSet.readFrom(in, psize);
+        final byte secondHdr = WritableObjects.readLongHeader(in);
+        final int csize = verifySize(WritableObjects.readFirstLong(in, secondHdr));
+        final int psize = verifySize(WritableObjects.readSecondLong(in, secondHdr));
 
 
-        return new FrontendHistoryMetadata(historyId, cookie, closed, closedTransactions, purgedTransactions);
+        return new FrontendHistoryMetadata(historyId, cookie, closed,
+            UnsignedLongBitmap.readFrom(in, csize),
+            ImmutableUnsignedLongSet.readFrom(in, psize));
     }
 
     @Override
     public String toString() {
     }
 
     @Override
     public String toString() {
-        return MoreObjects.toStringHelper(FrontendHistoryMetadata.class).add("historyId", historyId)
-                .add("cookie", cookie).add("closed", closed).add("closedTransactions", closedTransactions)
-                .add("purgedTransactions", purgedTransactions).toString();
+        return MoreObjects.toStringHelper(FrontendHistoryMetadata.class)
+            .add("historyId", historyId)
+            .add("cookie", cookie)
+            .add("closed", closed)
+            .add("closedTransactions", closedTransactions)
+            .add("purgedTransactions", purgedTransactions)
+            .toString();
+    }
+
+    private static int verifySize(final long size) throws IOException {
+        if (size < 0 || size > Integer.MAX_VALUE) {
+            throw new IOException("Invalid size " + size);
+        }
+        return (int) size;
     }
 }
     }
 }
diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongBitmap.java b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongBitmap.java
new file mode 100644 (file)
index 0000000..1d64e10
--- /dev/null
@@ -0,0 +1,281 @@
+/*
+ * 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.annotations.VisibleForTesting;
+import com.google.common.collect.Maps;
+import com.google.common.primitives.UnsignedLong;
+import edu.umd.cs.findbugs.annotations.SuppressFBWarnings;
+import java.io.DataInput;
+import java.io.DataOutput;
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Comparator;
+import java.util.HashMap;
+import java.util.Map;
+import java.util.Map.Entry;
+import org.eclipse.jdt.annotation.NonNull;
+import org.opendaylight.yangtools.concepts.Immutable;
+import org.opendaylight.yangtools.concepts.WritableObjects;
+
+/**
+ * A more efficient equivalent of {@code ImmutableMap<UnsignedLong, Boolean>}.
+ */
+@Beta
+public abstract class UnsignedLongBitmap implements Immutable {
+    @VisibleForTesting
+    static final class Regular extends UnsignedLongBitmap {
+        private final long[] keys;
+        private final boolean[] values;
+
+        Regular(final long[] keys, final boolean[] values) {
+            this.keys = requireNonNull(keys);
+            this.values = requireNonNull(values);
+            verify(keys.length == values.length);
+        }
+
+        @Override
+        public boolean isEmpty() {
+            return keys.length == 0;
+        }
+
+        @Override
+        public int size() {
+            return keys.length;
+        }
+
+        @Override
+        void writeEntriesTo(final DataOutput out) throws IOException {
+            for (int i = 0; i < keys.length; ++i) {
+                writeEntry(out, keys[i], values[i]);
+            }
+        }
+
+        @Override
+        StringBuilder appendEntries(final StringBuilder sb) {
+            final int last = keys.length - 1;
+            for (int i = 0; i < last; ++i) {
+                appendEntry(sb, keys[i], values[i]).append(", ");
+            }
+            return appendEntry(sb, keys[last], values[last]);
+        }
+
+        @Override
+        void putEntries(final HashMap<UnsignedLong, Boolean> ret) {
+            for (int i = 0; i < keys.length; ++i) {
+                ret.put(UnsignedLong.fromLongBits(keys[i]), values[i]);
+            }
+        }
+
+        @Override
+        public int hashCode() {
+            return Arrays.hashCode(keys) ^ Arrays.hashCode(values);
+        }
+
+        @Override
+        public boolean equals(final Object obj) {
+            if (obj == this) {
+                return true;
+            }
+            if (!(obj instanceof Regular)) {
+                return false;
+            }
+            final var other = (Regular) obj;
+            return Arrays.equals(keys, other.keys) && Arrays.equals(values, other.values);
+        }
+    }
+
+    private static final class Singleton extends UnsignedLongBitmap {
+        private final long key;
+        private final boolean value;
+
+        Singleton(final long key, final boolean value) {
+            this.key = key;
+            this.value = value;
+        }
+
+        @Override
+        public boolean isEmpty() {
+            return false;
+        }
+
+        @Override
+        public int size() {
+            return 1;
+        }
+
+        @Override
+        void writeEntriesTo(final DataOutput out) throws IOException {
+            writeEntry(out, key, value);
+        }
+
+        @Override
+        StringBuilder appendEntries(final StringBuilder sb) {
+            return sb.append(Long.toUnsignedString(key)).append('=').append(value);
+        }
+
+        @Override
+        void putEntries(final HashMap<UnsignedLong, Boolean> ret) {
+            ret.put(UnsignedLong.fromLongBits(key), value);
+        }
+
+        @Override
+        public int hashCode() {
+            return Long.hashCode(key) ^ Boolean.hashCode(value);
+        }
+
+        @Override
+        public boolean equals(final Object obj) {
+            if (obj == this) {
+                return true;
+            }
+            if (!(obj instanceof Singleton)) {
+                return false;
+            }
+            final var other = (Singleton) obj;
+            return key == other.key && value == other.value;
+        }
+    }
+
+    private static final @NonNull UnsignedLongBitmap EMPTY = new Regular(new long[0], new boolean[0]);
+
+    private UnsignedLongBitmap() {
+        // Hidden on purpose
+    }
+
+    public static @NonNull UnsignedLongBitmap of() {
+        return EMPTY;
+    }
+
+    public static @NonNull UnsignedLongBitmap of(final long keyBits, final boolean value) {
+        return new Singleton(keyBits, value);
+    }
+
+    public static @NonNull UnsignedLongBitmap copyOf(final Map<UnsignedLong, Boolean> map) {
+        final int size = map.size();
+        switch (size) {
+            case 0:
+                return of();
+            case 1:
+                final var entry = map.entrySet().iterator().next();
+                return of(entry.getKey().longValue(), entry.getValue());
+            default:
+                final var entries = new ArrayList<>(map.entrySet());
+                entries.sort(Comparator.comparing(Entry::getKey));
+
+                final var keys = new long[size];
+                final var values = new boolean[size];
+
+                int idx = 0;
+                for (var e : entries) {
+                    keys[idx] = e.getKey().longValue();
+                    values[idx] = e.getValue();
+                    ++idx;
+                }
+
+                return new Regular(keys, values);
+        }
+    }
+
+    public abstract boolean isEmpty();
+
+    public abstract int size();
+
+    public final @NonNull HashMap<UnsignedLong, Boolean> mutableCopy() {
+        final int size = size();
+        switch (size) {
+            case 0:
+                return new HashMap<>();
+            default:
+                final var ret = Maps.<UnsignedLong, Boolean>newHashMapWithExpectedSize(size);
+                putEntries(ret);
+                return ret;
+        }
+    }
+
+    public static @NonNull UnsignedLongBitmap readFrom(final @NonNull DataInput in, final int size) throws IOException {
+        switch (size) {
+            case 0:
+                return of();
+            case 1:
+                return new Singleton(WritableObjects.readLong(in), in.readBoolean());
+            default:
+                final var keys = new long[size];
+                final var values = new boolean[size];
+                for (int i = 0; i < size; ++i) {
+                    keys[i] = WritableObjects.readLong(in);
+                    values[i] = in.readBoolean();
+                }
+
+                // There should be no duplicates and the IDs need to be increasing
+                long prevKey = keys[0];
+                for (int i = 1; i < size; ++i) {
+                    final long key = keys[i];
+                    if (Long.compareUnsigned(prevKey, key) >= 0) {
+                        throw new IOException("Key " + Long.toUnsignedString(key) + " may not be used after key "
+                            + Long.toUnsignedString(prevKey));
+                    }
+                    prevKey = key;
+                }
+
+                return new Regular(keys, values);
+        }
+    }
+
+    public void writeEntriesTo(final @NonNull DataOutput out, final int size) throws IOException {
+        if (size != size()) {
+            throw new IOException("Mismatched size: expected " + size() + ", got " + size);
+        }
+        writeEntriesTo(out);
+    }
+
+    abstract void writeEntriesTo(@NonNull DataOutput out) throws IOException;
+
+    abstract StringBuilder appendEntries(StringBuilder sb);
+
+    abstract void putEntries(HashMap<UnsignedLong, Boolean> ret);
+
+    /**
+     * {@inheritDoc}
+     *
+     * <p>
+     * Implementations of this method return a deterministic value.
+     */
+    @Override
+    public abstract int hashCode();
+
+    @Override
+    public abstract boolean equals(Object obj);
+
+    @Override
+    public final String toString() {
+        return isEmpty() ? "{}" : appendEntries(new StringBuilder().append('{')).append('}').toString();
+    }
+
+    @SuppressFBWarnings(value = "UPM_UNCALLED_PRIVATE_METHOD",
+        justification = "https://github.com/spotbugs/spotbugs/issues/811")
+    private static StringBuilder appendEntry(final StringBuilder sb, final long key, final boolean value) {
+        return sb.append(Long.toUnsignedString(key)).append('=').append(value);
+    }
+
+    @SuppressFBWarnings(value = "UPM_UNCALLED_PRIVATE_METHOD",
+        justification = "https://github.com/spotbugs/spotbugs/issues/811")
+    private static void writeEntry(final @NonNull DataOutput out, final long key, final boolean value)
+            throws IOException {
+        // FIXME: This serialization format is what we inherited. We could do better by storing the boolean in
+        //        writeLong()'s flags. On the other had, we could also be writing longs by twos, which might be
+        //        benefitial.
+        WritableObjects.writeLong(out, key);
+        out.writeBoolean(value);
+    }
+}
index c02cea9..7daafcd 100644 (file)
@@ -13,7 +13,6 @@ import static org.junit.Assert.assertFalse;
 import static org.junit.Assert.assertThrows;
 import static org.junit.Assert.assertTrue;
 
 import static org.junit.Assert.assertThrows;
 import static org.junit.Assert.assertTrue;
 
-import com.google.common.collect.ImmutableMap;
 import com.google.common.primitives.UnsignedLong;
 import java.io.ByteArrayInputStream;
 import java.io.ByteArrayOutputStream;
 import com.google.common.primitives.UnsignedLong;
 import java.io.ByteArrayInputStream;
 import java.io.ByteArrayOutputStream;
@@ -31,6 +30,7 @@ import org.opendaylight.controller.cluster.access.concepts.FrontendType;
 import org.opendaylight.controller.cluster.access.concepts.MemberName;
 import org.opendaylight.controller.cluster.datastore.utils.ImmutableUnsignedLongSet;
 import org.opendaylight.controller.cluster.datastore.utils.MutableUnsignedLongSet;
 import org.opendaylight.controller.cluster.access.concepts.MemberName;
 import org.opendaylight.controller.cluster.datastore.utils.ImmutableUnsignedLongSet;
 import org.opendaylight.controller.cluster.datastore.utils.MutableUnsignedLongSet;
+import org.opendaylight.controller.cluster.datastore.utils.UnsignedLongBitmap;
 
 public class FrontendShardDataTreeSnapshotMetadataTest {
 
 
 public class FrontendShardDataTreeSnapshotMetadataTest {
 
@@ -108,8 +108,8 @@ public class FrontendShardDataTreeSnapshotMetadataTest {
         final ImmutableUnsignedLongSet purgedHistories = tmp.immutableCopy();
 
         return new FrontendClientMetadata(clientIdentifier, purgedHistories.immutableCopy(), List.of(
         final ImmutableUnsignedLongSet purgedHistories = tmp.immutableCopy();
 
         return new FrontendClientMetadata(clientIdentifier, purgedHistories.immutableCopy(), List.of(
-            new FrontendHistoryMetadata(num, num, true, ImmutableMap.of(UnsignedLong.ZERO, Boolean.TRUE),
-                purgedHistories)));
+            new FrontendHistoryMetadata(num, num, true,
+                UnsignedLongBitmap.copyOf(Map.of(UnsignedLong.ZERO, Boolean.TRUE)), purgedHistories)));
     }
 
     private static <T> void testObject(final T object, final T equalObject) {
     }
 
     private static <T> void testObject(final T object, final T equalObject) {
diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongBitmapTest.java b/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongBitmapTest.java
new file mode 100644 (file)
index 0000000..fc0b490
--- /dev/null
@@ -0,0 +1,150 @@
+/*
+ * 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.assertNotEquals;
+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 com.google.common.base.VerifyException;
+import com.google.common.io.ByteStreams;
+import com.google.common.primitives.UnsignedLong;
+import java.io.DataOutput;
+import java.io.IOException;
+import java.util.Map;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.mockito.junit.MockitoJUnitRunner;
+import org.opendaylight.controller.cluster.datastore.utils.UnsignedLongBitmap.Regular;
+import org.opendaylight.yangtools.concepts.WritableObjects;
+
+@RunWith(MockitoJUnitRunner.StrictStubs.class)
+public class UnsignedLongBitmapTest {
+    @Test
+    public void testEmpty() throws IOException {
+        final var empty = UnsignedLongBitmap.of();
+        assertTrue(empty.isEmpty());
+        assertEquals(empty, empty);
+        assertSame(empty, UnsignedLongBitmap.copyOf(Map.of()));
+        assertEquals(Map.of(), empty.mutableCopy());
+        assertEquals("{}", empty.toString());
+        assertEquals(0, empty.hashCode());
+
+        final var ex = assertThrows(IOException.class, () -> empty.writeEntriesTo(mock(DataOutput.class), 1));
+        assertEquals("Mismatched size: expected 0, got 1", ex.getMessage());
+
+        // Should not do anything
+        empty.writeEntriesTo(mock(DataOutput.class), 0);
+
+        assertSame(empty, assertWriteToReadFrom(empty));
+    }
+
+    @Test
+    public void testSingleton() {
+        final var one = UnsignedLongBitmap.of(0, false);
+        assertFalse(one.isEmpty());
+        assertEquals(1, one.size());
+        assertEquals(one, one);
+        assertEquals(one, UnsignedLongBitmap.of(0, false));
+        assertEquals(one, UnsignedLongBitmap.copyOf(Map.of(UnsignedLong.ZERO, false)));
+        assertEquals(Map.of(UnsignedLong.ZERO, false), one.mutableCopy());
+        assertEquals("{0=false}", one.toString());
+        assertEquals(1237, one.hashCode());
+
+        final var ex = assertThrows(IOException.class, () -> one.writeEntriesTo(mock(DataOutput.class), 0));
+        assertEquals("Mismatched size: expected 1, got 0", ex.getMessage());
+
+        assertEquals(one, UnsignedLongBitmap.of(0, false));
+        assertNotEquals(one, UnsignedLongBitmap.of(0, true));
+        assertNotEquals(one, UnsignedLongBitmap.of(1, false));
+        assertNotEquals(UnsignedLongBitmap.of(), one);
+        assertNotEquals(one, UnsignedLongBitmap.of());
+
+        assertWriteToReadFrom(one);
+    }
+
+    @Test
+    public void testRegular() {
+        final var one = UnsignedLongBitmap.copyOf(Map.of(UnsignedLong.ZERO, false, UnsignedLong.ONE, true));
+        assertFalse(one.isEmpty());
+        assertEquals(2, one.size());
+        assertEquals(one, one);
+        assertEquals(one, UnsignedLongBitmap.copyOf(Map.of(UnsignedLong.ONE, true, UnsignedLong.ZERO, false)));
+        assertEquals(Map.of(UnsignedLong.ZERO, false, UnsignedLong.ONE, true), one.mutableCopy());
+
+        assertNotEquals(one,
+            UnsignedLongBitmap.copyOf(Map.of(UnsignedLong.ZERO, false, UnsignedLong.valueOf(2), true)));
+        assertEquals("{0=false, 1=true}", one.toString());
+        assertEquals(40345, one.hashCode());
+
+        final var ex = assertThrows(IOException.class, () -> one.writeEntriesTo(mock(DataOutput.class), 1));
+        assertEquals("Mismatched size: expected 2, got 1", ex.getMessage());
+
+        final var two = UnsignedLongBitmap.copyOf(Map.of(UnsignedLong.ZERO, true, UnsignedLong.ONE, false));
+        assertFalse(two.isEmpty());
+        assertEquals(2, two.size());
+        assertEquals(two, two);
+        assertEquals(two, UnsignedLongBitmap.copyOf(Map.of(UnsignedLong.ZERO, true, UnsignedLong.ONE, false)));
+        assertEquals("{0=true, 1=false}", two.toString());
+        assertEquals(40549, two.hashCode());
+
+        assertNotEquals(one, two);
+        assertNotEquals(two, one);
+
+        assertWriteToReadFrom(one);
+        assertWriteToReadFrom(two);
+    }
+
+    private static UnsignedLongBitmap assertWriteToReadFrom(final UnsignedLongBitmap orig) {
+        final var dos = ByteStreams.newDataOutput();
+        try {
+            orig.writeEntriesTo(dos);
+        } catch (IOException e) {
+            throw new AssertionError(e);
+        }
+
+        final UnsignedLongBitmap copy;
+        try {
+            final var dis = ByteStreams.newDataInput(dos.toByteArray());
+            copy = UnsignedLongBitmap.readFrom(dis, orig.size());
+            assertThrows(IllegalStateException.class, () -> dis.readByte());
+        } catch (IOException e) {
+            throw new AssertionError(e);
+        }
+
+        assertEquals(orig, copy);
+        return copy;
+    }
+
+    @Test
+    public void testKeyOrder() throws IOException {
+        assertInvalidKey(0);
+        assertInvalidKey(1);
+    }
+
+    private static void assertInvalidKey(final long second) throws IOException {
+        final var out = ByteStreams.newDataOutput();
+        WritableObjects.writeLong(out, 1);
+        out.writeBoolean(false);
+        WritableObjects.writeLong(out, second);
+        out.writeBoolean(true);
+
+        final var ex = assertThrows(IOException.class,
+            () -> UnsignedLongBitmap.readFrom(ByteStreams.newDataInput(out.toByteArray()), 2));
+        assertEquals("Key " + second + " may not be used after key 1", ex.getMessage());
+    }
+
+    @Test
+    public void testInvalidArrays() {
+        assertThrows(VerifyException.class, () -> new Regular(new long[0], new boolean[] { false, false }));
+    }
+}