KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > oro > util > CacheLRU


1 package org.apache.oro.util;
2
3 /* ====================================================================
4  * The Apache Software License, Version 1.1
5  *
6  * Copyright (c) 2000 The Apache Software Foundation. All rights
7  * reserved.
8  *
9  * Redistribution and use in source and binary forms, with or without
10  * modification, are permitted provided that the following conditions
11  * are met:
12  *
13  * 1. Redistributions of source code must retain the above copyright
14  * notice, this list of conditions and the following disclaimer.
15  *
16  * 2. Redistributions in binary form must reproduce the above copyright
17  * notice, this list of conditions and the following disclaimer in
18  * the documentation and/or other materials provided with the
19  * distribution.
20  *
21  * 3. The end-user documentation included with the redistribution,
22  * if any, must include the following acknowledgment:
23  * "This product includes software developed by the
24  * Apache Software Foundation (http://www.apache.org/)."
25  * Alternately, this acknowledgment may appear in the software itself,
26  * if and wherever such third-party acknowledgments normally appear.
27  *
28  * 4. The names "Apache" and "Apache Software Foundation", "Jakarta-Oro"
29  * must not be used to endorse or promote products derived from this
30  * software without prior written permission. For written
31  * permission, please contact apache@apache.org.
32  *
33  * 5. Products derived from this software may not be called "Apache"
34  * or "Jakarta-Oro", nor may "Apache" or "Jakarta-Oro" appear in their
35  * name, without prior written permission of the Apache Software Foundation.
36  *
37  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
38  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
39  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
40  * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
41  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
42  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
43  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
44  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
45  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
46  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
47  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
48  * SUCH DAMAGE.
49  * ====================================================================
50  *
51  * This software consists of voluntary contributions made by many
52  * individuals on behalf of the Apache Software Foundation. For more
53  * information on the Apache Software Foundation, please see
54  * <http://www.apache.org/>.
55  *
56  * Portions of this software are based upon software originally written
57  * by Daniel F. Savarese. We appreciate his contributions.
58  */
59
60 import java.util.*;
61
62 /**
63  * This class is a GenericCache subclass implementing an LRU
64  * (Least Recently Used) cache replacement policy. In other words,
65  * values are added to the cache until it becomes full. Once the
66  * cache is full, when a new value is added to the cache, it replaces
67  * the least recently used value currently in the cache. This is probably
68  * the best general purpose cache replacement policy.
69
70  @author <a HREF="dfs@savarese.org">Daniel F. Savarese</a>
71  @version $Id: CacheLRU.java,v 1.1.1.1 2000/07/23 23:08:54 jon Exp $
72
73  * @see GenericCache
74  */
75 public final class CacheLRU extends GenericCache {
76   private int __head = 0, __tail = 0;
77   private int[] __next, __prev;
78
79   /**
80    * Creates a CacheLRU instance with a given cache capacity.
81    * <p>
82    * @param capacity The capacity of the cache.
83    */
84   public CacheLRU(int capacity) {
85     super(capacity);
86
87     int i;
88
89     __next = new int[_cache.length];
90     __prev = new int[_cache.length];
91
92     for(i=0; i < __next.length; i++)
93       __next[i] = __prev[i] = -1;
94   }
95
96
97   /**
98    * Same as:
99    * <blockquote><pre>
100    * CacheLRU(GenericCache.DEFAULT_CAPACITY);
101    * </pre></blockquote>
102    */
103   public CacheLRU(){
104     this(GenericCache.DEFAULT_CAPACITY);
105   }
106
107
108   private void __moveToFront(int index) {
109     int next, prev;
110
111     if(__head != index) {
112       next = __next[index];
113       prev = __prev[index];
114
115       // Only the head has a prev entry that is an invalid index so
116 // we don't check.
117 __next[prev] = next;
118
119       // Make sure index is valid. If it isn't, we're at the tail
120 // and don't set __prev[next].
121 if(next >= 0)
122     __prev[next] = prev;
123       else
124     __tail = prev;
125
126       __prev[index] = -1;
127       __next[index] = __head;
128       __prev[__head] = index;
129       __head = index;
130     }
131   }
132
133
134   public synchronized Object JavaDoc getElement(Object JavaDoc key) {
135     Object JavaDoc obj;
136
137     obj = _table.get(key);
138
139     if(obj != null) {
140       GenericCacheEntry entry;
141
142       entry = (GenericCacheEntry)obj;
143       // Maintain LRU property
144 __moveToFront(entry._index);
145
146       return entry._value;
147     }
148
149     return null;
150   }
151
152
153   /**
154    * Adds a value to the cache. If the cache is full, when a new value
155    * is added to the cache, it replaces the first of the current values
156    * in the cache to have been added (i.e., FIFO).
157    * <p>
158    * @param key The key referencing the value added to the cache.
159    * @param value The value to add to the cache.
160    */
161   public final synchronized void addElement(Object JavaDoc key, Object JavaDoc value) {
162     int index;
163     Object JavaDoc obj;
164
165     obj = _table.get(key);
166
167     if(obj != null) {
168       GenericCacheEntry entry;
169
170       // Just replace the value, but move it to the front.
171 entry = (GenericCacheEntry)obj;
172       entry._value = value;
173       entry._key = key;
174
175       __moveToFront(entry._index);
176
177       return;
178     }
179
180     // If we haven't filled the cache yet, place in next available spot
181 // and move to front.
182 if(!isFull()) {
183       if(_numEntries > 0) {
184     __prev[_numEntries] = __tail;
185     __next[_numEntries] = -1;
186     __moveToFront(_numEntries);
187       }
188       ++_numEntries;
189     } else {
190       // We replace the tail of the list.
191 _table.remove(_cache[__tail]._key);
192       __moveToFront(__tail);
193     }
194
195     _cache[__head]._value = value;
196     _cache[__head]._key = key;
197     _table.put(key, _cache[__head]);
198   }
199 }
200
Popular Tags