    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.commons.compress.harmony.unpack200;
    018
    019import java.util.ArrayList;
    020import java.util.Collections;
    021import java.util.HashMap;
    022import java.util.IdentityHashMap;
    023import java.util.List;
    024
    025/**
    026 * 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
    027 * HashMaps so the String keys are looked up and resolve to positions in the array rather than iterating through the arrays each time.
    028 *
    029 * 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.
    030 *
    031 * Note that this cache must be synchronized externally if it is shared.
    032 */
    033public class SegmentConstantPoolArrayCache {
    034
    035    /**
    036     * 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
    037     * which contain that value.
    038     */
    039    protected class CachedArray {
    040        String[] primaryArray;
    041        int lastKnownSize;
    042        HashMap<String, List<Integer>> primaryTable;
    043
    044        public CachedArray(final String[] array) {
    045            this.primaryArray = array;
    046            this.lastKnownSize = array.length;
    047            this.primaryTable = new HashMap<>(lastKnownSize);
    048            cacheIndexes();
    049        }
    050
    051        /**
    052         * Given a primaryArray, cache its values in a HashMap to provide a backwards mapping from element values to element indexes. For instance, a
    053         * 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.
    054         */
    055        protected void cacheIndexes() {
    056            for (int index = 0; index < primaryArray.length; index++) {
    057                final String key = primaryArray[index];
    058                primaryTable.computeIfAbsent(key, k -> new ArrayList<>()).add(Integer.valueOf(index));
    059            }
    060        }
    061
    062        /**
    063         * Given a particular key, answer a List of index locations in the array which contain that key.
    064         *
    065         * If no elements are found, answer an empty list.
    066         *
    067         * @param key String element of the array
    068         * @return List of indexes containing that key in the array.
    069         */
    070        public List<Integer> indexesForKey(final String key) {
    071            final List<Integer> list = primaryTable.get(key);
    072            return list != null ? list : Collections.emptyList();
    073        }
    074
    075        /**
    076         * 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.
    077         *
    078         * @return int last known size of the cached array
    079         */
    080        public int lastKnownSize() {
    081            return lastKnownSize;
    082        }
    083    }
    084
    085    protected IdentityHashMap<String[], CachedArray> knownArrays = new IdentityHashMap<>(1000);
    086    protected List<Integer> lastIndexes;
    087    protected String[] lastArray;
    088
    089    protected String lastKey;
    090
    091    /**
    092     * Tests whether a String array is correctly cached. Return false if the array is not cached, or if the array cache is outdated.
    093     *
    094     * @param array of String
    095     * @return boolean true if up-to-date cache, otherwise false.
    096     */
    097    protected boolean arrayIsCached(final String[] array) {
    098        final CachedArray cachedArray = knownArrays.get(array);
    099        return !(cachedArray == null || cachedArray.lastKnownSize() != array.length);
    100    }
    101
    102    /**
    103     * Caches the array passed in as the argument
    104     *
    105     * @param array String[] to cache
    106     */
    107    protected void cacheArray(final String[] array) {
    108        if (arrayIsCached(array)) {
    109            throw new IllegalArgumentException("Trying to cache an array that already exists");
    110        }
    111        knownArrays.put(array, new CachedArray(array));
    112        // Invalidate the cache-within-a-cache
    113        lastArray = null;
    114    }
    115
    116    /**
    117     * Gets the indices for the given key in the given array. If no such key exists in the cached array, answer -1.
    118     *
    119     * @param array String[] array to search for the value
    120     * @param key   String value for which to search
    121     * @return List collection of index positions in the array
    122     */
    123    public List<Integer> indexesForArrayKey(final String[] array, final String key) {
    124        if (!arrayIsCached(array)) {
    125            cacheArray(array);
    126        }
    127
    128        // If the search is one we've just done, don't even
    129        // bother looking and return the last indices. This
    130        // is a second cache within the cache. This is
    131        // efficient because we are usually looking for
    132        // several secondary elements with the same primary
    133        // key.
    134        if (lastArray == array && lastKey == key) {
    135            return lastIndexes;
    136        }
    137
    138        // Remember the last thing we found.
    139        lastArray = array;
    140        lastKey = key;
    141        lastIndexes = knownArrays.get(array).indexesForKey(key);
    142
    143        return lastIndexes;
    144    }
    145}