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     * CachedArray 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     * Given a String array, answer true if the array is correctly cached. Answer 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     * Cache 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     * Answer 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}