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