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: */
017:
018: package org.apache.naming.resources;
019:
020: import java.util.HashMap;
021: import java.util.Random;
022:
023: /**
024: * Implements a special purpose cache.
025: *
026: * @author <a href="mailto:remm@apache.org">Remy Maucherat</a>
027: * @version $Revision: 467222 $
028: */
029: public class ResourceCache {
030:
031: // ----------------------------------------------------------- Constructors
032:
033: public ResourceCache() {
034: }
035:
036: // ----------------------------------------------------- Instance Variables
037:
038: /**
039: * Random generator used to determine elements to free.
040: */
041: protected Random random = new Random();
042:
043: /**
044: * Cache.
045: * Path -> Cache entry.
046: */
047: protected CacheEntry[] cache = new CacheEntry[0];
048:
049: /**
050: * Not found cache.
051: */
052: protected HashMap notFoundCache = new HashMap();
053:
054: /**
055: * Max size of resources which will have their content cached.
056: */
057: protected int cacheMaxSize = 10240; // 10 MB
058:
059: /**
060: * Max amount of removals during a make space.
061: */
062: protected int maxAllocateIterations = 20;
063:
064: /**
065: * Entry hit ratio at which an entry will never be removed from the cache.
066: * Compared with entry.access / hitsCount
067: */
068: protected long desiredEntryAccessRatio = 3;
069:
070: /**
071: * Spare amount of not found entries.
072: */
073: protected int spareNotFoundEntries = 500;
074:
075: /**
076: * Current cache size in KB.
077: */
078: protected int cacheSize = 0;
079:
080: /**
081: * Number of accesses to the cache.
082: */
083: protected long accessCount = 0;
084:
085: /**
086: * Number of cache hits.
087: */
088: protected long hitsCount = 0;
089:
090: // ------------------------------------------------------------- Properties
091:
092: /**
093: * Return the access count.
094: * Note: Update is not synced, so the number may not be completely
095: * accurate.
096: */
097: public long getAccessCount() {
098: return accessCount;
099: }
100:
101: /**
102: * Return the maximum size of the cache in KB.
103: */
104: public int getCacheMaxSize() {
105: return cacheMaxSize;
106: }
107:
108: /**
109: * Set the maximum size of the cache in KB.
110: */
111: public void setCacheMaxSize(int cacheMaxSize) {
112: this .cacheMaxSize = cacheMaxSize;
113: }
114:
115: /**
116: * Return the current cache size in KB.
117: */
118: public int getCacheSize() {
119: return cacheSize;
120: }
121:
122: /**
123: * Return desired entry access ratio.
124: */
125: public long getDesiredEntryAccessRatio() {
126: return desiredEntryAccessRatio;
127: }
128:
129: /**
130: * Set the desired entry access ratio.
131: */
132: public void setDesiredEntryAccessRatio(long desiredEntryAccessRatio) {
133: this .desiredEntryAccessRatio = desiredEntryAccessRatio;
134: }
135:
136: /**
137: * Return the number of cache hits.
138: * Note: Update is not synced, so the number may not be completely
139: * accurate.
140: */
141: public long getHitsCount() {
142: return hitsCount;
143: }
144:
145: /**
146: * Return the maximum amount of iterations during a space allocation.
147: */
148: public int getMaxAllocateIterations() {
149: return maxAllocateIterations;
150: }
151:
152: /**
153: * Set the maximum amount of iterations during a space allocation.
154: */
155: public void setMaxAllocateIterations(int maxAllocateIterations) {
156: this .maxAllocateIterations = maxAllocateIterations;
157: }
158:
159: /**
160: * Return the amount of spare not found entries.
161: */
162: public int getSpareNotFoundEntries() {
163: return spareNotFoundEntries;
164: }
165:
166: /**
167: * Set the amount of spare not found entries.
168: */
169: public void setSpareNotFoundEntries(int spareNotFoundEntries) {
170: this .spareNotFoundEntries = spareNotFoundEntries;
171: }
172:
173: // --------------------------------------------------------- Public Methods
174:
175: public boolean allocate(int space) {
176:
177: int toFree = space - (cacheMaxSize - cacheSize);
178:
179: if (toFree <= 0) {
180: return true;
181: }
182:
183: // Increase the amount to free so that allocate won't have to run right
184: // away again
185: toFree += (cacheMaxSize / 20);
186:
187: int size = notFoundCache.size();
188: if (size > spareNotFoundEntries) {
189: notFoundCache.clear();
190: cacheSize -= size;
191: toFree -= size;
192: }
193:
194: if (toFree <= 0) {
195: return true;
196: }
197:
198: int attempts = 0;
199: int entriesFound = 0;
200: long totalSpace = 0;
201: int[] toRemove = new int[maxAllocateIterations];
202: while (toFree > 0) {
203: if (attempts == maxAllocateIterations) {
204: // Give up, no changes are made to the current cache
205: return false;
206: }
207: if (toFree > 0) {
208: // Randomly select an entry in the array
209: int entryPos = -1;
210: boolean unique = false;
211: while (!unique) {
212: unique = true;
213: entryPos = random.nextInt(cache.length);
214: // Guarantee uniqueness
215: for (int i = 0; i < entriesFound; i++) {
216: if (toRemove[i] == entryPos) {
217: unique = false;
218: }
219: }
220: }
221: long entryAccessRatio = ((cache[entryPos].accessCount * 100) / accessCount);
222: if (entryAccessRatio < desiredEntryAccessRatio) {
223: toRemove[entriesFound] = entryPos;
224: totalSpace += cache[entryPos].size;
225: toFree -= cache[entryPos].size;
226: entriesFound++;
227: }
228: }
229: attempts++;
230: }
231:
232: // Now remove the selected entries
233: java.util.Arrays.sort(toRemove, 0, entriesFound);
234: CacheEntry[] newCache = new CacheEntry[cache.length
235: - entriesFound];
236: int pos = 0;
237: int n = -1;
238: if (entriesFound > 0) {
239: n = toRemove[0];
240: for (int i = 0; i < cache.length; i++) {
241: if (i == n) {
242: if ((pos + 1) < entriesFound) {
243: n = toRemove[pos + 1];
244: pos++;
245: } else {
246: pos++;
247: n = -1;
248: }
249: } else {
250: newCache[i - pos] = cache[i];
251: }
252: }
253: }
254: cache = newCache;
255: cacheSize -= totalSpace;
256:
257: return true;
258:
259: }
260:
261: public CacheEntry lookup(String name) {
262:
263: CacheEntry cacheEntry = null;
264: CacheEntry[] currentCache = cache;
265: accessCount++;
266: int pos = find(currentCache, name);
267: if ((pos != -1) && (name.equals(currentCache[pos].name))) {
268: cacheEntry = currentCache[pos];
269: }
270: if (cacheEntry == null) {
271: try {
272: cacheEntry = (CacheEntry) notFoundCache.get(name);
273: } catch (Exception e) {
274: // Ignore: the reliability of this lookup is not critical
275: }
276: }
277: if (cacheEntry != null) {
278: hitsCount++;
279: }
280: return cacheEntry;
281:
282: }
283:
284: public void load(CacheEntry entry) {
285: if (entry.exists) {
286: if (insertCache(entry)) {
287: cacheSize += entry.size;
288: }
289: } else {
290: int sizeIncrement = (notFoundCache.get(entry.name) == null) ? 1
291: : 0;
292: notFoundCache.put(entry.name, entry);
293: cacheSize += sizeIncrement;
294: }
295: }
296:
297: public boolean unload(String name) {
298: CacheEntry removedEntry = removeCache(name);
299: if (removedEntry != null) {
300: cacheSize -= removedEntry.size;
301: return true;
302: } else if (notFoundCache.remove(name) != null) {
303: cacheSize--;
304: return true;
305: }
306: return false;
307: }
308:
309: /**
310: * Find a map elemnt given its name in a sorted array of map elements.
311: * This will return the index for the closest inferior or equal item in the
312: * given array.
313: */
314: private static final int find(CacheEntry[] map, String name) {
315:
316: int a = 0;
317: int b = map.length - 1;
318:
319: // Special cases: -1 and 0
320: if (b == -1) {
321: return -1;
322: }
323: if (name.compareTo(map[0].name) < 0) {
324: return -1;
325: }
326: if (b == 0) {
327: return 0;
328: }
329:
330: int i = 0;
331: while (true) {
332: i = (b + a) / 2;
333: int result = name.compareTo(map[i].name);
334: if (result > 0) {
335: a = i;
336: } else if (result == 0) {
337: return i;
338: } else {
339: b = i;
340: }
341: if ((b - a) == 1) {
342: int result2 = name.compareTo(map[b].name);
343: if (result2 < 0) {
344: return a;
345: } else {
346: return b;
347: }
348: }
349: }
350:
351: }
352:
353: /**
354: * Insert into the right place in a sorted MapElement array, and prevent
355: * duplicates.
356: */
357: private final boolean insertCache(CacheEntry newElement) {
358: CacheEntry[] oldCache = cache;
359: int pos = find(oldCache, newElement.name);
360: if ((pos != -1) && (newElement.name.equals(oldCache[pos].name))) {
361: return false;
362: }
363: CacheEntry[] newCache = new CacheEntry[cache.length + 1];
364: System.arraycopy(oldCache, 0, newCache, 0, pos + 1);
365: newCache[pos + 1] = newElement;
366: System.arraycopy(oldCache, pos + 1, newCache, pos + 2,
367: oldCache.length - pos - 1);
368: cache = newCache;
369: return true;
370: }
371:
372: /**
373: * Insert into the right place in a sorted MapElement array.
374: */
375: private final CacheEntry removeCache(String name) {
376: CacheEntry[] oldCache = cache;
377: int pos = find(oldCache, name);
378: if ((pos != -1) && (name.equals(oldCache[pos].name))) {
379: CacheEntry[] newCache = new CacheEntry[cache.length - 1];
380: System.arraycopy(oldCache, 0, newCache, 0, pos);
381: System.arraycopy(oldCache, pos + 1, newCache, pos,
382: oldCache.length - pos - 1);
383: cache = newCache;
384: return oldCache[pos];
385: }
386: return null;
387: }
388:
389: }
|