NormalizedNodeAggregator should also report empty
[controller.git] / 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 }