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