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}