1 /*
2 * Copyright (c) 1995, 2014, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package sun.misc;
27
28 import java.util.Dictionary;
29 import java.util.Enumeration;
30 import java.util.NoSuchElementException;
31
32 /**
33 * Caches the collision list.
34 */
35 class CacheEntry extends Ref {
36 int hash;
37 Object key;
38 CacheEntry next;
39 public Object reconstitute() {
40 return null;
41 }
42 }
43
44 /**
45 * The Cache class. Maps keys to values. Any object can be used as
46 * a key and/or value. This is very similar to the Hashtable
47 * class, except that after putting an object into the Cache,
48 * it is not guaranteed that a subsequent get will return it.
49 * The Cache will automatically remove entries if memory is
50 * getting tight and if the entry is not referenced from outside
51 * the Cache.<p>
52 *
53 * To sucessfully store and retrieve objects from a hash table the
54 * object used as the key must implement the hashCode() and equals()
55 * methods.<p>
56 *
57 * This example creates a Cache of numbers. It uses the names of
58 * the numbers as keys:
59 * <pre>
60 * Cache numbers = new Cache();
61 * numbers.put("one", new Integer(1));
62 * numbers.put("two", new Integer(1));
63 * numbers.put("three", new Integer(1));
64 * </pre>
65 * To retrieve a number use:
66 * <pre>
67 * Integer n = (Integer)numbers.get("two");
68 * if (n != null) {
69 * System.out.println("two = " + n);
70 * }
71 * </pre>
72 *
73 * @see java.lang.Object#hashCode
74 * @see java.lang.Object#equals
75 * @see sun.misc.Ref
76 * @deprecated Consider {@link java.util.LinkedHashMap} for LRU caches.
77 */
78 @Deprecated
79 public
80 class Cache extends Dictionary<Object, Object> {
81 /**
82 * The hash table data.
83 */
84 private CacheEntry table[];
85
86 /**
87 * The total number of entries in the hash table.
88 */
89 private int count;
90
91 /**
92 * Rehashes the table when count exceeds this threshold.
93 */
94 private int threshold;
95
96 /**
97 * The load factor for the hashtable.
98 */
99 private float loadFactor;
100
101 private void init(int initialCapacity, float loadFactor) {
102 if ((initialCapacity <= 0) || (loadFactor <= 0.0)) {
103 throw new IllegalArgumentException();
104 }
105 this.loadFactor = loadFactor;
106 table = new CacheEntry[initialCapacity];
107 threshold = (int) (initialCapacity * loadFactor);
108 }
109
110 /**
111 * Constructs a new, empty Cache with the specified initial
112 * capacity and the specified load factor.
113 * @param initialCapacity the initial number of buckets
114 * @param loadFactor a number between 0.0 and 1.0, it defines
115 * the threshold for rehashing the Cache into
116 * a bigger one.
117 * @exception IllegalArgumentException If the initial capacity
118 * is less than or equal to zero.
119 * @exception IllegalArgumentException If the load factor is
120 * less than or equal to zero.
121 */
122 public Cache (int initialCapacity, float loadFactor) {
123 init(initialCapacity, loadFactor);
124 }
125
126 /**
127 * Constructs a new, empty Cache with the specified initial
128 * capacity.
129 * @param initialCapacity the initial number of buckets
130 */
131 public Cache (int initialCapacity) {
132 init(initialCapacity, 0.75f);
133 }
134
135 /**
136 * Constructs a new, empty Cache. A default capacity and load factor
137 * is used. Note that the Cache will automatically grow when it gets
138 * full.
139 */
140 public Cache () {
141 try {
142 init(101, 0.75f);
143 } catch (IllegalArgumentException ex) {
144 // This should never happen
145 throw new Error("panic");
146 }
147 }
148
149 /**
150 * Returns the number of elements contained within the Cache.
151 */
152 public int size() {
153 return count;
154 }
155
156 /**
157 * Returns true if the Cache contains no elements.
158 */
159 public boolean isEmpty() {
160 return count == 0;
161 }
162
163 /**
164 * Returns an enumeration of the Cache's keys.
165 * @see Cache#elements
166 * @see Enumeration
167 */
168 public synchronized Enumeration<Object> keys() {
169 return new CacheEnumerator(table, true);
170 }
171
172 /**
173 * Returns an enumeration of the elements. Use the Enumeration methods
174 * on the returned object to fetch the elements sequentially.
175 * @see Cache#keys
176 * @see Enumeration
177 */
178 public synchronized Enumeration<Object> elements() {
179 return new CacheEnumerator(table, false);
180 }
181
182 /**
183 * Gets the object associated with the specified key in the Cache.
184 * @param key the key in the hash table
185 * @returns the element for the key or null if the key
186 * is not defined in the hash table.
187 * @see Cache#put
188 */
189 public synchronized Object get(Object key) {
190 CacheEntry tab[] = table;
191 int hash = key.hashCode();
192 int index = (hash & 0x7FFFFFFF) % tab.length;
193 for (CacheEntry e = tab[index]; e != null; e = e.next) {
194 if ((e.hash == hash) && e.key.equals(key)) {
195 return e.check();
196 }
197 }
198 return null;
199 }
200
201 /**
202 * Rehashes the contents of the table into a bigger table.
203 * This is method is called automatically when the Cache's
204 * size exceeds the threshold.
205 */
206 protected void rehash() {
207 int oldCapacity = table.length;
208 CacheEntry oldTable[] = table;
209
210 int newCapacity = oldCapacity * 2 + 1;
211 CacheEntry newTable[] = new CacheEntry[newCapacity];
212
213 threshold = (int) (newCapacity * loadFactor);
214 table = newTable;
215
216 // System.out.println("rehash old=" + oldCapacity + ", new=" +
217 // newCapacity + ", thresh=" + threshold + ", count=" + count);
218
219 for (int i = oldCapacity; i-- > 0;) {
220 for (CacheEntry old = oldTable[i]; old != null;) {
221 CacheEntry e = old;
222 old = old.next;
223 if (e.check() != null) {
224 int index = (e.hash & 0x7FFFFFFF) % newCapacity;
225 e.next = newTable[index];
226 newTable[index] = e;
227 } else
228 count--; /* remove entries that have disappeared */
229 }
230 }
231 }
232
233 /**
234 * Puts the specified element into the Cache, using the specified
235 * key. The element may be retrieved by doing a get() with the same
236 * key. The key and the element cannot be null.
237 * @param key the specified hashtable key
238 * @param value the specified element
239 * @return the old value of the key, or null if it did not have one.
240 * @exception NullPointerException If the value of the specified
241 * element is null.
242 * @see Cache#get
243 */
244 public synchronized Object put(Object key, Object value) {
245 // Make sure the value is not null
246 if (value == null) {
247 throw new NullPointerException();
248 }
249 // Makes sure the key is not already in the cache.
250 CacheEntry tab[] = table;
251 int hash = key.hashCode();
252 int index = (hash & 0x7FFFFFFF) % tab.length;
253 CacheEntry ne = null;
254 for (CacheEntry e = tab[index]; e != null; e = e.next) {
255 if ((e.hash == hash) && e.key.equals(key)) {
256 Object old = e.check();
257 e.setThing(value);
258 return old;
259 } else if (e.check() == null)
260 ne = e; /* reuse old flushed value */
261 }
262
263 if (count >= threshold) {
264 // Rehash the table if the threshold is exceeded
265 rehash();
266 return put(key, value);
267 }
268 // Creates the new entry.
269 if (ne == null) {
270 ne = new CacheEntry ();
271 ne.next = tab[index];
272 tab[index] = ne;
273 count++;
274 }
275 ne.hash = hash;
276 ne.key = key;
277 ne.setThing(value);
278 return null;
279 }
280
281 /**
282 * Removes the element corresponding to the key. Does nothing if the
283 * key is not present.
284 * @param key the key that needs to be removed
285 * @return the value of key, or null if the key was not found.
286 */
287 public synchronized Object remove(Object key) {
288 CacheEntry tab[] = table;
289 int hash = key.hashCode();
290 int index = (hash & 0x7FFFFFFF) % tab.length;
291 for (CacheEntry e = tab[index], prev = null; e != null; prev = e, e = e.next) {
292 if ((e.hash == hash) && e.key.equals(key)) {
293 if (prev != null) {
294 prev.next = e.next;
295 } else {
296 tab[index] = e.next;
297 }
298 count--;
299 return e.check();
300 }
301 }
302 return null;
303 }
304 }
305
306 /**
307 * A Cache enumerator class. This class should remain opaque
308 * to the client. It will use the Enumeration interface.
309 */
310 class CacheEnumerator implements Enumeration<Object> {
311 boolean keys;
312 int index;
313 CacheEntry table[];
314 CacheEntry entry;
315
316 CacheEnumerator (CacheEntry table[], boolean keys) {
317 this.table = table;
318 this.keys = keys;
319 this.index = table.length;
320 }
321
322 public boolean hasMoreElements() {
323 while (index >= 0) {
324 while (entry != null)
325 if (entry.check() != null)
326 return true;
327 else
328 entry = entry.next;
329 while (--index >= 0 && (entry = table[index]) == null) ;
330 }
331 return false;
332 }
333
334 public Object nextElement() {
335 while (index >= 0) {
336 if (entry == null)
337 while (--index >= 0 && (entry = table[index]) == null) ;
338 if (entry != null) {
339 CacheEntry e = entry;
340 entry = e.next;
341 if (e.check() != null)
342 return keys ? e.key : e.check();
343 }
344 }
345 throw new NoSuchElementException("CacheEnumerator");
346 }
347
348 }