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