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();
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 }
|
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();
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 }
|