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