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;
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();
}
@Override
public FrontendHistoryMetadata build() {
return new FrontendHistoryMetadata(identifier.getHistoryId(), identifier.getCookie(), closed,
- closedTransactions, purgedTransactions.immutableCopy());
+ UnsignedLongBitmap.copyOf(closedTransactions), purgedTransactions.immutableCopy());
}
void onHistoryClosed() {
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.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.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;
- 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,
- final Map<UnsignedLong, Boolean> closedTransactions, final ImmutableUnsignedLongSet purgedTransactions) {
+ final UnsignedLongBitmap closedTransactions, final ImmutableUnsignedLongSet purgedTransactions) {
this.historyId = historyId;
this.cookie = cookie;
this.closed = closed;
- this.closedTransactions = ImmutableMap.copyOf(closedTransactions);
+ this.closedTransactions = requireNonNull(closedTransactions);
this.purgedTransactions = requireNonNull(purgedTransactions);
}
return closed;
}
- public ImmutableMap<UnsignedLong, Boolean> getClosedTransactions() {
+ public UnsignedLongBitmap getClosedTransactions() {
return closedTransactions;
}
WritableObjects.writeLongs(out, historyId, cookie);
out.writeBoolean(closed);
+ final int closedSize = closedTransactions.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 {
- 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();
- 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() {
- 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;
}
}
--- /dev/null
+/*
+ * 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);
+ }
+}
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 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 {
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) {
--- /dev/null
+/*
+ * 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 }));
+ }
+}
Code Review / controller.git / commitdiff