001: /* CacheMap.java
002:
003: {{IS_NOTE
004:
005: Purpose:
006: Description:
007: History:
008: 2001/11/23 15:26:21, Create, Tom M. Yeh.
009: }}IS_NOTE
010:
011: Copyright (C) 2001 Potix Corporation. All Rights Reserved.
012:
013: {{IS_RIGHT
014: This program is distributed under GPL Version 2.0 in the hope that
015: it will be useful, but WITHOUT ANY WARRANTY.
016: }}IS_RIGHT
017: */
018: package org.zkoss.util;
019:
020: import java.util.AbstractCollection;
021: import java.util.Collection;
022: import java.util.Map;
023: import java.util.AbstractSet;
024: import java.util.Set;
025: import java.util.LinkedHashMap;
026: import java.util.Iterator;
027: import java.lang.ref.Reference;
028: import java.lang.ref.WeakReference;
029: import java.lang.ref.ReferenceQueue;
030:
031: import org.zkoss.lang.D;
032: import org.zkoss.lang.Objects;
033: import org.zkoss.util.logging.Log;
034:
035: /**
036: * The cache map. The key-to-value mappings hold in this map is
037: * temporary. They are removed when GC demanding memory and a
038: * criteria is met. The criteria is whether the mapping is old enough
039: * (called lifetime), or the upper bound is hit (called max-size).
040: *
041: * <p>The criteria can be changed by overriding {@link #canExpunge}.
042: * When to check the criteria can be changed by overriding
043: * {@link #shallExpunge}.
044: *
045: * <p>If the criteria is totally independent of GC, you could override
046: * {@link #newQueue} to return null. Then, {@link #shallExpunge}
047: * always returns true (rather than when GC is activated) -- of course,
048: * you could override {@link #shallExpunge}, too.
049: *
050: * <p>It is different from WeakHashMap:
051: *
052: * <ul>
053: * <li>The mapping might be removed even if the key is hold somewhere
054: * (i.e., strong reachable).</li>
055: * <li>The mapping might not be removed when GC demanding memory
056: * if the criteria doesn't meet.</li>
057: * <li>It is not serializable.</li>
058: * </ul>
059: *
060: * <p>Like other maps, it is not thread-safe. To get one, use
061: * java.util.Collections.synchronizedMap.
062: *
063: * <p>Implementation Note: there is another version of CacheMap that
064: * uses WeakReference for each value (refer to obsolete).
065: * The drawback is that all mapping will be queued and need to be examined,
066: * because GC tends to release all reference at once.
067: *
068: * <p>We don't use PhantomReference because it is still required to
069: * re-create the reference after enqueued.
070: *
071: * @author tomyeh
072: */
073: public class CacheMap implements Map, Cache, java.io.Serializable,
074: Cloneable {
075: private static final long serialVersionUID = 20070907L;
076: //private static final Log log = Log.lookup(CacheMap.class);
077:
078: /** @deprecated As of release 3.0.0, replaced by {@link Cache#DEFAULT_MAX_SIZE}.
079: */
080: public static final int DEFAULT_MAXSIZE = 1024;
081:
082: /** The map to store the mappings. */
083: private Map _map; //it is OK to serialized
084: /** The minimal lifetime. */
085: private int _lifetime = DEFAULT_LIFETIME;
086: /** The maximal allowed size. */
087: private int _maxsize = DEFAULT_MAX_SIZE;
088: /** The reference queue. */
089: private transient ReferenceQueue _que;
090: /** The reference. */
091: private transient WeakReference _ref;
092: /** A flag used for debug purpose. */
093: private transient boolean _inExpunge;
094:
095: /** The class to be hold in the reference (to know GC is demanding). */
096: private static class X {
097: }
098:
099: /** The class to hold key/value. */
100: protected static final class Value implements java.io.Serializable,
101: Cloneable {
102: private Object value;
103: private long access; //when the mapping is accessed
104:
105: /** Creates an instance to store in the map. */
106: private Value(Object value) {
107: this .value = value;
108: updateAccessTime();
109: }
110:
111: private final void updateAccessTime() {
112: this .access = System.currentTimeMillis();
113: }
114:
115: //-- utilities--//
116: /** Returns the value. */
117: public final Object getValue() {
118: return this .value;
119: }
120:
121: /** Returns the last access time. */
122: public final long getAccessTime() {
123: return this .access;
124: }
125:
126: //-- cloneable --//
127: public Object clone() {
128: try {
129: return super .clone();
130: } catch (CloneNotSupportedException e) {
131: throw new InternalError();
132: }
133: }
134:
135: //-- Object --//
136: public final String toString() {
137: return "(" + this .value + '@' + this .access + ')';
138: }
139: }
140:
141: //-- deriving to override --//
142: /**
143: * Called when a pair of key and value having been expunged.
144: * This method is called after it is removed, so you could
145: * add it back.
146: *
147: * <p>Default: does nothing
148: */
149: protected void onExpunge(Value v) {
150: }
151:
152: /** Returns by {@link #canExpunge} to denote it shall not be expunged. */
153: protected static final int EXPUNGE_NO = 0x0;
154: /** Returns by {@link #canExpunge} to denote it shall be expunged. */
155: protected static final int EXPUNGE_YES = 0x1; //must not zero
156: /** Returns by {@link #canExpunge} to denote the searching of the
157: * next mapping shall continue.
158: */
159: protected static final int EXPUNGE_CONTINUE = 0x0;
160: /** Returns by {@link #canExpunge} to denote the searching of the
161: * next mapping shall stop.
162: */
163: protected static final int EXPUNGE_STOP = 0x2; //must not zero
164:
165: /** Returns whether it is time to expunge.
166: * Once shallExpunge returns true, values are examined one-by-one thru
167: * {@link #canExpunge}, and expunged if EXPUNGE_YES.
168: *
169: * <p>This implementation returns true only if {@link #newQueue}
170: * returns null (in constructor) or GC was activated.
171: * You might override it to enforce expunge besides GC.
172: *
173: * @see #canExpunge
174: */
175: protected boolean shallExpunge() {
176: return _que == null || _que.poll() != null;
177: }
178:
179: /**
180: * Tests whether certain value is OK to expunge.
181: *
182: * <p>Note: values are tested thru {@link #canExpunge} only if
183: * {@link #shallExpunge} returns true.
184: *
185: * <p>Deriving classes might override this method to return different
186: * value for different criteria.
187: *
188: * <p>The return value coulde be a combination of EXPUNGE_xxx.
189: * One of EXPUNGE_YES and EXPUNGE_NO is returned to denote
190: * whether to expunge the mapping. One of EXPUNGE_CONTINUE and
191: * EXPUNGE_STOP is returned to denote whether to continue the
192: * searching of the next mapping for expunging.
193: *
194: * <p>Normally, you return either (EXPUNGE_YES|EXPUNGE_CONTINUE)
195: * or (EXPUNG_NO|EXPUNGE_STOP).
196: * Notice that the mapping is queried in the last-access order.
197: * Thus, you rarely needs to return (EXPUNGE_NO|EXPUNGE_CONTINUE)
198: * unless the appropriate one might be out of this order.
199: *
200: * <p>This implementation compares the access time and size.
201: * It returns (EXPUNGE_YES|EXPUNGE_CONTINUE) if OK, and
202: * (EXPUNGE_NO|EXPUNGE_STOP) if not.
203: *
204: * @return a combination of EXPUNGE_xxx
205: * @see #shallExpunge
206: */
207: protected int canExpunge(Value v) {
208: return _map.size() > getMaxSize()
209: || (System.currentTimeMillis() - v.access) > getLifetime() ? (EXPUNGE_YES | EXPUNGE_CONTINUE)
210: : (EXPUNGE_NO | EXPUNGE_STOP);
211: }
212:
213: private void expunge() {
214: if (shallExpunge()) {
215: if (_inExpunge)
216: throw new IllegalStateException("expung in expung?");
217: _inExpunge = true;
218: try {
219: //dennis, bug 1815633, remove some control code here
220:
221: for (final Iterator it = _map.values().iterator(); it
222: .hasNext();) {
223: final Value v = (Value) it.next();
224: final int result = canExpunge(v);
225: if ((result & EXPUNGE_YES) != 0) {
226: //if (D.ON && log.debugable())
227: // log.debug("expunge: value="+v.value+" size="+_map.size()+"("+getMaxSize()+") time="+v.access+"("+getLifetime()+")");
228:
229: it.remove();
230: onExpunge(v);
231: }
232:
233: if ((result & EXPUNGE_STOP) != 0)
234: break; //stop
235: }
236:
237: newRef();
238: } finally {
239: _inExpunge = false;
240: }
241: }
242: }
243:
244: /** Creates the reference queue.
245: * It is called only once in the constructor (so it is meaningless
246: * to change the returned value after constructed).
247: *
248: * <p>Default: new ReferenceQueue();<br>
249: * Override this method to return null if you want to expunge items
250: * every time {@link #get} or {@link #put} is called -- not only GC
251: * is activated.
252: * In other words, if {@link #newQueue} returns null, {@link #shallExpunge}
253: * always returns true (unless you override it too).
254: */
255: protected ReferenceQueue newQueue() {
256: return new ReferenceQueue();
257: }
258:
259: /** Re-create the reference so we can detect if GC was activated.
260: */
261: private void newRef() {
262: if (_que != null)
263: _ref = new WeakReference(new X(), _que);
264: }
265:
266: //-- constructors --//
267: /** Constructs a cache map with the specified max size and lifetime.
268: * @since 3.0.0
269: */
270: public CacheMap(int maxSize, int lifetime) {
271: this ();
272: setMaxSize(maxSize);
273: setLifetime(lifetime);
274: }
275:
276: /** Constructs a cachemap by using LinkedHashMap internally.
277: */
278: public CacheMap() {
279: _map = new LinkedHashMap(16, 0.75f, true);
280: init();
281: }
282:
283: /** Constructs a cachemap by using LinkedHashMap internally.
284: */
285: public CacheMap(int cap) {
286: _map = new LinkedHashMap(cap, 0.75f, true);
287: init();
288: }
289:
290: /** Constructs a cachemap by using LinkedHashMap internally.
291: */
292: public CacheMap(int cap, float load) {
293: _map = new LinkedHashMap(cap, load, true);
294: init();
295: }
296:
297: /** Initialization for contructor and de-serialized. */
298: private void init() {
299: _que = newQueue();
300: newRef();
301: }
302:
303: //-- extra api --//
304: /**
305: * Gets the minimal lifetime, unit=milliseconds.
306: * An mapping won't be removed by GC unless the minimal lifetime
307: * or the maximal allowed size exceeds.
308: * @see #getMaxSize
309: */
310: public int getLifetime() {
311: return _lifetime;
312: }
313:
314: /**
315: * Sets the minimal lifetime. Default: {@link #DEFAULT_LIFETIME}.
316: *
317: * @param lifetime the lifetime, unit=milliseconds;
318: * if non-posive, they will be removed immediately.
319: * @see #getLifetime
320: */
321: public void setLifetime(int lifetime) {
322: _lifetime = lifetime;
323: }
324:
325: /**
326: * Gets the maximal allowed size. Defalut: {@link #DEFAULT_MAX_SIZE}.
327: * An mapping won't be removed by GC unless the minimal lifetime
328: * or the maximal allowed size exceeds.
329: * @see #getLifetime
330: */
331: public int getMaxSize() {
332: return _maxsize;
333: }
334:
335: /**
336: * Sets the maximal allowed size.
337: * @see #getMaxSize
338: */
339: public void setMaxSize(int maxsize) {
340: _maxsize = maxsize;
341: }
342:
343: /**
344: * Gets the last accessed time, in system millisecs.
345: * @return the last accessed time; 0 if not found
346: */
347: /* To support this method, we cannot use access-ordered for _map
348: Then, get() and put() shall use remove and add
349: public final long getLastAccessTime(Object key) {
350: final Value v = (Value)_map.get(key);
351: return v != null ? v.access: 0;
352: }*/
353:
354: //-- Map --//
355: public boolean isEmpty() {
356: expunge();
357: return _map.isEmpty();
358: }
359:
360: /** Returns whether it is empty without trying to expunge first.
361: * @since 3.0.1
362: */
363: public boolean isEmptyWithoutExpunge() {
364: return _map.isEmpty();
365: }
366:
367: public int size() {
368: expunge();
369: return _map.size();
370: }
371:
372: /** Returns the size without trying to expunge first.
373: * @since 3.0.1
374: */
375: public int sizeWithoutExpunge() {
376: return _map.size();
377: }
378:
379: public void clear() {
380: _map.clear();
381: }
382:
383: public Object remove(Object key) {
384: expunge();
385: final Value v = (Value) _map.remove(key);
386: return v != null ? v.value : null;
387: }
388:
389: public Object get(Object key) {
390: expunge();
391: return getWithoutExpunge(key);
392: }
393:
394: /** Returns the value without trying to expunge first.
395: * It is useful if you want to preserve all entries.
396: */
397: public Object getWithoutExpunge(Object key) {
398: final Value v = (Value) _map.get(key); //re-order
399: if (v != null) {
400: v.updateAccessTime();
401: //assertion(key);
402: return v.value;
403: }
404: return null;
405: }
406:
407: public boolean containsKey(Object key) {
408: expunge();
409: return _map.containsKey(key);
410: }
411:
412: public boolean containsValue(Object value) {
413: expunge();
414: for (final Iterator it = _map.values().iterator(); it.hasNext();) {
415: final Value v = (Value) it.next();
416: if (Objects.equals(v.value, value))
417: return true;
418: }
419: return false;
420: }
421:
422: public Object put(Object key, Object value) {
423: expunge();
424: final Value v = (Value) _map.put(key, new Value(value));
425: return v != null ? v.value : null;
426: }
427:
428: public void putAll(Map map) {
429: for (final Iterator it = map.entrySet().iterator(); it
430: .hasNext();) {
431: final Map.Entry me = (Map.Entry) it.next();
432: put(me.getKey(), me.getValue());
433: }
434: }
435:
436: /** It wraps what is stored in _map, such that the caller
437: * won't know the value is wrapped with Value.
438: */
439: private class Entry implements Map.Entry {
440: final Map.Entry _me;
441:
442: private Entry(Map.Entry me) {
443: _me = me;
444: }
445:
446: public Object getKey() {
447: return _me.getKey();
448: }
449:
450: public Object getValue() {
451: return ((Value) _me.getValue()).value;
452: }
453:
454: public Object setValue(Object o) {
455: assert (!(o instanceof Value));
456:
457: //we don't re-order it to avoid comodification error
458: final Value v = (Value) _me.getValue();
459: final Object old = v.value;
460: v.value = o;
461: return old;
462: }
463:
464: //-- Object --//
465: public int hashCode() {
466: return _me.hashCode();
467: }
468:
469: public boolean equals(Object o) {
470: return (o instanceof Entry) && _me.equals(((Entry) o)._me);
471: }
472: }
473:
474: /** Abstract iterator. */
475: private class KeyIter implements Iterator {
476: protected Iterator _it;
477:
478: private KeyIter(Iterator it) {
479: _it = it;
480: }
481:
482: public boolean hasNext() {
483: return _it.hasNext();
484: }
485:
486: public void remove() {
487: _it.remove(); //remove from map
488: }
489:
490: public Object next() {
491: return _it.next();
492: }
493: }
494:
495: /** Entry iterator. Don't call expunge to avoid co-modified exception. */
496: private class EntryIter extends KeyIter {
497: private EntryIter(Iterator it) {
498: super (it);
499: }
500:
501: public Object next() {
502: return new Entry((Map.Entry) _it.next());
503: }
504: }
505:
506: /** The entry set. */
507: private class EntrySet extends AbstractSet {
508: private EntrySet() {
509: }
510:
511: //-- Set --//
512: public Iterator iterator() {
513: expunge();
514: return new EntryIter(_map.entrySet().iterator());
515: }
516:
517: public boolean contains(Object o) {
518: return (o instanceof Map.Entry)
519: && CacheMap.this .containsKey(((Map.Entry) o)
520: .getKey());
521: }
522:
523: public boolean remove(Object o) {
524: return (o instanceof Map.Entry)
525: && CacheMap.this .remove(((Map.Entry) o).getKey()) != null;
526: }
527:
528: public int size() {
529: return CacheMap.this .size();
530: }
531:
532: public void clear() {
533: CacheMap.this .clear();
534: }
535: }
536:
537: public Set entrySet() {
538: expunge();
539: return new EntrySet();
540: }
541:
542: /** The entry set. */
543: private class KeySet extends AbstractSet {
544: private KeySet() {
545: }
546:
547: //-- Set --//
548: public Iterator iterator() {
549: expunge();
550: return new KeyIter(_map.keySet().iterator());
551: }
552:
553: public boolean contains(Object o) {
554: return CacheMap.this .containsKey(o);
555: }
556:
557: public boolean remove(Object o) {
558: return CacheMap.this .remove(o) != null;
559: }
560:
561: public int size() {
562: return CacheMap.this .size();
563: }
564:
565: public void clear() {
566: CacheMap.this .clear();
567: }
568: }
569:
570: public Set keySet() {
571: expunge();
572: return new KeySet();
573: }
574:
575: /** Value iterator. Don't call expunge to avoid co-modified exception. */
576: private class ValueIter extends KeyIter {
577: private ValueIter(Iterator it) {
578: super (it);
579: }
580:
581: public Object next() {
582: return ((Value) _it.next()).value;
583: }
584: }
585:
586: /** The value collection. */
587: private class Values extends AbstractCollection {
588: public Iterator iterator() {
589: return new ValueIter(_map.values().iterator());
590: }
591:
592: public int size() {
593: return CacheMap.this .size();
594: }
595:
596: public boolean contains(Object o) {
597: return CacheMap.this .containsValue(o);
598: }
599:
600: public void clear() {
601: CacheMap.this .clear();
602: }
603: }
604:
605: public Collection values() {
606: expunge();
607: return new Values();
608: }
609:
610: //-- Object --//
611: public int hashCode() {
612: expunge();
613: return _map.hashCode();
614: }
615:
616: public boolean equals(Object o) {
617: expunge();
618: return o == this
619: || ((o instanceof CacheMap) && _map
620: .equals(((CacheMap) o)._map))
621: || ((o instanceof Map) && _map.equals((Map) o));
622: }
623:
624: public String toString() {
625: expunge();
626:
627: final StringBuffer sb = new StringBuffer(128).append('{');
628: if (!_map.isEmpty()) {
629: for (final Iterator it = _map.entrySet().iterator();;) {
630: final Map.Entry me = (Map.Entry) it.next();
631: sb.append(me.getKey()).append('=')
632: .append(
633: Objects
634: .toString(((Value) me
635: .getValue()).value));
636: if (it.hasNext())
637: sb.append(", ");
638: else
639: break; //done
640: }
641: }
642: return sb.append('}').toString();
643: }
644:
645: //-- Debug --//
646: /** To make sure that it is in the acess order. */
647: /*private final void assertion(Object key) {
648: long last = Long.MIN_VALUE;
649: int j = 0;
650: for (final Iterator it = _map.values().iterator(); it.hasNext(); ++j) {
651: final Value v = (Value)it.next();
652: assert v.access >= last: "Order is wrong: j="+j+" key="+key+" acs="+v.access+" map="+_map;
653: last = v.access;
654: }
655: }*/
656:
657: //Cloneable//
658: public Object clone() {
659: final CacheMap clone;
660: try {
661: clone = (CacheMap) super .clone();
662: } catch (CloneNotSupportedException e) {
663: throw new InternalError();
664: }
665:
666: clone._map = new LinkedHashMap(clone._map);
667: for (Iterator it = clone._map.entrySet().iterator(); it
668: .hasNext();) {
669: final Map.Entry me = (Map.Entry) it.next();
670: me.setValue(((Value) me.getValue()).clone());
671: }
672:
673: clone.init();
674: return clone;
675: }
676:
677: //Serializable//
678: //NOTE: they must be declared as private
679: private synchronized void writeObject(java.io.ObjectOutputStream s)
680: throws java.io.IOException {
681: s.defaultWriteObject();
682: }
683:
684: private synchronized void readObject(java.io.ObjectInputStream s)
685: throws java.io.IOException, ClassNotFoundException {
686: s.defaultReadObject();
687:
688: init();
689: }
690: }
|