KickJava   Java API By Example, From Geeks To Geeks.

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


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 a second
64  * chance FIFO (First In First Out) cache replacement policy. In other
65  * words, values are added to the cache until the cache becomes full.
66  * Once the cache is full, when a new value is added to the cache, it
67  * replaces the first of the current values in the cache to have been
68  * added, unless that value has been used recently (generally
69  * between the last cache replacement and now).
70  * If the value to be replaced has been used, it is given
71  * a second chance, and the next value in the cache is tested for
72  * replacement in the same manner. If all the values are given a
73  * second chance, then the original pattern selected for replacement is
74  * replaced.
75  
76  @author <a HREF="dfs@savarese.org">Daniel F. Savarese</a>
77  @version $Id: CacheFIFO2.java,v 1.1.1.1 2000/07/23 23:08:54 jon Exp $
78
79  * @see GenericCache
80  */
81 public final class CacheFIFO2 extends GenericCache {
82   private int __current = 0;
83   private boolean[] __tryAgain;
84
85   /**
86    * Creates a CacheFIFO2 instance with a given cache capacity.
87    * <p>
88    * @param capacity The capacity of the cache.
89    */
90   public CacheFIFO2(int capacity) {
91     super(capacity);
92
93     __tryAgain = new boolean[_cache.length];
94   }
95
96
97   /**
98    * Same as:
99    * <blockquote><pre>
100    * CacheFIFO2(GenericCache.DEFAULT_CAPACITY);
101    * </pre></blockquote>
102    */
103   public CacheFIFO2(){
104     this(GenericCache.DEFAULT_CAPACITY);
105   }
106
107
108   public synchronized Object JavaDoc getElement(Object JavaDoc key) {
109     Object JavaDoc obj;
110
111     obj = _table.get(key);
112
113     if(obj != null) {
114       GenericCacheEntry entry;
115
116       entry = (GenericCacheEntry)obj;
117
118       __tryAgain[entry._index] = true;
119       return entry._value;
120     }
121
122     return null;
123   }
124
125
126   /**
127    * Adds a value to the cache. If the cache is full, when a new value
128    * is added to the cache, it replaces the first of the current values
129    * in the cache to have been added (i.e., FIFO2).
130    * <p>
131    * @param key The key referencing the value added to the cache.
132    * @param value The value to add to the cache.
133    */
134   public final synchronized void addElement(Object JavaDoc key, Object JavaDoc value) {
135     int index;
136     Object JavaDoc obj;
137
138     obj = _table.get(key);
139
140     if(obj != null) {
141       GenericCacheEntry entry;
142
143       // Just replace the value. Technically this upsets the FIFO2 ordering,
144 // but it's expedient.
145 entry = (GenericCacheEntry)obj;
146       entry._value = value;
147       entry._key = key;
148
149       // Set the try again value to compensate.
150 __tryAgain[entry._index] = true;
151
152       return;
153     }
154
155     // If we haven't filled the cache yet, put it at the end.
156 if(!isFull()) {
157       index = _numEntries;
158       ++_numEntries;
159     } else {
160       // Otherwise, find the next slot that doesn't have a second chance.
161 index = __current;
162       
163       while(__tryAgain[index]) {
164     __tryAgain[index] = false;
165     if(++index >= __tryAgain.length)
166       index = 0;
167       }
168
169       __current = index + 1;
170       if(__current >= _cache.length)
171     __current = 0;
172
173       _table.remove(_cache[index]._key);
174     }
175
176     _cache[index]._value = value;
177     _cache[index]._key = key;
178     _table.put(key, _cache[index]);
179   }
180
181 }
182
183
Popular Tags