    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
    027 * be sped up by caching the arrays in HashMaps so the String keys are looked up and resolve to positions in the array
    028 * rather than iterating through the arrays each time.
    029 *
    030 * Because the arrays only grow (never shrink or change) we can use the last known size as a way to determine if the
    031 * array has changed.
    032 *
    033 * Note that this cache must be synchronized externally if it is shared.
    034 */
    035public class SegmentConstantPoolArrayCache {
    036
    037    protected IdentityHashMap knownArrays = new IdentityHashMap(1000);
    038
    039    protected List lastIndexes;
    040    protected String[] lastArray;
    041    protected String lastKey;
    042
    043    /**
    044     * Answer the indices for the given key in the given array. If no such key exists in the cached array, answer -1.
    045     *
    046     * @param array String[] array to search for the value
    047     * @param key String value for which to search
    048     * @return List collection of index positions in the array
    049     */
    050    public List indexesForArrayKey(final String[] array, final String key) {
    051        if (!arrayIsCached(array)) {
    052            cacheArray(array);
    053        }
    054
    055        // If the search is one we've just done, don't even
    056        // bother looking and return the last indices. This
    057        // is a second cache within the cache. This is
    058        // efficient because we usually are looking for
    059        // several secondary elements with the same primary
    060        // key.
    061        if ((lastArray == array) && (lastKey == key)) {
    062            return lastIndexes;
    063        }
    064
    065        // Remember the last thing we found.
    066        lastArray = array;
    067        lastKey = key;
    068        lastIndexes = ((CachedArray) knownArrays.get(array)).indexesForKey(key);
    069
    070        return lastIndexes;
    071    }
    072
    073    /**
    074     * Given a String array, answer true if the array is correctly cached. Answer false if the array is not cached, or
    075     * if the array cache is outdated.
    076     *
    077     * @param array of String
    078     * @return boolean true if up-to-date cache, otherwise false.
    079     */
    080    protected boolean arrayIsCached(final String[] array) {
    081        if (!knownArrays.containsKey(array)) {
    082            return false;
    083        }
    084        final CachedArray cachedArray = (CachedArray) knownArrays.get(array);
    085        if (cachedArray.lastKnownSize() != array.length) {
    086            return false;
    087        }
    088        return true;
    089    }
    090
    091    /**
    092     * Cache the array passed in as the argument
    093     *
    094     * @param array String[] to cache
    095     */
    096    protected void cacheArray(final String[] array) {
    097        if (arrayIsCached(array)) {
    098            throw new IllegalArgumentException("Trying to cache an array that already exists");
    099        }
    100        knownArrays.put(array, new CachedArray(array));
    101        // Invalidate the cache-within-a-cache
    102        lastArray = null;
    103    }
    104
    105    /**
    106     * CachedArray keeps track of the last known size of an array as well as a HashMap that knows the mapping from
    107     * element values to the indices of the array which contain that value.
    108     */
    109    protected class CachedArray {
    110        String[] primaryArray;
    111        int lastKnownSize;
    112        HashMap primaryTable;
    113
    114        public CachedArray(final String[] array) {
    115            super();
    116            this.primaryArray = array;
    117            this.lastKnownSize = array.length;
    118            this.primaryTable = new HashMap(lastKnownSize);
    119            cacheIndexes();
    120        }
    121
    122        /**
    123         * Answer the last known size of the array cached. If the last known size is not the same as the current size,
    124         * the array must have changed.
    125         *
    126         * @return int last known size of the cached array
    127         */
    128        public int lastKnownSize() {
    129            return lastKnownSize;
    130        }
    131
    132        /**
    133         * Given a particular key, answer a List of index locations in the array which contain that key.
    134         *
    135         * If no elements are found, answer an empty list.
    136         *
    137         * @param key String element of the array
    138         * @return List of indexes containing that key in the array.
    139         */
    140        public List indexesForKey(final String key) {
    141            if (!primaryTable.containsKey(key)) {
    142                return Collections.EMPTY_LIST;
    143            }
    144            return (List) primaryTable.get(key);
    145        }
    146
    147        /**
    148         * Given a primaryArray, cache its values in a HashMap to provide a backwards mapping from element values to
    149         * element indexes. For instance, a primaryArray of: {"Zero", "Foo", "Two", "Foo"} would yield a HashMap of:
    150         * "Zero" -&gt; 0 "Foo" -&gt; 1, 3 "Two" -&gt; 2 which is then cached.
    151         */
    152        protected void cacheIndexes() {
    153            for (int index = 0; index < primaryArray.length; index++) {
    154                final String key = primaryArray[index];
    155                if (!primaryTable.containsKey(key)) {
    156                    primaryTable.put(key, new ArrayList());
    157                }
    158                ((ArrayList) primaryTable.get(key)).add(Integer.valueOf(index));
    159            }
    160        }
    161    }
    162}