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