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