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" -> 0 "Foo" -> 1, 3 "Two" -> 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}