001: /*
002: * $Id: CacheLRU.java,v 1.10 2003/11/07 20:16:25 dfs Exp $
003: *
004: * ====================================================================
005: * The Apache Software License, Version 1.1
006: *
007: * Copyright (c) 2000 The Apache Software Foundation. All rights
008: * reserved.
009: *
010: * Redistribution and use in source and binary forms, with or without
011: * modification, are permitted provided that the following conditions
012: * are met:
013: *
014: * 1. Redistributions of source code must retain the above copyright
015: * notice, this list of conditions and the following disclaimer.
016: *
017: * 2. Redistributions in binary form must reproduce the above copyright
018: * notice, this list of conditions and the following disclaimer in
019: * the documentation and/or other materials provided with the
020: * distribution.
021: *
022: * 3. The end-user documentation included with the redistribution,
023: * if any, must include the following acknowledgment:
024: * "This product includes software developed by the
025: * Apache Software Foundation (http://www.apache.org/)."
026: * Alternately, this acknowledgment may appear in the software itself,
027: * if and wherever such third-party acknowledgments normally appear.
028: *
029: * 4. The names "Apache" and "Apache Software Foundation", "Jakarta-Oro"
030: * must not be used to endorse or promote products derived from this
031: * software without prior written permission. For written
032: * permission, please contact apache@apache.org.
033: *
034: * 5. Products derived from this software may not be called "Apache"
035: * or "Jakarta-Oro", nor may "Apache" or "Jakarta-Oro" appear in their
036: * name, without prior written permission of the Apache Software Foundation.
037: *
038: * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
039: * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
040: * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
041: * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
042: * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
043: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
044: * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
045: * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
046: * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
047: * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
048: * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
049: * SUCH DAMAGE.
050: * ====================================================================
051: *
052: * This software consists of voluntary contributions made by many
053: * individuals on behalf of the Apache Software Foundation. For more
054: * information on the Apache Software Foundation, please see
055: * <http://www.apache.org/>.
056: */
057:
058: package org.apache.oro.util;
059:
060: import java.util.*;
061:
062: /**
063: * This class is a GenericCache subclass implementing an LRU
064: * (Least Recently Used) cache replacement policy. In other words,
065: * values are added to the cache until it becomes full. Once the
066: * cache is full, when a new value is added to the cache, it replaces
067: * the least recently used value currently in the cache. This is probably
068: * the best general purpose cache replacement policy.
069: *
070: * @version @version@
071: * @since 1.0
072: * @see GenericCache
073: */
074: public final class CacheLRU extends GenericCache {
075: private int __head = 0, __tail = 0;
076: private int[] __next, __prev;
077:
078: /**
079: * Creates a CacheLRU instance with a given cache capacity.
080: * <p>
081: * @param capacity The capacity of the cache.
082: */
083: public CacheLRU(int capacity) {
084: super (capacity);
085:
086: int i;
087:
088: __next = new int[_cache.length];
089: __prev = new int[_cache.length];
090:
091: for (i = 0; i < __next.length; i++)
092: __next[i] = __prev[i] = -1;
093: }
094:
095: /**
096: * Same as:
097: * <blockquote><pre>
098: * CacheLRU(GenericCache.DEFAULT_CAPACITY);
099: * </pre></blockquote>
100: */
101: public CacheLRU() {
102: this (GenericCache.DEFAULT_CAPACITY);
103: }
104:
105: private void __moveToFront(int index) {
106: int next, prev;
107:
108: if (__head != index) {
109: next = __next[index];
110: prev = __prev[index];
111:
112: // Only the head has a prev entry that is an invalid index so
113: // we don't check.
114: __next[prev] = next;
115:
116: // Make sure index is valid. If it isn't, we're at the tail
117: // and don't set __prev[next].
118: if (next >= 0)
119: __prev[next] = prev;
120: else
121: __tail = prev;
122:
123: __prev[index] = -1;
124: __next[index] = __head;
125: __prev[__head] = index;
126: __head = index;
127: }
128: }
129:
130: public synchronized Object getElement(Object key) {
131: Object obj;
132:
133: obj = _table.get(key);
134:
135: if (obj != null) {
136: GenericCacheEntry entry;
137:
138: entry = (GenericCacheEntry) obj;
139: // Maintain LRU property
140: __moveToFront(entry._index);
141:
142: return entry._value;
143: }
144:
145: return null;
146: }
147:
148: /**
149: * Adds a value to the cache. If the cache is full, when a new value
150: * is added to the cache, it replaces the least recently used value
151: * in the cache (i.e., LRU).
152: * <p>
153: * @param key The key referencing the value added to the cache.
154: * @param value The value to add to the cache.
155: */
156: public final synchronized void addElement(Object key, Object value) {
157: Object obj;
158:
159: obj = _table.get(key);
160:
161: if (obj != null) {
162: GenericCacheEntry entry;
163:
164: // Just replace the value, but move it to the front.
165: entry = (GenericCacheEntry) obj;
166: entry._value = value;
167: entry._key = key;
168:
169: __moveToFront(entry._index);
170:
171: return;
172: }
173:
174: // If we haven't filled the cache yet, place in next available spot
175: // and move to front.
176: if (!isFull()) {
177: if (_numEntries > 0) {
178: __prev[_numEntries] = __tail;
179: __next[_numEntries] = -1;
180: __moveToFront(_numEntries);
181: }
182: ++_numEntries;
183: } else {
184: // We replace the tail of the list.
185: _table.remove(_cache[__tail]._key);
186: __moveToFront(__tail);
187: }
188:
189: _cache[__head]._value = value;
190: _cache[__head]._key = key;
191: _table.put(key, _cache[__head]);
192: }
193: }
|