1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.apache.logging.log4j.util;
18
19 import java.io.ByteArrayInputStream;
20 import java.io.ByteArrayOutputStream;
21 import java.io.IOException;
22 import java.io.InvalidObjectException;
23 import java.io.ObjectInputStream;
24 import java.io.ObjectOutputStream;
25 import java.util.Arrays;
26 import java.util.ConcurrentModificationException;
27 import java.util.HashMap;
28 import java.util.Map;
29 import java.util.Objects;
30
31 import org.apache.logging.log4j.status.StatusLogger;
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56 public class SortedArrayStringMap implements IndexedStringMap {
57
58
59
60
61 private static final int DEFAULT_INITIAL_CAPACITY = 4;
62 private static final long serialVersionUID = -5748905872274478116L;
63 private static final int HASHVAL = 31;
64
65 private static final TriConsumer<String, Object, StringMap> PUT_ALL = new TriConsumer<String, Object, StringMap>() {
66 @Override
67 public void accept(final String key, final Object value, final StringMap contextData) {
68 contextData.putValue(key, value);
69 }
70 };
71
72
73
74
75 private static final String[] EMPTY = {};
76 private static final String FROZEN = "Frozen collection cannot be modified";
77
78 private transient String[] keys = EMPTY;
79 private transient Object[] values = EMPTY;
80
81
82
83
84 private transient int size;
85
86
87
88
89
90
91
92 private int threshold;
93 private boolean immutable;
94 private transient boolean iterating;
95
96 public SortedArrayStringMap() {
97 this(DEFAULT_INITIAL_CAPACITY);
98 }
99
100 public SortedArrayStringMap(final int initialCapacity) {
101 if (initialCapacity < 1) {
102 throw new IllegalArgumentException("Initial capacity must be at least one but was " + initialCapacity);
103 }
104 threshold = ceilingNextPowerOfTwo(initialCapacity);
105 }
106
107 public SortedArrayStringMap(final ReadOnlyStringMap other) {
108 if (other instanceof SortedArrayStringMap) {
109 initFrom0((SortedArrayStringMap) other);
110 } else if (other != null) {
111 resize(ceilingNextPowerOfTwo(other.size()));
112 other.forEach(PUT_ALL, this);
113 }
114 }
115
116 public SortedArrayStringMap(final Map<String, ?> map) {
117 resize(ceilingNextPowerOfTwo(map.size()));
118 for (final Map.Entry<String, ?> entry : map.entrySet()) {
119 putValue(entry.getKey(), entry.getValue());
120 }
121 }
122
123 private void assertNotFrozen() {
124 if (immutable) {
125 throw new UnsupportedOperationException(FROZEN);
126 }
127 }
128
129 private void assertNoConcurrentModification() {
130 if (iterating) {
131 throw new ConcurrentModificationException();
132 }
133 }
134
135 @Override
136 public void clear() {
137 if (keys == EMPTY) {
138 return;
139 }
140 assertNotFrozen();
141 assertNoConcurrentModification();
142
143 Arrays.fill(keys, 0, size, null);
144 Arrays.fill(values, 0, size, null);
145 size = 0;
146 }
147
148 @Override
149 public boolean containsKey(final String key) {
150 return indexOfKey(key) >= 0;
151 }
152
153 @Override
154 public Map<String, String> toMap() {
155 final Map<String, String> result = new HashMap<>(size());
156 for (int i = 0; i < size(); i++) {
157 final Object value = getValueAt(i);
158 result.put(getKeyAt(i), value == null ? null : String.valueOf(value));
159 }
160 return result;
161 }
162
163 @Override
164 public void freeze() {
165 immutable = true;
166 }
167
168 @Override
169 public boolean isFrozen() {
170 return immutable;
171 }
172
173 @SuppressWarnings("unchecked")
174 @Override
175 public <V> V getValue(final String key) {
176 final int index = indexOfKey(key);
177 if (index < 0) {
178 return null;
179 }
180 return (V) values[index];
181 }
182
183 @Override
184 public boolean isEmpty() {
185 return size == 0;
186 }
187
188 @Override
189 public int indexOfKey(final String key) {
190 if (keys == EMPTY) {
191 return -1;
192 }
193 if (key == null) {
194 return nullKeyIndex();
195 }
196 final int start = size > 0 && keys[0] == null ? 1 : 0;
197 return Arrays.binarySearch(keys, start, size, key);
198 }
199
200 private int nullKeyIndex() {
201 return size > 0 && keys[0] == null ? 0 : ~0;
202 }
203
204 @Override
205 public void putValue(final String key, final Object value) {
206 assertNotFrozen();
207 assertNoConcurrentModification();
208
209 if (keys == EMPTY) {
210 inflateTable(threshold);
211 }
212 final int index = indexOfKey(key);
213 if (index >= 0) {
214 keys[index] = key;
215 values[index] = value;
216 } else {
217 insertAt(~index, key, value);
218 }
219 }
220
221 private void insertAt(final int index, final String key, final Object value) {
222 ensureCapacity();
223 System.arraycopy(keys, index, keys, index + 1, size - index);
224 System.arraycopy(values, index, values, index + 1, size - index);
225 keys[index] = key;
226 values[index] = value;
227 size++;
228 }
229
230 @Override
231 public void putAll(final ReadOnlyStringMap source) {
232 if (source == this || source == null || source.isEmpty()) {
233
234
235
236 return;
237 }
238 assertNotFrozen();
239 assertNoConcurrentModification();
240
241 if (source instanceof SortedArrayStringMap) {
242 if (this.size == 0) {
243 initFrom0((SortedArrayStringMap) source);
244 } else {
245 merge((SortedArrayStringMap) source);
246 }
247 } else if (source != null) {
248 source.forEach(PUT_ALL, this);
249 }
250 }
251
252 private void initFrom0(final SortedArrayStringMap other) {
253 if (keys.length < other.size) {
254 keys = new String[other.threshold];
255 values = new Object[other.threshold];
256 }
257 System.arraycopy(other.keys, 0, keys, 0, other.size);
258 System.arraycopy(other.values, 0, values, 0, other.size);
259
260 size = other.size;
261 threshold = other.threshold;
262 }
263
264 private void merge(final SortedArrayStringMap other) {
265 final String[] myKeys = keys;
266 final Object[] myVals = values;
267 final int newSize = other.size + this.size;
268 threshold = ceilingNextPowerOfTwo(newSize);
269 if (keys.length < threshold) {
270 keys = new String[threshold];
271 values = new Object[threshold];
272 }
273
274 boolean overwrite = true;
275 if (other.size() > size()) {
276
277 System.arraycopy(myKeys, 0, keys, other.size, this.size);
278 System.arraycopy(myVals, 0, values, other.size, this.size);
279
280
281 System.arraycopy(other.keys, 0, keys, 0, other.size);
282 System.arraycopy(other.values, 0, values, 0, other.size);
283 size = other.size;
284
285
286 overwrite = false;
287 } else {
288 System.arraycopy(myKeys, 0, keys, 0, this.size);
289 System.arraycopy(myVals, 0, values, 0, this.size);
290
291
292 System.arraycopy(other.keys, 0, keys, this.size, other.size);
293 System.arraycopy(other.values, 0, values, this.size, other.size);
294
295
296 }
297 for (int i = size; i < newSize; i++) {
298 final int index = indexOfKey(keys[i]);
299 if (index < 0) {
300 insertAt(~index, keys[i], values[i]);
301 } else if (overwrite) {
302 keys[index] = keys[i];
303 values[index] = values[i];
304 }
305 }
306
307 Arrays.fill(keys, size, newSize, null);
308 Arrays.fill(values, size, newSize, null);
309 }
310
311 private void ensureCapacity() {
312 if (size >= threshold) {
313 resize(threshold * 2);
314 }
315 }
316
317 private void resize(final int newCapacity) {
318 final String[] oldKeys = keys;
319 final Object[] oldValues = values;
320
321 keys = new String[newCapacity];
322 values = new Object[newCapacity];
323
324 System.arraycopy(oldKeys, 0, keys, 0, size);
325 System.arraycopy(oldValues, 0, values, 0, size);
326
327 threshold = newCapacity;
328 }
329
330
331
332
333 private void inflateTable(final int toSize) {
334 threshold = toSize;
335 keys = new String[toSize];
336 values = new Object[toSize];
337 }
338
339 @Override
340 public void remove(final String key) {
341 if (keys == EMPTY) {
342 return;
343 }
344
345 final int index = indexOfKey(key);
346 if (index >= 0) {
347 assertNotFrozen();
348 assertNoConcurrentModification();
349
350 System.arraycopy(keys, index + 1, keys, index, size - 1 - index);
351 System.arraycopy(values, index + 1, values, index, size - 1 - index);
352 keys[size - 1] = null;
353 values[size - 1] = null;
354 size--;
355 }
356 }
357
358 @Override
359 public String getKeyAt(final int index) {
360 if (index < 0 || index >= size) {
361 return null;
362 }
363 return keys[index];
364 }
365
366 @SuppressWarnings("unchecked")
367 @Override
368 public <V> V getValueAt(final int index) {
369 if (index < 0 || index >= size) {
370 return null;
371 }
372 return (V) values[index];
373 }
374
375 @Override
376 public int size() {
377 return size;
378 }
379
380 @SuppressWarnings("unchecked")
381 @Override
382 public <V> void forEach(final BiConsumer<String, ? super V> action) {
383 iterating = true;
384 try {
385 for (int i = 0; i < size; i++) {
386 action.accept(keys[i], (V) values[i]);
387 }
388 } finally {
389 iterating = false;
390 }
391 }
392
393 @SuppressWarnings("unchecked")
394 @Override
395 public <V, T> void forEach(final TriConsumer<String, ? super V, T> action, final T state) {
396 iterating = true;
397 try {
398 for (int i = 0; i < size; i++) {
399 action.accept(keys[i], (V) values[i], state);
400 }
401 } finally {
402 iterating = false;
403 }
404 }
405
406 @Override
407 public boolean equals(final Object obj) {
408 if (obj == this) {
409 return true;
410 }
411 if (!(obj instanceof SortedArrayStringMap)) {
412 return false;
413 }
414 final SortedArrayStringMap other = (SortedArrayStringMap) obj;
415 if (this.size() != other.size()) {
416 return false;
417 }
418 for (int i = 0; i < size(); i++) {
419 if (!Objects.equals(keys[i], other.keys[i])) {
420 return false;
421 }
422 if (!Objects.equals(values[i], other.values[i])) {
423 return false;
424 }
425 }
426 return true;
427 }
428
429 @Override
430 public int hashCode() {
431 int result = 37;
432 result = HASHVAL * result + size;
433 result = HASHVAL * result + hashCode(keys, size);
434 result = HASHVAL * result + hashCode(values, size);
435 return result;
436 }
437
438 private static int hashCode(final Object[] values, final int length) {
439 int result = 1;
440 for (int i = 0; i < length; i++) {
441 result = HASHVAL * result + (values[i] == null ? 0 : values[i].hashCode());
442 }
443 return result;
444 }
445
446 @Override
447 public String toString() {
448 final StringBuilder sb = new StringBuilder(256);
449 sb.append('{');
450 for (int i = 0; i < size; i++) {
451 if (i > 0) {
452 sb.append(", ");
453 }
454 sb.append(keys[i]).append('=');
455 sb.append(values[i] == this ? "(this map)" : values[i]);
456 }
457 sb.append('}');
458 return sb.toString();
459 }
460
461
462
463
464
465
466
467
468
469
470
471
472 private void writeObject(final java.io.ObjectOutputStream s) throws IOException {
473
474 s.defaultWriteObject();
475
476
477 if (keys == EMPTY) {
478 s.writeInt(ceilingNextPowerOfTwo(threshold));
479 } else {
480 s.writeInt(keys.length);
481 }
482
483
484 s.writeInt(size);
485
486
487 if (size > 0) {
488 for (int i = 0; i < size; i++) {
489 s.writeObject(keys[i]);
490 try {
491 s.writeObject(marshall(values[i]));
492 } catch (final Exception e) {
493 handleSerializationException(e, i, keys[i]);
494 s.writeObject(null);
495 }
496 }
497 }
498 }
499
500 private static byte[] marshall(final Object obj) throws IOException {
501 if (obj == null) {
502 return null;
503 }
504 final ByteArrayOutputStream bout = new ByteArrayOutputStream();
505 try (ObjectOutputStream oos = new ObjectOutputStream(bout)) {
506 oos.writeObject(obj);
507 oos.flush();
508 return bout.toByteArray();
509 }
510 }
511
512 private static Object unmarshall(final byte[] data) throws IOException, ClassNotFoundException {
513 final ByteArrayInputStream bin = new ByteArrayInputStream(data);
514 try (ObjectInputStream ois = new ObjectInputStream(bin)) {
515 return ois.readObject();
516 }
517 }
518
519
520
521
522
523
524
525
526
527 private static int ceilingNextPowerOfTwo(final int x) {
528 final int BITS_PER_INT = 32;
529 return 1 << (BITS_PER_INT - Integer.numberOfLeadingZeros(x - 1));
530 }
531
532
533
534
535
536 private void readObject(final java.io.ObjectInputStream s) throws IOException, ClassNotFoundException {
537
538 s.defaultReadObject();
539
540
541 keys = EMPTY;
542 values = EMPTY;
543
544
545 final int capacity = s.readInt();
546 if (capacity < 0) {
547 throw new InvalidObjectException("Illegal capacity: " + capacity);
548 }
549
550
551 final int mappings = s.readInt();
552 if (mappings < 0) {
553 throw new InvalidObjectException("Illegal mappings count: " + mappings);
554 }
555
556
557 if (mappings > 0) {
558 inflateTable(capacity);
559 } else {
560 threshold = capacity;
561 }
562
563
564 for (int i = 0; i < mappings; i++) {
565 keys[i] = (String) s.readObject();
566 try {
567 final byte[] marshalledObject = (byte[]) s.readObject();
568 values[i] = marshalledObject == null ? null : unmarshall(marshalledObject);
569 } catch (final Exception | LinkageError error) {
570 handleSerializationException(error, i, keys[i]);
571 values[i] = null;
572 }
573 }
574 size = mappings;
575 }
576
577 private void handleSerializationException(final Throwable t, final int i, final String key) {
578 StatusLogger.getLogger().warn("Ignoring {} for key[{}] ('{}')", String.valueOf(t), i, keys[i]);
579 }
580 }