88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore/*
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * Copyright 2009 Goldman Sachs International. All Rights Reserved.
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore *
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * This code is free software; you can redistribute it and/or modify it
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * under the terms of the GNU General Public License version 2 only, as
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * published by the Free Software Foundation.
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore *
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * This code is distributed in the hope that it will be useful, but WITHOUT
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * version 2 for more details (a copy is included in the LICENSE file that
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * accompanied this code).
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore *
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * You should have received a copy of the GNU General Public License version
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * 2 along with this work; if not, write to the Free Software Foundation,
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore *
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * or visit www.oracle.com if you need additional information or have any
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * questions.
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore *
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore */
a33ad26ef1f3b7a3fcf2fad564e6bd3798fdcbaeZhao Edgar Liu - Sun Microsystems
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore/*
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * @test
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * @bug 6865031
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * @summary Application gives bad result (throws bad exception) with compressed oops
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * @run main/othervm -XX:+IgnoreUnrecognizedVMOptions -XX:+UseCompressedOops -XX:HeapBaseMinAddress=32g -XX:-LoopUnswitching -XX:CompileCommand=inline,AbstractMemoryEfficientList.equals Test hello goodbye
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore */
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amoreimport java.lang.ref.ReferenceQueue;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amoreimport java.lang.ref.WeakReference;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amoreimport java.util.ArrayList;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amoreimport java.util.Arrays;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amoreimport java.util.List;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amoreinterface MyList {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore public int size();
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore public Object set(final int index, final Object element);
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore public Object get(final int index);
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore}
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amoreabstract class AbstractMemoryEfficientList implements MyList {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore abstract public int size();
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore abstract public Object get(final int index);
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore abstract public Object set(final int index, final Object element);
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore public boolean equals(Object o) {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore if (o == this) {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore return true;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore if (!(o instanceof MyList)) {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore return false;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore final MyList that = (MyList) o;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore if (this.size() != that.size()) {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore return false;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore for (int i = 0; i < this.size(); i++) {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore try {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore if (!((this.get(i)).equals(that.get(i)))) {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore return false;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore } catch (IndexOutOfBoundsException e) {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore System.out.println("THROWING RT EXC");
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore System.out.println("concurrent modification of this:" + this.getClass() + ":" + System.identityHashCode(this) + "; that:" + that.getClass() + ":" + System.identityHashCode(that) + "; i:" + i);
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore e.printStackTrace();
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore System.exit(97);
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore throw new RuntimeException("concurrent modification of this:" + this.getClass() + ":" + System.identityHashCode(this) + "; that:" + that.getClass() + ":" + System.identityHashCode(that) + "; i:" + i, e);
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore return true;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore public int hashCode() {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore int hashCode = 1;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore for (int i = 0; i < this.size(); i++) {
a33ad26ef1f3b7a3fcf2fad564e6bd3798fdcbaeZhao Edgar Liu - Sun Microsystems Object obj = this.get(i);
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore hashCode = 31 * hashCode + (obj == null ? 0 : obj.hashCode());
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore return hashCode;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore}
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amorefinal class SingletonList extends AbstractMemoryEfficientList {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore private Object element1;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore SingletonList(final Object obj1) {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore super();
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore this.element1 = obj1;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore public int size() {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore return 1;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore public Object get(final int index) {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore if (index == 0) {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore return this.element1;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore } else {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + this.size());
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore public Object set(final int index, final Object element) {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore if (index == 0) {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore final Object previousElement = this.element1;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore this.element1 = element;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore return previousElement;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore } else {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + this.size());
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore}
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amorefinal class DoubletonList extends AbstractMemoryEfficientList {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore private Object element1;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore private Object element2;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore DoubletonList(final Object obj1, final Object obj2) {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore this.element1 = obj1;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore this.element2 = obj2;
a33ad26ef1f3b7a3fcf2fad564e6bd3798fdcbaeZhao Edgar Liu - Sun Microsystems }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore public int size() {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore return 2;
a33ad26ef1f3b7a3fcf2fad564e6bd3798fdcbaeZhao Edgar Liu - Sun Microsystems }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore public Object get(final int index) {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore switch (index) {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore case 0 : return this.element1;
a33ad26ef1f3b7a3fcf2fad564e6bd3798fdcbaeZhao Edgar Liu - Sun Microsystems case 1 : return this.element2;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore default: throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + this.size());
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
a33ad26ef1f3b7a3fcf2fad564e6bd3798fdcbaeZhao Edgar Liu - Sun Microsystems public Object set(final int index, final Object element) {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore switch (index) {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore case 0 :
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore final Object previousElement = this.element1;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore this.element1 = element;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore return previousElement;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore case 1 :
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore final Object previousElement = this.element2;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore this.element2 = element;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore return previousElement;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore default : throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + this.size());
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore}
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amoreclass WeakPool<V> {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore protected static final int DEFAULT_INITIAL_CAPACITY = 16;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore private static final int MAXIMUM_CAPACITY = 1 << 30;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore private static final float DEFAULT_LOAD_FACTOR = 0.75f;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore protected Entry<V>[] table;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore private int size;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore protected int threshold;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore private final float loadFactor;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore private final ReferenceQueue<V> queue = new ReferenceQueue<V>();
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore public WeakPool()
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore this.loadFactor = DEFAULT_LOAD_FACTOR;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore threshold = DEFAULT_INITIAL_CAPACITY;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore table = new Entry[DEFAULT_INITIAL_CAPACITY];
a33ad26ef1f3b7a3fcf2fad564e6bd3798fdcbaeZhao Edgar Liu - Sun Microsystems }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore /**
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * Check for equality of non-null reference x and possibly-null y. By
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * default uses Object.equals.
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore */
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore private boolean eq(Object x, Object y)
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore return x == y || x.equals(y);
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore /**
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * Return index for hash code h.
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore */
a33ad26ef1f3b7a3fcf2fad564e6bd3798fdcbaeZhao Edgar Liu - Sun Microsystems private int indexFor(int h, int length)
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore return h & length - 1;
a33ad26ef1f3b7a3fcf2fad564e6bd3798fdcbaeZhao Edgar Liu - Sun Microsystems }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore /**
a33ad26ef1f3b7a3fcf2fad564e6bd3798fdcbaeZhao Edgar Liu - Sun Microsystems * Expunge stale entries from the table.
a33ad26ef1f3b7a3fcf2fad564e6bd3798fdcbaeZhao Edgar Liu - Sun Microsystems */
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore private void expungeStaleEntries()
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore Object r;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore while ((r = queue.poll()) != null)
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore Entry e = (Entry) r;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore int h = e.hash;
a33ad26ef1f3b7a3fcf2fad564e6bd3798fdcbaeZhao Edgar Liu - Sun Microsystems int i = indexFor(h, table.length);
a33ad26ef1f3b7a3fcf2fad564e6bd3798fdcbaeZhao Edgar Liu - Sun Microsystems
a33ad26ef1f3b7a3fcf2fad564e6bd3798fdcbaeZhao Edgar Liu - Sun Microsystems // System.out.println("EXPUNGING " + h);
a33ad26ef1f3b7a3fcf2fad564e6bd3798fdcbaeZhao Edgar Liu - Sun Microsystems Entry<V> prev = table[i];
a33ad26ef1f3b7a3fcf2fad564e6bd3798fdcbaeZhao Edgar Liu - Sun Microsystems Entry<V> p = prev;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore while (p != null)
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore Entry<V> next = p.next;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore if (p == e)
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore if (prev == e)
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore table[i] = next;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore else
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore prev.next = next;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore e.next = null; // Help GC
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore size--;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore break;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore prev = p;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore p = next;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore /**
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * Return the table after first expunging stale entries
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore */
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore private Entry<V>[] getTable()
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore expungeStaleEntries();
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore return table;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore /**
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * Returns the number of key-value mappings in this map.
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * This result is a snapshot, and may not reflect unprocessed
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * entries that will be removed before next attempted access
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * because they are no longer referenced.
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore */
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore public int size()
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore if (size == 0)
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore return 0;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore expungeStaleEntries();
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore return size;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore /**
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * Returns <tt>true</tt> if this map contains no key-value mappings.
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * This result is a snapshot, and may not reflect unprocessed
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * entries that will be removed before next attempted access
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * because they are no longer referenced.
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore */
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore public boolean isEmpty()
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore return size() == 0;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore /**
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * Returns the value stored in the pool that equals the requested key
a33ad26ef1f3b7a3fcf2fad564e6bd3798fdcbaeZhao Edgar Liu - Sun Microsystems * or <tt>null</tt> if the map contains no mapping for
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * this key (or the key is null)
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore *
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * @param key the key whose equals value is to be returned.
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * @return the object that is equal the specified key, or
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * <tt>null</tt> if key is null or no object in the pool equals the key.
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore */
a33ad26ef1f3b7a3fcf2fad564e6bd3798fdcbaeZhao Edgar Liu - Sun Microsystems public V get(V key)
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
a33ad26ef1f3b7a3fcf2fad564e6bd3798fdcbaeZhao Edgar Liu - Sun Microsystems if (key == null)
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore return null;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore int h = key.hashCode();
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore Entry<V>[] tab = getTable();
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore int index = indexFor(h, tab.length);
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore Entry<V> e = tab[index];
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore while (e != null)
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore V candidate = e.get();
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore if (e.hash == h && eq(key, candidate))
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore return candidate;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore e = e.next;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore return null;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore /**
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * Returns the entry associated with the specified key in the HashMap.
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * Returns null if the HashMap contains no mapping for this key.
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore */
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore Entry getEntry(Object key)
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore int h = key.hashCode();
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore Entry[] tab = getTable();
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore int index = indexFor(h, tab.length);
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore Entry e = tab[index];
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore while (e != null && !(e.hash == h && eq(key, e.get())))
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore e = e.next;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore return e;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore /**
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * Places the object into the pool. If the object is null, nothing happens.
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * If an equal object already exists, it is not replaced.
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore *
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * @param key the object to put into the pool. key may be null.
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * @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
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore */
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore public V put(V key)
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore if (key == null)
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore return null;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore int h = key.hashCode();
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore Entry<V>[] tab = getTable();
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore int i = indexFor(h, tab.length);
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore for (Entry<V> e = tab[i]; e != null; e = e.next)
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore V candidate = e.get();
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore if (h == e.hash && eq(key, candidate))
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore return candidate;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore tab[i] = new Entry<V>(key, queue, h, tab[i]);
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore if (++size >= threshold)
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore resize(tab.length * 2);
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore // System.out.println("Added " + key + " to pool");
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore return key;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore /**
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * Rehashes the contents of this map into a new array with a
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * larger capacity. This method is called automatically when the
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * number of keys in this map reaches its threshold.
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * <p/>
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * If current capacity is MAXIMUM_CAPACITY, this method does not
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * resize the map, but but sets threshold to Integer.MAX_VALUE.
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * This has the effect of preventing future calls.
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore *
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * @param newCapacity the new capacity, MUST be a power of two;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * must be greater than current capacity unless current
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * capacity is MAXIMUM_CAPACITY (in which case value
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * is irrelevant).
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore */
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore void resize(int newCapacity)
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore Entry<V>[] oldTable = getTable();
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore int oldCapacity = oldTable.length;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore if (oldCapacity == MAXIMUM_CAPACITY)
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore threshold = Integer.MAX_VALUE;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore return;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore Entry<V>[] newTable = new Entry[newCapacity];
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore transfer(oldTable, newTable);
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore table = newTable;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore /*
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * If ignoring null elements and processing ref queue caused massive
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * shrinkage, then restore old table. This should be rare, but avoids
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * unbounded expansion of garbage-filled tables.
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore */
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore if (size >= threshold / 2)
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore threshold = (int) (newCapacity * loadFactor);
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
68c47f65208790c466e5e484f2293d3baed71c6aGarrett D'Amore else
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore expungeStaleEntries();
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore transfer(newTable, oldTable);
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore table = oldTable;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
68c47f65208790c466e5e484f2293d3baed71c6aGarrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore /**
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * Transfer all entries from src to dest tables
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore */
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore private void transfer(Entry[] src, Entry[] dest)
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore for (int j = 0; j < src.length; ++j)
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore Entry e = src[j];
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore src[j] = null;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore while (e != null)
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
68c47f65208790c466e5e484f2293d3baed71c6aGarrett D'Amore Entry next = e.next;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore Object key = e.get();
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore if (key == null)
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore e.next = null; // Help GC
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore size--;
68c47f65208790c466e5e484f2293d3baed71c6aGarrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore else
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore int i = indexFor(e.hash, dest.length);
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore e.next = dest[i];
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore dest[i] = e;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore e = next;
68c47f65208790c466e5e484f2293d3baed71c6aGarrett D'Amore }
68c47f65208790c466e5e484f2293d3baed71c6aGarrett D'Amore }
68c47f65208790c466e5e484f2293d3baed71c6aGarrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore /**
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * Removes the object in the pool that equals the key.
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore *
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * @param key
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * @return previous value associated with specified key, or <tt>null</tt>
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * if there was no mapping for key or the key is null.
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore */
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore public V removeFromPool(V key)
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore if (key == null)
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore return null;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore int h = key.hashCode();
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore Entry<V>[] tab = getTable();
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore int i = indexFor(h, tab.length);
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore Entry<V> prev = tab[i];
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore Entry<V> e = prev;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore while (e != null)
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore Entry<V> next = e.next;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore V candidate = e.get();
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore if (h == e.hash && eq(key, candidate))
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore size--;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore if (prev == e)
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore tab[i] = next;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore else
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore prev.next = next;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore return candidate;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore prev = e;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore e = next;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore return null;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore /**
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * Removes all mappings from this map.
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore */
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore public void clear()
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore // clear out ref queue. We don't need to expunge entries
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore // since table is getting cleared.
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore while (queue.poll() != null)
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
68c47f65208790c466e5e484f2293d3baed71c6aGarrett D'Amore // nop
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore table = new Entry[DEFAULT_INITIAL_CAPACITY];
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore threshold = DEFAULT_INITIAL_CAPACITY;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore size = 0;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore // Allocation of array may have caused GC, which may have caused
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore // additional entries to go stale. Removing these entries from the
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore // reference queue will make them eligible for reclamation.
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore while (queue.poll() != null)
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore // nop
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
a33ad26ef1f3b7a3fcf2fad564e6bd3798fdcbaeZhao Edgar Liu - Sun Microsystems }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore /**
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * The entries in this hash table extend WeakReference, using its main ref
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * field as the key.
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore */
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore protected static class Entry<V>
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore extends WeakReference<V>
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore private final int hash;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore private Entry<V> next;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore /**
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore * Create new entry.
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore */
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore Entry(final V key, final ReferenceQueue<V> queue, final int hash, final Entry<V> next)
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
a33ad26ef1f3b7a3fcf2fad564e6bd3798fdcbaeZhao Edgar Liu - Sun Microsystems super(key, queue);
a33ad26ef1f3b7a3fcf2fad564e6bd3798fdcbaeZhao Edgar Liu - Sun Microsystems this.hash = hash;
a33ad26ef1f3b7a3fcf2fad564e6bd3798fdcbaeZhao Edgar Liu - Sun Microsystems this.next = next;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore public V getKey()
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore return super.get();
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
a33ad26ef1f3b7a3fcf2fad564e6bd3798fdcbaeZhao Edgar Liu - Sun Microsystems
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore public boolean equals(Object o)
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore if (!(o instanceof WeakPool.Entry))
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore return false;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore WeakPool.Entry<V> that = (WeakPool.Entry<V>) o;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore V k1 = this.getKey();
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore V k2 = that.getKey();
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore return (k1==k2 || k1.equals(k2));
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore public int hashCode()
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore return this.hash;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore public String toString()
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore return String.valueOf(this.getKey());
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore}
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amorefinal class MultiSynonymKey {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore private List<MyList> keys;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore public MultiSynonymKey() {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore keys = new ArrayList<MyList>();
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore public MultiSynonymKey(MyList... arg) {
68c47f65208790c466e5e484f2293d3baed71c6aGarrett D'Amore keys = Arrays.asList(arg);
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
68c47f65208790c466e5e484f2293d3baed71c6aGarrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore public List<MyList> getKeys() {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore return keys;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
68c47f65208790c466e5e484f2293d3baed71c6aGarrett D'Amore
68c47f65208790c466e5e484f2293d3baed71c6aGarrett D'Amore public int hashCode() {
68c47f65208790c466e5e484f2293d3baed71c6aGarrett D'Amore return this.getKeys().hashCode();
68c47f65208790c466e5e484f2293d3baed71c6aGarrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
68c47f65208790c466e5e484f2293d3baed71c6aGarrett D'Amore public boolean equals(Object obj) {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore if (this == obj) {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore return true;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore if (!(obj instanceof MultiSynonymKey)) {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore return false;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore MultiSynonymKey that = (MultiSynonymKey) obj;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore return this.getKeys().equals(that.getKeys());
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore }
68c47f65208790c466e5e484f2293d3baed71c6aGarrett D'Amore
68c47f65208790c466e5e484f2293d3baed71c6aGarrett D'Amore public String toString() {
68c47f65208790c466e5e484f2293d3baed71c6aGarrett D'Amore return this.getClass().getName() + this.getKeys().toString();
68c47f65208790c466e5e484f2293d3baed71c6aGarrett D'Amore }
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore}
68c47f65208790c466e5e484f2293d3baed71c6aGarrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amorepublic class Test extends Thread {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore static public Test test;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore static private byte[] arg1;
68c47f65208790c466e5e484f2293d3baed71c6aGarrett D'Amore static private byte[] arg2;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore static public WeakPool<MultiSynonymKey> wp;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore public volatile MultiSynonymKey ml1;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore public volatile MultiSynonymKey ml2;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore private volatile MultiSynonymKey ml3;
68c47f65208790c466e5e484f2293d3baed71c6aGarrett D'Amore
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore public void run() {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore int count=0;
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore while (true) {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore try {
88447a05f537aabe9a1bc3d5313f22581ec992a7Garrett D'Amore Thread.sleep(10);
} catch (Exception e) {}
synchronized (wp) {
ml2 = new MultiSynonymKey(new DoubletonList(new String(arg1), new String(arg2)));
wp.put(ml2);
ml3 = new MultiSynonymKey(new DoubletonList(new String(arg1), new String(arg2)));
}
try {
Thread.sleep(10);
} catch (Exception e) {}
synchronized (wp) {
ml1 = new MultiSynonymKey(new SingletonList(new String(arg1)));
wp.put(ml1);
ml3 = new MultiSynonymKey(new SingletonList(new String(arg1)));
}
if (count++==100)
System.exit(95);
}
}
public static void main(String[] args) throws Exception {
wp = new WeakPool<MultiSynonymKey>();
test = new Test();
test.arg1 = args[0].getBytes();
test.arg2 = args[1].getBytes();
test.ml1 = new MultiSynonymKey(new SingletonList(new String(test.arg1)));
test.ml2 = new MultiSynonymKey(new DoubletonList(new String(test.arg1), new String(test.arg2)));
test.ml3 = new MultiSynonymKey(new DoubletonList(new String(test.arg1), new String(test.arg2)));
wp.put(test.ml1);
wp.put(test.ml2);
test.setDaemon(true);
test.start();
int counter = 0;
while (true) {
synchronized (wp) {
MultiSynonymKey foo = test.ml3;
if (wp.put(foo) == foo) {
// System.out.println("foo " + counter);
// System.out.println(foo);
}
}
counter++;
}
}
private boolean eq(Object x, Object y) {
return x == y || x.equals(y);
}
}