LRUCachePolicy


1   /*
2     * JBoss, Home of Professional Open Source
3     * Copyright 2005, JBoss Inc., and individual contributors as indicated
4     * by the @authors tag. See the copyright.txt in the distribution for a
5     * full listing of individual contributors.
6     *
7     * This is free software; you can redistribute it and/or modify it
8     * under the terms of the GNU Lesser General Public License as
9     * published by the Free Software Foundation; either version 2.1 of
10    * the License, or (at your option) any later version.
11    *
12    * This software is distributed in the hope that it will be useful,
13    * but WITHOUT ANY WARRANTY; without even the implied warranty of
14    * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15    * Lesser General Public License for more details.
16    *
17    * You should have received a copy of the GNU Lesser General Public
18    * License along with this software; if not, write to the Free
19    * Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
20    * 02110-1301 USA, or see the FSF site: http://www.fsf.org.
21    */
22  package org.jboss.util;
23  
24  import java.util.HashMap  ;
25  
26  /**
27   * Implementation of a Least Recently Used cache policy.
28   *
29   * @author <a HREF="mailto:simone.bordet@compaq.com">Simone Bordet</a>
30   * @version $Revision: 1958 $
31   */
32  public class LRUCachePolicy
33     implements CachePolicy
34  {
35     // Constants -----------------------------------------------------
36  
37     // Attributes ----------------------------------------------------
38     /**
39      * The map holding the cached objects
40      */
41     protected HashMap   m_map;
42     /**
43      * The linked list used to implement the LRU algorithm
44      */
45     protected LRUList m_list;
46     /**
47      * The maximum capacity of this cache
48      */
49     protected int m_maxCapacity;
50     /**
51      * The minimum capacity of this cache
52      */
53     protected int m_minCapacity;
54  
55     // Static --------------------------------------------------------
56  
57     // Constructors --------------------------------------------------
58     /**
59      * Creates a LRU cache policy object with zero cache capacity.
60      *
61      * @see #create
62      */
63     public LRUCachePolicy()
64     {
65     }
66     /**
67      * Creates a LRU cache policy object with the specified minimum
68      * and maximum capacity.
69      *
70      * @see #create
71      */
72     public LRUCachePolicy(int min, int max)
73     {
74        if (min < 2 || min > max) {throw new IllegalArgumentException  ("Illegal cache capacities");}
75        m_minCapacity = min;
76        m_maxCapacity = max;
77     }
78  
79     // Public --------------------------------------------------------
80  
81     // Service implementation ----------------------------------------------
82     /**
83      * Initializes the cache, creating all required objects and initializing their
84      * values.
85      * @see #start
86      * @see #destroy
87      */
88     public void create()
89     {
90        m_map = new HashMap  ();
91        m_list = createList();
92        m_list.m_maxCapacity = m_maxCapacity;
93        m_list.m_minCapacity = m_minCapacity;
94        m_list.m_capacity = m_maxCapacity;
95     }
96     /**
97      * Starts this cache that is now ready to be used.
98      * @see #create
99      * @see #stop
100     */
101    public void start()
102    {
103    }
104    /**
105     * Stops this cache thus {@link #flush}ing all cached objects. <br>
106     * After this method is called, a call to {@link #start} will restart the cache.
107     * @see #start
108     * @see #destroy
109     */
110    public void stop()
111    {
112       if (m_list != null)
113       {
114          flush();
115       }
116    }
117    /**
118     * Destroys the cache that is now unusable. <br>
119     * To have it working again it must be re-{@link #create}ed and
120     * re-{@link #start}ed.
121     *
122     * @see #create
123     */
124    public void destroy()
125    {
126       if( m_map != null )
127          m_map.clear();
128       if( m_list != null )
129          m_list.clear();
130    }
131 
132    public Object   get(Object   key)
133    {
134       if (key == null)
135       {
136          throw new IllegalArgumentException  ("Requesting an object using a null key");
137       }
138 
139       LRUCacheEntry value = (LRUCacheEntry)m_map.get(key);
140       if (value != null)
141       {
142          m_list.promote(value);
143          return value.m_object;
144       }
145       else
146       {
147          cacheMiss();
148          return null;
149       }
150    }
151    public Object   peek(Object   key)
152    {
153       if (key == null)
154       {
155          throw new IllegalArgumentException  ("Requesting an object using a null key");
156       }
157 
158       LRUCacheEntry value = (LRUCacheEntry)m_map.get(key);
159       if (value == null)
160       {
161          return null;
162       }
163       else
164       {
165          return value.m_object;
166       }
167    }
168    public void insert(Object   key, Object   o)
169    {
170       if (o == null) {throw new IllegalArgumentException  ("Cannot insert a null object in the cache");}
171       if (key == null) {throw new IllegalArgumentException  ("Cannot insert an object in the cache with null key");}
172       if (m_map.containsKey(key))
173       {
174          throw new IllegalStateException  ("Attempt to put in the cache an object that is already there");
175       }
176       m_list.demote();
177       LRUCacheEntry entry = createCacheEntry(key, o);
178       m_map.put(key, entry);
179       m_list.promote(entry);
180    }
181    public void remove(Object   key)
182    {
183       if (key == null) {throw new IllegalArgumentException  ("Removing an object using a null key");}
184 
185       Object   value = m_map.remove(key);
186       if (value != null)
187       {
188          m_list.remove((LRUCacheEntry)value);
189       }
190       //else Do nothing, the object isn't in the cache list
191    }
192    public void flush()
193    {
194       LRUCacheEntry entry = null;
195       while ((entry = m_list.m_tail) != null)
196       {
197          ageOut(entry);
198       }
199    }
200 
201    public int size() {
202       return m_list.m_count;
203    }
204 
205    // Y overrides ---------------------------------------------------
206 
207    // Package protected ---------------------------------------------
208 
209    // Protected -----------------------------------------------------
210    /**
211     * Factory method for the linked list used by this cache implementation.
212     */
213    protected LRUList createList() {return new LRUList();}
214    /**
215     * Callback method called when the cache algorithm ages out of the cache
216     * the given entry. <br>
217     * The implementation here is removing the given entry from the cache.
218     */
219    protected void ageOut(LRUCacheEntry entry)
220    {
221       remove(entry.m_key);
222    }
223    /**
224     * Callback method called when a cache miss happens.
225     */
226    protected void cacheMiss()
227    {
228    }
229    /**
230     * Factory method for cache entries
231     */
232    protected LRUCacheEntry createCacheEntry(Object   key, Object   value)
233    {
234       return new LRUCacheEntry(key, value);
235    }
236 
237    // Private -------------------------------------------------------
238 
239    // Inner classes -------------------------------------------------
240    /**
241     * Double queued list used to store cache entries.
242     */
243    public class LRUList
244    {
245       /** The maximum capacity of the cache list */
246       public int m_maxCapacity;
247       /** The minimum capacity of the cache list */
248       public int m_minCapacity;
249       /** The current capacity of the cache list */
250       public int m_capacity;
251       /** The number of cached objects */
252       public int m_count;
253       /** The head of the double linked list */
254       public LRUCacheEntry m_head;
255       /** The tail of the double linked list */
256       public LRUCacheEntry m_tail;
257       /** The cache misses happened */
258       public int m_cacheMiss;
259       /**
260        * Creates a new double queued list.
261        */
262       protected LRUList()
263       {
264          m_head = null;
265          m_tail = null;
266          m_count = 0;
267       }
268       /**
269        * Promotes the cache entry <code>entry</code> to the last used position
270        * of the list. <br>
271        * If the object is already there, does nothing.
272        * @param entry the object to be promoted, cannot be null
273        * @see #demote
274        * @throws IllegalStateException if this method is called with a full cache
275        */
276       protected void promote(LRUCacheEntry entry)
277       {
278          if (entry == null) {throw new IllegalArgumentException  ("Trying to promote a null object");}
279          if (m_capacity < 1) {throw new IllegalStateException  ("Can't work with capacity < 1");}
280 
281          entryPromotion(entry);
282 
283          entry.m_time = System.currentTimeMillis();
284          if (entry.m_prev == null)
285          {
286             if (entry.m_next == null)
287             {
288                // entry is new or there is only the head
289                if (m_count == 0) // cache is empty
290                {
291                   m_head = entry;
292                   m_tail = entry;
293                   ++m_count;
294                   entryAdded(entry);
295                }
296                else if (m_count == 1 && m_head == entry) {} // there is only the head and I want to promote it, do nothing
297                else if (m_count < m_capacity)
298                {
299                   entry.m_prev = null;
300                   entry.m_next = m_head;
301                   m_head.m_prev = entry;
302                   m_head = entry;
303                   ++m_count;
304                   entryAdded(entry);
305                }
306                else if (m_count < m_maxCapacity)
307                {
308                   entry.m_prev = null;
309                   entry.m_next = m_head;
310                   m_head.m_prev = entry;
311                   m_head = entry;
312                   ++m_count;
313                   int oldCapacity = m_capacity;
314                   ++m_capacity;
315                   entryAdded(entry);
316                   capacityChanged(oldCapacity);
317                }
318                else {throw new IllegalStateException  ("Attempt to put a new cache entry on a full cache");}
319             }
320             else {} // entry is the head, do nothing
321          }
322          else
323          {
324             if (entry.m_next == null) // entry is the tail
325             {
326                LRUCacheEntry beforeLast = entry.m_prev;
327                beforeLast.m_next = null;
328                entry.m_prev = null;
329                entry.m_next = m_head;
330                m_head.m_prev = entry;
331                m_head = entry;
332                m_tail = beforeLast;
333             }
334             else // entry is in the middle of the list
335             {
336                LRUCacheEntry previous = entry.m_prev;
337                previous.m_next = entry.m_next;
338                entry.m_next.m_prev = previous;
339                entry.m_prev = null;
340                entry.m_next = m_head;
341                m_head.m_prev = entry;
342                m_head = entry;
343             }
344          }
345       }
346       /**
347        * Demotes from the cache the least used entry. <br>
348        * If the cache is not full, does nothing.
349        * @see #promote
350        */
351       protected void demote()
352       {
353          if (m_capacity < 1) {throw new IllegalStateException  ("Can't work with capacity < 1");}
354          if (m_count > m_maxCapacity) {throw new IllegalStateException  ("Cache list entries number (" + m_count + ") > than the maximum allowed (" + m_maxCapacity + ")");}
355          if (m_count == m_maxCapacity)
356          {
357             LRUCacheEntry entry = m_tail;
358 
359             // the entry will be removed by ageOut
360             ageOut(entry);
361          }
362          else {} // cache is not full, do nothing
363       }
364       /**
365        * Removes from the cache list the specified entry.
366        */
367       protected void remove(LRUCacheEntry entry)
368       {
369          if (entry == null) {throw new IllegalArgumentException  ("Cannot remove a null entry from the cache");}
370          if (m_count < 1) {throw new IllegalStateException  ("Trying to remove an entry from an empty cache");}
371 
372          entry.m_key = entry.m_object = null;
373          if (m_count == 1)
374          {
375             m_head = m_tail = null;
376          }
377          else
378          {
379             if (entry.m_prev == null) // the head
380             {
381                m_head = entry.m_next;
382                m_head.m_prev = null;
383                entry.m_next = null;
384             }
385             else if (entry.m_next == null) // the tail
386             {
387                m_tail = entry.m_prev;
388                m_tail.m_next = null;
389                entry.m_prev = null;
390             }
391             else // in the middle
392             {
393                entry.m_next.m_prev = entry.m_prev;
394                entry.m_prev.m_next = entry.m_next;
395                entry.m_prev = null;
396                entry.m_next = null;
397             }
398          }
399          --m_count;
400          entryRemoved(entry);
401       }
402       /**
403        * Callback that signals that the given entry is just about to be added.
404        */
405       protected void entryPromotion(LRUCacheEntry entry) {}
406       /**
407        * Callback that signals that the given entry has been added to the cache.
408        */
409       protected void entryAdded(LRUCacheEntry entry) {}
410       /**
411        * Callback that signals that the given entry has been removed from the cache.
412        */
413       protected void entryRemoved(LRUCacheEntry entry) {}
414       /**
415        * Callback that signals that the capacity of the cache is changed.
416        * @param oldCapacity the capacity before the change happened
417        */
418       protected void capacityChanged(int oldCapacity) {}
419 
420       protected void clear()
421       {
422          LRUCacheEntry entry = m_head;
423          m_head = null;
424          m_tail = null;
425          m_count = 0;
426          for (; entry != null; entry = entry.m_next)
427             entryRemoved(entry);
428       }
429 
430       public String   toString()
431       {
432          String   s = Integer.toHexString(super.hashCode());
433          s += " size: " + m_count;
434          for (LRUCacheEntry entry = m_head; entry != null; entry = entry.m_next)
435          {
436             s += "\n" + entry;
437          }
438          return s;
439       }
440    }
441 
442    /**
443     * Double linked cell used as entry in the cache list.
444     */
445    public class LRUCacheEntry
446    {
447       /** Reference to the next cell in the list */
448       public  LRUCacheEntry m_next;
449       /** Reference to the previous cell in the list */
450       public LRUCacheEntry m_prev;
451       /** The key used to retrieve the cached object */
452       public Object   m_key;
453       /** The cached object */
454       public Object   m_object;
455       /** The timestamp of the creation */
456       public long m_time;
457       /**
458        * Creates a new double linked cell, storing the object we
459        * want to cache and the key that is used to retrieve it.
460        */
461       protected LRUCacheEntry(Object   key, Object   object)
462       {
463          m_key = key;
464          m_object = object;
465          m_next = null;
466          m_prev = null;
467          m_time = 0; // Set when inserted in the list.
468       }
469       public String   toString()
470       {
471          return "key: " + m_key + ", object: " + ( m_object==null ? "null" : Integer.toHexString(m_object.hashCode())) + ", entry: " + Integer.toHexString(super.hashCode());
472       }
473    }
474 }
475
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags