opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongBitmap.java

   1 /*
   2  * Copyright (c) 2021 PANTHEON.tech, s.r.o. and others.  All rights reserved.
   3  *
   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
   7  */
   8 package org.opendaylight.controller.cluster.datastore.utils;
   9
  10 import static com.google.common.base.Verify.verify;
  11 import static java.util.Objects.requireNonNull;
  12
  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;
  25 import java.util.Map;
  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;
  30
  31 /**
  32  * A more efficient equivalent of {@code ImmutableMap<UnsignedLong, Boolean>}.
  33  */
  34 @Beta
  35 public abstract class UnsignedLongBitmap implements Immutable {
  36     @VisibleForTesting
  37     static final class Regular extends UnsignedLongBitmap {
  38         private final long[] keys;
  39         private final boolean[] values;
  40
  41         Regular(final long[] keys, final boolean[] values) {
  42             this.keys = requireNonNull(keys);
  43             this.values = requireNonNull(values);
  44             verify(keys.length == values.length);
  45         }
  46
  47         @Override
  48         public boolean isEmpty() {
  49             return keys.length == 0;
  50         }
  51
  52         @Override
  53         public int size() {
  54             return keys.length;
  55         }
  56
  57         @Override
  58         void writeEntriesTo(final DataOutput out) throws IOException {
  59             for (int i = 0; i < keys.length; ++i) {
  60                 writeEntry(out, keys[i], values[i]);
  61             }
  62         }
  63
  64         @Override
  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(", ");
  69             }
  70             return appendEntry(sb, keys[last], values[last]);
  71         }
  72
  73         @Override
  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]);
  77             }
  78         }
  79
  80         @Override
  81         public int hashCode() {
  82             return Arrays.hashCode(keys) ^ Arrays.hashCode(values);
  83         }
  84
  85         @Override
  86         public boolean equals(final Object obj) {
  87             if (obj == this) {
  88                 return true;
  89             }
  90             if (!(obj instanceof Regular)) {
  91                 return false;
  92             }
  93             final var other = (Regular) obj;
  94             return Arrays.equals(keys, other.keys) && Arrays.equals(values, other.values);
  95         }
  96     }
  97
  98     private static final class Singleton extends UnsignedLongBitmap {
  99         private final long key;
 100         private final boolean value;
 101
 102         Singleton(final long key, final boolean value) {
 103             this.key = key;
 104             this.value = value;
 105         }
 106
 107         @Override
 108         public boolean isEmpty() {
 109             return false;
 110         }
 111
 112         @Override
 113         public int size() {
 114             return 1;
 115         }
 116
 117         @Override
 118         void writeEntriesTo(final DataOutput out) throws IOException {
 119             writeEntry(out, key, value);
 120         }
 121
 122         @Override
 123         StringBuilder appendEntries(final StringBuilder sb) {
 124             return sb.append(Long.toUnsignedString(key)).append('=').append(value);
 125         }
 126
 127         @Override
 128         void putEntries(final HashMap<UnsignedLong, Boolean> ret) {
 129             ret.put(UnsignedLong.fromLongBits(key), value);
 130         }
 131
 132         @Override
 133         public int hashCode() {
 134             return Long.hashCode(key) ^ Boolean.hashCode(value);
 135         }
 136
 137         @Override
 138         public boolean equals(final Object obj) {
 139             if (obj == this) {
 140                 return true;
 141             }
 142             if (!(obj instanceof Singleton)) {
 143                 return false;
 144             }
 145             final var other = (Singleton) obj;
 146             return key == other.key && value == other.value;
 147         }
 148     }
 149
 150     private static final @NonNull UnsignedLongBitmap EMPTY = new Regular(new long[0], new boolean[0]);
 151
 152     private UnsignedLongBitmap() {
 153         // Hidden on purpose
 154     }
 155
 156     public static @NonNull UnsignedLongBitmap of() {
 157         return EMPTY;
 158     }
 159
 160     public static @NonNull UnsignedLongBitmap of(final long keyBits, final boolean value) {
 161         return new Singleton(keyBits, value);
 162     }
 163
 164     public static @NonNull UnsignedLongBitmap copyOf(final Map<UnsignedLong, Boolean> map) {
 165         final int size = map.size();
 166         switch (size) {
 167             case 0:
 168                 return of();
 169             case 1:
 170                 final var entry = map.entrySet().iterator().next();
 171                 return of(entry.getKey().longValue(), entry.getValue());
 172             default:
 173                 final var entries = new ArrayList<>(map.entrySet());
 174                 entries.sort(Comparator.comparing(Entry::getKey));
 175
 176                 final var keys = new long[size];
 177                 final var values = new boolean[size];
 178
 179                 int idx = 0;
 180                 for (var e : entries) {
 181                     keys[idx] = e.getKey().longValue();
 182                     values[idx] = e.getValue();
 183                     ++idx;
 184                 }
 185
 186                 return new Regular(keys, values);
 187         }
 188     }
 189
 190     public abstract boolean isEmpty();
 191
 192     public abstract int size();
 193
 194     public final @NonNull HashMap<UnsignedLong, Boolean> mutableCopy() {
 195         final int size = size();
 196         switch (size) {
 197             case 0:
 198                 return new HashMap<>();
 199             default:
 200                 final var ret = Maps.<UnsignedLong, Boolean>newHashMapWithExpectedSize(size);
 201                 putEntries(ret);
 202                 return ret;
 203         }
 204     }
 205
 206     public static @NonNull UnsignedLongBitmap readFrom(final @NonNull DataInput in, final int size) throws IOException {
 207         switch (size) {
 208             case 0:
 209                 return of();
 210             case 1:
 211                 return new Singleton(WritableObjects.readLong(in), in.readBoolean());
 212             default:
 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();
 218                 }
 219
 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));
 227                     }
 228                     prevKey = key;
 229                 }
 230
 231                 return new Regular(keys, values);
 232         }
 233     }
 234
 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);
 238         }
 239         writeEntriesTo(out);
 240     }
 241
 242     abstract void writeEntriesTo(@NonNull DataOutput out) throws IOException;
 243
 244     abstract StringBuilder appendEntries(StringBuilder sb);
 245
 246     abstract void putEntries(HashMap<UnsignedLong, Boolean> ret);
 247
 248     /**
 249      * {@inheritDoc}
 250      *
 251      * <p>
 252      * Implementations of this method return a deterministic value.
 253      */
 254     @Override
 255     public abstract int hashCode();
 256
 257     @Override
 258     public abstract boolean equals(Object obj);
 259
 260     @Override
 261     public final String toString() {
 262         return isEmpty() ? "{}" : appendEntries(new StringBuilder().append('{')).append('}').toString();
 263     }
 264
 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);
 269     }
 270
 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)
 274             throws IOException {
 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
 277         //        benefitial.
 278         WritableObjects.writeLong(out, key);
 279         out.writeBoolean(value);
 280     }
 281 }