001: /*
002: * $Id: CacheFIFO2.java,v 1.7 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 a second
064: * chance FIFO (First In First Out) cache replacement policy. In other
065: * words, values are added to the cache until the cache becomes full.
066: * Once the cache is full, when a new value is added to the cache, it
067: * replaces the first of the current values in the cache to have been
068: * added, unless that value has been used recently (generally
069: * between the last cache replacement and now).
070: * If the value to be replaced has been used, it is given
071: * a second chance, and the next value in the cache is tested for
072: * replacement in the same manner. If all the values are given a
073: * second chance, then the original pattern selected for replacement is
074: * replaced.
075: *
076: * @version @version@
077: * @since 1.0
078: * @see GenericCache
079: */
080: public final class CacheFIFO2 extends GenericCache {
081: private int __current = 0;
082: private boolean[] __tryAgain;
083:
084: /**
085: * Creates a CacheFIFO2 instance with a given cache capacity.
086: * <p>
087: * @param capacity The capacity of the cache.
088: */
089: public CacheFIFO2(int capacity) {
090: super (capacity);
091:
092: __tryAgain = new boolean[_cache.length];
093: }
094:
095: /**
096: * Same as:
097: * <blockquote><pre>
098: * CacheFIFO2(GenericCache.DEFAULT_CAPACITY);
099: * </pre></blockquote>
100: */
101: public CacheFIFO2() {
102: this (GenericCache.DEFAULT_CAPACITY);
103: }
104:
105: public synchronized Object getElement(Object key) {
106: Object obj;
107:
108: obj = _table.get(key);
109:
110: if (obj != null) {
111: GenericCacheEntry entry;
112:
113: entry = (GenericCacheEntry) obj;
114:
115: __tryAgain[entry._index] = true;
116: return entry._value;
117: }
118:
119: return null;
120: }
121:
122: /**
123: * Adds a value to the cache. If the cache is full, when a new value
124: * is added to the cache, it replaces the first of the current values
125: * in the cache to have been added (i.e., FIFO2).
126: * <p>
127: * @param key The key referencing the value added to the cache.
128: * @param value The value to add to the cache.
129: */
130: public final synchronized void addElement(Object key, Object value) {
131: int index;
132: Object obj;
133:
134: obj = _table.get(key);
135:
136: if (obj != null) {
137: GenericCacheEntry entry;
138:
139: // Just replace the value. Technically this upsets the FIFO2 ordering,
140: // but it's expedient.
141: entry = (GenericCacheEntry) obj;
142: entry._value = value;
143: entry._key = key;
144:
145: // Set the try again value to compensate.
146: __tryAgain[entry._index] = true;
147:
148: return;
149: }
150:
151: // If we haven't filled the cache yet, put it at the end.
152: if (!isFull()) {
153: index = _numEntries;
154: ++_numEntries;
155: } else {
156: // Otherwise, find the next slot that doesn't have a second chance.
157: index = __current;
158:
159: while (__tryAgain[index]) {
160: __tryAgain[index] = false;
161: if (++index >= __tryAgain.length)
162: index = 0;
163: }
164:
165: __current = index + 1;
166: if (__current >= _cache.length)
167: __current = 0;
168:
169: _table.remove(_cache[index]._key);
170: }
171:
172: _cache[index]._value = value;
173: _cache[index]._key = key;
174: _table.put(key, _cache[index]);
175: }
176:
177: }
|