001: /*
002:
003: This software is OSI Certified Open Source Software.
004: OSI Certified is a certification mark of the Open Source Initiative.
005:
006: The license (Mozilla version 1.0) can be read at the MMBase site.
007: See http://www.MMBase.org/license
008:
009: */
010: package org.mmbase.util;
011:
012: import org.mmbase.cache.CacheImplementationInterface;
013: import java.util.*;
014: import org.mmbase.util.logging.*;
015:
016: /**
017: * A hashtable which has a maximum of entries. Old entries are
018: * removed when the maximum is reached. This table is used mostly to
019: * implement a simple caching system.
020: *
021: * @move consider moving to org.mmbase.cache
022: * @author Rico Jansen
023: * @author Michiel Meeuwissen
024: * @version $Id: LRUHashtable.java,v 1.30 2007/08/01 06:44:43 michiel Exp $
025: * @see org.mmbase.cache.Cache
026: * @deprecated use org.mmbase.cache.implementation.LRUCache
027: */
028: public class LRUHashtable<K, V> implements Cloneable,
029: CacheImplementationInterface<K, V>, SizeMeasurable {
030:
031: private static final Logger log = Logging
032: .getLoggerInstance(LRUHashtable.class);
033:
034: private final Hashtable<K, LRUEntry> backing;
035:
036: /**
037: * First (virtual) element of the table.
038: * The element that follows root is the oldest element in the table
039: * (and thus first to be removed if size maxes out).
040: */
041: private final LRUEntry root = new LRUEntry();
042: /**
043: * Last (virtual) element of the table.
044: * The element that precedes dangling is the latest element in the table
045: */
046: private final LRUEntry dangling = new LRUEntry();
047:
048: /**
049: * Maximum size (capacity) of the table
050: */
051: private int maxSize = 0;
052:
053: /**
054: * Creates the URL Hashtable.
055: * @param size the maximum capacity
056: * @param cap the starting capacity (used to improve performance)
057: * @param lf the amount with which current capacity frows
058: */
059: public LRUHashtable(int size, int cap, float lf) {
060: backing = new Hashtable<K, LRUEntry>(cap, lf);
061: root.next = dangling;
062: dangling.prev = root;
063: this .maxSize = size;
064: }
065:
066: /**
067: * Creates the URL Hashtable with growing capacity 0.75.
068: * @param size the maximum capacity
069: * @param cap the starting capacity (used to improve performance)
070: */
071: public LRUHashtable(int size, int cap) {
072: this (size, cap, 0.75f);
073: }
074:
075: /**
076: * Creates the URL Hashtable with starting capacity 101 and
077: * growing capacity 0.75.
078: * @param size the maximum capacity
079: */
080: public LRUHashtable(int size) {
081: this (size, 101, 0.75f);
082: }
083:
084: /**
085: * Creates the URL Hashtable with maximum capacity 100,
086: * starting capacity 101, and growing capacity 0.75.
087: */
088: public LRUHashtable() {
089: this (100, 101, 0.75f);
090: }
091:
092: /**
093: * Store an element in the table.
094: * @param key the key of the element
095: * @param value the value of the element
096: * @return the original value of the element if it existed, <code>null</code> if it could not be found
097: */
098: public synchronized V put(K key, V value) {
099: LRUEntry work = backing.get(key);
100: V rtn;
101: if (work != null) {
102: rtn = work.value;
103: work.value = value;
104: removeEntry(work);
105: appendEntry(work);
106: } else {
107: rtn = null;
108: work = new LRUEntry(key, value);
109: backing.put(key, work);
110: appendEntry(work);
111: if (backing.size() > maxSize) {
112: K remove = root.next.key;
113: Object was = remove(remove);
114: assert was != null;
115: if (was == null) {
116: log
117: .warn("Nothing was removed, while that was expected "
118: + remove
119: + " should have been removed");
120: }
121: }
122: }
123: return rtn;
124: }
125:
126: public void putAll(Map<? extends K, ? extends V> t) {
127: for (Map.Entry<? extends K, ? extends V> e : t.entrySet()) {
128: put(e.getKey(), e.getValue());
129: }
130: }
131:
132: public boolean containsValue(Object o) {
133: return values().contains(o);
134: }
135:
136: public boolean containsKey(Object o) {
137: return backing.containsKey(o);
138: }
139:
140: public boolean isEmpty() {
141: return backing.isEmpty();
142: }
143:
144: /**
145: * Retrieves the count of the object with a certain key.
146: * @param key the key of the element
147: * @return the times the key has been requested
148: */
149: public int getCount(Object key) {
150: LRUEntry work = backing.get(key);
151: if (work != null) {
152: return work.requestCount;
153: } else {
154: return -1;
155: }
156: }
157:
158: /**
159: * Retrieves an element from the table.
160: * @param key the key of the element
161: * @return the value of the element, or <code>null</code> if it could not be found
162: */
163: public synchronized V get(Object key) {
164: LRUEntry work = backing.get(key);
165: if (work != null) {
166: work.requestCount++;
167: V rtn = work.value;
168: removeEntry(work);
169: appendEntry(work);
170: return rtn;
171: } else {
172: return null;
173: }
174: }
175:
176: /**
177: * Remove an element from the table.
178: * @param key the key of the element
179: * @return the original value of the element if it existed, <code>null</code> if it could not be found
180: */
181: public synchronized V remove(Object key) {
182: LRUEntry work = backing.remove(key);
183: if (work != null) {
184: V rtn = work.value;
185: removeEntry(work);
186: return rtn;
187: } else {
188: return null;
189: }
190: }
191:
192: /**
193: * You should only remove entries from LRUHashtable using the 'remove' function, or using the
194: * iterator of entrySet() otherwise the linked list gets messed up. The keySet of LRUHashtable
195: * therefore returns an unmodifiable set.
196: * @since MMBase-1.6.3
197: */
198: public Set<K> keySet() {
199: return Collections.unmodifiableSet(backing.keySet());
200: }
201:
202: /**
203: * Returns the entries of this Map. Modification are reflected.
204: *
205: * @since MMBase-1.6.3
206: */
207: public Set<Map.Entry<K, V>> entrySet() {
208: //throw new UnsupportedOperationException();
209: return new LRUEntrySet();
210: }
211:
212: /**
213: * @see #keySet
214: * @since MMBase-1.6.3
215: */
216: public Collection<V> values() {
217: return new LRUValues();
218: }
219:
220: /**
221: * Return the current size of the table
222: */
223: public int size() {
224: return backing.size();
225: }
226:
227: /**
228: * Change the maximum size of the table.
229: * This may result in removal of entries in the table.
230: * @param size the new desired size
231: */
232: public void setMaxSize(int size) {
233: if (size < 0)
234: throw new IllegalArgumentException(
235: "Cannot set size of LRUHashtable to negative value");
236: if (size < maxSize) {
237: while (size() > maxSize) {
238: remove(root.next.key);
239: }
240: }
241: maxSize = size;
242: }
243:
244: /**
245: * Return the maximum size of the table
246: */
247: public int maxSize() {
248: return maxSize;
249: }
250:
251: /**
252: * Append an entry to the end of the list.
253: */
254: private void appendEntry(LRUEntry wrk) {
255: dangling.prev.next = wrk;
256: wrk.prev = dangling.prev;
257: wrk.next = dangling;
258: dangling.prev = wrk;
259: }
260:
261: /**
262: * remove an entry from the list.
263: */
264: private void removeEntry(LRUEntry wrk) {
265: wrk.next.prev = wrk.prev;
266: wrk.prev.next = wrk.next;
267: wrk.next = null;
268: wrk.prev = null;
269: }
270:
271: /**
272: * Returns a description of the table.
273: * The information shown includes current size, maximum size, ratio of misses and hits,
274: * and a description of the underlying hashtable
275: */
276: public String toString() {
277: return "Size=" + size() + ", Max=" + maxSize;
278: }
279:
280: /**
281: * Returns a description of the table.
282: * The information shown includes current size, maximum size, ratio of misses and hits,
283: * and either a description of the underlying hashtable, or a list of all stored values.
284: * @param which if <code>true</code>, the stored values are described.
285: * @return a description of the table.
286: */
287: public String toString(boolean which) {
288: if (which) {
289: StringBuilder b = new StringBuilder();
290: b.append("Size " + size() + ", Max " + maxSize + " : ");
291: b.append(super .toString());
292: return b.toString();
293: } else {
294: return toString();
295: }
296: }
297:
298: /**
299: * Clears the table.
300: */
301: public synchronized void clear() {
302: while (root.next != dangling)
303: removeEntry(root.next);
304: backing.clear();
305: }
306:
307: /**
308: * NOT IMPLEMENTED
309: */
310: public synchronized Object clone() {
311: throw new UnsupportedOperationException();
312: }
313:
314: /**
315: * Returns an <code>Enumeration</code> on the table's element values.
316: */
317: public synchronized Enumeration<V> elements() {
318: return new LRUHashtableEnumeration();
319: }
320:
321: /**
322: * @deprecated use getOrderedEntries
323: */
324: public Enumeration<V> getOrderedElements() {
325: return getOrderedElements(-1);
326: }
327:
328: /**
329: * @deprecated use getOrderedEntries
330: */
331: public Enumeration<V> getOrderedElements(int maxnumber) {
332: List<V> results = new ArrayList<V>();
333: LRUEntry current = root.next;
334: if (maxnumber != -1) {
335: int i = 0;
336: while (current != null && current != dangling
337: && i < maxnumber) {
338: results.add(0, current.value);
339: current = current.next;
340: i++;
341: }
342: } else {
343: while (current != null && current != dangling) {
344: results.add(0, current.value);
345: current = current.next;
346: }
347: }
348: return Collections.enumeration(results);
349: }
350:
351: /**
352: * Returns an ordered list of Map.Entry's.
353: *
354: * @since MMBase-1.6
355: */
356:
357: public List<? extends Map.Entry<K, V>> getOrderedEntries() {
358: return getOrderedEntries(-1);
359: }
360:
361: /**
362: * Returns an ordered list of Map.Entry's. This can be used to
363: * present the contents of the LRU Map.
364: *
365: * @since MMBase-1.6
366: */
367:
368: public List<? extends Map.Entry<K, V>> getOrderedEntries(
369: int maxNumber) {
370: List<Map.Entry<K, V>> results = new ArrayList<Map.Entry<K, V>>();
371: LRUEntry current = root.next;
372: int i = 0;
373: while (current != null && current != dangling
374: && (maxNumber < 0 || i < maxNumber)) {
375: results.add(0, current);
376: current = current.next;
377: i++;
378: }
379: return Collections.unmodifiableList(results);
380: }
381:
382: public void config(Map<String, String> map) {
383: // lru needs no configuration.
384: }
385:
386: public int getByteSize() {
387: return getByteSize(new SizeOf());
388: }
389:
390: public int getByteSize(SizeOf sizeof) {
391: int len = 4 * SizeOf.SZ_REF + (30 + 5 * SizeOf.SZ_REF) * size(); // 30:overhead of Hashtable, 5*SZ_REF: overhead of LRUEntry
392: LRUEntry current = root.next;
393: while (current != null && current != dangling) {
394: current = current.next;
395: len += sizeof.sizeof(current.key);
396: len += sizeof.sizeof(current.value);
397: }
398: return len;
399: }
400:
401: /**
402: * Enumerator for the LRUHashtable.
403: */
404: private class LRUHashtableEnumeration implements Enumeration<V> {
405: private Enumeration<V> super ior;
406:
407: LRUHashtableEnumeration() {
408: super ior = LRUHashtable.this .elements();
409: }
410:
411: public boolean hasMoreElements() {
412: return super ior.hasMoreElements();
413: }
414:
415: public V nextElement() {
416: LRUEntry entry = (LRUEntry) super ior.nextElement();
417: return entry.value;
418: }
419: }
420:
421: /**
422: * Element used to store information from the LRUHashtable.
423: */
424: public class LRUEntry implements Map.Entry<K, V>, SizeMeasurable {
425: /**
426: * The element value
427: */
428: protected V value;
429: /**
430: * The next, newer, element
431: */
432: protected LRUEntry next;
433: /**
434: * The previous, older, element
435: */
436: protected LRUEntry prev;
437: /**
438: * The element key
439: */
440: protected K key;
441: /**
442: * the number of times this
443: * entry has been requested
444: */
445: protected int requestCount = 0;
446:
447: LRUEntry() {
448: this (null, null);
449: }
450:
451: LRUEntry(K key, V val) {
452: this (key, val, null, null);
453: }
454:
455: LRUEntry(K key, V value, LRUEntry prev, LRUEntry next) {
456: this .value = value;
457: this .next = next;
458: this .prev = prev;
459: this .key = key;
460: }
461:
462: public K getKey() {
463: return key;
464: }
465:
466: public V getValue() {
467: return value;
468: }
469:
470: public V setValue(V o) {
471: throw new UnsupportedOperationException(
472: "Cannot change values in LRU Hashtable");
473: }
474:
475: public int getByteSize() {
476: return new SizeOf().sizeof(value);
477: }
478:
479: public int getByteSize(SizeOf sizeof) {
480: return 20 + // 5 references
481: sizeof.sizeof(value);
482: }
483:
484: public String toString() {
485: return key
486: + "="
487: + (value == LRUHashtable.this ? "[this lru]"
488: : String.valueOf(value));
489: }
490:
491: }
492:
493: /**
494: * Used by 'entrySet' implementation, to make the Map modifiable.
495: * @since MMBase-1.7.2
496: */
497: protected class LRUEntrySet extends AbstractSet<Map.Entry<K, V>> {
498: Set<Map.Entry<K, LRUEntry>> set;
499:
500: LRUEntrySet() {
501: set = LRUHashtable.this .backing.entrySet();
502: }
503:
504: public int size() {
505: return set.size();
506: }
507:
508: public Iterator<Map.Entry<K, V>> iterator() {
509: return new LRUEntrySetIterator(set.iterator());
510: }
511: }
512:
513: /**
514: * Used by 'entrySet' implementation, to make the Map modifiable.
515: * @since MMBase-1.7.2
516: */
517: protected class LRUEntrySetIterator implements
518: Iterator<Map.Entry<K, V>> {
519: final Iterator<Map.Entry<K, LRUEntry>> it;
520: LRUEntry work;
521:
522: LRUEntrySetIterator(Iterator<Map.Entry<K, LRUEntry>> i) {
523: it = i;
524: }
525:
526: public boolean hasNext() {
527: return it.hasNext();
528: }
529:
530: public Map.Entry<K, V> next() {
531: Map.Entry<K, LRUEntry> entry = it.next();
532: work = entry.getValue();
533: return work;
534: }
535:
536: public void remove() {
537: it.remove();
538: if (work != null) {
539: LRUHashtable.this .removeEntry(work);
540: }
541: }
542: }
543:
544: /**
545: * @since MMBase-1.9
546: */
547: protected class LRUValues extends AbstractCollection<V> {
548: final Collection<LRUEntry> col;
549:
550: LRUValues() {
551: col = LRUHashtable.this .backing.values();
552: }
553:
554: public int size() {
555: return col.size();
556: }
557:
558: public Iterator<V> iterator() {
559: final Iterator<LRUEntry> i = col.iterator();
560: return new Iterator<V>() {
561: LRUEntry work;
562:
563: public boolean hasNext() {
564: return i.hasNext();
565: }
566:
567: public V next() {
568: work = i.next();
569: return work.getValue();
570: }
571:
572: public void remove() {
573: i.remove();
574: if (work != null) {
575: LRUHashtable.this.removeEntry(work);
576: }
577: }
578: };
579: }
580: }
581:
582: }
|