001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements. See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache license, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License. You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the license for the specific language governing permissions and
015 * limitations under the license.
016 */
017package org.apache.logging.log4j.util;
018
019import java.io.ByteArrayInputStream;
020import java.io.ByteArrayOutputStream;
021import java.io.IOException;
022import java.io.InvalidObjectException;
023import java.io.ObjectInputStream;
024import java.io.ObjectOutputStream;
025import java.util.Arrays;
026import java.util.ConcurrentModificationException;
027import java.util.HashMap;
028import java.util.Map;
029import java.util.Objects;
030
031import org.apache.logging.log4j.status.StatusLogger;
032
033/**
034 * <em>Consider this class private.</em>
035 * Array-based implementation of the {@code ReadOnlyStringMap} interface. Keys are held in a sorted array.
036 * <p>
037 * This is not a generic collection, but makes some trade-offs to optimize for the Log4j context data use case:
038 * </p>
039 * <ul>
040 *   <li>Garbage-free iteration over key-value pairs with {@code BiConsumer} and {@code TriConsumer}.</li>
041 *   <li>Fast copy. If the ThreadContextMap is also an instance of {@code SortedArrayStringMap}, the full thread context
042 *     data can be transferred with two array copies and two field updates.</li>
043 *   <li>Acceptable performance for small data sets. The current implementation stores keys in a sorted array, values
044 *     are stored in a separate array at the same index.
045 *     Worst-case performance of {@code get} and {@code containsKey} is O(log N),
046 *     worst-case performance of {@code put} and {@code remove} is O(N log N).
047 *     The expectation is that for the small values of {@code N} (less than 100) that are the vast majority of
048 *     ThreadContext use cases, the constants dominate performance more than the asymptotic performance of the
049 *     algorithms used.
050 *     </li>
051 *     <li>Compact representation.</li>
052 * </ul>
053 *
054 * @since 2.7
055 */
056public class SortedArrayStringMap implements IndexedStringMap {
057
058    /**
059     * The default initial capacity.
060     */
061    private static final int DEFAULT_INITIAL_CAPACITY = 4;
062    private static final long serialVersionUID = -5748905872274478116L;
063    private static final int HASHVAL = 31;
064
065    private static final TriConsumer<String, Object, StringMap> PUT_ALL = new TriConsumer<String, Object, StringMap>() {
066        @Override
067        public void accept(final String key, final Object value, final StringMap contextData) {
068            contextData.putValue(key, value);
069        }
070    };
071
072    /**
073     * An empty array instance to share when the table is not inflated.
074     */
075    private static final String[] EMPTY = {};
076    private static final String FROZEN = "Frozen collection cannot be modified";
077
078    private transient String[] keys = EMPTY;
079    private transient Object[] values = EMPTY;
080
081    /**
082     * The number of key-value mappings contained in this map.
083     */
084    private transient int size;
085
086    /**
087     * The next size value at which to resize (capacity * load factor).
088     * @serial
089     */
090    // If table == EMPTY_TABLE then this is the initial capacity at which the
091    // table will be created when inflated.
092    private int threshold;
093    private boolean immutable;
094    private transient boolean iterating;
095
096    public SortedArrayStringMap() {
097        this(DEFAULT_INITIAL_CAPACITY);
098    }
099
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) { // null key is located at the start of the array
194            return nullKeyIndex(); // insert at index zero
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 { // not found, so insert.
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            // this.putAll(this) does not modify this collection
234            // this.putAll(null) does not modify this collection
235            // this.putAll(empty ReadOnlyStringMap) does not modify this collection
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        // move largest collection to the beginning of this data structure, smallest to the end
274        boolean overwrite = true;
275        if (other.size() > size()) {
276            // move original key-values to end
277            System.arraycopy(myKeys, 0, keys, other.size, this.size);
278            System.arraycopy(myVals, 0, values, other.size, this.size);
279
280            // insert additional key-value pairs at the beginning
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            // loop over original keys and insert (drop values for same key)
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            // move additional key-value pairs to end
292            System.arraycopy(other.keys, 0, keys, this.size, other.size);
293            System.arraycopy(other.values, 0, values, this.size, other.size);
294
295            // new values are at the end, will be processed below. Overwrite is true.
296        }
297        for (int i = size; i < newSize; i++) {
298            final int index = indexOfKey(keys[i]);
299            if (index < 0) { // key does not exist
300                insertAt(~index, keys[i], values[i]);
301            } else if (overwrite) { // existing key: only overwrite when looping over the new values
302                keys[index] = keys[i];
303                values[index] = values[i];
304            }
305        }
306        // prevent memory leak: null out references
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     * Inflates the table.
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     * Save the state of the {@code SortedArrayStringMap} instance to a stream (i.e.,
463     * serialize it).
464     *
465     * @serialData The <i>capacity</i> of the SortedArrayStringMap (the length of the
466     *             bucket array) is emitted (int), followed by the
467     *             <i>size</i> (an int, the number of key-value
468     *             mappings), followed by the key (Object) and value (Object)
469     *             for each key-value mapping.  The key-value mappings are
470     *             emitted in no particular order.
471     */
472    private void writeObject(final java.io.ObjectOutputStream s) throws IOException {
473        // Write out the threshold, and any hidden stuff
474        s.defaultWriteObject();
475
476        // Write out number of buckets
477        if (keys == EMPTY) {
478            s.writeInt(ceilingNextPowerOfTwo(threshold));
479        } else {
480            s.writeInt(keys.length);
481        }
482
483        // Write out size (number of Mappings)
484        s.writeInt(size);
485
486        // Write out keys and values (alternating)
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     * Calculate the next power of 2, greater than or equal to x.
521     * <p>
522     * From Hacker's Delight, Chapter 3, Harry S. Warren Jr.
523     *
524     * @param x Value to round up
525     * @return The next power of 2 from x inclusive
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     * Reconstitute the {@code SortedArrayStringMap} instance from a stream (i.e.,
534     * deserialize it).
535     */
536    private void readObject(final java.io.ObjectInputStream s)  throws IOException, ClassNotFoundException {
537        // Read in the threshold (ignored), and any hidden stuff
538        s.defaultReadObject();
539
540        // set other fields that need values
541        keys = EMPTY;
542        values = EMPTY;
543
544        // Read in number of buckets
545        final int capacity = s.readInt();
546        if (capacity < 0) {
547            throw new InvalidObjectException("Illegal capacity: " + capacity);
548        }
549
550        // Read number of mappings
551        final int mappings = s.readInt();
552        if (mappings < 0) {
553            throw new InvalidObjectException("Illegal mappings count: " + mappings);
554        }
555
556        // allocate the bucket array;
557        if (mappings > 0) {
558            inflateTable(capacity);
559        } else {
560            threshold = capacity;
561        }
562
563        // Read the keys and values, and put the mappings in the arrays
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}