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 java.io.DataInput;
  18 import java.io.DataOutput;
  19 import java.io.IOException;
  20 import java.util.ArrayList;
  21 import java.util.Arrays;
  22 import java.util.Comparator;
  23 import java.util.HashMap;
  24 import java.util.Map;
  25 import java.util.Map.Entry;
  26 import org.eclipse.jdt.annotation.NonNull;
  27 import org.opendaylight.yangtools.concepts.Immutable;
  28 import org.opendaylight.yangtools.concepts.WritableObjects;
  29
  30 /**
  31  * A more efficient equivalent of {@code ImmutableMap<UnsignedLong, Boolean>}.
  32  */
  33 @Beta
  34 public abstract class UnsignedLongBitmap implements Immutable {
  35     @VisibleForTesting
  36     static final class Regular extends UnsignedLongBitmap {
  37         private final long[] keys;
  38         private final boolean[] values;
  39
  40         Regular(final long[] keys, final boolean[] values) {
  41             this.keys = requireNonNull(keys);
  42             this.values = requireNonNull(values);
  43             verify(keys.length == values.length);
  44         }
  45
  46         @Override
  47         public boolean isEmpty() {
  48             return keys.length == 0;
  49         }
  50
  51         @Override
  52         public int size() {
  53             return keys.length;
  54         }
  55
  56         @Override
  57         void writeEntriesTo(final DataOutput out) throws IOException {
  58             for (int i = 0; i < keys.length; ++i) {
  59                 writeEntry(out, keys[i], values[i]);
  60             }
  61         }
  62
  63         @Override
  64         StringBuilder appendEntries(final StringBuilder sb) {
  65             final int last = keys.length - 1;
  66             for (int i = 0; i < last; ++i) {
  67                 appendEntry(sb, keys[i], values[i]).append(", ");
  68             }
  69             return appendEntry(sb, keys[last], values[last]);
  70         }
  71
  72         @Override
  73         void putEntries(final HashMap<UnsignedLong, Boolean> ret) {
  74             for (int i = 0; i < keys.length; ++i) {
  75                 ret.put(UnsignedLong.fromLongBits(keys[i]), values[i]);
  76             }
  77         }
  78
  79         @Override
  80         public int hashCode() {
  81             return Arrays.hashCode(keys) ^ Arrays.hashCode(values);
  82         }
  83
  84         @Override
  85         public boolean equals(final Object obj) {
  86             if (obj == this) {
  87                 return true;
  88             }
  89             if (!(obj instanceof Regular)) {
  90                 return false;
  91             }
  92             final var other = (Regular) obj;
  93             return Arrays.equals(keys, other.keys) && Arrays.equals(values, other.values);
  94         }
  95     }
  96
  97     private static final class Singleton extends UnsignedLongBitmap {
  98         private final long key;
  99         private final boolean value;
 100
 101         Singleton(final long key, final boolean value) {
 102             this.key = key;
 103             this.value = value;
 104         }
 105
 106         @Override
 107         public boolean isEmpty() {
 108             return false;
 109         }
 110
 111         @Override
 112         public int size() {
 113             return 1;
 114         }
 115
 116         @Override
 117         void writeEntriesTo(final DataOutput out) throws IOException {
 118             writeEntry(out, key, value);
 119         }
 120
 121         @Override
 122         StringBuilder appendEntries(final StringBuilder sb) {
 123             return sb.append(Long.toUnsignedString(key)).append('=').append(value);
 124         }
 125
 126         @Override
 127         void putEntries(final HashMap<UnsignedLong, Boolean> ret) {
 128             ret.put(UnsignedLong.fromLongBits(key), value);
 129         }
 130
 131         @Override
 132         public int hashCode() {
 133             return Long.hashCode(key) ^ Boolean.hashCode(value);
 134         }
 135
 136         @Override
 137         public boolean equals(final Object obj) {
 138             if (obj == this) {
 139                 return true;
 140             }
 141             if (!(obj instanceof Singleton)) {
 142                 return false;
 143             }
 144             final var other = (Singleton) obj;
 145             return key == other.key && value == other.value;
 146         }
 147     }
 148
 149     private static final @NonNull UnsignedLongBitmap EMPTY = new Regular(new long[0], new boolean[0]);
 150
 151     private UnsignedLongBitmap() {
 152         // Hidden on purpose
 153     }
 154
 155     public static @NonNull UnsignedLongBitmap of() {
 156         return EMPTY;
 157     }
 158
 159     public static @NonNull UnsignedLongBitmap of(final long keyBits, final boolean value) {
 160         return new Singleton(keyBits, value);
 161     }
 162
 163     public static @NonNull UnsignedLongBitmap copyOf(final Map<UnsignedLong, Boolean> map) {
 164         final int size = map.size();
 165         switch (size) {
 166             case 0:
 167                 return of();
 168             case 1:
 169                 final var entry = map.entrySet().iterator().next();
 170                 return of(entry.getKey().longValue(), entry.getValue());
 171             default:
 172                 final var entries = new ArrayList<>(map.entrySet());
 173                 entries.sort(Comparator.comparing(Entry::getKey));
 174
 175                 final var keys = new long[size];
 176                 final var values = new boolean[size];
 177
 178                 int idx = 0;
 179                 for (var e : entries) {
 180                     keys[idx] = e.getKey().longValue();
 181                     values[idx] = e.getValue();
 182                     ++idx;
 183                 }
 184
 185                 return new Regular(keys, values);
 186         }
 187     }
 188
 189     public abstract boolean isEmpty();
 190
 191     public abstract int size();
 192
 193     public final @NonNull HashMap<UnsignedLong, Boolean> mutableCopy() {
 194         final int size = size();
 195         switch (size) {
 196             case 0:
 197                 return new HashMap<>();
 198             default:
 199                 final var ret = Maps.<UnsignedLong, Boolean>newHashMapWithExpectedSize(size);
 200                 putEntries(ret);
 201                 return ret;
 202         }
 203     }
 204
 205     public static @NonNull UnsignedLongBitmap readFrom(final @NonNull DataInput in, final int size) throws IOException {
 206         switch (size) {
 207             case 0:
 208                 return of();
 209             case 1:
 210                 return new Singleton(WritableObjects.readLong(in), in.readBoolean());
 211             default:
 212                 final var keys = new long[size];
 213                 final var values = new boolean[size];
 214                 for (int i = 0; i < size; ++i) {
 215                     keys[i] = WritableObjects.readLong(in);
 216                     values[i] = in.readBoolean();
 217                 }
 218
 219                 // There should be no duplicates and the IDs need to be increasing
 220                 long prevKey = keys[0];
 221                 for (int i = 1; i < size; ++i) {
 222                     final long key = keys[i];
 223                     if (Long.compareUnsigned(prevKey, key) >= 0) {
 224                         throw new IOException("Key " + Long.toUnsignedString(key) + " may not be used after key "
 225                             + Long.toUnsignedString(prevKey));
 226                     }
 227                     prevKey = key;
 228                 }
 229
 230                 return new Regular(keys, values);
 231         }
 232     }
 233
 234     public void writeEntriesTo(final @NonNull DataOutput out, final int size) throws IOException {
 235         if (size != size()) {
 236             throw new IOException("Mismatched size: expected " + size() + ", got " + size);
 237         }
 238         writeEntriesTo(out);
 239     }
 240
 241     abstract void writeEntriesTo(@NonNull DataOutput out) throws IOException;
 242
 243     abstract StringBuilder appendEntries(StringBuilder sb);
 244
 245     abstract void putEntries(HashMap<UnsignedLong, Boolean> ret);
 246
 247     /**
 248      * {@inheritDoc}
 249      *
 250      * <p>
 251      * Implementations of this method return a deterministic value.
 252      */
 253     @Override
 254     public abstract int hashCode();
 255
 256     @Override
 257     public abstract boolean equals(Object obj);
 258
 259     @Override
 260     public final String toString() {
 261         return isEmpty() ? "{}" : appendEntries(new StringBuilder().append('{')).append('}').toString();
 262     }
 263
 264     private static StringBuilder appendEntry(final StringBuilder sb, final long key, final boolean value) {
 265         return sb.append(Long.toUnsignedString(key)).append('=').append(value);
 266     }
 267
 268     private static void writeEntry(final @NonNull DataOutput out, final long key, final boolean value)
 269             throws IOException {
 270         // FIXME: This serialization format is what we inherited. We could do better by storing the boolean in
 271         //        writeLong()'s flags. On the other had, we could also be writing longs by twos, which might be
 272         //        benefitial.
 273         WritableObjects.writeLong(out, key);
 274         out.writeBoolean(value);
 275     }
 276 }