KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > naming > resources > ResourceCache


1 /*
2  * Licensed to the Apache Software Foundation (ASF) under one or more
3  * contributor license agreements. See the NOTICE file distributed with
4  * this work for additional information regarding copyright ownership.
5  * The ASF licenses this file to You under the Apache License, Version 2.0
6  * (the "License"); you may not use this file except in compliance with
7  * the License. You may obtain a copy of the License at
8  *
9  * http://www.apache.org/licenses/LICENSE-2.0
10  *
11  * Unless required by applicable law or agreed to in writing, software
12  * distributed under the License is distributed on an "AS IS" BASIS,
13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  * See the License for the specific language governing permissions and
15  * limitations under the License.
16  */
17
18 package org.apache.naming.resources;
19
20 import java.util.HashMap JavaDoc;
21 import java.util.Random JavaDoc;
22
23
24 /**
25  * Implements a special purpose cache.
26  *
27  * @author <a HREF="mailto:remm@apache.org">Remy Maucherat</a>
28  * @version $Revision: 467222 $
29  */
30 public class ResourceCache {
31     
32     
33     // ----------------------------------------------------------- Constructors
34
35     
36     public ResourceCache() {
37     }
38     
39     
40     // ----------------------------------------------------- Instance Variables
41
42
43     /**
44      * Random generator used to determine elements to free.
45      */
46     protected Random JavaDoc random = new Random JavaDoc();
47
48
49     /**
50      * Cache.
51      * Path -> Cache entry.
52      */
53     protected CacheEntry[] cache = new CacheEntry[0];
54
55
56     /**
57      * Not found cache.
58      */
59     protected HashMap JavaDoc notFoundCache = new HashMap JavaDoc();
60
61
62     /**
63      * Max size of resources which will have their content cached.
64      */
65     protected int cacheMaxSize = 10240; // 10 MB
66
67
68     /**
69      * Max amount of removals during a make space.
70      */
71     protected int maxAllocateIterations = 20;
72
73
74     /**
75      * Entry hit ratio at which an entry will never be removed from the cache.
76      * Compared with entry.access / hitsCount
77      */
78     protected long desiredEntryAccessRatio = 3;
79
80
81     /**
82      * Spare amount of not found entries.
83      */
84     protected int spareNotFoundEntries = 500;
85
86
87     /**
88      * Current cache size in KB.
89      */
90     protected int cacheSize = 0;
91
92
93     /**
94      * Number of accesses to the cache.
95      */
96     protected long accessCount = 0;
97
98
99     /**
100      * Number of cache hits.
101      */
102     protected long hitsCount = 0;
103
104
105     // ------------------------------------------------------------- Properties
106
107
108     /**
109      * Return the access count.
110      * Note: Update is not synced, so the number may not be completely
111      * accurate.
112      */
113     public long getAccessCount() {
114         return accessCount;
115     }
116
117
118     /**
119      * Return the maximum size of the cache in KB.
120      */
121     public int getCacheMaxSize() {
122         return cacheMaxSize;
123     }
124
125
126     /**
127      * Set the maximum size of the cache in KB.
128      */
129     public void setCacheMaxSize(int cacheMaxSize) {
130         this.cacheMaxSize = cacheMaxSize;
131     }
132
133
134     /**
135      * Return the current cache size in KB.
136      */
137     public int getCacheSize() {
138         return cacheSize;
139     }
140
141
142     /**
143      * Return desired entry access ratio.
144      */
145     public long getDesiredEntryAccessRatio() {
146         return desiredEntryAccessRatio;
147     }
148
149
150     /**
151      * Set the desired entry access ratio.
152      */
153     public void setDesiredEntryAccessRatio(long desiredEntryAccessRatio) {
154         this.desiredEntryAccessRatio = desiredEntryAccessRatio;
155     }
156
157
158     /**
159      * Return the number of cache hits.
160      * Note: Update is not synced, so the number may not be completely
161      * accurate.
162      */
163     public long getHitsCount() {
164         return hitsCount;
165     }
166
167
168     /**
169      * Return the maximum amount of iterations during a space allocation.
170      */
171     public int getMaxAllocateIterations() {
172         return maxAllocateIterations;
173     }
174
175
176     /**
177      * Set the maximum amount of iterations during a space allocation.
178      */
179     public void setMaxAllocateIterations(int maxAllocateIterations) {
180         this.maxAllocateIterations = maxAllocateIterations;
181     }
182
183
184     /**
185      * Return the amount of spare not found entries.
186      */
187     public int getSpareNotFoundEntries() {
188         return spareNotFoundEntries;
189     }
190
191
192     /**
193      * Set the amount of spare not found entries.
194      */
195     public void setSpareNotFoundEntries(int spareNotFoundEntries) {
196         this.spareNotFoundEntries = spareNotFoundEntries;
197     }
198
199
200     // --------------------------------------------------------- Public Methods
201
202
203     public boolean allocate(int space) {
204
205         int toFree = space - (cacheMaxSize - cacheSize);
206
207         if (toFree <= 0) {
208             return true;
209         }
210
211         // Increase the amount to free so that allocate won't have to run right
212 // away again
213 toFree += (cacheMaxSize / 20);
214
215         int size = notFoundCache.size();
216         if (size > spareNotFoundEntries) {
217             notFoundCache.clear();
218             cacheSize -= size;
219             toFree -= size;
220         }
221
222         if (toFree <= 0) {
223             return true;
224         }
225
226         int attempts = 0;
227         int entriesFound = 0;
228         long totalSpace = 0;
229         int[] toRemove = new int[maxAllocateIterations];
230         while (toFree > 0) {
231             if (attempts == maxAllocateIterations) {
232                 // Give up, no changes are made to the current cache
233 return false;
234             }
235             if (toFree > 0) {
236                 // Randomly select an entry in the array
237 int entryPos = -1;
238                 boolean unique = false;
239                 while (!unique) {
240                     unique = true;
241                     entryPos = random.nextInt(cache.length) ;
242                     // Guarantee uniqueness
243 for (int i = 0; i < entriesFound; i++) {
244                         if (toRemove[i] == entryPos) {
245                             unique = false;
246                         }
247                     }
248                 }
249                 long entryAccessRatio =
250                     ((cache[entryPos].accessCount * 100) / accessCount);
251                 if (entryAccessRatio < desiredEntryAccessRatio) {
252                     toRemove[entriesFound] = entryPos;
253                     totalSpace += cache[entryPos].size;
254                     toFree -= cache[entryPos].size;
255                     entriesFound++;
256                 }
257             }
258             attempts++;
259         }
260
261         // Now remove the selected entries
262 java.util.Arrays.sort(toRemove, 0, entriesFound);
263         CacheEntry[] newCache = new CacheEntry[cache.length - entriesFound];
264         int pos = 0;
265         int n = -1;
266         if (entriesFound > 0) {
267             n = toRemove[0];
268             for (int i = 0; i < cache.length; i++) {
269                 if (i == n) {
270                     if ((pos + 1) < entriesFound) {
271                         n = toRemove[pos + 1];
272                         pos++;
273                     } else {
274                         pos++;
275                         n = -1;
276                     }
277                 } else {
278                     newCache[i - pos] = cache[i];
279                 }
280             }
281         }
282         cache = newCache;
283         cacheSize -= totalSpace;
284
285         return true;
286
287     }
288
289
290     public CacheEntry lookup(String JavaDoc name) {
291
292         CacheEntry cacheEntry = null;
293         CacheEntry[] currentCache = cache;
294         accessCount++;
295         int pos = find(currentCache, name);
296         if ((pos != -1) && (name.equals(currentCache[pos].name))) {
297             cacheEntry = currentCache[pos];
298         }
299         if (cacheEntry == null) {
300             try {
301                 cacheEntry = (CacheEntry) notFoundCache.get(name);
302             } catch (Exception JavaDoc e) {
303                 // Ignore: the reliability of this lookup is not critical
304 }
305         }
306         if (cacheEntry != null) {
307             hitsCount++;
308         }
309         return cacheEntry;
310
311     }
312
313
314     public void load(CacheEntry entry) {
315         if (entry.exists) {
316             if (insertCache(entry)) {
317                 cacheSize += entry.size;
318             }
319         } else {
320             int sizeIncrement = (notFoundCache.get(entry.name) == null) ? 1 : 0;
321             notFoundCache.put(entry.name, entry);
322             cacheSize += sizeIncrement;
323         }
324     }
325
326
327     public boolean unload(String JavaDoc name) {
328         CacheEntry removedEntry = removeCache(name);
329         if (removedEntry != null) {
330             cacheSize -= removedEntry.size;
331             return true;
332         } else if (notFoundCache.remove(name) != null) {
333             cacheSize--;
334             return true;
335         }
336         return false;
337     }
338
339
340     /**
341      * Find a map elemnt given its name in a sorted array of map elements.
342      * This will return the index for the closest inferior or equal item in the
343      * given array.
344      */
345     private static final int find(CacheEntry[] map, String JavaDoc name) {
346
347         int a = 0;
348         int b = map.length - 1;
349
350         // Special cases: -1 and 0
351 if (b == -1) {
352             return -1;
353         }
354         if (name.compareTo(map[0].name) < 0) {
355             return -1;
356         }
357         if (b == 0) {
358             return 0;
359         }
360
361         int i = 0;
362         while (true) {
363             i = (b + a) / 2;
364             int result = name.compareTo(map[i].name);
365             if (result > 0) {
366                 a = i;
367             } else if (result == 0) {
368                 return i;
369             } else {
370                 b = i;
371             }
372             if ((b - a) == 1) {
373                 int result2 = name.compareTo(map[b].name);
374                 if (result2 < 0) {
375                     return a;
376                 } else {
377                     return b;
378                 }
379             }
380         }
381
382     }
383
384
385     /**
386      * Insert into the right place in a sorted MapElement array, and prevent
387      * duplicates.
388      */
389     private final boolean insertCache(CacheEntry newElement) {
390         CacheEntry[] oldCache = cache;
391         int pos = find(oldCache, newElement.name);
392         if ((pos != -1) && (newElement.name.equals(oldCache[pos].name))) {
393             return false;
394         }
395         CacheEntry[] newCache = new CacheEntry[cache.length + 1];
396         System.arraycopy(oldCache, 0, newCache, 0, pos + 1);
397         newCache[pos + 1] = newElement;
398         System.arraycopy
399             (oldCache, pos + 1, newCache, pos + 2, oldCache.length - pos - 1);
400         cache = newCache;
401         return true;
402     }
403
404
405     /**
406      * Insert into the right place in a sorted MapElement array.
407      */
408     private final CacheEntry removeCache(String JavaDoc name) {
409         CacheEntry[] oldCache = cache;
410         int pos = find(oldCache, name);
411         if ((pos != -1) && (name.equals(oldCache[pos].name))) {
412             CacheEntry[] newCache = new CacheEntry[cache.length - 1];
413             System.arraycopy(oldCache, 0, newCache, 0, pos);
414             System.arraycopy(oldCache, pos + 1, newCache, pos,
415                              oldCache.length - pos - 1);
416             cache = newCache;
417             return oldCache[pos];
418         }
419         return null;
420     }
421
422 }
423
Popular Tags