bundles/org.eclipse.equinox.common/src/org/eclipse/core/internal/runtime/ReferenceHashSet.java - equinox/rt.equinox.bundles - Git at Google

 /*******************************************************************************
  * Copyright (c) 2004, 2015 IBM Corporation and others.
  * All rights reserved. This program and the accompanying materials
  * are made available under the terms of the Eclipse Public License v1.0
  * which accompanies this distribution, and is available at
  * http://www.eclipse.org/legal/epl-v10.html
  *
  * Contributors:
  *     IBM Corporation - initial API and implementation
  *     Sergey Prigogin (Google) - use parameterized types (bug 442021)
  *******************************************************************************/
 package org.eclipse.core.internal.runtime;

 import java.lang.ref.*;

 /**
  * A hashset whose values can be garbage collected.
  * This API is EXPERIMENTAL and provided as early access.
  * @since 3.1
  */
 public class ReferenceHashSet<T> {

 	private interface HashedReference<T> {
 		@Override
 		int hashCode();

 		T get();
 	}

 	private class HashableWeakReference<U> extends WeakReference<U> implements HashedReference<U> {
 		public int hashCode;

 		public HashableWeakReference(U referent, ReferenceQueue<? super U> queue) {
 			super(referent, queue);
 			this.hashCode = referent.hashCode();
 		}

 		@Override
 		public boolean equals(Object obj) {
 			if (!(obj instanceof HashableWeakReference))
 				return false;
 			U referent = super.get();
 			@SuppressWarnings("unchecked")
 			Object other = ((HashableWeakReference<?>) obj).get();
 			if (referent == null)
 				return other == null;
 			return referent.equals(other);
 		}

 		@Override
 		public int hashCode() {
 			return this.hashCode;
 		}

 		@Override
 		public String toString() {
 			Object referent = super.get();
 			if (referent == null)
 				return "[hashCode=" + this.hashCode + "] <referent was garbage collected>"; //$NON-NLS-1$  //$NON-NLS-2$
 			return "[hashCode=" + this.hashCode + "] " + referent.toString(); //$NON-NLS-1$ //$NON-NLS-2$
 		}
 	}

 	private class HashableSoftReference<U> extends SoftReference<U> implements HashedReference<U> {
 		public int hashCode;

 		public HashableSoftReference(U referent, ReferenceQueue<? super U> queue) {
 			super(referent, queue);
 			this.hashCode = referent.hashCode();
 		}

 		@Override
 		public boolean equals(Object obj) {
 			if (!(obj instanceof HashableWeakReference))
 				return false;
 			Object referent = super.get();
 			@SuppressWarnings("unchecked")
 			Object other = ((HashableWeakReference<?>) obj).get();
 			if (referent == null)
 				return other == null;
 			return referent.equals(other);
 		}

 		@Override
 		public int hashCode() {
 			return this.hashCode;
 		}

 		@Override
 		public String toString() {
 			Object referent = super.get();
 			if (referent == null)
 				return "[hashCode=" + this.hashCode + "] <referent was garbage collected>"; //$NON-NLS-1$  //$NON-NLS-2$
 			return "[hashCode=" + this.hashCode + "] " + referent.toString(); //$NON-NLS-1$ //$NON-NLS-2$
 		}
 	}

 	private class StrongReference<U> implements HashedReference<U> {
 		private U referent;

 		public StrongReference(U referent, ReferenceQueue<? super U> queue) {
 			this.referent = referent;
 		}

 		@Override
 		public int hashCode() {
 			return referent.hashCode();
 		}

 		@Override
 		public U get() {
 			return referent;
 		}

 		@Override
 		public boolean equals(Object obj) {
 			return referent.equals(obj);
 		}
 	}

 	HashedReference<T>[] values;

 	public int elementSize; // number of elements in the table

 	int threshold;

 	ReferenceQueue<T> referenceQueue = new ReferenceQueue<>();

 	public ReferenceHashSet() {
 		this(5);
 	}

 	@SuppressWarnings("unchecked")
 	public ReferenceHashSet(int size) {
 		this.elementSize = 0;
 		this.threshold = size; // size represents the expected
 		// number of elements
 		int extraRoom = (int) (size * 1.75f);
 		if (this.threshold == extraRoom)
 			extraRoom++;
 		this.values = new HashedReference[extraRoom];
 	}

 	/**
 	 * Constant indicating that hard references should be used.
 	 */
 	final public static int HARD = 0;

 	/**
 	 * Constant indiciating that soft references should be used.
 	 */
 	final public static int SOFT = 1;

 	/**
 	 * Constant indicating that weak references should be used.
 	 */
 	final public static int WEAK = 2;

 	private HashedReference<T> toReference(int type, T referent) {
 		switch (type) {
 			case HARD :
 				return new StrongReference<>(referent, referenceQueue);
 			case SOFT :
 				return new HashableSoftReference<>(referent, referenceQueue);
 			case WEAK :
 				return new HashableWeakReference<>(referent, referenceQueue);
 			default :
 				throw new Error();
 		}
 	}

 	/*
 	 * Adds the given object to this set. If an object that is equals to the
 	 * given object already exists, do nothing. Returns the existing object or
 	 * the new object if not found.
 	 */
 	public T add(T obj, int referenceType) {
 		cleanupGarbageCollectedValues();
 		int index = (obj.hashCode() & 0x7FFFFFFF) % this.values.length;
 		HashedReference<T> currentValue;
 		while ((currentValue = this.values[index]) != null) {
 			T referent;
 			if (obj.equals(referent = currentValue.get())) {
 				return referent;
 			}
 			index = (index + 1) % this.values.length;
 		}
 		this.values[index] = toReference(referenceType, obj);

 		// assumes the threshold is never equal to the size of the table
 		if (++this.elementSize > this.threshold)
 			rehash();

 		return obj;
 	}

 	private void addValue(HashedReference<T> value) {
 		Object obj = value.get();
 		if (obj == null)
 			return;
 		int valuesLength = this.values.length;
 		int index = (value.hashCode() & 0x7FFFFFFF) % valuesLength;
 		HashedReference<T> currentValue;
 		while ((currentValue = this.values[index]) != null) {
 			if (obj.equals(currentValue.get())) {
 				return;
 			}
 			index = (index + 1) % valuesLength;
 		}
 		this.values[index] = value;

 		// assumes the threshold is never equal to the size of the table
 		if (++this.elementSize > this.threshold)
 			rehash();
 	}

 	private void cleanupGarbageCollectedValues() {
 		HashedReference<?> toBeRemoved;
 		while ((toBeRemoved = (HashedReference<?>) this.referenceQueue.poll()) != null) {
 			int hashCode = toBeRemoved.hashCode();
 			int valuesLength = this.values.length;
 			int index = (hashCode & 0x7FFFFFFF) % valuesLength;
 			HashedReference<T> currentValue;
 			while ((currentValue = this.values[index]) != null) {
 				if (currentValue == toBeRemoved) {
 					// replace the value at index with the last value with the
 					// same hash
 					int sameHash = index;
 					int current;
 					while ((currentValue = this.values[current = (sameHash + 1) % valuesLength]) != null && currentValue.hashCode() == hashCode)
 						sameHash = current;
 					this.values[index] = this.values[sameHash];
 					this.values[sameHash] = null;
 					this.elementSize--;
 					break;
 				}
 				index = (index + 1) % valuesLength;
 			}
 		}
 	}

 	public boolean contains(T obj) {
 		return get(obj) != null;
 	}

 	/*
 	 * Return the object that is in this set and that is equals to the given
 	 * object. Return null if not found.
 	 */
 	public T get(T obj) {
 		cleanupGarbageCollectedValues();
 		int valuesLength = this.values.length;
 		int index = (obj.hashCode() & 0x7FFFFFFF) % valuesLength;
 		HashedReference<T> currentValue;
 		while ((currentValue = this.values[index]) != null) {
 			T referent;
 			if (obj.equals(referent = currentValue.get())) {
 				return referent;
 			}
 			index = (index + 1) % valuesLength;
 		}
 		return null;
 	}

 	private void rehash() {
 		ReferenceHashSet<T> newHashSet = new ReferenceHashSet<>(this.elementSize * 2); // double the number of expected elements
 		newHashSet.referenceQueue = this.referenceQueue;
 		HashedReference<T> currentValue;
 		for (int i = 0, length = this.values.length; i < length; i++)
 			if ((currentValue = this.values[i]) != null)
 				newHashSet.addValue(currentValue);

 		this.values = newHashSet.values;
 		this.threshold = newHashSet.threshold;
 		this.elementSize = newHashSet.elementSize;
 	}

 	/*
 	 * Removes the object that is in this set and that is equals to the given
 	 * object. Return the object that was in the set, or null if not found.
 	 */
 	public Object remove(T obj) {
 		cleanupGarbageCollectedValues();
 		int valuesLength = this.values.length;
 		int index = (obj.hashCode() & 0x7FFFFFFF) % valuesLength;
 		HashedReference<T> currentValue;
 		while ((currentValue = this.values[index]) != null) {
 			Object referent;
 			if (obj.equals(referent = currentValue.get())) {
 				this.elementSize--;
 				this.values[index] = null;
 				rehash();
 				return referent;
 			}
 			index = (index + 1) % valuesLength;
 		}
 		return null;
 	}

 	public int size() {
 		return this.elementSize;
 	}

 	@Override
 	public String toString() {
 		StringBuffer buffer = new StringBuffer("{"); //$NON-NLS-1$
 		for (int i = 0, length = this.values.length; i < length; i++) {
 			HashedReference<T> value = this.values[i];
 			if (value != null) {
 				Object ref = value.get();
 				if (ref != null) {
 					buffer.append(ref.toString());
 					buffer.append(", "); //$NON-NLS-1$
 				}
 			}
 		}
 		buffer.append("}"); //$NON-NLS-1$
 		return buffer.toString();
 	}

 	public Object[] toArray() {
 		cleanupGarbageCollectedValues();
 		Object[] result = new Object[elementSize];
 		int resultSize = 0;
 		for (int i = 0; i < values.length; i++) {
 			if (values[i] == null)
 				continue;
 			Object tmp = values[i].get();
 			if (tmp != null)
 				result[resultSize++] = tmp;
 		}
 		if (result.length == resultSize)
 			return result;
 		Object[] finalResult = new Object[resultSize];
 		System.arraycopy(result, 0, finalResult, 0, resultSize);
 		return finalResult;
 	}
 }
	/*******************************************************************************
	* Copyright (c) 2004, 2015 IBM Corporation and others.
	* All rights reserved. This program and the accompanying materials
	* are made available under the terms of the Eclipse Public License v1.0
	* which accompanies this distribution, and is available at
	* http://www.eclipse.org/legal/epl-v10.html
	*
	* Contributors:
	* IBM Corporation - initial API and implementation
	* Sergey Prigogin (Google) - use parameterized types (bug 442021)
	*******************************************************************************/
	package org.eclipse.core.internal.runtime;

	import java.lang.ref.*;

	/**
	* A hashset whose values can be garbage collected.
	* This API is EXPERIMENTAL and provided as early access.
	* @since 3.1
	*/
	public class ReferenceHashSet<T> {

	private interface HashedReference<T> {
	@Override
	int hashCode();

	T get();
	}

	private class HashableWeakReference<U> extends WeakReference<U> implements HashedReference<U> {
	public int hashCode;

	public HashableWeakReference(U referent, ReferenceQueue<? super U> queue) {
	super(referent, queue);
	this.hashCode = referent.hashCode();
	}

	@Override
	public boolean equals(Object obj) {
	if (!(obj instanceof HashableWeakReference))
	return false;
	U referent = super.get();
	@SuppressWarnings("unchecked")
	Object other = ((HashableWeakReference<?>) obj).get();
	if (referent == null)
	return other == null;
	return referent.equals(other);
	}

	@Override
	public int hashCode() {
	return this.hashCode;
	}

	@Override
	public String toString() {
	Object referent = super.get();
	if (referent == null)
	return "[hashCode=" + this.hashCode + "] <referent was garbage collected>"; //$NON-NLS-1$ //$NON-NLS-2$
	return "[hashCode=" + this.hashCode + "] " + referent.toString(); //$NON-NLS-1$ //$NON-NLS-2$
	}
	}

	private class HashableSoftReference<U> extends SoftReference<U> implements HashedReference<U> {
	public int hashCode;

	public HashableSoftReference(U referent, ReferenceQueue<? super U> queue) {
	super(referent, queue);
	this.hashCode = referent.hashCode();
	}

	@Override
	public boolean equals(Object obj) {
	if (!(obj instanceof HashableWeakReference))
	return false;
	Object referent = super.get();
	@SuppressWarnings("unchecked")
	Object other = ((HashableWeakReference<?>) obj).get();
	if (referent == null)
	return other == null;
	return referent.equals(other);
	}

	@Override
	public int hashCode() {
	return this.hashCode;
	}

	@Override
	public String toString() {
	Object referent = super.get();
	if (referent == null)
	return "[hashCode=" + this.hashCode + "] <referent was garbage collected>"; //$NON-NLS-1$ //$NON-NLS-2$
	return "[hashCode=" + this.hashCode + "] " + referent.toString(); //$NON-NLS-1$ //$NON-NLS-2$
	}
	}

	private class StrongReference<U> implements HashedReference<U> {
	private U referent;

	public StrongReference(U referent, ReferenceQueue<? super U> queue) {
	this.referent = referent;
	}

	@Override
	public int hashCode() {
	return referent.hashCode();
	}

	@Override
	public U get() {
	return referent;
	}

	@Override
	public boolean equals(Object obj) {
	return referent.equals(obj);
	}
	}

	HashedReference<T>[] values;

	public int elementSize; // number of elements in the table

	int threshold;

	ReferenceQueue<T> referenceQueue = new ReferenceQueue<>();

	public ReferenceHashSet() {
	this(5);
	}

	@SuppressWarnings("unchecked")
	public ReferenceHashSet(int size) {
	this.elementSize = 0;
	this.threshold = size; // size represents the expected
	// number of elements
	int extraRoom = (int) (size * 1.75f);
	if (this.threshold == extraRoom)
	extraRoom++;
	this.values = new HashedReference[extraRoom];
	}

	/**
	* Constant indicating that hard references should be used.
	*/
	final public static int HARD = 0;

	/**
	* Constant indiciating that soft references should be used.
	*/
	final public static int SOFT = 1;

	/**
	* Constant indicating that weak references should be used.
	*/
	final public static int WEAK = 2;

	private HashedReference<T> toReference(int type, T referent) {
	switch (type) {
	case HARD :
	return new StrongReference<>(referent, referenceQueue);
	case SOFT :
	return new HashableSoftReference<>(referent, referenceQueue);
	case WEAK :
	return new HashableWeakReference<>(referent, referenceQueue);
	default :
	throw new Error();
	}
	}

	/*
	* Adds the given object to this set. If an object that is equals to the
	* given object already exists, do nothing. Returns the existing object or
	* the new object if not found.
	*/
	public T add(T obj, int referenceType) {
	cleanupGarbageCollectedValues();
	int index = (obj.hashCode() & 0x7FFFFFFF) % this.values.length;
	HashedReference<T> currentValue;
	while ((currentValue = this.values[index]) != null) {
	T referent;
	if (obj.equals(referent = currentValue.get())) {
	return referent;
	}
	index = (index + 1) % this.values.length;
	}
	this.values[index] = toReference(referenceType, obj);

	// assumes the threshold is never equal to the size of the table
	if (++this.elementSize > this.threshold)
	rehash();

	return obj;
	}

	private void addValue(HashedReference<T> value) {
	Object obj = value.get();
	if (obj == null)
	return;
	int valuesLength = this.values.length;
	int index = (value.hashCode() & 0x7FFFFFFF) % valuesLength;
	HashedReference<T> currentValue;
	while ((currentValue = this.values[index]) != null) {
	if (obj.equals(currentValue.get())) {
	return;
	}
	index = (index + 1) % valuesLength;
	}
	this.values[index] = value;

	// assumes the threshold is never equal to the size of the table
	if (++this.elementSize > this.threshold)
	rehash();
	}

	private void cleanupGarbageCollectedValues() {
	HashedReference<?> toBeRemoved;
	while ((toBeRemoved = (HashedReference<?>) this.referenceQueue.poll()) != null) {
	int hashCode = toBeRemoved.hashCode();
	int valuesLength = this.values.length;
	int index = (hashCode & 0x7FFFFFFF) % valuesLength;
	HashedReference<T> currentValue;
	while ((currentValue = this.values[index]) != null) {
	if (currentValue == toBeRemoved) {
	// replace the value at index with the last value with the
	// same hash
	int sameHash = index;
	int current;
	while ((currentValue = this.values[current = (sameHash + 1) % valuesLength]) != null && currentValue.hashCode() == hashCode)
	sameHash = current;
	this.values[index] = this.values[sameHash];
	this.values[sameHash] = null;
	this.elementSize--;
	break;
	}
	index = (index + 1) % valuesLength;
	}
	}
	}

	public boolean contains(T obj) {
	return get(obj) != null;
	}

	/*
	* Return the object that is in this set and that is equals to the given
	* object. Return null if not found.
	*/
	public T get(T obj) {
	cleanupGarbageCollectedValues();
	int valuesLength = this.values.length;
	int index = (obj.hashCode() & 0x7FFFFFFF) % valuesLength;
	HashedReference<T> currentValue;
	while ((currentValue = this.values[index]) != null) {
	T referent;
	if (obj.equals(referent = currentValue.get())) {
	return referent;
	}
	index = (index + 1) % valuesLength;
	}
	return null;
	}

	private void rehash() {
	ReferenceHashSet<T> newHashSet = new ReferenceHashSet<>(this.elementSize * 2); // double the number of expected elements
	newHashSet.referenceQueue = this.referenceQueue;
	HashedReference<T> currentValue;
	for (int i = 0, length = this.values.length; i < length; i++)
	if ((currentValue = this.values[i]) != null)
	newHashSet.addValue(currentValue);

	this.values = newHashSet.values;
	this.threshold = newHashSet.threshold;
	this.elementSize = newHashSet.elementSize;
	}

	/*
	* Removes the object that is in this set and that is equals to the given
	* object. Return the object that was in the set, or null if not found.
	*/
	public Object remove(T obj) {
	cleanupGarbageCollectedValues();
	int valuesLength = this.values.length;
	int index = (obj.hashCode() & 0x7FFFFFFF) % valuesLength;
	HashedReference<T> currentValue;
	while ((currentValue = this.values[index]) != null) {
	Object referent;
	if (obj.equals(referent = currentValue.get())) {
	this.elementSize--;
	this.values[index] = null;
	rehash();
	return referent;
	}
	index = (index + 1) % valuesLength;
	}
	return null;
	}

	public int size() {
	return this.elementSize;
	}

	@Override
	public String toString() {
	StringBuffer buffer = new StringBuffer("{"); //$NON-NLS-1$
	for (int i = 0, length = this.values.length; i < length; i++) {
	HashedReference<T> value = this.values[i];
	if (value != null) {
	Object ref = value.get();
	if (ref != null) {
	buffer.append(ref.toString());
	buffer.append(", "); //$NON-NLS-1$
	}
	}
	}
	buffer.append("}"); //$NON-NLS-1$
	return buffer.toString();
	}

	public Object[] toArray() {
	cleanupGarbageCollectedValues();
	Object[] result = new Object[elementSize];
	int resultSize = 0;
	for (int i = 0; i < values.length; i++) {
	if (values[i] == null)
	continue;
	Object tmp = values[i].get();
	if (tmp != null)
	result[resultSize++] = tmp;
	}
	if (result.length == resultSize)
	return result;
	Object[] finalResult = new Object[resultSize];
	System.arraycopy(result, 0, finalResult, 0, resultSize);
	return finalResult;
	}
	}