View Javadoc
1   package org.apache.commons.jcs.utils.struct;
2   
3   /*
4    * Licensed to the Apache Software Foundation (ASF) under one
5    * or more contributor license agreements.  See the NOTICE file
6    * distributed with this work for additional information
7    * regarding copyright ownership.  The ASF licenses this file
8    * to you under the Apache License, Version 2.0 (the
9    * "License"); you may not use this file except in compliance
10   * with the License.  You may obtain a copy of the License at
11   *
12   *   http://www.apache.org/licenses/LICENSE-2.0
13   *
14   * Unless required by applicable law or agreed to in writing,
15   * software distributed under the License is distributed on an
16   * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
17   * KIND, either express or implied.  See the License for the
18   * specific language governing permissions and limitations
19   * under the License.
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   * This is a simple LRUMap. It implements most of the map methods. It is not recommended that you
45   * use any but put, get, remove, and clear.
46   * <p>
47   * Children can implement the processRemovedLRU method if they want to handle the removal of the
48   * lest recently used item.
49   * <p>
50   * This class was abstracted out of the LRU Memory cache. Put, remove, and get should be thread
51   * safe. It uses a hashtable and our own double linked list.
52   * <p>
53   * Locking is done on the instance.
54   * <p>
55   * @author aaron smuts
56   */
57  public abstract class AbstractLRUMap<K, V>
58      implements Map<K, V>
59  {
60      /** The logger */
61      private static final Log log = LogFactory.getLog( AbstractLRUMap.class );
62  
63      /** double linked list for lru */
64      private final DoubleLinkedList<LRUElementDescriptor<K, V>> list;
65  
66      /** Map where items are stored by key. */
67      private Map<K, LRUElementDescriptor<K, V>> map;
68  
69      /** stats */
70      int hitCnt = 0;
71  
72      /** stats */
73      int missCnt = 0;
74  
75      /** stats */
76      int putCnt = 0;
77  
78      /** make configurable */
79      private int chunkSize = 1;
80  
81      private final Lock lock = new ReentrantLock();
82  
83      /**
84       * This creates an unbounded version. Setting the max objects will result in spooling on
85       * subsequent puts.
86       */
87      public AbstractLRUMap()
88      {
89          list = new DoubleLinkedList<LRUElementDescriptor<K, V>>();
90  
91          // normal hashtable is faster for
92          // sequential keys.
93          map = new ConcurrentHashMap<K, LRUElementDescriptor<K, V>>();
94      }
95  
96  
97      /**
98       * This simply returns the number of elements in the map.
99       * <p>
100      * @see java.util.Map#size()
101      */
102     @Override
103     public int size()
104     {
105         return map.size();
106     }
107 
108     /**
109      * This removes all the items. It clears the map and the double linked list.
110      * <p>
111      * @see java.util.Map#clear()
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      * Returns true if the map is empty.
130      * <p>
131      * @see java.util.Map#isEmpty()
132      */
133     @Override
134     public boolean isEmpty()
135     {
136         return map.isEmpty();
137     }
138 
139     /**
140      * Returns true if the map contains an element for the supplied key.
141      * <p>
142      * @see java.util.Map#containsKey(java.lang.Object)
143      */
144     @Override
145     public boolean containsKey( Object key )
146     {
147         return map.containsKey( key );
148     }
149 
150     /**
151      * This is an expensive operation that determines if the object supplied is mapped to any key.
152      * <p>
153      * @see java.util.Map#containsValue(java.lang.Object)
154      */
155     @Override
156     public boolean containsValue( Object value )
157     {
158         return map.containsValue( value );
159     }
160 
161     /**
162      * @return map.values();
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      * @param source
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      * @param key
194      * @return Object
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         // verifyCache();
227         return retVal;
228     }
229 
230     /**
231      * This gets an element out of the map without adjusting it's position in the LRU. In other
232      * words, this does not count as being used. If the element is the last item in the list, it
233      * will still be the last time in the list.
234      * <p>
235      * @param key
236      * @return Object
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      * @param key
262      * @return Object removed
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         // remove single item.
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      * @param key
294      * @param value
295      * @return Object
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             // TODO address double synchronization of addFirst, use write lock
307             addFirst( key, value );
308             // this must be synchronized
309             LRUElementDescriptor<K, V> first = list.getFirst();
310             old = map.put(first.getKey(), first);
311 
312             // If the node was the same as an existing node, remove it.
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         // If the element limit is reached, we need to spool
324 
325         if (shouldRemove())
326         {
327             if (log.isDebugEnabled())
328             {
329                 log.debug( "In memory limit reached, removing least recently used." );
330             }
331 
332             // The spool will put them in a disk event queue, so there is no
333             // need to pre-queue the queuing. This would be a bit wasteful
334             // and wouldn't save much time in this synchronous call.
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      * Adds a new node to the start of the link list.
388      * <p>
389      * @param key
390      * @param val The feature to be added to the First
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      * Returns the size of the list.
408      * <p>
409      * @return int
410      */
411     private int dumpCacheSize()
412     {
413         return list.size();
414     }
415 
416     /**
417      * Dump the cache entries from first to list for debugging.
418      */
419     @SuppressWarnings("unchecked") // No generics for public fields
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      * Dump the cache map for debugging.
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      * Checks to see if all the items that should be in the cache are. Checks consistency between
450      * List and map.
451      */
452     @SuppressWarnings("unchecked") // No generics for public fields
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      * Logs an error is an element that should be in the cache is not.
541      * <p>
542      * @param key
543      */
544     @SuppressWarnings("unchecked") // No generics for public fields
545     protected void verifyCache( Object key )
546     {
547         if ( !log.isDebugEnabled() )
548         {
549             return;
550         }
551 
552         boolean found = false;
553 
554         // go through the linked list looking for the key
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      * This is called when an item is removed from the LRU. We just log some information.
572      * <p>
573      * Children can implement this method for special behavior.
574      * @param key
575      * @param value
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      * The chunk size is the number of items to remove when the max is reached. By default it is 1.
588      * <p>
589      * @param chunkSize The chunkSize to set.
590      */
591     public void setChunkSize( int chunkSize )
592     {
593         this.chunkSize = chunkSize;
594     }
595 
596     /**
597      * @return Returns the chunkSize.
598      */
599     public int getChunkSize()
600     {
601         return chunkSize;
602     }
603 
604     /**
605      * @return IStats
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      * This returns a set of entries. Our LRUMapEntry is used since the value stored in the
627      * underlying map is a node in the double linked list. We wouldn't want to return this to the
628      * client, so we construct a new entry with the payload of the node.
629      * <p>
630      * TODO we should return out own set wrapper, so we can avoid the extra object creation if it
631      * isn't necessary.
632      * <p>
633      * @see java.util.Map#entrySet()
634      */
635     @Override
636     public Set<Map.Entry<K, V>> entrySet()
637     {
638         lock.lock();
639         try
640         {
641             // TODO we should return a defensive copy
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      * @return map.keySet();
660      */
661     @Override
662     public Set<K> keySet()
663     {
664         // TODO fix this, it needs to return the keys inside the wrappers.
665         return map.keySet();
666     }
667 
668 }