Wed, 22 Jan 2014 12:37:28 -0800
Added tag jdk8u5-b05 for changeset b90de55aca30
kvn@1334 | 1 | /* |
kvn@1334 | 2 | * Copyright 2009 Goldman Sachs International. All Rights Reserved. |
kvn@1334 | 3 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
kvn@1334 | 4 | * |
kvn@1334 | 5 | * This code is free software; you can redistribute it and/or modify it |
kvn@1334 | 6 | * under the terms of the GNU General Public License version 2 only, as |
kvn@1334 | 7 | * published by the Free Software Foundation. |
kvn@1334 | 8 | * |
kvn@1334 | 9 | * This code is distributed in the hope that it will be useful, but WITHOUT |
kvn@1334 | 10 | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
kvn@1334 | 11 | * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
kvn@1334 | 12 | * version 2 for more details (a copy is included in the LICENSE file that |
kvn@1334 | 13 | * accompanied this code). |
kvn@1334 | 14 | * |
kvn@1334 | 15 | * You should have received a copy of the GNU General Public License version |
kvn@1334 | 16 | * 2 along with this work; if not, write to the Free Software Foundation, |
kvn@1334 | 17 | * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
kvn@1334 | 18 | * |
trims@1907 | 19 | * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
trims@1907 | 20 | * or visit www.oracle.com if you need additional information or have any |
trims@1907 | 21 | * questions. |
kvn@1334 | 22 | * |
kvn@1334 | 23 | */ |
kvn@1334 | 24 | |
kvn@1334 | 25 | /* |
kvn@1334 | 26 | * @test |
kvn@1334 | 27 | * @bug 6865031 |
kvn@1334 | 28 | * @summary Application gives bad result (throws bad exception) with compressed oops |
kvn@1391 | 29 | * @run main/othervm -XX:+IgnoreUnrecognizedVMOptions -XX:+UseCompressedOops -XX:HeapBaseMinAddress=32g -XX:-LoopUnswitching -XX:CompileCommand=inline,AbstractMemoryEfficientList.equals Test hello goodbye |
kvn@1334 | 30 | */ |
kvn@1334 | 31 | |
kvn@1334 | 32 | import java.lang.ref.ReferenceQueue; |
kvn@1334 | 33 | import java.lang.ref.WeakReference; |
kvn@1334 | 34 | import java.util.ArrayList; |
kvn@1334 | 35 | import java.util.Arrays; |
kvn@1334 | 36 | import java.util.List; |
kvn@1334 | 37 | |
kvn@1334 | 38 | interface MyList { |
kvn@1334 | 39 | public int size(); |
kvn@1334 | 40 | public Object set(final int index, final Object element); |
kvn@1334 | 41 | public Object get(final int index); |
kvn@1334 | 42 | } |
kvn@1334 | 43 | |
kvn@1334 | 44 | abstract class AbstractMemoryEfficientList implements MyList { |
kvn@1334 | 45 | abstract public int size(); |
kvn@1334 | 46 | abstract public Object get(final int index); |
kvn@1334 | 47 | abstract public Object set(final int index, final Object element); |
kvn@1334 | 48 | |
kvn@1334 | 49 | public boolean equals(Object o) { |
kvn@1334 | 50 | if (o == this) { |
kvn@1334 | 51 | return true; |
kvn@1334 | 52 | } |
kvn@1334 | 53 | |
kvn@1334 | 54 | if (!(o instanceof MyList)) { |
kvn@1334 | 55 | return false; |
kvn@1334 | 56 | } |
kvn@1334 | 57 | |
kvn@1334 | 58 | final MyList that = (MyList) o; |
kvn@1334 | 59 | if (this.size() != that.size()) { |
kvn@1334 | 60 | return false; |
kvn@1334 | 61 | } |
kvn@1334 | 62 | |
kvn@1334 | 63 | for (int i = 0; i < this.size(); i++) { |
kvn@1334 | 64 | try { |
kvn@1334 | 65 | if (!((this.get(i)).equals(that.get(i)))) { |
kvn@1334 | 66 | return false; |
kvn@1334 | 67 | } |
kvn@1334 | 68 | } catch (IndexOutOfBoundsException e) { |
kvn@1334 | 69 | System.out.println("THROWING RT EXC"); |
kvn@1334 | 70 | System.out.println("concurrent modification of this:" + this.getClass() + ":" + System.identityHashCode(this) + "; that:" + that.getClass() + ":" + System.identityHashCode(that) + "; i:" + i); |
kvn@1334 | 71 | e.printStackTrace(); |
kvn@1334 | 72 | System.exit(97); |
kvn@1334 | 73 | throw new RuntimeException("concurrent modification of this:" + this.getClass() + ":" + System.identityHashCode(this) + "; that:" + that.getClass() + ":" + System.identityHashCode(that) + "; i:" + i, e); |
kvn@1334 | 74 | } |
kvn@1334 | 75 | } |
kvn@1334 | 76 | return true; |
kvn@1334 | 77 | } |
kvn@1334 | 78 | |
kvn@1334 | 79 | public int hashCode() { |
kvn@1334 | 80 | int hashCode = 1; |
kvn@1334 | 81 | for (int i = 0; i < this.size(); i++) { |
kvn@1334 | 82 | Object obj = this.get(i); |
kvn@1334 | 83 | hashCode = 31 * hashCode + (obj == null ? 0 : obj.hashCode()); |
kvn@1334 | 84 | } |
kvn@1334 | 85 | return hashCode; |
kvn@1334 | 86 | } |
kvn@1334 | 87 | } |
kvn@1334 | 88 | |
kvn@1334 | 89 | final class SingletonList extends AbstractMemoryEfficientList { |
kvn@1334 | 90 | private Object element1; |
kvn@1334 | 91 | |
kvn@1334 | 92 | SingletonList(final Object obj1) { |
kvn@1334 | 93 | super(); |
kvn@1334 | 94 | this.element1 = obj1; |
kvn@1334 | 95 | } |
kvn@1334 | 96 | |
kvn@1334 | 97 | public int size() { |
kvn@1334 | 98 | return 1; |
kvn@1334 | 99 | } |
kvn@1334 | 100 | |
kvn@1334 | 101 | public Object get(final int index) { |
kvn@1334 | 102 | if (index == 0) { |
kvn@1334 | 103 | return this.element1; |
kvn@1334 | 104 | } else { |
kvn@1334 | 105 | throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + this.size()); |
kvn@1334 | 106 | } |
kvn@1334 | 107 | } |
kvn@1334 | 108 | |
kvn@1334 | 109 | public Object set(final int index, final Object element) { |
kvn@1334 | 110 | if (index == 0) { |
kvn@1334 | 111 | final Object previousElement = this.element1; |
kvn@1334 | 112 | this.element1 = element; |
kvn@1334 | 113 | return previousElement; |
kvn@1334 | 114 | } else { |
kvn@1334 | 115 | throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + this.size()); |
kvn@1334 | 116 | } |
kvn@1334 | 117 | } |
kvn@1334 | 118 | } |
kvn@1334 | 119 | |
kvn@1334 | 120 | final class DoubletonList extends AbstractMemoryEfficientList { |
kvn@1334 | 121 | private Object element1; |
kvn@1334 | 122 | private Object element2; |
kvn@1334 | 123 | |
kvn@1334 | 124 | DoubletonList(final Object obj1, final Object obj2) { |
kvn@1334 | 125 | this.element1 = obj1; |
kvn@1334 | 126 | this.element2 = obj2; |
kvn@1334 | 127 | } |
kvn@1334 | 128 | |
kvn@1334 | 129 | public int size() { |
kvn@1334 | 130 | return 2; |
kvn@1334 | 131 | } |
kvn@1334 | 132 | |
kvn@1334 | 133 | public Object get(final int index) { |
kvn@1334 | 134 | switch (index) { |
kvn@1334 | 135 | case 0 : return this.element1; |
kvn@1334 | 136 | case 1 : return this.element2; |
kvn@1334 | 137 | default: throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + this.size()); |
kvn@1334 | 138 | } |
kvn@1334 | 139 | } |
kvn@1334 | 140 | |
kvn@1334 | 141 | public Object set(final int index, final Object element) { |
kvn@1334 | 142 | switch (index) { |
kvn@1334 | 143 | case 0 : |
kvn@1334 | 144 | { |
kvn@1334 | 145 | final Object previousElement = this.element1; |
kvn@1334 | 146 | this.element1 = element; |
kvn@1334 | 147 | return previousElement; |
kvn@1334 | 148 | } |
kvn@1334 | 149 | case 1 : |
kvn@1334 | 150 | { |
kvn@1334 | 151 | final Object previousElement = this.element2; |
kvn@1334 | 152 | this.element2 = element; |
kvn@1334 | 153 | return previousElement; |
kvn@1334 | 154 | } |
kvn@1334 | 155 | default : throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + this.size()); |
kvn@1334 | 156 | } |
kvn@1334 | 157 | } |
kvn@1334 | 158 | } |
kvn@1334 | 159 | |
kvn@1334 | 160 | class WeakPool<V> { |
kvn@1334 | 161 | protected static final int DEFAULT_INITIAL_CAPACITY = 16; |
kvn@1334 | 162 | private static final int MAXIMUM_CAPACITY = 1 << 30; |
kvn@1334 | 163 | private static final float DEFAULT_LOAD_FACTOR = 0.75f; |
kvn@1334 | 164 | |
kvn@1334 | 165 | protected Entry<V>[] table; |
kvn@1334 | 166 | |
kvn@1334 | 167 | private int size; |
kvn@1334 | 168 | protected int threshold; |
kvn@1334 | 169 | private final float loadFactor; |
kvn@1334 | 170 | private final ReferenceQueue<V> queue = new ReferenceQueue<V>(); |
kvn@1334 | 171 | |
kvn@1334 | 172 | public WeakPool() |
kvn@1334 | 173 | { |
kvn@1334 | 174 | this.loadFactor = DEFAULT_LOAD_FACTOR; |
kvn@1334 | 175 | threshold = DEFAULT_INITIAL_CAPACITY; |
kvn@1334 | 176 | table = new Entry[DEFAULT_INITIAL_CAPACITY]; |
kvn@1334 | 177 | } |
kvn@1334 | 178 | |
kvn@1334 | 179 | /** |
kvn@1334 | 180 | * Check for equality of non-null reference x and possibly-null y. By |
kvn@1334 | 181 | * default uses Object.equals. |
kvn@1334 | 182 | */ |
kvn@1334 | 183 | private boolean eq(Object x, Object y) |
kvn@1334 | 184 | { |
kvn@1334 | 185 | return x == y || x.equals(y); |
kvn@1334 | 186 | } |
kvn@1334 | 187 | |
kvn@1334 | 188 | /** |
kvn@1334 | 189 | * Return index for hash code h. |
kvn@1334 | 190 | */ |
kvn@1334 | 191 | private int indexFor(int h, int length) |
kvn@1334 | 192 | { |
kvn@1334 | 193 | return h & length - 1; |
kvn@1334 | 194 | } |
kvn@1334 | 195 | |
kvn@1334 | 196 | /** |
kvn@1334 | 197 | * Expunge stale entries from the table. |
kvn@1334 | 198 | */ |
kvn@1334 | 199 | private void expungeStaleEntries() |
kvn@1334 | 200 | { |
kvn@1334 | 201 | Object r; |
kvn@1334 | 202 | while ((r = queue.poll()) != null) |
kvn@1334 | 203 | { |
kvn@1334 | 204 | Entry e = (Entry) r; |
kvn@1334 | 205 | int h = e.hash; |
kvn@1334 | 206 | int i = indexFor(h, table.length); |
kvn@1334 | 207 | |
kvn@1334 | 208 | // System.out.println("EXPUNGING " + h); |
kvn@1334 | 209 | Entry<V> prev = table[i]; |
kvn@1334 | 210 | Entry<V> p = prev; |
kvn@1334 | 211 | while (p != null) |
kvn@1334 | 212 | { |
kvn@1334 | 213 | Entry<V> next = p.next; |
kvn@1334 | 214 | if (p == e) |
kvn@1334 | 215 | { |
kvn@1334 | 216 | if (prev == e) |
kvn@1334 | 217 | { |
kvn@1334 | 218 | table[i] = next; |
kvn@1334 | 219 | } |
kvn@1334 | 220 | else |
kvn@1334 | 221 | { |
kvn@1334 | 222 | prev.next = next; |
kvn@1334 | 223 | } |
kvn@1334 | 224 | e.next = null; // Help GC |
kvn@1334 | 225 | size--; |
kvn@1334 | 226 | break; |
kvn@1334 | 227 | } |
kvn@1334 | 228 | prev = p; |
kvn@1334 | 229 | p = next; |
kvn@1334 | 230 | } |
kvn@1334 | 231 | } |
kvn@1334 | 232 | } |
kvn@1334 | 233 | |
kvn@1334 | 234 | /** |
kvn@1334 | 235 | * Return the table after first expunging stale entries |
kvn@1334 | 236 | */ |
kvn@1334 | 237 | private Entry<V>[] getTable() |
kvn@1334 | 238 | { |
kvn@1334 | 239 | expungeStaleEntries(); |
kvn@1334 | 240 | return table; |
kvn@1334 | 241 | } |
kvn@1334 | 242 | |
kvn@1334 | 243 | /** |
kvn@1334 | 244 | * Returns the number of key-value mappings in this map. |
kvn@1334 | 245 | * This result is a snapshot, and may not reflect unprocessed |
kvn@1334 | 246 | * entries that will be removed before next attempted access |
kvn@1334 | 247 | * because they are no longer referenced. |
kvn@1334 | 248 | */ |
kvn@1334 | 249 | public int size() |
kvn@1334 | 250 | { |
kvn@1334 | 251 | if (size == 0) |
kvn@1334 | 252 | { |
kvn@1334 | 253 | return 0; |
kvn@1334 | 254 | } |
kvn@1334 | 255 | expungeStaleEntries(); |
kvn@1334 | 256 | return size; |
kvn@1334 | 257 | } |
kvn@1334 | 258 | |
kvn@1334 | 259 | /** |
kvn@1334 | 260 | * Returns <tt>true</tt> if this map contains no key-value mappings. |
kvn@1334 | 261 | * This result is a snapshot, and may not reflect unprocessed |
kvn@1334 | 262 | * entries that will be removed before next attempted access |
kvn@1334 | 263 | * because they are no longer referenced. |
kvn@1334 | 264 | */ |
kvn@1334 | 265 | public boolean isEmpty() |
kvn@1334 | 266 | { |
kvn@1334 | 267 | return size() == 0; |
kvn@1334 | 268 | } |
kvn@1334 | 269 | |
kvn@1334 | 270 | /** |
kvn@1334 | 271 | * Returns the value stored in the pool that equals the requested key |
kvn@1334 | 272 | * or <tt>null</tt> if the map contains no mapping for |
kvn@1334 | 273 | * this key (or the key is null) |
kvn@1334 | 274 | * |
kvn@1334 | 275 | * @param key the key whose equals value is to be returned. |
kvn@1334 | 276 | * @return the object that is equal the specified key, or |
kvn@1334 | 277 | * <tt>null</tt> if key is null or no object in the pool equals the key. |
kvn@1334 | 278 | */ |
kvn@1334 | 279 | public V get(V key) |
kvn@1334 | 280 | { |
kvn@1334 | 281 | if (key == null) |
kvn@1334 | 282 | { |
kvn@1334 | 283 | return null; |
kvn@1334 | 284 | } |
kvn@1334 | 285 | int h = key.hashCode(); |
kvn@1334 | 286 | Entry<V>[] tab = getTable(); |
kvn@1334 | 287 | int index = indexFor(h, tab.length); |
kvn@1334 | 288 | Entry<V> e = tab[index]; |
kvn@1334 | 289 | while (e != null) |
kvn@1334 | 290 | { |
kvn@1334 | 291 | V candidate = e.get(); |
kvn@1334 | 292 | if (e.hash == h && eq(key, candidate)) |
kvn@1334 | 293 | { |
kvn@1334 | 294 | return candidate; |
kvn@1334 | 295 | } |
kvn@1334 | 296 | e = e.next; |
kvn@1334 | 297 | } |
kvn@1334 | 298 | return null; |
kvn@1334 | 299 | } |
kvn@1334 | 300 | |
kvn@1334 | 301 | /** |
kvn@1334 | 302 | * Returns the entry associated with the specified key in the HashMap. |
kvn@1334 | 303 | * Returns null if the HashMap contains no mapping for this key. |
kvn@1334 | 304 | */ |
kvn@1334 | 305 | Entry getEntry(Object key) |
kvn@1334 | 306 | { |
kvn@1334 | 307 | int h = key.hashCode(); |
kvn@1334 | 308 | Entry[] tab = getTable(); |
kvn@1334 | 309 | int index = indexFor(h, tab.length); |
kvn@1334 | 310 | Entry e = tab[index]; |
kvn@1334 | 311 | while (e != null && !(e.hash == h && eq(key, e.get()))) |
kvn@1334 | 312 | { |
kvn@1334 | 313 | e = e.next; |
kvn@1334 | 314 | } |
kvn@1334 | 315 | return e; |
kvn@1334 | 316 | } |
kvn@1334 | 317 | |
kvn@1334 | 318 | /** |
kvn@1334 | 319 | * Places the object into the pool. If the object is null, nothing happens. |
kvn@1334 | 320 | * If an equal object already exists, it is not replaced. |
kvn@1334 | 321 | * |
kvn@1334 | 322 | * @param key the object to put into the pool. key may be null. |
kvn@1334 | 323 | * @return the object in the pool that is equal to the key, or the newly placed key if no such object existed when put was called |
kvn@1334 | 324 | */ |
kvn@1334 | 325 | public V put(V key) |
kvn@1334 | 326 | { |
kvn@1334 | 327 | if (key == null) |
kvn@1334 | 328 | { |
kvn@1334 | 329 | return null; |
kvn@1334 | 330 | } |
kvn@1334 | 331 | int h = key.hashCode(); |
kvn@1334 | 332 | Entry<V>[] tab = getTable(); |
kvn@1334 | 333 | int i = indexFor(h, tab.length); |
kvn@1334 | 334 | |
kvn@1334 | 335 | for (Entry<V> e = tab[i]; e != null; e = e.next) |
kvn@1334 | 336 | { |
kvn@1334 | 337 | V candidate = e.get(); |
kvn@1334 | 338 | if (h == e.hash && eq(key, candidate)) |
kvn@1334 | 339 | { |
kvn@1334 | 340 | return candidate; |
kvn@1334 | 341 | } |
kvn@1334 | 342 | } |
kvn@1334 | 343 | |
kvn@1334 | 344 | tab[i] = new Entry<V>(key, queue, h, tab[i]); |
kvn@1334 | 345 | |
kvn@1334 | 346 | if (++size >= threshold) |
kvn@1334 | 347 | { |
kvn@1334 | 348 | resize(tab.length * 2); |
kvn@1334 | 349 | } |
kvn@1334 | 350 | |
kvn@1334 | 351 | // System.out.println("Added " + key + " to pool"); |
kvn@1334 | 352 | return key; |
kvn@1334 | 353 | } |
kvn@1334 | 354 | |
kvn@1334 | 355 | /** |
kvn@1334 | 356 | * Rehashes the contents of this map into a new array with a |
kvn@1334 | 357 | * larger capacity. This method is called automatically when the |
kvn@1334 | 358 | * number of keys in this map reaches its threshold. |
kvn@1334 | 359 | * <p/> |
kvn@1334 | 360 | * If current capacity is MAXIMUM_CAPACITY, this method does not |
kvn@1334 | 361 | * resize the map, but but sets threshold to Integer.MAX_VALUE. |
kvn@1334 | 362 | * This has the effect of preventing future calls. |
kvn@1334 | 363 | * |
kvn@1334 | 364 | * @param newCapacity the new capacity, MUST be a power of two; |
kvn@1334 | 365 | * must be greater than current capacity unless current |
kvn@1334 | 366 | * capacity is MAXIMUM_CAPACITY (in which case value |
kvn@1334 | 367 | * is irrelevant). |
kvn@1334 | 368 | */ |
kvn@1334 | 369 | void resize(int newCapacity) |
kvn@1334 | 370 | { |
kvn@1334 | 371 | Entry<V>[] oldTable = getTable(); |
kvn@1334 | 372 | int oldCapacity = oldTable.length; |
kvn@1334 | 373 | if (oldCapacity == MAXIMUM_CAPACITY) |
kvn@1334 | 374 | { |
kvn@1334 | 375 | threshold = Integer.MAX_VALUE; |
kvn@1334 | 376 | return; |
kvn@1334 | 377 | } |
kvn@1334 | 378 | |
kvn@1334 | 379 | Entry<V>[] newTable = new Entry[newCapacity]; |
kvn@1334 | 380 | transfer(oldTable, newTable); |
kvn@1334 | 381 | table = newTable; |
kvn@1334 | 382 | |
kvn@1334 | 383 | /* |
kvn@1334 | 384 | * If ignoring null elements and processing ref queue caused massive |
kvn@1334 | 385 | * shrinkage, then restore old table. This should be rare, but avoids |
kvn@1334 | 386 | * unbounded expansion of garbage-filled tables. |
kvn@1334 | 387 | */ |
kvn@1334 | 388 | if (size >= threshold / 2) |
kvn@1334 | 389 | { |
kvn@1334 | 390 | threshold = (int) (newCapacity * loadFactor); |
kvn@1334 | 391 | } |
kvn@1334 | 392 | else |
kvn@1334 | 393 | { |
kvn@1334 | 394 | expungeStaleEntries(); |
kvn@1334 | 395 | transfer(newTable, oldTable); |
kvn@1334 | 396 | table = oldTable; |
kvn@1334 | 397 | } |
kvn@1334 | 398 | } |
kvn@1334 | 399 | |
kvn@1334 | 400 | /** |
kvn@1334 | 401 | * Transfer all entries from src to dest tables |
kvn@1334 | 402 | */ |
kvn@1334 | 403 | private void transfer(Entry[] src, Entry[] dest) |
kvn@1334 | 404 | { |
kvn@1334 | 405 | for (int j = 0; j < src.length; ++j) |
kvn@1334 | 406 | { |
kvn@1334 | 407 | Entry e = src[j]; |
kvn@1334 | 408 | src[j] = null; |
kvn@1334 | 409 | while (e != null) |
kvn@1334 | 410 | { |
kvn@1334 | 411 | Entry next = e.next; |
kvn@1334 | 412 | Object key = e.get(); |
kvn@1334 | 413 | if (key == null) |
kvn@1334 | 414 | { |
kvn@1334 | 415 | e.next = null; // Help GC |
kvn@1334 | 416 | size--; |
kvn@1334 | 417 | } |
kvn@1334 | 418 | else |
kvn@1334 | 419 | { |
kvn@1334 | 420 | int i = indexFor(e.hash, dest.length); |
kvn@1334 | 421 | e.next = dest[i]; |
kvn@1334 | 422 | dest[i] = e; |
kvn@1334 | 423 | } |
kvn@1334 | 424 | e = next; |
kvn@1334 | 425 | } |
kvn@1334 | 426 | } |
kvn@1334 | 427 | } |
kvn@1334 | 428 | |
kvn@1334 | 429 | /** |
kvn@1334 | 430 | * Removes the object in the pool that equals the key. |
kvn@1334 | 431 | * |
kvn@1334 | 432 | * @param key |
kvn@1334 | 433 | * @return previous value associated with specified key, or <tt>null</tt> |
kvn@1334 | 434 | * if there was no mapping for key or the key is null. |
kvn@1334 | 435 | */ |
kvn@1334 | 436 | public V removeFromPool(V key) |
kvn@1334 | 437 | { |
kvn@1334 | 438 | if (key == null) |
kvn@1334 | 439 | { |
kvn@1334 | 440 | return null; |
kvn@1334 | 441 | } |
kvn@1334 | 442 | int h = key.hashCode(); |
kvn@1334 | 443 | Entry<V>[] tab = getTable(); |
kvn@1334 | 444 | int i = indexFor(h, tab.length); |
kvn@1334 | 445 | Entry<V> prev = tab[i]; |
kvn@1334 | 446 | Entry<V> e = prev; |
kvn@1334 | 447 | |
kvn@1334 | 448 | while (e != null) |
kvn@1334 | 449 | { |
kvn@1334 | 450 | Entry<V> next = e.next; |
kvn@1334 | 451 | V candidate = e.get(); |
kvn@1334 | 452 | if (h == e.hash && eq(key, candidate)) |
kvn@1334 | 453 | { |
kvn@1334 | 454 | size--; |
kvn@1334 | 455 | if (prev == e) |
kvn@1334 | 456 | { |
kvn@1334 | 457 | tab[i] = next; |
kvn@1334 | 458 | } |
kvn@1334 | 459 | else |
kvn@1334 | 460 | { |
kvn@1334 | 461 | prev.next = next; |
kvn@1334 | 462 | } |
kvn@1334 | 463 | return candidate; |
kvn@1334 | 464 | } |
kvn@1334 | 465 | prev = e; |
kvn@1334 | 466 | e = next; |
kvn@1334 | 467 | } |
kvn@1334 | 468 | |
kvn@1334 | 469 | return null; |
kvn@1334 | 470 | } |
kvn@1334 | 471 | |
kvn@1334 | 472 | /** |
kvn@1334 | 473 | * Removes all mappings from this map. |
kvn@1334 | 474 | */ |
kvn@1334 | 475 | public void clear() |
kvn@1334 | 476 | { |
kvn@1334 | 477 | // clear out ref queue. We don't need to expunge entries |
kvn@1334 | 478 | // since table is getting cleared. |
kvn@1334 | 479 | while (queue.poll() != null) |
kvn@1334 | 480 | { |
kvn@1334 | 481 | // nop |
kvn@1334 | 482 | } |
kvn@1334 | 483 | |
kvn@1334 | 484 | table = new Entry[DEFAULT_INITIAL_CAPACITY]; |
kvn@1334 | 485 | threshold = DEFAULT_INITIAL_CAPACITY; |
kvn@1334 | 486 | size = 0; |
kvn@1334 | 487 | |
kvn@1334 | 488 | // Allocation of array may have caused GC, which may have caused |
kvn@1334 | 489 | // additional entries to go stale. Removing these entries from the |
kvn@1334 | 490 | // reference queue will make them eligible for reclamation. |
kvn@1334 | 491 | while (queue.poll() != null) |
kvn@1334 | 492 | { |
kvn@1334 | 493 | // nop |
kvn@1334 | 494 | } |
kvn@1334 | 495 | } |
kvn@1334 | 496 | |
kvn@1334 | 497 | /** |
kvn@1334 | 498 | * The entries in this hash table extend WeakReference, using its main ref |
kvn@1334 | 499 | * field as the key. |
kvn@1334 | 500 | */ |
kvn@1334 | 501 | protected static class Entry<V> |
kvn@1334 | 502 | extends WeakReference<V> |
kvn@1334 | 503 | { |
kvn@1334 | 504 | private final int hash; |
kvn@1334 | 505 | private Entry<V> next; |
kvn@1334 | 506 | |
kvn@1334 | 507 | /** |
kvn@1334 | 508 | * Create new entry. |
kvn@1334 | 509 | */ |
kvn@1334 | 510 | Entry(final V key, final ReferenceQueue<V> queue, final int hash, final Entry<V> next) |
kvn@1334 | 511 | { |
kvn@1334 | 512 | super(key, queue); |
kvn@1334 | 513 | this.hash = hash; |
kvn@1334 | 514 | this.next = next; |
kvn@1334 | 515 | } |
kvn@1334 | 516 | |
kvn@1334 | 517 | public V getKey() |
kvn@1334 | 518 | { |
kvn@1334 | 519 | return super.get(); |
kvn@1334 | 520 | } |
kvn@1334 | 521 | |
kvn@1334 | 522 | public boolean equals(Object o) |
kvn@1334 | 523 | { |
kvn@1334 | 524 | if (!(o instanceof WeakPool.Entry)) |
kvn@1334 | 525 | { |
kvn@1334 | 526 | return false; |
kvn@1334 | 527 | } |
kvn@1334 | 528 | WeakPool.Entry<V> that = (WeakPool.Entry<V>) o; |
kvn@1334 | 529 | V k1 = this.getKey(); |
kvn@1334 | 530 | V k2 = that.getKey(); |
kvn@1334 | 531 | return (k1==k2 || k1.equals(k2)); |
kvn@1334 | 532 | } |
kvn@1334 | 533 | |
kvn@1334 | 534 | public int hashCode() |
kvn@1334 | 535 | { |
kvn@1334 | 536 | return this.hash; |
kvn@1334 | 537 | } |
kvn@1334 | 538 | |
kvn@1334 | 539 | public String toString() |
kvn@1334 | 540 | { |
kvn@1334 | 541 | return String.valueOf(this.getKey()); |
kvn@1334 | 542 | } |
kvn@1334 | 543 | } |
kvn@1334 | 544 | } |
kvn@1334 | 545 | |
kvn@1334 | 546 | final class MultiSynonymKey { |
kvn@1334 | 547 | private List<MyList> keys; |
kvn@1334 | 548 | |
kvn@1334 | 549 | public MultiSynonymKey() { |
kvn@1334 | 550 | keys = new ArrayList<MyList>(); |
kvn@1334 | 551 | } |
kvn@1334 | 552 | |
kvn@1334 | 553 | public MultiSynonymKey(MyList... arg) { |
kvn@1334 | 554 | keys = Arrays.asList(arg); |
kvn@1334 | 555 | } |
kvn@1334 | 556 | |
kvn@1334 | 557 | public List<MyList> getKeys() { |
kvn@1334 | 558 | return keys; |
kvn@1334 | 559 | } |
kvn@1334 | 560 | |
kvn@1334 | 561 | public int hashCode() { |
kvn@1334 | 562 | return this.getKeys().hashCode(); |
kvn@1334 | 563 | } |
kvn@1334 | 564 | |
kvn@1334 | 565 | public boolean equals(Object obj) { |
kvn@1334 | 566 | if (this == obj) { |
kvn@1334 | 567 | return true; |
kvn@1334 | 568 | } |
kvn@1334 | 569 | |
kvn@1334 | 570 | if (!(obj instanceof MultiSynonymKey)) { |
kvn@1334 | 571 | return false; |
kvn@1334 | 572 | } |
kvn@1334 | 573 | |
kvn@1334 | 574 | MultiSynonymKey that = (MultiSynonymKey) obj; |
kvn@1334 | 575 | return this.getKeys().equals(that.getKeys()); |
kvn@1334 | 576 | } |
kvn@1334 | 577 | |
kvn@1334 | 578 | public String toString() { |
kvn@1334 | 579 | return this.getClass().getName() + this.getKeys().toString(); |
kvn@1334 | 580 | } |
kvn@1334 | 581 | } |
kvn@1334 | 582 | |
kvn@1334 | 583 | public class Test extends Thread { |
kvn@1334 | 584 | static public Test test; |
kvn@1334 | 585 | static private byte[] arg1; |
kvn@1334 | 586 | static private byte[] arg2; |
kvn@1334 | 587 | static public WeakPool<MultiSynonymKey> wp; |
kvn@1334 | 588 | public volatile MultiSynonymKey ml1; |
kvn@1334 | 589 | public volatile MultiSynonymKey ml2; |
kvn@1334 | 590 | private volatile MultiSynonymKey ml3; |
kvn@1334 | 591 | |
kvn@1334 | 592 | public void run() { |
kvn@1334 | 593 | int count=0; |
kvn@1334 | 594 | while (true) { |
kvn@1334 | 595 | try { |
kvn@1334 | 596 | Thread.sleep(10); |
kvn@1334 | 597 | } catch (Exception e) {} |
kvn@1334 | 598 | synchronized (wp) { |
kvn@1334 | 599 | ml2 = new MultiSynonymKey(new DoubletonList(new String(arg1), new String(arg2))); |
kvn@1334 | 600 | wp.put(ml2); |
kvn@1334 | 601 | ml3 = new MultiSynonymKey(new DoubletonList(new String(arg1), new String(arg2))); |
kvn@1334 | 602 | } |
kvn@1334 | 603 | try { |
kvn@1334 | 604 | Thread.sleep(10); |
kvn@1334 | 605 | } catch (Exception e) {} |
kvn@1334 | 606 | synchronized (wp) { |
kvn@1334 | 607 | ml1 = new MultiSynonymKey(new SingletonList(new String(arg1))); |
kvn@1334 | 608 | wp.put(ml1); |
kvn@1334 | 609 | ml3 = new MultiSynonymKey(new SingletonList(new String(arg1))); |
kvn@1334 | 610 | } |
kvn@1334 | 611 | if (count++==100) |
kvn@1334 | 612 | System.exit(95); |
kvn@1334 | 613 | } |
kvn@1334 | 614 | } |
kvn@1334 | 615 | |
kvn@1334 | 616 | public static void main(String[] args) throws Exception { |
kvn@1334 | 617 | wp = new WeakPool<MultiSynonymKey>(); |
kvn@1334 | 618 | test = new Test(); |
kvn@1334 | 619 | |
kvn@1334 | 620 | test.arg1 = args[0].getBytes(); |
kvn@1334 | 621 | test.arg2 = args[1].getBytes(); |
kvn@1334 | 622 | |
kvn@1334 | 623 | test.ml1 = new MultiSynonymKey(new SingletonList(new String(test.arg1))); |
kvn@1334 | 624 | test.ml2 = new MultiSynonymKey(new DoubletonList(new String(test.arg1), new String(test.arg2))); |
kvn@1334 | 625 | test.ml3 = new MultiSynonymKey(new DoubletonList(new String(test.arg1), new String(test.arg2))); |
kvn@1334 | 626 | |
kvn@1334 | 627 | wp.put(test.ml1); |
kvn@1334 | 628 | wp.put(test.ml2); |
kvn@1334 | 629 | |
kvn@1334 | 630 | test.setDaemon(true); |
kvn@1334 | 631 | test.start(); |
kvn@1334 | 632 | |
kvn@1334 | 633 | int counter = 0; |
kvn@1334 | 634 | while (true) { |
kvn@1334 | 635 | synchronized (wp) { |
kvn@1334 | 636 | MultiSynonymKey foo = test.ml3; |
kvn@1334 | 637 | |
kvn@1334 | 638 | if (wp.put(foo) == foo) { |
kvn@1334 | 639 | // System.out.println("foo " + counter); |
kvn@1334 | 640 | // System.out.println(foo); |
kvn@1334 | 641 | } |
kvn@1334 | 642 | } |
kvn@1334 | 643 | counter++; |
kvn@1334 | 644 | } |
kvn@1334 | 645 | } |
kvn@1334 | 646 | |
kvn@1334 | 647 | private boolean eq(Object x, Object y) { |
kvn@1334 | 648 | return x == y || x.equals(y); |
kvn@1334 | 649 | } |
kvn@1334 | 650 | } |