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