KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > joseki > util > cache > CachePolicyLRU


1 /*
2  * (c) Copyright 2003, 2004 Hewlett-Packard Development Company, LP
3  * [See end of file]
4  */
5
6
7 /** Everyone's favourite cache policy - Least Recently Used
8  *
9  * @author Andy Seaborne
10  * @version $Id: CachePolicyLRU.java,v 1.5 2004/04/30 14:13:13 andy_seaborne Exp $
11  */
12  
13 package org.joseki.util.cache;
14
15 import java.util.* ;
16 import org.apache.commons.logging.*;
17
18 public class CachePolicyLRU implements CachePolicy
19 {
20     static Log log = LogFactory.getLog(CachePolicyLRU.class.getName()) ;
21     
22     // This implementation simply keeps a linked list.
23 // When an object is accessed, the item is moved to the front and
24 // the LRU object is the last in the list.
25
26     // Requires O(n) update.
27
28     // Alternative implmentation:
29 // Use a set to entries which record the access count.
30 // Scan to expel. Update O(set access).
31 // This would extend to weighted LRU
32 // but is more space costly.
33
34     // The low (first) end is the most recently used.
35 LinkedList list = new LinkedList() ;
36     
37     public Object JavaDoc[] expel(int count)
38     {
39         if ( log.isTraceEnabled() )
40             log.trace("expel("+count+")") ;
41         
42         Object JavaDoc[] keys = new Object JavaDoc[count] ;
43         for ( int i = 0 ; i < count ; i++ )
44         {
45             keys[i] = list.removeLast() ;
46             if ( log.isTraceEnabled() )
47                 log.trace("expel "+keys[i]) ;
48         }
49         return keys ;
50     }
51     
52     
53     public void update(Object JavaDoc key)
54     {
55         if ( log.isTraceEnabled() )
56             log.trace("update("+key+")") ;
57         if ( ! list.getFirst().equals(key) )
58         {
59             list.remove(key) ;
60             list.addFirst(key) ;
61         }
62
63         if ( log.isTraceEnabled() )
64             dump() ;
65     }
66     
67
68     public void newItem(Object JavaDoc key, Object JavaDoc value)
69     {
70         if ( log.isTraceEnabled() )
71            log.trace("newItem("+key+")") ;
72         list.addFirst(key) ;
73     }
74    
75     private void dump()
76     {
77         String JavaDoc $state = "" ;
78         for ( Iterator iter = list.listIterator() ; iter.hasNext() ; )
79         {
80             $state = $state+iter.next()+" " ;
81         }
82         log.trace($state) ;
83     }
84 }
85
86
87 /*
88  * (c) Copyright 2003, 2004 Hewlett-Packard Development Company, LP
89  * All rights reserved.
90  *
91  * Redistribution and use in source and binary forms, with or without
92  * modification, are permitted provided that the following conditions
93  * are met:
94  * 1. Redistributions of source code must retain the above copyright
95  * notice, this list of conditions and the following disclaimer.
96  * 2. Redistributions in binary form must reproduce the above copyright
97  * notice, this list of conditions and the following disclaimer in the
98  * documentation and/or other materials provided with the distribution.
99  * 3. The name of the author may not be used to endorse or promote products
100  * derived from this software without specific prior written permission.
101  *
102  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
103  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
104  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
105  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
106  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
107  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
108  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
109  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
110  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
111  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
112  */
113
Popular Tags