    001/*
    002 * Licensed to the Apache Software Foundation (ASF) under one
    003 * or more contributor license agreements.  See the NOTICE file
    004 * distributed with this work for additional information
    005 * regarding copyright ownership.  The ASF licenses this file
    006 * to you under the Apache License, Version 2.0 (the
    007 * "License"); you may not use this file except in compliance
    008 * with the License.  You may obtain a copy of the License at
    009 *
    010 *   https://www.apache.org/licenses/LICENSE-2.0
    011 *
    012 * Unless required by applicable law or agreed to in writing,
    013 * software distributed under the License is distributed on an
    014 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
    015 * KIND, either express or implied.  See the License for the
    016 * specific language governing permissions and limitations
    017 * under the License.
    018 */
    019package org.apache.commons.compress.harmony.unpack200;
    020
    021import java.util.ArrayList;
    022import java.util.Collections;
    023import java.util.HashMap;
    024import java.util.IdentityHashMap;
    025import java.util.List;
    026
    027/**
    028 * The SegmentConstantPool spends a lot of time searching through large arrays of Strings looking for matches. This can be sped up by caching the arrays in
    029 * HashMaps so the String keys are looked up and resolve to positions in the array rather than iterating through the arrays each time.
    030 *
    031 * Because the arrays only grow (never shrink or change) we can use the last known size as a way to determine if the array has changed.
    032 *
    033 * Note that this cache must be synchronized externally if it is shared.
    034 */
    035public class SegmentConstantPoolArrayCache {
    036
    037    /**
    038     * Keeps track of the last known size of an array as well as a HashMap that knows the mapping from element values to the indices of the array
    039     * which contain that value.
    040     */
    041    protected class CachedArray {
    042        String[] primaryArray;
    043        int lastKnownSize;
    044        HashMap<String, List<Integer>> primaryTable;
    045
    046        public CachedArray(final String[] array) {
    047            this.primaryArray = array;
    048            this.lastKnownSize = array.length;
    049            this.primaryTable = new HashMap<>(lastKnownSize);
    050            cacheIndexes();
    051        }
    052
    053        /**
    054         * Given a primaryArray, cache its values in a HashMap to provide a backwards mapping from element values to element indexes. For instance, a
    055         * primaryArray of: {"Zero", "Foo", "Two", "Foo"} would yield a HashMap of: "Zero" -&gt; 0 "Foo" -&gt; 1, 3 "Two" -&gt; 2 which is then cached.
    056         */
    057        protected void cacheIndexes() {
    058            for (int index = 0; index < primaryArray.length; index++) {
    059                final String key = primaryArray[index];
    060                primaryTable.computeIfAbsent(key, k -> new ArrayList<>()).add(Integer.valueOf(index));
    061            }
    062        }
    063
    064        /**
    065         * Given a particular key, answer a List of index locations in the array which contain that key.
    066         *
    067         * If no elements are found, answer an empty list.
    068         *
    069         * @param key String element of the array
    070         * @return List of indexes containing that key in the array.
    071         */
    072        public List<Integer> indexesForKey(final String key) {
    073            final List<Integer> list = primaryTable.get(key);
    074            return list != null ? list : Collections.emptyList();
    075        }
    076
    077        /**
    078         * Answer the last known size of the array cached. If the last known size is not the same as the current size, the array must have changed.
    079         *
    080         * @return int last known size of the cached array
    081         */
    082        public int lastKnownSize() {
    083            return lastKnownSize;
    084        }
    085    }
    086
    087    protected IdentityHashMap<String[], CachedArray> knownArrays = new IdentityHashMap<>(1000);
    088    protected List<Integer> lastIndexes;
    089    protected String[] lastArray;
    090
    091    protected String lastKey;
    092
    093    /**
    094     * Tests whether a String array is correctly cached. Return false if the array is not cached, or if the array cache is outdated.
    095     *
    096     * @param array of String
    097     * @return boolean true if up-to-date cache, otherwise false.
    098     */
    099    protected boolean arrayIsCached(final String[] array) {
    100        final CachedArray cachedArray = knownArrays.get(array);
    101        return !(cachedArray == null || cachedArray.lastKnownSize() != array.length);
    102    }
    103
    104    /**
    105     * Caches the array passed in as the argument
    106     *
    107     * @param array String[] to cache
    108     */
    109    protected void cacheArray(final String[] array) {
    110        if (arrayIsCached(array)) {
    111            throw new IllegalArgumentException("Trying to cache an array that already exists");
    112        }
    113        knownArrays.put(array, new CachedArray(array));
    114        // Invalidate the cache-within-a-cache
    115        lastArray = null;
    116    }
    117
    118    /**
    119     * Gets the indices for the given key in the given array. If no such key exists in the cached array, answer -1.
    120     *
    121     * @param array String[] array to search for the value
    122     * @param key   String value for which to search
    123     * @return List collection of index positions in the array
    124     */
    125    public List<Integer> indexesForArrayKey(final String[] array, final String key) {
    126        if (!arrayIsCached(array)) {
    127            cacheArray(array);
    128        }
    129
    130        // If the search is one we've just done, don't even
    131        // bother looking and return the last indices. This
    132        // is a second cache within the cache. This is
    133        // efficient because we are usually looking for
    134        // several secondary elements with the same primary
    135        // key.
    136        if (lastArray == array && lastKey == key) {
    137            return lastIndexes;
    138        }
    139
    140        // Remember the last thing we found.
    141        lastArray = array;
    142        lastKey = key;
    143        lastIndexes = knownArrays.get(array).indexesForKey(key);
    144
    145        return lastIndexes;
    146    }
    147}