2 * Copyright (c) 2021 PANTHEON.tech, s.r.o. and others. All rights reserved.
4 * This program and the accompanying materials are made available under the
5 * terms of the Eclipse Public License v1.0 which accompanies this distribution,
6 * and is available at http://www.eclipse.org/legal/epl-v10.html
8 package org.opendaylight.controller.cluster.datastore.utils;
10 import static com.google.common.base.Verify.verify;
11 import static java.util.Objects.requireNonNull;
13 import com.google.common.annotations.Beta;
14 import com.google.common.annotations.VisibleForTesting;
15 import com.google.common.collect.Maps;
16 import com.google.common.primitives.UnsignedLong;
17 import edu.umd.cs.findbugs.annotations.SuppressFBWarnings;
18 import java.io.DataInput;
19 import java.io.DataOutput;
20 import java.io.IOException;
21 import java.util.ArrayList;
22 import java.util.Arrays;
23 import java.util.Comparator;
24 import java.util.HashMap;
26 import java.util.Map.Entry;
27 import org.eclipse.jdt.annotation.NonNull;
28 import org.opendaylight.yangtools.concepts.Immutable;
29 import org.opendaylight.yangtools.concepts.WritableObjects;
32 * A more efficient equivalent of {@code ImmutableMap<UnsignedLong, Boolean>}.
35 public abstract class UnsignedLongBitmap implements Immutable {
37 static final class Regular extends UnsignedLongBitmap {
38 private final long[] keys;
39 private final boolean[] values;
41 Regular(final long[] keys, final boolean[] values) {
42 this.keys = requireNonNull(keys);
43 this.values = requireNonNull(values);
44 verify(keys.length == values.length);
48 public boolean isEmpty() {
49 return keys.length == 0;
58 void writeEntriesTo(final DataOutput out) throws IOException {
59 for (int i = 0; i < keys.length; ++i) {
60 writeEntry(out, keys[i], values[i]);
65 StringBuilder appendEntries(final StringBuilder sb) {
66 final int last = keys.length - 1;
67 for (int i = 0; i < last; ++i) {
68 appendEntry(sb, keys[i], values[i]).append(", ");
70 return appendEntry(sb, keys[last], values[last]);
74 void putEntries(final HashMap<UnsignedLong, Boolean> ret) {
75 for (int i = 0; i < keys.length; ++i) {
76 ret.put(UnsignedLong.fromLongBits(keys[i]), values[i]);
81 public int hashCode() {
82 return Arrays.hashCode(keys) ^ Arrays.hashCode(values);
86 public boolean equals(final Object obj) {
90 if (!(obj instanceof Regular)) {
93 final var other = (Regular) obj;
94 return Arrays.equals(keys, other.keys) && Arrays.equals(values, other.values);
98 private static final class Singleton extends UnsignedLongBitmap {
99 private final long key;
100 private final boolean value;
102 Singleton(final long key, final boolean value) {
108 public boolean isEmpty() {
118 void writeEntriesTo(final DataOutput out) throws IOException {
119 writeEntry(out, key, value);
123 StringBuilder appendEntries(final StringBuilder sb) {
124 return sb.append(Long.toUnsignedString(key)).append('=').append(value);
128 void putEntries(final HashMap<UnsignedLong, Boolean> ret) {
129 ret.put(UnsignedLong.fromLongBits(key), value);
133 public int hashCode() {
134 return Long.hashCode(key) ^ Boolean.hashCode(value);
138 public boolean equals(final Object obj) {
142 if (!(obj instanceof Singleton)) {
145 final var other = (Singleton) obj;
146 return key == other.key && value == other.value;
150 private static final @NonNull UnsignedLongBitmap EMPTY = new Regular(new long[0], new boolean[0]);
152 private UnsignedLongBitmap() {
156 public static @NonNull UnsignedLongBitmap of() {
160 public static @NonNull UnsignedLongBitmap of(final long keyBits, final boolean value) {
161 return new Singleton(keyBits, value);
164 public static @NonNull UnsignedLongBitmap copyOf(final Map<UnsignedLong, Boolean> map) {
165 final int size = map.size();
170 final var entry = map.entrySet().iterator().next();
171 return of(entry.getKey().longValue(), entry.getValue());
173 final var entries = new ArrayList<>(map.entrySet());
174 entries.sort(Comparator.comparing(Entry::getKey));
176 final var keys = new long[size];
177 final var values = new boolean[size];
180 for (var e : entries) {
181 keys[idx] = e.getKey().longValue();
182 values[idx] = e.getValue();
186 return new Regular(keys, values);
190 public abstract boolean isEmpty();
192 public abstract int size();
194 public final @NonNull HashMap<UnsignedLong, Boolean> mutableCopy() {
195 final int size = size();
198 return new HashMap<>();
200 final var ret = Maps.<UnsignedLong, Boolean>newHashMapWithExpectedSize(size);
206 public static @NonNull UnsignedLongBitmap readFrom(final @NonNull DataInput in, final int size) throws IOException {
211 return new Singleton(WritableObjects.readLong(in), in.readBoolean());
213 final var keys = new long[size];
214 final var values = new boolean[size];
215 for (int i = 0; i < size; ++i) {
216 keys[i] = WritableObjects.readLong(in);
217 values[i] = in.readBoolean();
220 // There should be no duplicates and the IDs need to be increasing
221 long prevKey = keys[0];
222 for (int i = 1; i < size; ++i) {
223 final long key = keys[i];
224 if (Long.compareUnsigned(prevKey, key) >= 0) {
225 throw new IOException("Key " + Long.toUnsignedString(key) + " may not be used after key "
226 + Long.toUnsignedString(prevKey));
231 return new Regular(keys, values);
235 public void writeEntriesTo(final @NonNull DataOutput out, final int size) throws IOException {
236 if (size != size()) {
237 throw new IOException("Mismatched size: expected " + size() + ", got " + size);
242 abstract void writeEntriesTo(@NonNull DataOutput out) throws IOException;
244 abstract StringBuilder appendEntries(StringBuilder sb);
246 abstract void putEntries(HashMap<UnsignedLong, Boolean> ret);
252 * Implementations of this method return a deterministic value.
255 public abstract int hashCode();
258 public abstract boolean equals(Object obj);
261 public final String toString() {
262 return isEmpty() ? "{}" : appendEntries(new StringBuilder().append('{')).append('}').toString();
265 @SuppressFBWarnings(value = "UPM_UNCALLED_PRIVATE_METHOD",
266 justification = "https://github.com/spotbugs/spotbugs/issues/811")
267 private static StringBuilder appendEntry(final StringBuilder sb, final long key, final boolean value) {
268 return sb.append(Long.toUnsignedString(key)).append('=').append(value);
271 @SuppressFBWarnings(value = "UPM_UNCALLED_PRIVATE_METHOD",
272 justification = "https://github.com/spotbugs/spotbugs/issues/811")
273 private static void writeEntry(final @NonNull DataOutput out, final long key, final boolean value)
275 // FIXME: This serialization format is what we inherited. We could do better by storing the boolean in
276 // writeLong()'s flags. On the other had, we could also be writing longs by twos, which might be
278 WritableObjects.writeLong(out, key);
279 out.writeBoolean(value);