/*

 * Copyright 2009 Goldman Sachs International.  All Rights Reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

 * CA 95054 USA or visit www.sun.com if you need additional information or

 * have any questions.

 *

 */

/*

 * @test

 * @bug 6865031

 * @summary Application gives bad result (throws bad exception) with compressed oops

 */

import java.lang.ref.ReferenceQueue;

import java.lang.ref.WeakReference;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.List;

interface MyList {

    public int size();

    public Object set(final int index, final Object element);

    public Object get(final int index);

}

abstract class AbstractMemoryEfficientList implements MyList {

    abstract public int size();

    abstract public Object get(final int index);

    abstract public Object set(final int index, final Object element);

    public boolean equals(Object o) {

        if (o == this) {

            return true;

        }

        if (!(o instanceof MyList)) {

            return false;

        }

        final MyList that = (MyList) o;

        if (this.size() != that.size()) {

            return false;

        }

        for (int i = 0; i < this.size(); i++) {

            try {

                if (!((this.get(i)).equals(that.get(i)))) {

                    return false;

                }

            } catch (IndexOutOfBoundsException e) {

                System.out.println("THROWING RT EXC");

                System.out.println("concurrent modification of this:" + this.getClass() + ":" + System.identityHashCode(this) + "; that:" + that.getClass() + ":" + System.identityHashCode(that) + "; i:" + i);

                e.printStackTrace();

                System.exit(97);

                throw new RuntimeException("concurrent modification of this:" + this.getClass() + ":" + System.identityHashCode(this) + "; that:" + that.getClass() + ":" + System.identityHashCode(that) + "; i:" + i, e);

            }

        }

        return true;

    }

    public int hashCode() {

        int hashCode = 1;

        for (int i = 0; i < this.size(); i++) {

            Object obj = this.get(i);

            hashCode = 31 * hashCode + (obj == null ? 0 : obj.hashCode());

        }

        return hashCode;

    }

}

final class SingletonList extends AbstractMemoryEfficientList {

    private Object element1;

    SingletonList(final Object obj1) {

        super();

        this.element1 = obj1;

    }

    public int size() {

        return 1;

    }

    public Object get(final int index) {

        if (index == 0) {

            return this.element1;

        } else {

            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + this.size());

        }

    }

    public Object set(final int index, final Object element) {

        if (index == 0) {

            final Object previousElement = this.element1;

            this.element1 = element;

            return previousElement;

        } else {

            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + this.size());

        }

    }

}

final class DoubletonList extends AbstractMemoryEfficientList {

    private Object element1;

    private Object element2;

    DoubletonList(final Object obj1, final Object obj2) {

        this.element1 = obj1;

        this.element2 = obj2;

    }

    public int size() {

        return 2;

    }

    public Object get(final int index) {

        switch (index) {

            case 0 : return this.element1;

            case 1 : return this.element2;

            default: throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + this.size());

        }

    }

    public Object set(final int index, final Object element) {

        switch (index) {

            case 0 :

            {

                final Object previousElement = this.element1;

                this.element1 = element;

                return previousElement;

            }

            case 1 :

            {

                final Object previousElement = this.element2;

                this.element2 = element;

                return previousElement;

            }

            default : throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + this.size());

        }

    }

}

class WeakPool<V> {

    protected static final int DEFAULT_INITIAL_CAPACITY = 16;

    private static final int MAXIMUM_CAPACITY = 1 << 30;

    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    protected Entry<V>[] table;

    private int size;

    protected int threshold;

    private final float loadFactor;

    private final ReferenceQueue<V> queue = new ReferenceQueue<V>();

    public WeakPool()

    {

        this.loadFactor = DEFAULT_LOAD_FACTOR;

        threshold = DEFAULT_INITIAL_CAPACITY;

        table = new Entry[DEFAULT_INITIAL_CAPACITY];

    }

    /**

     * Check for equality of non-null reference x and possibly-null y.  By

     * default uses Object.equals.

     */

    private boolean eq(Object x, Object y)

    {

        return x == y || x.equals(y);

    }

    /**

     * Return index for hash code h.

     */

    private int indexFor(int h, int length)

    {

        return h & length - 1;

    }

    /**

     * Expunge stale entries from the table.

     */

    private void expungeStaleEntries()

    {

        Object r;

        while ((r = queue.poll()) != null)

        {

            Entry e = (Entry) r;

            int h = e.hash;

            int i = indexFor(h, table.length);

            // System.out.println("EXPUNGING " + h);

            Entry<V> prev = table[i];

            Entry<V> p = prev;

            while (p != null)

            {

                Entry<V> next = p.next;

                if (p == e)

                {

                    if (prev == e)

                    {

                        table[i] = next;

                    }

                    else

                    {

                        prev.next = next;

                    }

                    e.next = null;  // Help GC

                    size--;

                    break;

                }

                prev = p;

                p = next;

            }

        }

    }

    /**

     * Return the table after first expunging stale entries

     */

    private Entry<V>[] getTable()

    {

        expungeStaleEntries();

        return table;

    }

    /**

     * Returns the number of key-value mappings in this map.

     * This result is a snapshot, and may not reflect unprocessed

     * entries that will be removed before next attempted access

     * because they are no longer referenced.

     */

    public int size()

    {

        if (size == 0)

        {

            return 0;

        }

        expungeStaleEntries();

        return size;

    }

    /**

     * Returns <tt>true</tt> if this map contains no key-value mappings.

     * This result is a snapshot, and may not reflect unprocessed

     * entries that will be removed before next attempted access

     * because they are no longer referenced.

     */

    public boolean isEmpty()

    {

        return size() == 0;

    }

    /**

     * Returns the value stored in the pool that equals the requested key

     * or <tt>null</tt> if the map contains no mapping for

     * this key (or the key is null)

     *

     * @param key the key whose equals value is to be returned.

     * @return the object that is equal the specified key, or

     *         <tt>null</tt> if key is null or no object in the pool equals the key.

     */

    public V get(V key)

    {

        if (key == null)

        {

            return null;

        }

        int h = key.hashCode();

        Entry<V>[] tab = getTable();

        int index = indexFor(h, tab.length);

        Entry<V> e = tab[index];

        while (e != null)

        {

            V candidate = e.get();

            if (e.hash == h && eq(key, candidate))

            {

                return candidate;

            }

            e = e.next;

        }

        return null;

    }

    /**

     * Returns the entry associated with the specified key in the HashMap.

     * Returns null if the HashMap contains no mapping for this key.

     */

    Entry getEntry(Object key)

    {

        int h = key.hashCode();

        Entry[] tab = getTable();

        int index = indexFor(h, tab.length);

        Entry e = tab[index];

        while (e != null && !(e.hash == h && eq(key, e.get())))

        {

            e = e.next;

        }

        return e;

    }

    /**

     * Places the object into the pool. If the object is null, nothing happens.

     * If an equal object already exists, it is not replaced.

     *

     * @param key the object to put into the pool. key may be null.

     * @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

     */

    public V put(V key)

    {

        if (key == null)

        {

            return null;

        }

        int h = key.hashCode();

        Entry<V>[] tab = getTable();

        int i = indexFor(h, tab.length);

        for (Entry<V> e = tab[i]; e != null; e = e.next)

        {

            V candidate = e.get();

            if (h == e.hash && eq(key, candidate))

            {

                return candidate;

            }

        }

        tab[i] = new Entry<V>(key, queue, h, tab[i]);

        if (++size >= threshold)

        {

            resize(tab.length * 2);

        }

    // System.out.println("Added " + key + " to pool");

        return key;

    }

    /**

     * Rehashes the contents of this map into a new array with a

     * larger capacity.  This method is called automatically when the

     * number of keys in this map reaches its threshold.

     * <p/>

     * If current capacity is MAXIMUM_CAPACITY, this method does not

     * resize the map, but but sets threshold to Integer.MAX_VALUE.

     * This has the effect of preventing future calls.

     *

     * @param newCapacity the new capacity, MUST be a power of two;

     *                    must be greater than current capacity unless current

     *                    capacity is MAXIMUM_CAPACITY (in which case value

     *                    is irrelevant).

     */

    void resize(int newCapacity)

    {

        Entry<V>[] oldTable = getTable();

        int oldCapacity = oldTable.length;

        if (oldCapacity == MAXIMUM_CAPACITY)

        {

            threshold = Integer.MAX_VALUE;

            return;

        }

        Entry<V>[] newTable = new Entry[newCapacity];

        transfer(oldTable, newTable);

        table = newTable;

        /*

         * If ignoring null elements and processing ref queue caused massive

         * shrinkage, then restore old table.  This should be rare, but avoids

         * unbounded expansion of garbage-filled tables.

         */

        if (size >= threshold / 2)

        {

            threshold = (int) (newCapacity * loadFactor);

        }

        else

        {

            expungeStaleEntries();

            transfer(newTable, oldTable);

            table = oldTable;

        }

    }

    /**

     * Transfer all entries from src to dest tables

     */

    private void transfer(Entry[] src, Entry[] dest)

    {

        for (int j = 0; j < src.length; ++j)

        {

            Entry e = src[j];

            src[j] = null;

            while (e != null)

            {

                Entry next = e.next;

                Object key = e.get();

                if (key == null)

                {

                    e.next = null;  // Help GC

                    size--;

                }

                else

                {

                    int i = indexFor(e.hash, dest.length);

                    e.next = dest[i];

                    dest[i] = e;

                }

                e = next;

            }

        }

    }

    /**

     * Removes the object in the pool that equals the key.

     *

     * @param key

     * @return previous value associated with specified key, or <tt>null</tt>

     *         if there was no mapping for key or the key is null.

     */

    public V removeFromPool(V key)

    {

        if (key == null)

        {

            return null;

        }

        int h = key.hashCode();

        Entry<V>[] tab = getTable();

        int i = indexFor(h, tab.length);

        Entry<V> prev = tab[i];

        Entry<V> e = prev;

        while (e != null)

        {

            Entry<V> next = e.next;

            V candidate = e.get();

            if (h == e.hash && eq(key, candidate))

            {

                size--;

                if (prev == e)

                {

                    tab[i] = next;

                }

                else

                {

                    prev.next = next;

                }

                return candidate;

            }

            prev = e;

            e = next;

        }

        return null;

    }

    /**

     * Removes all mappings from this map.

     */

    public void clear()

    {

        // clear out ref queue. We don't need to expunge entries

        // since table is getting cleared.

        while (queue.poll() != null)

        {

            // nop

        }

        table = new Entry[DEFAULT_INITIAL_CAPACITY];

        threshold = DEFAULT_INITIAL_CAPACITY;

        size = 0;

        // Allocation of array may have caused GC, which may have caused

        // additional entries to go stale.  Removing these entries from the

        // reference queue will make them eligible for reclamation.

        while (queue.poll() != null)

        {

            // nop

        }

    }

    /**

     * The entries in this hash table extend WeakReference, using its main ref

     * field as the key.

     */

    protected static class Entry<V>

    extends WeakReference<V>

    {

        private final int hash;

        private Entry<V> next;

        /**

         * Create new entry.

         */

        Entry(final V key, final ReferenceQueue<V> queue, final int hash, final Entry<V> next)

        {

            super(key, queue);

            this.hash = hash;

            this.next = next;

        }

        public V getKey()

        {

            return super.get();

        }

        public boolean equals(Object o)

        {

            if (!(o instanceof WeakPool.Entry))

            {

                return false;

            }

            WeakPool.Entry<V> that = (WeakPool.Entry<V>) o;