001: /**
002: * $Revision$
003: * $Date$
004: *
005: * Copyright (C) 1999-2005 Jive Software. All rights reserved.
006: * This software is the proprietary information of Jive Software. Use is subject to license terms.
007: */package org.jivesoftware.util.cache;
008:
009: import org.jivesoftware.util.LinkedListNode;
010: import org.jivesoftware.util.Log;
011:
012: import java.io.IOException;
013: import java.io.ObjectOutputStream;
014: import java.io.OutputStream;
015: import java.util.*;
016:
017: /**
018: * Default, non-distributed implementation of the Cache interface.
019: * The algorithm for cache is as follows: a HashMap is maintained for fast
020: * object lookup. Two linked lists are maintained: one keeps objects in the
021: * order they are accessed from cache, the other keeps objects in the order
022: * they were originally added to cache. When objects are added to cache, they
023: * are first wrapped by a CacheObject which maintains the following pieces
024: * of information:<ul>
025: *
026: * <li> The size of the object (in bytes).
027: * <li> A pointer to the node in the linked list that maintains accessed
028: * order for the object. Keeping a reference to the node lets us avoid
029: * linear scans of the linked list.
030: * <li> A pointer to the node in the linked list that maintains the age
031: * of the object in cache. Keeping a reference to the node lets us avoid
032: * linear scans of the linked list.</ul><p>
033: *
034: * To get an object from cache, a hash lookup is performed to get a reference
035: * to the CacheObject that wraps the real object we are looking for.
036: * The object is subsequently moved to the front of the accessed linked list
037: * and any necessary cache cleanups are performed. Cache deletion and expiration
038: * is performed as needed.
039: *
040: * @author Matt Tucker
041: */
042: public class DefaultCache<K, V> implements Cache<K, V> {
043:
044: /**
045: * The map the keys and values are stored in.
046: */
047: protected Map<K, DefaultCache.CacheObject<V>> map;
048:
049: /**
050: * Linked list to maintain order that cache objects are accessed
051: * in, most used to least used.
052: */
053: protected org.jivesoftware.util.LinkedList lastAccessedList;
054:
055: /**
056: * Linked list to maintain time that cache objects were initially added
057: * to the cache, most recently added to oldest added.
058: */
059: protected org.jivesoftware.util.LinkedList ageList;
060:
061: /**
062: * Maximum size in bytes that the cache can grow to.
063: */
064: private long maxCacheSize;
065:
066: /**
067: * Maintains the current size of the cache in bytes.
068: */
069: private int cacheSize = 0;
070:
071: /**
072: * Maximum length of time objects can exist in cache before expiring.
073: */
074: protected long maxLifetime;
075:
076: /**
077: * Maintain the number of cache hits and misses. A cache hit occurs every
078: * time the get method is called and the cache contains the requested
079: * object. A cache miss represents the opposite occurence.<p>
080: *
081: * Keeping track of cache hits and misses lets one measure how efficient
082: * the cache is; the higher the percentage of hits, the more efficient.
083: */
084: protected long cacheHits, cacheMisses = 0L;
085:
086: /**
087: * The name of the cache.
088: */
089: private String name;
090:
091: /**
092: * Create a new default cache and specify the maximum size of for the cache in
093: * bytes, and the maximum lifetime of objects.
094: *
095: * @param name a name for the cache.
096: * @param maxSize the maximum size of the cache in bytes. -1 means the cache
097: * has no max size.
098: * @param maxLifetime the maximum amount of time objects can exist in
099: * cache before being deleted. -1 means objects never expire.
100: */
101: public DefaultCache(String name, long maxSize, long maxLifetime) {
102: this .name = name;
103: this .maxCacheSize = maxSize;
104: this .maxLifetime = maxLifetime;
105:
106: // Our primary data structure is a HashMap. The default capacity of 11
107: // is too small in almost all cases, so we set it bigger.
108: map = new HashMap<K, CacheObject<V>>(103);
109:
110: lastAccessedList = new org.jivesoftware.util.LinkedList();
111: ageList = new org.jivesoftware.util.LinkedList();
112: }
113:
114: public synchronized V put(K key, V value) {
115: // Delete an old entry if it exists.
116: V answer = remove(key);
117:
118: int objectSize = calculateSize(value);
119:
120: // If the object is bigger than the entire cache, simply don't add it.
121: if (maxCacheSize > 0 && objectSize > maxCacheSize * .90) {
122: Log.warn("Cache: " + name + " -- object with key " + key
123: + " is too large to fit in cache. Size is "
124: + objectSize);
125: return value;
126: }
127: cacheSize += objectSize;
128: DefaultCache.CacheObject<V> cacheObject = new DefaultCache.CacheObject<V>(
129: value, objectSize);
130: map.put(key, cacheObject);
131: // Make an entry into the cache order list.
132: LinkedListNode lastAccessedNode = lastAccessedList
133: .addFirst(key);
134: // Store the cache order list entry so that we can get back to it
135: // during later lookups.
136: cacheObject.lastAccessedListNode = lastAccessedNode;
137: // Add the object to the age list
138: LinkedListNode ageNode = ageList.addFirst(key);
139: // We make an explicit call to currentTimeMillis() so that total accuracy
140: // of lifetime calculations is better than one second.
141: ageNode.timestamp = System.currentTimeMillis();
142: cacheObject.ageListNode = ageNode;
143:
144: // If cache is too full, remove least used cache entries until it is
145: // not too full.
146: cullCache();
147:
148: return answer;
149: }
150:
151: public synchronized V get(Object key) {
152: // First, clear all entries that have been in cache longer than the
153: // maximum defined age.
154: deleteExpiredEntries();
155:
156: DefaultCache.CacheObject<V> cacheObject = map.get(key);
157: if (cacheObject == null) {
158: // The object didn't exist in cache, so increment cache misses.
159: cacheMisses++;
160: return null;
161: }
162:
163: // The object exists in cache, so increment cache hits. Also, increment
164: // the object's read count.
165: cacheHits++;
166: cacheObject.readCount++;
167:
168: // Remove the object from it's current place in the cache order list,
169: // and re-insert it at the front of the list.
170: cacheObject.lastAccessedListNode.remove();
171: lastAccessedList.addFirst(cacheObject.lastAccessedListNode);
172:
173: return cacheObject.object;
174: }
175:
176: public synchronized V remove(Object key) {
177: DefaultCache.CacheObject<V> cacheObject = map.get(key);
178: // If the object is not in cache, stop trying to remove it.
179: if (cacheObject == null) {
180: return null;
181: }
182: // remove from the hash map
183: map.remove(key);
184: // remove from the cache order list
185: cacheObject.lastAccessedListNode.remove();
186: cacheObject.ageListNode.remove();
187: // remove references to linked list nodes
188: cacheObject.ageListNode = null;
189: cacheObject.lastAccessedListNode = null;
190: // removed the object, so subtract its size from the total.
191: cacheSize -= cacheObject.size;
192: return cacheObject.object;
193: }
194:
195: public synchronized void clear() {
196: Object[] keys = map.keySet().toArray();
197: for (int i = 0; i < keys.length; i++) {
198: remove(keys[i]);
199: }
200:
201: // Now, reset all containers.
202: map.clear();
203: lastAccessedList.clear();
204: lastAccessedList = new org.jivesoftware.util.LinkedList();
205: ageList.clear();
206: ageList = new org.jivesoftware.util.LinkedList();
207:
208: cacheSize = 0;
209: cacheHits = 0;
210: cacheMisses = 0;
211: }
212:
213: public int size() {
214: // First, clear all entries that have been in cache longer than the
215: // maximum defined age.
216: deleteExpiredEntries();
217:
218: return map.size();
219: }
220:
221: public boolean isEmpty() {
222: // First, clear all entries that have been in cache longer than the
223: // maximum defined age.
224: deleteExpiredEntries();
225:
226: return map.isEmpty();
227: }
228:
229: public Collection<V> values() {
230: // First, clear all entries that have been in cache longer than the
231: // maximum defined age.
232: deleteExpiredEntries();
233: return new DefaultCache.CacheObjectCollection(map.values());
234: }
235:
236: /**
237: * Wraps a cached object collection to return a view of its inner objects
238: */
239: private final class CacheObjectCollection<V> implements
240: Collection<V> {
241: private Collection<DefaultCache.CacheObject<V>> cachedObjects;
242:
243: private CacheObjectCollection(
244: Collection<DefaultCache.CacheObject<V>> cachedObjects) {
245: this .cachedObjects = new ArrayList<CacheObject<V>>(
246: cachedObjects);
247: }
248:
249: public int size() {
250: return cachedObjects.size();
251: }
252:
253: public boolean isEmpty() {
254: return size() == 0;
255: }
256:
257: public boolean contains(Object o) {
258: Iterator<V> it = iterator();
259: while (it.hasNext()) {
260: if (it.next().equals(o)) {
261: return true;
262: }
263: }
264: return false;
265: }
266:
267: public Iterator<V> iterator() {
268: return new Iterator<V>() {
269: private final Iterator<DefaultCache.CacheObject<V>> it = cachedObjects
270: .iterator();
271:
272: public boolean hasNext() {
273: return it.hasNext();
274: }
275:
276: public V next() {
277: if (it.hasNext()) {
278: DefaultCache.CacheObject<V> object = it.next();
279: if (object == null) {
280: return null;
281: } else {
282: return object.object;
283: }
284: } else {
285: throw new NoSuchElementException();
286: }
287: }
288:
289: public void remove() {
290: throw new UnsupportedOperationException();
291: }
292: };
293: }
294:
295: public Object[] toArray() {
296: Object[] array = new Object[size()];
297: Iterator it = iterator();
298: int i = 0;
299: while (it.hasNext()) {
300: array[i] = it.next();
301: }
302: return array;
303: }
304:
305: public <V> V[] toArray(V[] a) {
306: Iterator<V> it = (Iterator<V>) iterator();
307: int i = 0;
308: while (it.hasNext()) {
309: a[i++] = it.next();
310: }
311: return a;
312: }
313:
314: public boolean containsAll(Collection<?> c) {
315: Iterator it = c.iterator();
316: while (it.hasNext()) {
317: if (!contains(it.next())) {
318: return false;
319: }
320: }
321: return true;
322: }
323:
324: public boolean add(V o) {
325: throw new UnsupportedOperationException();
326: }
327:
328: public boolean remove(Object o) {
329: throw new UnsupportedOperationException();
330: }
331:
332: public boolean addAll(Collection<? extends V> coll) {
333: throw new UnsupportedOperationException();
334: }
335:
336: public boolean removeAll(Collection<?> coll) {
337: throw new UnsupportedOperationException();
338: }
339:
340: public boolean retainAll(Collection<?> coll) {
341: throw new UnsupportedOperationException();
342: }
343:
344: public void clear() {
345: throw new UnsupportedOperationException();
346: }
347: }
348:
349: public boolean containsKey(Object key) {
350: // First, clear all entries that have been in cache longer than the
351: // maximum defined age.
352: deleteExpiredEntries();
353:
354: return map.containsKey(key);
355: }
356:
357: public void putAll(Map<? extends K, ? extends V> map) {
358: for (Iterator<? extends K> i = map.keySet().iterator(); i
359: .hasNext();) {
360: K key = i.next();
361: V value = map.get(key);
362: put(key, value);
363: }
364: }
365:
366: public boolean containsValue(Object value) {
367: // First, clear all entries that have been in cache longer than the
368: // maximum defined age.
369: deleteExpiredEntries();
370:
371: if (value == null) {
372: return containsNullValue();
373: }
374:
375: Iterator it = values().iterator();
376: while (it.hasNext()) {
377: if (value.equals(it.next())) {
378: return true;
379: }
380: }
381: return false;
382: }
383:
384: private boolean containsNullValue() {
385: Iterator it = values().iterator();
386: while (it.hasNext()) {
387: if (it.next() == null) {
388: return true;
389: }
390: }
391: return false;
392: }
393:
394: public Set<Entry<K, V>> entrySet() {
395: // First, clear all entries that have been in cache longer than the
396: // maximum defined age.
397: deleteExpiredEntries();
398: // TODO Make this work right
399:
400: synchronized (this ) {
401: final Map<K, V> result = new HashMap<K, V>();
402: for (final Entry<K, DefaultCache.CacheObject<V>> entry : map
403: .entrySet()) {
404: result.put(entry.getKey(), entry.getValue().object);
405: }
406: return result.entrySet();
407: }
408: }
409:
410: public Set<K> keySet() {
411: // First, clear all entries that have been in cache longer than the
412: // maximum defined age.
413: deleteExpiredEntries();
414: synchronized (this ) {
415: return new HashSet<K>(map.keySet());
416: }
417: }
418:
419: /**
420: * Returns the name of this cache. The name is completely arbitrary
421: * and used only for display to administrators.
422: *
423: * @return the name of this cache.
424: */
425: public String getName() {
426: return name;
427: }
428:
429: /**
430: * Sets the name of this cache.
431: *
432: * @param name the name of this cache.
433: */
434: public void setName(String name) {
435: this .name = name;
436: }
437:
438: /**
439: * Returns the number of cache hits. A cache hit occurs every
440: * time the get method is called and the cache contains the requested
441: * object.<p>
442: *
443: * Keeping track of cache hits and misses lets one measure how efficient
444: * the cache is; the higher the percentage of hits, the more efficient.
445: *
446: * @return the number of cache hits.
447: */
448: public long getCacheHits() {
449: return cacheHits;
450: }
451:
452: /**
453: * Returns the number of cache misses. A cache miss occurs every
454: * time the get method is called and the cache does not contain the
455: * requested object.<p>
456: *
457: * Keeping track of cache hits and misses lets one measure how efficient
458: * the cache is; the higher the percentage of hits, the more efficient.
459: *
460: * @return the number of cache hits.
461: */
462: public long getCacheMisses() {
463: return cacheMisses;
464: }
465:
466: /**
467: * Returns the size of the cache contents in bytes. This value is only a
468: * rough approximation, so cache users should expect that actual VM
469: * memory used by the cache could be significantly higher than the value
470: * reported by this method.
471: *
472: * @return the size of the cache contents in bytes.
473: */
474: public int getCacheSize() {
475: return cacheSize;
476: }
477:
478: /**
479: * Returns the maximum size of the cache (in bytes). If the cache grows larger
480: * than the max size, the least frequently used items will be removed. If
481: * the max cache size is set to -1, there is no size limit.
482: *
483: * @return the maximum size of the cache (-1 indicates unlimited max size).
484: */
485: public long getMaxCacheSize() {
486: return maxCacheSize;
487: }
488:
489: /**
490: * Sets the maximum size of the cache. If the cache grows larger
491: * than the max size, the least frequently used items will be removed. If
492: * the max cache size is set to -1, there is no size limit.
493: *
494: * @param maxCacheSize the maximum size of this cache (-1 indicates unlimited max size).
495: */
496: public void setMaxCacheSize(int maxCacheSize) {
497: this .maxCacheSize = maxCacheSize;
498: CacheFactory.setMaxSizeProperty(name, maxCacheSize);
499: // It's possible that the new max size is smaller than our current cache
500: // size. If so, we need to delete infrequently used items.
501: cullCache();
502: }
503:
504: /**
505: * Returns the maximum number of milleseconds that any object can live
506: * in cache. Once the specified number of milleseconds passes, the object
507: * will be automatically expried from cache. If the max lifetime is set
508: * to -1, then objects never expire.
509: *
510: * @return the maximum number of milleseconds before objects are expired.
511: */
512: public long getMaxLifetime() {
513: return maxLifetime;
514: }
515:
516: /**
517: * Sets the maximum number of milleseconds that any object can live
518: * in cache. Once the specified number of milleseconds passes, the object
519: * will be automatically expried from cache. If the max lifetime is set
520: * to -1, then objects never expire.
521: *
522: * @param maxLifetime the maximum number of milleseconds before objects are expired.
523: */
524: public void setMaxLifetime(long maxLifetime) {
525: this .maxLifetime = maxLifetime;
526: CacheFactory.setMaxLifetimeProperty(name, maxLifetime);
527: }
528:
529: /**
530: * Returns the size of an object in bytes. Determining size by serialization
531: * is only used as a last resort.
532: *
533: * @return the size of an object in bytes.
534: */
535: private int calculateSize(Object object) {
536: // If the object is Cacheable, ask it its size.
537: if (object instanceof Cacheable) {
538: return ((Cacheable) object).getCachedSize();
539: }
540: // Check for other common types of objects put into cache.
541: else if (object instanceof String) {
542: return CacheSizes.sizeOfString((String) object);
543: } else if (object instanceof Long) {
544: return CacheSizes.sizeOfLong();
545: } else if (object instanceof Integer) {
546: return CacheSizes.sizeOfObject() + CacheSizes.sizeOfInt();
547: } else if (object instanceof Boolean) {
548: return CacheSizes.sizeOfObject()
549: + CacheSizes.sizeOfBoolean();
550: } else if (object instanceof long[]) {
551: long[] array = (long[]) object;
552: return CacheSizes.sizeOfObject() + array.length
553: * CacheSizes.sizeOfLong();
554: } else if (object instanceof byte[]) {
555: byte[] array = (byte[]) object;
556: return CacheSizes.sizeOfObject() + array.length;
557: }
558: // Default behavior -- serialize the object to determine its size.
559: else {
560: int size = 1;
561: try {
562: // Default to serializing the object out to determine size.
563: DefaultCache.NullOutputStream out = new DefaultCache.NullOutputStream();
564: ObjectOutputStream outObj = new ObjectOutputStream(out);
565: outObj.writeObject(object);
566: size = out.size();
567: } catch (IOException ioe) {
568: Log.error(ioe);
569: }
570: return size;
571: }
572: }
573:
574: /**
575: * Clears all entries out of cache where the entries are older than the
576: * maximum defined age.
577: */
578: protected void deleteExpiredEntries() {
579: // Check if expiration is turned on.
580: if (maxLifetime <= 0) {
581: return;
582: }
583:
584: // Remove all old entries. To do this, we remove objects from the end
585: // of the linked list until they are no longer too old. We get to avoid
586: // any hash lookups or looking at any more objects than is strictly
587: // neccessary.
588: LinkedListNode node = ageList.getLast();
589: // If there are no entries in the age list, return.
590: if (node == null) {
591: return;
592: }
593:
594: // Determine the expireTime, which is the moment in time that elements
595: // should expire from cache. Then, we can do an easy to check to see
596: // if the expire time is greater than the expire time.
597: long expireTime = System.currentTimeMillis() - maxLifetime;
598:
599: while (expireTime > node.timestamp) {
600: // Remove the object
601: remove(node.object);
602:
603: // Get the next node.
604: node = ageList.getLast();
605: // If there are no more entries in the age list, return.
606: if (node == null) {
607: return;
608: }
609: }
610: }
611:
612: /**
613: * Removes objects from cache if the cache is too full. "Too full" is
614: * defined as within 3% of the maximum cache size. Whenever the cache is
615: * is too big, the least frequently used elements are deleted until the
616: * cache is at least 10% empty.
617: */
618: protected final void cullCache() {
619: // Check if a max cache size is defined.
620: if (maxCacheSize < 0) {
621: return;
622: }
623:
624: // See if the cache size is within 3% of being too big. If so, clean out
625: // cache until it's 10% free.
626: if (cacheSize >= maxCacheSize * .97) {
627: // First, delete any old entries to see how much memory that frees.
628: deleteExpiredEntries();
629: int desiredSize = (int) (maxCacheSize * .90);
630: while (cacheSize > desiredSize) {
631: // Get the key and invoke the remove method on it.
632: remove(lastAccessedList.getLast().object);
633: }
634: }
635: }
636:
637: /**
638: * Wrapper for all objects put into cache. It's primary purpose is to maintain
639: * references to the linked lists that maintain the creation time of the object
640: * and the ordering of the most used objects.
641: */
642: private static class CacheObject<V> {
643:
644: /**
645: * Underlying object wrapped by the CacheObject.
646: */
647: public V object;
648:
649: /**
650: * The size of the Cacheable object. The size of the Cacheable
651: * object is only computed once when it is added to the cache. This makes
652: * the assumption that once objects are added to cache, they are mostly
653: * read-only and that their size does not change significantly over time.
654: */
655: public int size;
656:
657: /**
658: * A reference to the node in the cache order list. We keep the reference
659: * here to avoid linear scans of the list. Every time the object is
660: * accessed, the node is removed from its current spot in the list and
661: * moved to the front.
662: */
663: public LinkedListNode lastAccessedListNode;
664:
665: /**
666: * A reference to the node in the age order list. We keep the reference
667: * here to avoid linear scans of the list. The reference is used if the
668: * object has to be deleted from the list.
669: */
670: public LinkedListNode ageListNode;
671:
672: /**
673: * A count of the number of times the object has been read from cache.
674: */
675: public int readCount = 0;
676:
677: /**
678: * Creates a new cache object wrapper. The size of the Cacheable object
679: * must be passed in in order to prevent another possibly expensive
680: * lookup by querying the object itself for its size.<p>
681: *
682: * @param object the underlying Object to wrap.
683: * @param size the size of the Cachable object in bytes.
684: */
685: public CacheObject(V object, int size) {
686: this .object = object;
687: this .size = size;
688: }
689: }
690:
691: /**
692: * An extension of OutputStream that does nothing but calculate the number
693: * of bytes written through it.
694: */
695: private static class NullOutputStream extends OutputStream {
696:
697: int size = 0;
698:
699: public void write(int b) throws IOException {
700: size++;
701: }
702:
703: public void write(byte[] b) throws IOException {
704: size += b.length;
705: }
706:
707: public void write(byte[] b, int off, int len) {
708: size += len;
709: }
710:
711: /**
712: * Returns the number of bytes written out through the stream.
713: *
714: * @return the number of bytes written to the stream.
715: */
716: public int size() {
717: return size;
718: }
719: }
720: }
|