| /* |
| * Licensed to the Apache Software Foundation (ASF) under one or more |
| * contributor license agreements. See the NOTICE file distributed with |
| * this work for additional information regarding copyright ownership. |
| * The ASF licenses this file to You under the Apache License, Version 2.0 |
| * (the "License"); you may not use this file except in compliance with |
| * the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| package org.apache.sis.util.collection; |
| |
| import java.util.Arrays; |
| import java.util.Objects; |
| import java.util.Iterator; |
| import java.util.AbstractSet; |
| import java.lang.reflect.Array; |
| import org.apache.sis.util.Debug; |
| import org.apache.sis.util.ArraysExt; |
| import org.apache.sis.util.Utilities; |
| import org.apache.sis.util.Workaround; |
| import org.apache.sis.util.ArgumentChecks; |
| import org.apache.sis.util.NullArgumentException; |
| |
| import static org.apache.sis.util.collection.WeakEntry.*; |
| |
| |
| /** |
| * A set of objects hold by weak references. An entry in a {@code WeakHashSet} will automatically |
| * be removed when it is no longer in ordinary use. More precisely, the presence of an entry will |
| * not prevent the entry from being discarded by the garbage collector, that is, made finalizable, |
| * finalized, and then reclaimed. When an entry has been discarded it is effectively removed from |
| * the set, so this class behaves somewhat differently than other {@link java.util.Set} implementations. |
| * |
| * <p>If the elements stored in this set are arrays like {@code int[]}, {@code float[]} or |
| * {@code Object[]}, then the hash code computations and the comparisons are performed using |
| * the static {@code hashCode(a)} and {@code equals(a1, a2)} methods defined in the {@link Arrays} |
| * class.</p> |
| * |
| * <h2>Optimizing memory use in factory implementations</h2> |
| * The {@code WeakHashSet} class has a {@link #get(Object)} method that is not part of the |
| * {@link java.util.Set} interface. This {@code get} method retrieves an entry from this set |
| * that is equals to the supplied object. The {@link #unique(Object)} method combines a |
| * {@code get} followed by a {@code add} operation if the specified object was not in the set. |
| * This is similar in spirit to the {@link String#intern()} method. The following example shows |
| * a convenient way to use {@code WeakHashSet} as an internal pool of immutable objects: |
| * |
| * {@preformat java |
| * private final WeakHashSet<Foo> pool = new WeakHashSet<Foo>(Foo.class); |
| * |
| * public Foo create(String definition) { |
| * Foo created = new Foo(definition); |
| * return pool.unique(created); |
| * } |
| * } |
| * |
| * Thus, {@code WeakHashSet} can be used inside a factory to prevent creating duplicate immutable objects. |
| * |
| * <h2>Thread safety</h2> |
| * The same {@code WeakHashSet} instance can be safely used by many threads without synchronization on the part of |
| * the caller. But if a sequence of two or more method calls need to appear atomic from other threads perspective, |
| * then the caller can synchronize on {@code this}. |
| * |
| * @author Martin Desruisseaux (MPO, IRD, Geomatys) |
| * @version 0.3 |
| * |
| * @param <E> the type of elements in the set. |
| * |
| * @see java.util.WeakHashMap |
| * |
| * @since 0.3 |
| * @module |
| */ |
| public class WeakHashSet<E> extends AbstractSet<E> implements CheckedContainer<E> { |
| /** |
| * A weak reference to an element. This is an element in a linked list. |
| * When the reference is disposed, it is removed from the enclosing set. |
| */ |
| private final class Entry extends WeakEntry<E> { |
| /** |
| * Constructs a new weak reference. |
| */ |
| Entry(final E obj, final Entry next, final int hash) { |
| super(obj, next, hash); |
| } |
| |
| /** |
| * Invoked by {@link org.apache.sis.internal.system.ReferenceQueueConsumer} |
| * for removing the reference from the enclosing collection. |
| */ |
| @Override |
| public void dispose() { |
| super.clear(); |
| removeEntry(this); |
| } |
| } |
| |
| /** |
| * Table of weak references. |
| */ |
| private Entry[] table; |
| |
| /** |
| * Number of non-null elements in {@link #table}. This is used for determining |
| * when {@link WeakEntry#rehash(WeakEntry[], int, String)} needs to be invoked. |
| */ |
| private int count; |
| |
| /** |
| * The type of the elements in this set. |
| */ |
| private final Class<E> elementType; |
| |
| /** |
| * {@code true} if the elements in this set may be arrays. If the elements can not |
| * be arrays, then we can avoid the calls to the costly {@link Utilities} methods. |
| */ |
| private final boolean mayContainArrays; |
| |
| /** |
| * The last time when {@link #table} was not in need for rehash. When the garbage collector |
| * collected a lot of elements, we will wait a few seconds before rehashing {@link #table} |
| * in case lot of news elements are going to be added. Without this field, we noticed many |
| * "reduce", "expand", "reduce", "expand", <i>etc.</i> cycles. |
| */ |
| private transient long lastTimeNormalCapacity; |
| |
| /** |
| * Creates a {@code WeakHashSet} for elements of the specified type. |
| * |
| * @param type the type of the element to be included in this set. |
| */ |
| public WeakHashSet(final Class<E> type) { |
| elementType = type; |
| mayContainArrays = type.isArray() || type.equals(Object.class); |
| lastTimeNormalCapacity = System.nanoTime(); |
| /* |
| * Workaround for the "generic array creation" compiler error. |
| * Otherwise we would use the commented-out line instead. |
| */ |
| @SuppressWarnings("unchecked") |
| @Workaround(library="JDK", version="1.7") |
| final Entry[] table = (Entry[]) Array.newInstance(Entry.class, MIN_CAPACITY); |
| // table = new Entry[size]; |
| this.table = table; |
| } |
| |
| /** |
| * Returns the type of elements in this set. |
| */ |
| @Override |
| public Class<E> getElementType() { |
| return elementType; |
| } |
| |
| /** |
| * Invoked by {@link Entry} when an element has been collected by the garbage |
| * collector. This method removes the weak reference from the {@link #table}. |
| * |
| * @param toRemove the entry to remove from this map. |
| */ |
| private synchronized void removeEntry(final Entry toRemove) { |
| assert isValid(); |
| final int capacity = table.length; |
| if (toRemove.removeFrom(table, toRemove.hash % capacity)) { |
| count--; |
| assert isValid(); |
| if (count < lowerCapacityThreshold(capacity)) { |
| final long currentTime = System.nanoTime(); |
| if (currentTime - lastTimeNormalCapacity > REHASH_DELAY) { |
| table = (Entry[]) WeakEntry.rehash(table, count, "remove"); |
| lastTimeNormalCapacity = currentTime; |
| assert isValid(); |
| } |
| } |
| } |
| } |
| |
| /** |
| * Checks if this {@code WeakHashSet} is valid. This method counts the number of elements and |
| * compares it to {@link #count}. This method is invoked in assertions only. |
| * |
| * @return whether {@link #count} matches the expected value. |
| */ |
| @Debug |
| private boolean isValid() { |
| if (!Thread.holdsLock(this)) { |
| throw new AssertionError(); |
| } |
| if (count > upperCapacityThreshold(table.length)) { |
| throw new AssertionError(count); |
| } |
| return count(table) == count; |
| } |
| |
| /** |
| * Returns the count of element in this set. |
| * |
| * @return number of elements in this set. |
| */ |
| @Override |
| public synchronized int size() { |
| assert isValid(); |
| return count; |
| } |
| |
| /** |
| * Adds the specified element to this set if it is not already present. |
| * If this set already contains the specified element, the call leaves |
| * this set unchanged and returns {@code false}. |
| * |
| * @param element element to be added to this set. |
| * @return {@code true} if this set did not already contain the specified element. |
| * @throws NullArgumentException if the given object is {@code null}. |
| */ |
| @Override |
| public synchronized boolean add(final E element) throws NullArgumentException { |
| ArgumentChecks.ensureNonNull("element", element); |
| return intern(element, ADD) == null; |
| } |
| |
| /** |
| * Removes a single instance of the specified element from this set, if it is present |
| * Null values are considered never present. |
| * |
| * @param element element to be removed from this set, if present. Can be {@code null}. |
| * @return {@code true} if the set contained the specified element. |
| */ |
| @Override |
| public synchronized boolean remove(final Object element) { |
| return intern(element, REMOVE) != null; |
| } |
| |
| /** |
| * Returns an object equals to the specified object, if present. If this set doesn't |
| * contain any object equals to {@code element}, then this method returns {@code null}. |
| * Null values are considered never present. |
| * |
| * @param element the element to get. |
| * @return an element equals to the given one if already presents in the set, |
| * or {@code null} otherwise. |
| * |
| * @see #unique(Object) |
| */ |
| public synchronized E get(final Object element) { |
| return intern(element, GET); |
| } |
| |
| /** |
| * Returns {@code true} if this set contains the specified element. |
| * Null values are considered never present. |
| * |
| * @param element object to be checked for containment in this set. Can be {@code null}. |
| * @return {@code true} if this set contains the specified element. |
| */ |
| @Override |
| public synchronized boolean contains(final Object element) { |
| return intern(element, GET) != null; |
| } |
| |
| /** |
| * Returns an object equals to {@code element} if such an object already exist in this |
| * {@code WeakHashSet}. Otherwise, adds {@code element} to this {@code WeakHashSet}. |
| * This method is functionally equivalents to the following code: |
| * |
| * {@preformat java |
| * if (element != null) { |
| * T current = get(element); |
| * if (current != null) { |
| * return current; |
| * } else { |
| * add(element); |
| * } |
| * } |
| * return element; |
| * } |
| * |
| * @param <T> the type of the element to get. Can be {@code null}. |
| * @param element the element to get or to add in the set if not already presents, |
| * or {@code null} if the given element was null. |
| * @return an element equals to the given one if already presents in the set, |
| * or the given {@code object} otherwise. |
| */ |
| public synchronized <T extends E> T unique(final T element) { |
| /* |
| * There is no way to make sure that this operation is really safe. |
| * We have to trust the Object.equals(Object) method to be strict |
| * about the type of compared objects. |
| */ |
| return (T) intern(element, INTERN); |
| } |
| |
| // Arguments for the {@link #intern} method. |
| /** The "remove" operation. */ private static final int REMOVE = -1; |
| /** The "get" operation. */ private static final int GET = 0; |
| /** The "add" operation. */ private static final int ADD = +1; |
| /** The "intern" operation. */ private static final int INTERN = +2; |
| |
| /** |
| * Implementation of the {@link #add(Object)}, {@link #remove(Object)}, {@link #get(Object)}, |
| * {@link #contains(Object)} and {@link #unique(Object)} methods. |
| */ |
| private E intern(final Object obj, final int operation) { |
| assert isValid(); |
| if (obj != null) { |
| /* |
| * Check if the object is already contained in this |
| * WeakHashSet. If yes, return the existing element. |
| */ |
| Entry[] table = this.table; |
| final int hash = (mayContainArrays ? Utilities.deepHashCode(obj) : obj.hashCode()) & HASH_MASK; |
| int index = hash % table.length; |
| for (Entry e=table[index]; e!=null; e=(Entry) e.next) { |
| final E candidate = e.get(); |
| if (mayContainArrays ? Objects.deepEquals(candidate, obj) : obj.equals(candidate)) { |
| if (operation == REMOVE) { |
| e.dispose(); |
| } |
| return candidate; |
| } |
| // Do not remove the null element; lets ReferenceQueue do its job |
| // (it was a bug to remove element here as an "optimization") |
| } |
| if (operation >= ADD) { |
| /* |
| * Check if the table needs to be rehashed, and add {@code obj} to the table. |
| */ |
| if (++count >= lowerCapacityThreshold(table.length)) { |
| if (count > upperCapacityThreshold(table.length)) { |
| this.table = table = (Entry[]) rehash(table, count, "add"); |
| index = hash % table.length; |
| } |
| lastTimeNormalCapacity = System.nanoTime(); |
| } |
| final E element = elementType.cast(obj); |
| table[index] = new Entry(element, table[index], hash); |
| assert isValid(); |
| if (operation == INTERN) { |
| return element; |
| } |
| } |
| } |
| return null; |
| } |
| |
| /** |
| * Removes all of the elements from this set. |
| */ |
| @Override |
| public synchronized void clear() { |
| Arrays.fill(table, null); |
| count = 0; |
| } |
| |
| /** |
| * Returns a view of this set as an array. Elements will be in an arbitrary |
| * order. Note that this array contains strong references. Consequently, no |
| * object reclamation will occur as long as a reference to this array is hold. |
| * |
| * @return all elements in this set. |
| */ |
| @Override |
| public synchronized E[] toArray() { |
| assert isValid(); |
| @SuppressWarnings("unchecked") |
| final E[] elements = (E[]) Array.newInstance(elementType, count); |
| int index = 0; |
| for (Entry el : table) { |
| while (el != null) { |
| if ((elements[index] = el.get()) != null) { |
| index++; |
| } |
| el = (Entry) el.next; |
| } |
| } |
| return ArraysExt.resize(elements, index); |
| } |
| |
| /** |
| * Returns an iterator over the elements contained in this collection. |
| * No element from this set will be garbage collected as long as a |
| * reference to the iterator is hold. |
| * |
| * @return an iterator over all elements in this set. |
| */ |
| @Override |
| public Iterator<E> iterator() { |
| return Arrays.asList(toArray()).iterator(); |
| } |
| } |