View Javadoc

1   package org.apache.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.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      // double linked list for lru
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      // if the max is less than 0, there is no limit!
72      int maxObjects = -1;
73  
74      // make configurable
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          // normal hshtable is faster for
88          // sequential keys.
89          map = new Hashtable();
90          // map = new ConcurrentHashMap();
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      * (non-Javadoc)
157      * @see java.util.Map#values()
158      */
159     public Collection values()
160     {
161         return map.values();
162     }
163 
164     /*
165      * (non-Javadoc)
166      * @see java.util.Map#putAll(java.util.Map)
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      * (non-Javadoc)
184      * @see java.util.Map#get(java.lang.Object)
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         // verifyCache();
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      * (non-Javadoc)
251      * @see java.util.Map#remove(java.lang.Object)
252      */
253     public Object remove( Object key )
254     {
255         if ( log.isDebugEnabled() )
256         {
257             log.debug( "removing item for key: " + key );
258         }
259 
260         // remove single item.
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      * (non-Javadoc)
275      * @see java.util.Map#put(java.lang.Object, java.lang.Object)
276      */
277     public Object put( Object key, Object value )
278     {
279         putCnt++;
280 
281         LRUElementDescriptor old = null;
282         synchronized ( this )
283         {
284             // TODO address double synchronization of addFirst, use write lock
285             addFirst( key, value );
286             // this must be synchronized
287             old = (LRUElementDescriptor) map.put( ( (LRUElementDescriptor) list.getFirst() ).getKey(), list.getFirst() );
288 
289             // If the node was the same as an existing node, remove it.
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         // If the element limit is reached, we need to spool
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             // Write the last 'chunkSize' items to disk.
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             // The spool will put them in a disk event queue, so there is no
316             // need to pre-queue the queuing. This would be a bit wasteful
317             // and wouldn't save much time in this synchronous call.
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         // go through the linked list looking for the key
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         // get an array and put them in the Stats object
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         // todo, we should return a defensive copy
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      * (non-Javadoc)
657      * @see java.util.Map#keySet()
658      */
659     public Set keySet()
660     {
661         // TODO fix this, it needs to return the keys inside the wrappers.
662         return map.keySet();
663     }
664 }