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