001: /*
002: * Licensed to the Apache Software Foundation (ASF) under one
003: * or more contributor license agreements. See the NOTICE file
004: * distributed with this work for additional information
005: * regarding copyright ownership. The ASF licenses this file
006: * to you under the Apache License, Version 2.0 (the
007: * "License"); you may not use this file except in compliance
008: * with the License. You may obtain a copy of the License at
009: *
010: * http://www.apache.org/licenses/LICENSE-2.0
011: *
012: * Unless required by applicable law or agreed to in writing,
013: * software distributed under the License is distributed on an
014: * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
015: * KIND, either express or implied. See the License for the
016: * specific language governing permissions and limitations
017: * under the License.
018: */
019: package org.apache.openjpa.util;
020:
021: import java.util.AbstractCollection;
022: import java.util.AbstractSet;
023: import java.util.Collection;
024: import java.util.Collections;
025: import java.util.HashMap;
026: import java.util.Iterator;
027: import java.util.Map;
028: import java.util.Set;
029:
030: import org.apache.commons.collections.Predicate;
031: import org.apache.commons.collections.iterators.FilterIterator;
032: import org.apache.commons.collections.iterators.IteratorChain;
033: import org.apache.openjpa.lib.util.LRUMap;
034: import org.apache.openjpa.lib.util.ReferenceHashMap;
035: import org.apache.openjpa.lib.util.ReferenceMap;
036: import org.apache.openjpa.lib.util.SizedMap;
037: import org.apache.openjpa.lib.util.concurrent.ConcurrentHashMap;
038: import org.apache.openjpa.lib.util.concurrent.ConcurrentReferenceHashMap;
039: import org.apache.openjpa.lib.util.concurrent.ReentrantLock;
040:
041: /**
042: * Fixed-size map that has ability to pin/unpin entries and move overflow to
043: * a backing soft map.
044: *
045: * @author Patrick Linskey
046: * @author Abe White
047: */
048: public class CacheMap implements Map {
049:
050: /**
051: * The map for non-expired and non-pinned references.
052: */
053: protected final SizedMap cacheMap;
054:
055: /**
056: * The map for expired references.
057: */
058: protected final SizedMap softMap;
059:
060: /**
061: * The set of objects pinned into the cache.
062: */
063: protected final Map pinnedMap;
064:
065: // number of pinned values (not including keys not mapped to values)
066: private int _pinnedSize = 0;
067:
068: private final ReentrantLock _writeLock = new ReentrantLock();
069: private final ReentrantLock _readLock;
070:
071: /**
072: * Create a non-LRU (and therefore highly concurrent) cache map with a
073: * size of 1000.
074: */
075: public CacheMap() {
076: this (false, 1000);
077: }
078:
079: /**
080: * Create a cache map with the given properties.
081: */
082: public CacheMap(boolean lru, int max) {
083: this (lru, max, max / 2, .75F);
084: }
085:
086: /**
087: * Create a cache map with the given properties.
088: */
089: public CacheMap(boolean lru, int max, int size, float load) {
090: if (size < 0)
091: size = 500;
092: if (!lru) {
093: cacheMap = new ConcurrentHashMap(size, load) {
094: public void overflowRemoved(Object key, Object value) {
095: cacheMapOverflowRemoved(key, value);
096: }
097: };
098: softMap = new ConcurrentReferenceHashMap(ReferenceMap.HARD,
099: ReferenceMap.SOFT, size, load) {
100: public void overflowRemoved(Object key, Object value) {
101: softMapOverflowRemoved(key, value);
102: }
103:
104: public void valueExpired(Object key) {
105: softMapValueExpired(key);
106: }
107: };
108: pinnedMap = new ConcurrentHashMap();
109: _readLock = null;
110: } else {
111: cacheMap = new LRUMap(size, load) {
112: public void overflowRemoved(Object key, Object value) {
113: cacheMapOverflowRemoved(key, value);
114: }
115: };
116: softMap = new ReferenceHashMap(ReferenceMap.HARD,
117: ReferenceMap.SOFT, size, load) {
118: public void overflowRemoved(Object key, Object value) {
119: softMapOverflowRemoved(key, value);
120: }
121:
122: public void valueExpired(Object key) {
123: softMapValueExpired(key);
124: }
125: };
126: pinnedMap = new HashMap();
127: _readLock = _writeLock;
128: }
129: cacheMap.setMaxSize((max < 0) ? Integer.MAX_VALUE : max);
130: }
131:
132: /**
133: * Called from {@link SizedMap#overflowRemoved} in the cache map.
134: */
135: protected void cacheMapOverflowRemoved(Object key, Object value) {
136: if (softMap.size() < softMap.getMaxSize())
137: put(softMap, key, value);
138: else
139: entryRemoved(key, value, true);
140: }
141:
142: /**
143: * Called from {@link SizedMap#overflowRemoved} in the soft map.
144: */
145: protected void softMapOverflowRemoved(Object key, Object value) {
146: entryRemoved(key, value, true);
147: }
148:
149: /**
150: * Called when a value expires from the soft map.
151: */
152: protected void softMapValueExpired(Object key) {
153: entryRemoved(key, null, true);
154: }
155:
156: /**
157: * Put the given entry into the given map. Allows subclasses to
158: * take additional actions.
159: */
160: protected Object put(Map map, Object key, Object value) {
161: return map.put(key, value);
162: }
163:
164: /**
165: * Remove the given key from the given map. Allows subclasses to
166: * take additional actions.
167: */
168: protected Object remove(Map map, Object key) {
169: return map.remove(key);
170: }
171:
172: /**
173: * Acquire read lock.
174: */
175: public void readLock() {
176: if (_readLock != null)
177: _readLock.lock();
178: }
179:
180: /**
181: * Release read lock.
182: */
183: public void readUnlock() {
184: if (_readLock != null)
185: _readLock.unlock();
186: }
187:
188: /**
189: * Acquire write lock.
190: */
191: public void writeLock() {
192: _writeLock.lock();
193: }
194:
195: /**
196: * Release write lock.
197: */
198: public void writeUnlock() {
199: _writeLock.unlock();
200: }
201:
202: /**
203: * Whether this cache map uses LRU eviction.
204: */
205: public boolean isLRU() {
206: return _readLock != null;
207: }
208:
209: /**
210: * The maximum number of hard references to maintain, or -1 for no limit.
211: */
212: public void setCacheSize(int size) {
213: writeLock();
214: try {
215: cacheMap.setMaxSize((size < 0) ? Integer.MAX_VALUE : size);
216: } finally {
217: writeUnlock();
218: }
219: }
220:
221: /**
222: * The maximum number of hard references to maintain, or -1 for no limit.
223: */
224: public int getCacheSize() {
225: int max = cacheMap.getMaxSize();
226: return (max == Integer.MAX_VALUE) ? -1 : max;
227: }
228:
229: /**
230: * The maximum number of soft references to maintain, or -1 for no limit.
231: */
232: public void setSoftReferenceSize(int size) {
233: writeLock();
234: try {
235: softMap.setMaxSize((size < 0) ? Integer.MAX_VALUE : size);
236: } finally {
237: writeUnlock();
238: }
239: }
240:
241: /**
242: * The maximum number of soft references to maintain, or -1 for no limit.
243: */
244: public int getSoftReferenceSize() {
245: int max = softMap.getMaxSize();
246: return (max == Integer.MAX_VALUE) ? -1 : max;
247: }
248:
249: /**
250: * The keys pinned into the map.
251: */
252: public Set getPinnedKeys() {
253: readLock();
254: try {
255: return Collections.unmodifiableSet(pinnedMap.keySet());
256: } finally {
257: readUnlock();
258: }
259: }
260:
261: /**
262: * Locks the given key and its value into the map. Objects pinned into
263: * the map are not counted towards the maximum cache size, and are never
264: * evicted implicitly. You may pin keys for which no value is in the map.
265: *
266: * @return true if the givne key's value was pinned; false if no value
267: * for the given key is cached
268: */
269: public boolean pin(Object key) {
270: writeLock();
271: try {
272: // if we don't have a pinned map we need to create one; else if the
273: // pinned map already contains the key, nothing to do
274: if (pinnedMap.containsKey(key))
275: return pinnedMap.get(key) != null;
276:
277: // check other maps for key
278: Object val = remove(cacheMap, key);
279: if (val == null)
280: val = remove(softMap, key);
281:
282: // pin key
283: put(pinnedMap, key, val);
284: if (val != null) {
285: _pinnedSize++;
286: return true;
287: }
288: return false;
289: } finally {
290: writeUnlock();
291: }
292: }
293:
294: /**
295: * Undo a pinning.
296: */
297: public boolean unpin(Object key) {
298: writeLock();
299: try {
300: Object val = remove(pinnedMap, key);
301: if (val != null) {
302: // put back into unpinned cache
303: put(key, val);
304: _pinnedSize--;
305: return true;
306: }
307: return false;
308: } finally {
309: writeUnlock();
310: }
311: }
312:
313: /**
314: * Invoked when a key-value pair is evicted from this data
315: * structure. This is invoked with <code>expired</code> set to
316: * <code>true</code> when an object is dropped because of space
317: * requirements or through garbage collection of soft references.
318: * It is invoked with <code>expired</code> set to <code>false</code>
319: * when an object is explicitly removed via the {@link #remove} or
320: * {@link #clear} methods. This may be invoked more than once for a
321: * given entry.
322: *
323: * @param value may be null if the value was a soft reference that has
324: * been GCd
325: * @since 0.2.5.0
326: */
327: protected void entryRemoved(Object key, Object value,
328: boolean expired) {
329: }
330:
331: /**
332: * Invoked when an entry is added to the cache. This may be invoked
333: * more than once for an entry.
334: */
335: protected void entryAdded(Object key, Object value) {
336: }
337:
338: public Object get(Object key) {
339: readLock();
340: try {
341: Object val = pinnedMap.get(key);
342: if (val != null)
343: return val;
344:
345: val = cacheMap.get(key);
346: if (val == null) {
347: // if we find the key in the soft map, move it back into
348: // the primary map
349: val = softMap.get(key);
350: if (val != null)
351: put(key, val);
352: }
353: return val;
354: } finally {
355: readUnlock();
356: }
357: }
358:
359: public Object put(Object key, Object value) {
360: writeLock();
361: try {
362: // if the key is pinned, just interact directly with the pinned map
363: Object val;
364: if (pinnedMap.containsKey(key)) {
365: val = put(pinnedMap, key, value);
366: if (val == null) {
367: _pinnedSize++;
368: entryAdded(key, value);
369: } else {
370: entryRemoved(key, val, false);
371: entryAdded(key, value);
372: }
373: return val;
374: }
375:
376: // if no hard refs, don't put anything
377: if (cacheMap.getMaxSize() == 0)
378: return null;
379:
380: // otherwise, put the value into the map and clear it from the
381: // soft map
382: val = put(cacheMap, key, value);
383: if (val == null) {
384: val = remove(softMap, key);
385: if (val == null)
386: entryAdded(key, value);
387: else {
388: entryRemoved(key, val, false);
389: entryAdded(key, value);
390: }
391: } else {
392: entryRemoved(key, val, false);
393: entryAdded(key, value);
394: }
395: return val;
396: } finally {
397: writeUnlock();
398: }
399: }
400:
401: public void putAll(Map map) {
402: Map.Entry entry;
403: for (Iterator itr = map.entrySet().iterator(); itr.hasNext();) {
404: entry = (Map.Entry) itr.next();
405: put(entry.getKey(), entry.getValue());
406: }
407: }
408:
409: /**
410: * If <code>key</code> is pinned into the cache, the pin is
411: * cleared and the object is removed.
412: */
413: public Object remove(Object key) {
414: writeLock();
415: try {
416: // if the key is pinned, just interact directly with the
417: // pinned map
418: Object val;
419: if (pinnedMap.containsKey(key)) {
420: // re-put with null value; we still want key pinned
421: val = put(pinnedMap, key, null);
422: if (val != null) {
423: _pinnedSize--;
424: entryRemoved(key, val, false);
425: }
426: return val;
427: }
428:
429: val = remove(cacheMap, key);
430: if (val == null)
431: val = softMap.remove(key);
432: if (val != null)
433: entryRemoved(key, val, false);
434:
435: return val;
436: } finally {
437: writeUnlock();
438: }
439: }
440:
441: /**
442: * Removes pinned objects as well as unpinned ones.
443: */
444: public void clear() {
445: writeLock();
446: try {
447: notifyEntryRemovals(pinnedMap.entrySet());
448: pinnedMap.clear();
449: _pinnedSize = 0;
450:
451: notifyEntryRemovals(cacheMap.entrySet());
452: cacheMap.clear();
453:
454: notifyEntryRemovals(softMap.entrySet());
455: softMap.clear();
456: } finally {
457: writeUnlock();
458: }
459: }
460:
461: private void notifyEntryRemovals(Set set) {
462: Map.Entry entry;
463: for (Iterator itr = set.iterator(); itr.hasNext();) {
464: entry = (Map.Entry) itr.next();
465: if (entry.getValue() != null)
466: entryRemoved(entry.getKey(), entry.getValue(), false);
467: }
468: }
469:
470: public int size() {
471: readLock();
472: try {
473: return _pinnedSize + cacheMap.size() + softMap.size();
474: } finally {
475: readUnlock();
476: }
477: }
478:
479: public boolean isEmpty() {
480: return size() == 0;
481: }
482:
483: public boolean containsKey(Object key) {
484: readLock();
485: try {
486: return pinnedMap.get(key) != null
487: || cacheMap.containsKey(key)
488: || softMap.containsKey(key);
489: } finally {
490: readUnlock();
491: }
492: }
493:
494: public boolean containsValue(Object val) {
495: readLock();
496: try {
497: return pinnedMap.containsValue(val)
498: || cacheMap.containsValue(val)
499: || softMap.containsValue(val);
500: } finally {
501: readUnlock();
502: }
503: }
504:
505: public Set keySet() {
506: return new KeySet();
507: }
508:
509: public Collection values() {
510: return new ValueCollection();
511: }
512:
513: public Set entrySet() {
514: return new EntrySet();
515: }
516:
517: public String toString() {
518: readLock();
519: try {
520: return "CacheMap:" + cacheMap.toString() + "::"
521: + softMap.toString();
522: } finally {
523: readUnlock();
524: }
525: }
526:
527: /**
528: * View of the entry set.
529: */
530: private class EntrySet extends AbstractSet {
531:
532: public int size() {
533: return CacheMap.this .size();
534: }
535:
536: public boolean add(Object o) {
537: Map.Entry entry = (Map.Entry) o;
538: put(entry.getKey(), entry.getValue());
539: return true;
540: }
541:
542: public Iterator iterator() {
543: return new EntryIterator(EntryIterator.ENTRY);
544: }
545: }
546:
547: /**
548: * View of the key set.
549: */
550: private class KeySet extends AbstractSet {
551:
552: public int size() {
553: return CacheMap.this .size();
554: }
555:
556: public Iterator iterator() {
557: return new EntryIterator(EntryIterator.KEY);
558: }
559: }
560:
561: /**
562: * View of the value collection.
563: */
564: private class ValueCollection extends AbstractCollection {
565:
566: public int size() {
567: return CacheMap.this .size();
568: }
569:
570: public Iterator iterator() {
571: return new EntryIterator(EntryIterator.VALUE);
572: }
573: }
574:
575: /**
576: * Iterator over all entries.
577: */
578: private class EntryIterator implements Iterator, Predicate {
579:
580: public static final int ENTRY = 0;
581: public static final int KEY = 1;
582: public static final int VALUE = 2;
583:
584: private final IteratorChain _itr = new IteratorChain();
585: private final int _type;
586:
587: public EntryIterator(int type) {
588: _type = type;
589: _itr.addIterator(new FilterIterator(getView(pinnedMap),
590: this ));
591: _itr.addIterator(getView(cacheMap));
592: _itr.addIterator(getView(softMap));
593: }
594:
595: /**
596: * Return an iterator over the appropriate view of the given map.
597: */
598: private Iterator getView(Map m) {
599: if (m == null)
600: return null;
601:
602: switch (_type) {
603: case KEY:
604: return m.keySet().iterator();
605: case VALUE:
606: return m.values().iterator();
607: default:
608: return m.entrySet().iterator();
609: }
610: }
611:
612: public boolean hasNext() {
613: return _itr.hasNext();
614: }
615:
616: public Object next() {
617: return _itr.next();
618: }
619:
620: public void remove() {
621: _itr.remove();
622: }
623:
624: public boolean evaluate(Object obj) {
625: switch (_type) {
626: case ENTRY:
627: return ((Map.Entry) obj).getValue() != null;
628: case VALUE:
629: return obj != null;
630: default:
631: return true;
632: }
633: }
634: }
635: }
|