1 package org.apache.jcs.utils.struct;
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 import java.io.Serializable;
23 import java.util.ArrayList;
24 import java.util.Collection;
25 import java.util.HashSet;
26 import java.util.Hashtable;
27 import java.util.Iterator;
28 import java.util.Map;
29 import java.util.NoSuchElementException;
30 import java.util.Set;
31
32 import org.apache.commons.logging.Log;
33 import org.apache.commons.logging.LogFactory;
34 import org.apache.jcs.engine.control.group.GroupAttrName;
35 import org.apache.jcs.engine.stats.StatElement;
36 import org.apache.jcs.engine.stats.Stats;
37 import org.apache.jcs.engine.stats.behavior.IStatElement;
38 import org.apache.jcs.engine.stats.behavior.IStats;
39
40 /***
41 * This is a simple LRUMap. It implements most of the map methods. It is not recommended that you
42 * use any but put, get, remove, and clear.
43 * <p>
44 * Children can implement the processRemovedLRU method if they want to handle the removal of the
45 * lest recently used item.
46 * <p>
47 * This class was abstracted out of the LRU Memory cache. Put, remove, and get should be thread
48 * safe. It uses a hashtable and our own double linked list.
49 * <p>
50 * Locking is done on the instance.
51 * <p>
52 * @author aaronsm
53 */
54 public class LRUMap
55 implements Map
56 {
57 private final static Log log = LogFactory.getLog( LRUMap.class );
58
59
60 private DoubleLinkedList list;
61
62 /*** Map where items are stored by key. */
63 protected Map map;
64
65 int hitCnt = 0;
66
67 int missCnt = 0;
68
69 int putCnt = 0;
70
71
72 int maxObjects = -1;
73
74
75 private int chunkSize = 1;
76
77 /***
78 * This creates an unbounded version. Setting the max objects will result in spooling on
79 * subsequent puts.
80 * <p>
81 * @param maxObjects
82 */
83 public LRUMap()
84 {
85 list = new DoubleLinkedList();
86
87
88
89 map = new Hashtable();
90
91 }
92
93 /***
94 * This sets the size limit.
95 * <p>
96 * @param maxObjects
97 */
98 public LRUMap( int maxObjects )
99 {
100 this();
101 this.maxObjects = maxObjects;
102 }
103
104 /***
105 * This simply returned the number of elements in the map.
106 * <p>
107 * @see java.util.Map#size()
108 */
109 public int size()
110 {
111 return map.size();
112 }
113
114 /***
115 * This removes all the items. It clears the map and the double linked list.
116 * <p>
117 * @see java.util.Map#clear()
118 */
119 public void clear()
120 {
121 map.clear();
122 list.removeAll();
123 }
124
125 /***
126 * Returns true if the map is empty.
127 * <p>
128 * @see java.util.Map#isEmpty()
129 */
130 public boolean isEmpty()
131 {
132 return map.size() == 0;
133 }
134
135 /***
136 * Returns true if the map contains an element for the supplied key.
137 * <p>
138 * @see java.util.Map#containsKey(java.lang.Object)
139 */
140 public boolean containsKey( Object key )
141 {
142 return map.containsKey( key );
143 }
144
145 /***
146 * This is an expensive operation that determines if the object supplied is mapped to any key.
147 * <p>
148 * @see java.util.Map#containsValue(java.lang.Object)
149 */
150 public boolean containsValue( Object value )
151 {
152 return map.containsValue( value );
153 }
154
155
156
157
158
159 public Collection values()
160 {
161 return map.values();
162 }
163
164
165
166
167
168 public void putAll( Map source )
169 {
170 if ( source != null )
171 {
172 Set entries = source.entrySet();
173 Iterator it = entries.iterator();
174 while ( it.hasNext() )
175 {
176 Entry entry = (Entry) it.next();
177 this.put( entry.getKey(), entry.getValue() );
178 }
179 }
180 }
181
182
183
184
185
186 public Object get( Object key )
187 {
188 Object retVal = null;
189
190 if ( log.isDebugEnabled() )
191 {
192 log.debug( "getting item for key " + key );
193 }
194
195 LRUElementDescriptor me = (LRUElementDescriptor) map.get( key );
196
197 if ( me != null )
198 {
199 hitCnt++;
200 if ( log.isDebugEnabled() )
201 {
202 log.debug( "LRUMap hit for " + key );
203 }
204
205 retVal = me.getPayload();
206
207 list.makeFirst( me );
208 }
209 else
210 {
211 missCnt++;
212 log.debug( "LRUMap miss for " + key );
213 }
214
215
216 return retVal;
217 }
218
219 /***
220 * This gets an element out of the map without adjusting it's posisiton in the LRU. In other
221 * words, this does not count as being used. If the element is the last item in the list, it
222 * will still be the last itme in the list.
223 * <p>
224 * @param key
225 * @return Object
226 */
227 public Object getQuiet( Object key )
228 {
229 Object ce = null;
230
231 LRUElementDescriptor me = (LRUElementDescriptor) map.get( key );
232 if ( me != null )
233 {
234 if ( log.isDebugEnabled() )
235 {
236 log.debug( "LRUMap quiet hit for " + key );
237 }
238
239 ce = me.getPayload();
240 }
241 else if ( log.isDebugEnabled() )
242 {
243 log.debug( "LRUMap quiet miss for " + key );
244 }
245
246 return ce;
247 }
248
249
250
251
252
253 public Object remove( Object key )
254 {
255 if ( log.isDebugEnabled() )
256 {
257 log.debug( "removing item for key: " + key );
258 }
259
260
261 LRUElementDescriptor me = (LRUElementDescriptor) map.remove( key );
262
263 if ( me != null )
264 {
265 list.remove( me );
266
267 return me.getPayload();
268 }
269
270 return null;
271 }
272
273
274
275
276
277 public Object put( Object key, Object value )
278 {
279 putCnt++;
280
281 LRUElementDescriptor old = null;
282 synchronized ( this )
283 {
284
285 addFirst( key, value );
286
287 old = (LRUElementDescriptor) map.put( ( (LRUElementDescriptor) list.getFirst() ).getKey(), list.getFirst() );
288
289
290 if ( old != null && ( (LRUElementDescriptor) list.getFirst() ).getKey().equals( old.getKey() ) )
291 {
292 list.remove( old );
293 }
294 }
295
296 int size = map.size();
297
298
299 if ( this.maxObjects >= 0 && size > this.maxObjects )
300 {
301 if ( log.isDebugEnabled() )
302 {
303 log.debug( "In memory limit reached, removing least recently used." );
304 }
305
306
307 int chunkSizeCorrected = Math.min( size, getChunkSize() );
308
309 if ( log.isDebugEnabled() )
310 {
311 log.debug( "About to remove the least recently used. map size: " + size + ", max objects: "
312 + this.maxObjects + ", items to spool: " + chunkSizeCorrected );
313 }
314
315
316
317
318
319 for ( int i = 0; i < chunkSizeCorrected; i++ )
320 {
321 synchronized ( this )
322 {
323 if ( list.getLast() != null )
324 {
325 if ( ( (LRUElementDescriptor) list.getLast() ) != null )
326 {
327 processRemovedLRU( ( (LRUElementDescriptor) list.getLast() ).getKey(),
328 ( (LRUElementDescriptor) list.getLast() ).getPayload() );
329 if ( !map.containsKey( ( (LRUElementDescriptor) list.getLast() ).getKey() ) )
330 {
331 log.error( "update: map does not contain key: "
332 + ( (LRUElementDescriptor) list.getLast() ).getKey() );
333 verifyCache();
334 }
335 if ( map.remove( ( (LRUElementDescriptor) list.getLast() ).getKey() ) == null )
336 {
337 log.warn( "update: remove failed for key: "
338 + ( (LRUElementDescriptor) list.getLast() ).getKey() );
339 verifyCache();
340 }
341 }
342 else
343 {
344 throw new Error( "update: last.ce is null!" );
345 }
346 list.removeLast();
347 }
348 else
349 {
350 verifyCache();
351 throw new Error( "update: last is null!" );
352 }
353 }
354 }
355
356 if ( log.isDebugEnabled() )
357 {
358 log.debug( "update: After spool map size: " + map.size() );
359 }
360 if ( map.size() != dumpCacheSize() )
361 {
362 log.error( "update: After spool, size mismatch: map.size() = " + map.size() + ", linked list size = "
363 + dumpCacheSize() );
364 }
365 }
366
367 if ( old != null )
368 {
369 return old.getPayload();
370 }
371 return null;
372 }
373
374 /***
375 * Adds a new node to the start of the link list.
376 * <p>
377 * @param key
378 * @param val The feature to be added to the First
379 */
380 private synchronized void addFirst( Object key, Object val )
381 {
382
383 LRUElementDescriptor me = new LRUElementDescriptor( key, val );
384 list.addFirst( me );
385 return;
386 }
387
388 /***
389 * Returns the size of the list.
390 * <p>
391 * @return int
392 */
393 private int dumpCacheSize()
394 {
395 return list.size();
396 }
397
398 /***
399 * Dump the cache entries from first to list for debugging.
400 */
401 public void dumpCacheEntries()
402 {
403 log.debug( "dumpingCacheEntries" );
404 for ( LRUElementDescriptor me = (LRUElementDescriptor) list.getFirst(); me != null; me = (LRUElementDescriptor) me.next )
405 {
406 if ( log.isDebugEnabled() )
407 {
408 log.debug( "dumpCacheEntries> key=" + me.getKey() + ", val=" + me.getPayload() );
409 }
410 }
411 }
412
413 /***
414 * Dump the cache map for debugging.
415 */
416 public void dumpMap()
417 {
418 log.debug( "dumpingMap" );
419 for ( Iterator itr = map.entrySet().iterator(); itr.hasNext(); )
420 {
421 Map.Entry e = (Map.Entry) itr.next();
422 LRUElementDescriptor me = (LRUElementDescriptor) e.getValue();
423 if ( log.isDebugEnabled() )
424 {
425 log.debug( "dumpMap> key=" + e.getKey() + ", val=" + me.getPayload() );
426 }
427 }
428 }
429
430 /***
431 * Checks to see if all the items that should be in the cache are. Checks consistency between
432 * List and map.
433 */
434 protected void verifyCache()
435 {
436 if ( !log.isDebugEnabled() )
437 {
438 return;
439 }
440
441 boolean found = false;
442 log.debug( "verifycache: mapContains " + map.size() + " elements, linked list contains " + dumpCacheSize()
443 + " elements" );
444 log.debug( "verifycache: checking linked list by key " );
445 for ( LRUElementDescriptor li = (LRUElementDescriptor) list.getFirst(); li != null; li = (LRUElementDescriptor) li.next )
446 {
447 Object key = li.getKey();
448 if ( !map.containsKey( key ) )
449 {
450 log.error( "verifycache: map does not contain key : " + li.getKey() );
451 log.error( "li.hashcode=" + li.getKey().hashCode() );
452 log.error( "key class=" + key.getClass() );
453 log.error( "key hashcode=" + key.hashCode() );
454 log.error( "key toString=" + key.toString() );
455 if ( key instanceof GroupAttrName )
456 {
457 GroupAttrName name = (GroupAttrName) key;
458 log.error( "GroupID hashcode=" + name.groupId.hashCode() );
459 log.error( "GroupID.class=" + name.groupId.getClass() );
460 log.error( "AttrName hashcode=" + name.attrName.hashCode() );
461 log.error( "AttrName.class=" + name.attrName.getClass() );
462 }
463 dumpMap();
464 }
465 else if ( map.get( li.getKey() ) == null )
466 {
467 log.error( "verifycache: linked list retrieval returned null for key: " + li.getKey() );
468 }
469 }
470
471 log.debug( "verifycache: checking linked list by value " );
472 for ( LRUElementDescriptor li3 = (LRUElementDescriptor) list.getFirst(); li3 != null; li3 = (LRUElementDescriptor) li3.next )
473 {
474 if ( map.containsValue( li3 ) == false )
475 {
476 log.error( "verifycache: map does not contain value : " + li3 );
477 dumpMap();
478 }
479 }
480
481 log.debug( "verifycache: checking via keysets!" );
482 for ( Iterator itr2 = map.keySet().iterator(); itr2.hasNext(); )
483 {
484 found = false;
485 Serializable val = null;
486 try
487 {
488 val = (Serializable) itr2.next();
489 }
490 catch ( NoSuchElementException nse )
491 {
492 log.error( "verifycache: no such element exception" );
493 }
494
495 for ( LRUElementDescriptor li2 = (LRUElementDescriptor) list.getFirst(); li2 != null; li2 = (LRUElementDescriptor) li2.next )
496 {
497 if ( val.equals( li2.getKey() ) )
498 {
499 found = true;
500 break;
501 }
502 }
503 if ( !found )
504 {
505 log.error( "verifycache: key not found in list : " + val );
506 dumpCacheEntries();
507 if ( map.containsKey( val ) )
508 {
509 log.error( "verifycache: map contains key" );
510 }
511 else
512 {
513 log.error( "verifycache: map does NOT contain key, what the HECK!" );
514 }
515 }
516 }
517 }
518
519 /***
520 * Logs an error is an element that should be in the cache is not.
521 * <p>
522 * @param key
523 */
524 protected void verifyCache( Object key )
525 {
526 if ( !log.isDebugEnabled() )
527 {
528 return;
529 }
530
531 boolean found = false;
532
533
534 for ( LRUElementDescriptor li = (LRUElementDescriptor) list.getFirst(); li != null; li = (LRUElementDescriptor) li.next )
535 {
536 if ( li.getKey() == key )
537 {
538 found = true;
539 log.debug( "verifycache(key) key match: " + key );
540 break;
541 }
542 }
543 if ( !found )
544 {
545 log.error( "verifycache(key), couldn't find key! : " + key );
546 }
547 }
548
549 /***
550 * This is called when an item is removed from the LRU. We just log some information.
551 * <p>
552 * Children can implement this method for special behavior.
553 * @param key
554 * @param value
555 */
556 protected void processRemovedLRU( Object key, Object value )
557 {
558 if ( log.isDebugEnabled() )
559 {
560 log.debug( "Removing key: [" + key + "] from LRUMap store, value = [" + value + "]" );
561 log.debug( "LRUMap store size: '" + this.size() + "'." );
562 }
563 }
564
565 /***
566 * The chunk size is the number of items to remove when the max is reached. By default it is 1.
567 * <p>
568 * @param chunkSize The chunkSize to set.
569 */
570 public void setChunkSize( int chunkSize )
571 {
572 this.chunkSize = chunkSize;
573 }
574
575 /***
576 * @return Returns the chunkSize.
577 */
578 public int getChunkSize()
579 {
580 return chunkSize;
581 }
582
583 /***
584 * @return IStats
585 */
586 public IStats getStatistics()
587 {
588 IStats stats = new Stats();
589 stats.setTypeName( "LRUMap" );
590
591 ArrayList elems = new ArrayList();
592
593 IStatElement se = null;
594
595 se = new StatElement();
596 se.setName( "List Size" );
597 se.setData( "" + list.size() );
598 elems.add( se );
599
600 se = new StatElement();
601 se.setName( "Map Size" );
602 se.setData( "" + map.size() );
603 elems.add( se );
604
605 se = new StatElement();
606 se.setName( "Put Count" );
607 se.setData( "" + putCnt );
608 elems.add( se );
609
610 se = new StatElement();
611 se.setName( "Hit Count" );
612 se.setData( "" + hitCnt );
613 elems.add( se );
614
615 se = new StatElement();
616 se.setName( "Miss Count" );
617 se.setData( "" + missCnt );
618 elems.add( se );
619
620
621 IStatElement[] ses = (IStatElement[]) elems.toArray( new StatElement[0] );
622 stats.setStatElements( ses );
623
624 return stats;
625 }
626
627 /***
628 * This returns a set of entries. Our LRUMapEntry is used since the value stored in the
629 * underlying map is a node in the double linked list. We wouldn't want to return this to the
630 * client, so we construct a new entry with the payload of the node.
631 * <p>
632 * TODO we should return out own set wrapper, so we can avoid the extra object creation if it
633 * isn't necessary.
634 * <p>
635 * @see java.util.Map#entrySet()
636 */
637 public synchronized Set entrySet()
638 {
639
640 Set entries = map.entrySet();
641
642 Set unWrapped = new HashSet();
643
644 Iterator it = entries.iterator();
645 while ( it.hasNext() )
646 {
647 Entry pre = (Entry) it.next();
648 Entry post = new LRUMapEntry( pre.getKey(), ( (LRUElementDescriptor) pre.getValue() ).getPayload() );
649 unWrapped.add( post );
650 }
651
652 return unWrapped;
653 }
654
655
656
657
658
659 public Set keySet()
660 {
661
662 return map.keySet();
663 }
664 }