/*
 * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved.
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

package java.beans;

import java.lang.ref.ReferenceQueue;
import java.lang.ref.WeakReference;

/**
 * Hash table based mapping, which uses weak references to store keys
 * and reference-equality in place of object-equality to compare them.
 * An entry will automatically be removed when its key is no longer
 * in ordinary use. Both null values and the null key are supported.
 * This class does not require additional synchronization.
 * A thread-safety is provided by a fragile combination
 * of synchronized blocks and volatile fields.
 * Be very careful during editing!
 *
 * @see java.util.IdentityHashMap
 * @see java.util.WeakHashMap
 */
abstract class WeakIdentityMap<T> {

 private static final int MAXIMUM_CAPACITY = 1 << 30; // it MUST be a power of two
 private static final Object NULL = new Object(); // special object for null key

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

 private volatile Entry<T>[] table = newTable(1<<3); // table's length MUST be a power of two
 private int threshold = 6; // the next size value at which to resize
 private int size = 0; // the number of key-value mappings

 public T get(Object key) {
 removeStaleEntries();
 if (key == null) {
 key = NULL;
 }
 int hash = key.hashCode();
 Entry<T>[] table = this.table;
 // unsynchronized search improves performance
 // the null value does not mean that there are no needed entry
 int index = getIndex(table, hash);
 for (Entry<T> entry = table[index]; entry != null; entry = entry.next) {
 if (entry.isMatched(key, hash)) {
 return entry.value;
 }
 }
 synchronized (NULL) {
 // synchronized search improves stability
 // we must create and add new value if there are no needed entry
 index = getIndex(this.table, hash);
 for (Entry<T> entry = this.table[index]; entry != null; entry = entry.next) {
 if (entry.isMatched(key, hash)) {
 return entry.value;
 }
 }
 T value = create(key);
 this.table[index] = new Entry<T>(key, hash, value, this.queue, this.table[index]);
 if (++this.size >= this.threshold) {
 if (this.table.length == MAXIMUM_CAPACITY) {
 this.threshold = Integer.MAX_VALUE;
 }
 else {
 removeStaleEntries();
 table = newTable(this.table.length * 2);
 transfer(this.table, table);
 // 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 (this.size >= this.threshold / 2) {
 this.table = table;
 this.threshold *= 2;
 }
 else {
 transfer(table, this.table);
 }
 }
 }
 return value;
 }
 }

 protected abstract T create(Object key);

 private void removeStaleEntries() {
 Object ref = this.queue.poll();
 if (ref != null) {
 synchronized (NULL) {
 do {
 @SuppressWarnings("unchecked")
 Entry<T> entry = (Entry<T>) ref;
 int index = getIndex(this.table, entry.hash);

 Entry<T> prev = this.table[index];
 Entry<T> current = prev;
 while (current != null) {
 Entry<T> next = current.next;
 if (current == entry) {
 if (prev == entry) {
 this.table[index] = next;
 }
 else {
 prev.next = next;
 }
 entry.value = null; // Help GC
 entry.next = null; // Help GC
 this.size--;
 break;
 }
 prev = current;
 current = next;
 }
 ref = this.queue.poll();
 }
 while (ref != null);
 }
 }
 }

 private void transfer(Entry<T>[] oldTable, Entry<T>[] newTable) {
 for (int i = 0; i < oldTable.length; i++) {
 Entry<T> entry = oldTable[i];
 oldTable[i] = null;
 while (entry != null) {
 Entry<T> next = entry.next;
 Object key = entry.get();
 if (key == null) {
 entry.value = null; // Help GC
 entry.next = null; // Help GC
 this.size--;
 }
 else {
 int index = getIndex(newTable, entry.hash);
 entry.next = newTable[index];
 newTable[index] = entry;
 }
 entry = next;
 }
 }
 }


 @SuppressWarnings("unchecked")
 private Entry<T>[] newTable(int length) {
 return (Entry<T>[]) new Entry<?>[length];
 }

 private static int getIndex(Entry<?>[] table, int hash) {
 return hash & (table.length - 1);
 }

 private static class Entry<T> extends WeakReference<Object> {
 private final int hash;
 private volatile T value;
 private volatile Entry<T> next;

 Entry(Object key, int hash, T value, ReferenceQueue<Object> queue, Entry<T> next) {
 super(key, queue);
 this.hash = hash;
 this.value = value;
 this.next = next;
 }

 boolean isMatched(Object key, int hash) {
 return (this.hash == hash) && (key == get());
 }
 }
}