sis-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From desruisse...@apache.org
Subject svn commit: r1394005 - in /sis/trunk/sis-utility/src/main/java/org/apache/sis/util/collection: Collections.java WeakEntry.java WeakHashSet.java
Date Thu, 04 Oct 2012 11:57:40 GMT
Author: desruisseaux
Date: Thu Oct  4 11:57:40 2012
New Revision: 1394005

URL: http://svn.apache.org/viewvc?rev=1394005&view=rev
Log:
Factored some WeakHashSet internal mechanic in a separated class for easier sharing with WeakValueHashMap.

Added:
    sis/trunk/sis-utility/src/main/java/org/apache/sis/util/collection/WeakEntry.java
      - copied, changed from r1393359, sis/trunk/sis-utility/src/main/java/org/apache/sis/util/collection/WeakHashSet.java
Modified:
    sis/trunk/sis-utility/src/main/java/org/apache/sis/util/collection/Collections.java
    sis/trunk/sis-utility/src/main/java/org/apache/sis/util/collection/WeakHashSet.java

Modified: sis/trunk/sis-utility/src/main/java/org/apache/sis/util/collection/Collections.java
URL: http://svn.apache.org/viewvc/sis/trunk/sis-utility/src/main/java/org/apache/sis/util/collection/Collections.java?rev=1394005&r1=1394004&r2=1394005&view=diff
==============================================================================
--- sis/trunk/sis-utility/src/main/java/org/apache/sis/util/collection/Collections.java (original)
+++ sis/trunk/sis-utility/src/main/java/org/apache/sis/util/collection/Collections.java Thu
Oct  4 11:57:40 2012
@@ -18,7 +18,9 @@ package org.apache.sis.util.collection;
 
 import java.util.*;
 import java.io.Serializable;
+import java.util.logging.Logger;
 import org.apache.sis.util.Static;
+import org.apache.sis.util.logging.Logging;
 
 import static java.util.Collections.list;
 import static java.util.Collections.emptySet;
@@ -55,6 +57,11 @@ import static java.util.Collections.unmo
  */
 public final class Collections extends Static {
     /**
+     * The logger where to logs collection events, if logging at the finest level is enabled.
+     */
+    static final Logger LOGGER = Logging.getLogger(Collections.class);
+
+    /**
      * Do not allow instantiation of this class.
      */
     private Collections() {

Copied: sis/trunk/sis-utility/src/main/java/org/apache/sis/util/collection/WeakEntry.java
(from r1393359, sis/trunk/sis-utility/src/main/java/org/apache/sis/util/collection/WeakHashSet.java)
URL: http://svn.apache.org/viewvc/sis/trunk/sis-utility/src/main/java/org/apache/sis/util/collection/WeakEntry.java?p2=sis/trunk/sis-utility/src/main/java/org/apache/sis/util/collection/WeakEntry.java&p1=sis/trunk/sis-utility/src/main/java/org/apache/sis/util/collection/WeakHashSet.java&r1=1393359&r2=1394005&rev=1394005&view=diff
==============================================================================
--- sis/trunk/sis-utility/src/main/java/org/apache/sis/util/collection/WeakHashSet.java (original)
+++ sis/trunk/sis-utility/src/main/java/org/apache/sis/util/collection/WeakEntry.java Thu
Oct  4 11:57:40 2012
@@ -16,511 +16,166 @@
  */
 package org.apache.sis.util.collection;
 
-import java.util.Arrays;
-import java.util.Iterator;
-import java.util.AbstractSet;
 import java.util.logging.Level;
 import java.util.logging.Logger;
 import java.util.logging.LogRecord;
-import java.lang.reflect.Array;
 import java.lang.ref.WeakReference;
-import net.jcip.annotations.ThreadSafe;
+import java.lang.reflect.Array;
 
-import org.apache.sis.util.Debug;
-import org.apache.sis.util.Utilities;
 import org.apache.sis.util.Disposable;
-import org.apache.sis.util.Workaround;
-import org.apache.sis.util.logging.Logging;
 import org.apache.sis.internal.util.ReferenceQueueConsumer;
 
-import static org.apache.sis.util.Arrays.resize;
-
-// Related to JDK7
-import org.apache.sis.internal.util.Objects;
-
 
 /**
- * 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.
- *
- * {@section Optimizing memory use in factory implementations}
- * 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 = WeakHashSet.newInstance(Foo.class);
- *
- *     public Foo create(String definition) {
- *         Foo created = new Foo(definition);
- *         return pool.unique(created);
- *     }
- * }
+ * A weak reference to an element in a {@link WeakHashSet} or {@link WeakValueHashMap}.
+ * This is an element in a linked list. When the reference is disposed, it is removed
+ * from the enclosing collection.
  *
- * Thus, {@code WeakHashSet} can be used inside a factory to prevent creating duplicate
- * immutable objects.
- *
- * @param <E> The type of elements in the set.
+ * @param <E> The type of elements in the collection.
  *
  * @author  Martin Desruisseaux (MPO, IRD, Geomatys)
  * @since   0.3 (derived from geotk-1.0)
  * @version 0.3
  * @module
- *
- * @see java.util.WeakHashMap
  */
-@ThreadSafe
-public class WeakHashSet<E> extends AbstractSet<E> implements CheckedContainer<E>
{
-    /**
-     * Minimal capacity for {@link #table}.
-     */
-    private static final int MIN_CAPACITY = 21;
-
-    /**
-     * Load factor. Control the moment where {@link #table} must be rebuild.
-     */
-    private static final float LOAD_FACTOR = 0.75f;
-
-    /**
-     * 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 WeakReference<E> implements Disposable {
-        /**
-         * The next entry, or {@code null} if there is none.
-         */
-        Entry next;
-
-        /**
-         * The hash value of this element.
-         */
-        final int hash;
-
-        /**
-         * Constructs a new weak reference.
-         */
-        Entry(final E obj, final Entry next, final int hash) {
-            super(obj, ReferenceQueueConsumer.DEFAULT.queue);
-            assert ReferenceQueueConsumer.DEFAULT.isAlive();
-            this.next = next;
-            this.hash = hash;
-        }
-
-        /**
-         * Clears the reference.
-         */
-        @Override
-        public void dispose() {
-            clear();
-            removeEntry(this);
-        }
-    }
-
+abstract class WeakEntry<E> extends WeakReference<E> implements Disposable {
     /**
-     * Table of weak references.
+     * Minimal capacity for the internal table of entries.
      */
-    private Entry[] table;
+    static final int MIN_CAPACITY = 7;
 
     /**
-     * Number of non-null elements in {@link #table}.
+     * The mask to apply on hash code values for ensuring positive values.
      */
-    private int count;
+    static final int HASH_MASK = Integer.MAX_VALUE;
 
     /**
-     * The type of the elements in this set.
+     * Number of millisecond to wait before to rehash the table for reducing its size.
      */
-    private final Class<E> elementType;
+    static final long HOLD_TIME = 60 * 1000L;
 
     /**
-     * {@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.
+     * The next entry, or {@code null} if there is none.
      */
-    private final boolean mayContainArrays;
+    WeakEntry<E> next;
 
     /**
-     * The next size value at which to resize. This value should
-     * be <code>{@link #table}.length*{@link #LOAD_FACTOR}</code>.
+     * The absolute value of the hash value of the referenced object.
      */
-    private int threshold;
+    final int hash;
 
     /**
-     * Constructs a {@code WeakHashSet} for elements of the specified type.
-     *
-     * @param <E>  The type of elements in the set.
-     * @param type The type of elements in the set.
-     * @return An initially empty set for elements of the given type.
+     * Constructs a new weak reference.
      */
-    public static <E> WeakHashSet<E> newInstance(final Class<E> type) {
-        return new WeakHashSet<E>(type);
+    WeakEntry(final E obj, final WeakEntry<E> next, final int hash) {
+        super(obj, ReferenceQueueConsumer.DEFAULT.queue);
+        assert ReferenceQueueConsumer.DEFAULT.isAlive();
+        this.next = next;
+        this.hash = hash;
     }
 
     /**
-     * Constructs a {@code WeakHashSet} for elements of the specified type.
+     * Counts the number of entries in the given table.
+     * This method does not verify if the referenced object has been garbage collected.
      *
-     * @param type The type of the element to be included in this set.
-     */
-    protected WeakHashSet(final Class<E> type) {
-        this.elementType = type;
-        mayContainArrays = type.isArray() || type.equals(Object.class);
-        final Entry[] table = newEntryTable(MIN_CAPACITY);
-        threshold = Math.round(table.length * LOAD_FACTOR);
-    }
-
-    /**
-     * Sets the {@link #table} array to the specified size. The content of the old array
is lost.
-     * The value is returned for convenience (this is actually a paranoiac safety for making
sure
-     * that the caller will really use the new array, in case of synchronization bug).
-     * <p>
-     * This method is a workaround for the "<cite>generic array creation</cite>"
compiler error.
-     * Otherwise we would use the commented-out line instead.
-     */
-    @Workaround(library="JDK", version="1.7")
-    @SuppressWarnings("unchecked")
-    private Entry[] newEntryTable(final int size) {
-//      table = new Entry[size];
-        return table = (Entry[]) Array.newInstance(Entry.class, size);
-    }
-
-    /**
-     * Returns the type of elements in this set.
+     * @param  <E>   The type of elements in the collection.
+     * @param  table The table in which to count the number of entries.
+     * @return Number of entries in the given table.
      */
-    @Override
-    public Class<E> getElementType() {
-        return elementType;
+    static <E> int count(final WeakEntry<E>[] table) {
+        int n = 0;
+        for (int i=0; i<table.length; i++) {
+            for (WeakEntry<E> e=table[i]; e!=null; e=e.next) {
+                n++;
+            }
+        }
+        return n;
     }
 
     /**
-     * Invoked by {@link Entry} when an element has been collected by the garbage
-     * collector. This method will remove the weak reference from {@link #table}.
+     * Removes this entry from the given table of entries.
+     *
+     * @param  table    The table from which to remove this entry.
+     * @param  removeAt The index of this entry in the given table.
+     * @return {@code true} if this entry has been found and removed, or {@code false} otherwise.
      */
-    private synchronized void removeEntry(final Entry toRemove) {
-        assert valid() : count;
-        final Entry[] table = this.table;
-        final int i = toRemove.hash % table.length;
-        Entry prev = null;
-        Entry e = table[i];
+    final boolean removeFrom(final WeakEntry<E>[] table, final int removeAt) {
+        WeakEntry<E> prev = null;
+        WeakEntry<E> e = table[removeAt];
         while (e != null) {
-            if (e == toRemove) {
+            if (e == this) {
                 if (prev != null) {
                     prev.next = e.next;
                 } else {
-                    table[i] = e.next;
+                    table[removeAt] = e.next;
                 }
-                count--;
-                assert valid();
-                /*
-                 * If the number of elements has dimunished significatively, rehash the table.
-                 * We can't continue the loop pass that point, since 'e' is no longer valid.
-                 */
-                if (count <= threshold/4) {
-                    this.table = rehash("remove");
-                }
-                return;
+                // We can't continue the loop pass that point, since 'e' is no longer valid.
+                return true;
             }
             prev = e;
             e = e.next;
         }
-        assert valid();
-        /*
-         * If we reach this point, its mean that reference 'toRemove' has not
-         * been found. This situation may occurs if 'toRemove' has already been
-         * removed in a previous run of 'rehash'.
-         */
+        return false;
     }
 
     /**
-     * Rehash {@link #table}.
+     * Rehashes the given table.
      *
-     * @param  caller The method invoking this one. User for logging purpose only.
-     * @return The new table array. This is actually the value of the {@link #table} field,
but is
-     *         returned as a paranoiac safety for making sure that the caller uses the table
we just
-     *         created (in case of synchronization bug).
-     */
-    private Entry[] rehash(final String caller) {
-        assert Thread.holdsLock(this);
-        assert valid();
-        final Entry[] oldTable = table;
-        final int capacity = Math.max(Math.round(count / (LOAD_FACTOR/2)), count + MIN_CAPACITY);
+     * @param  oldTable     The table to rehash.
+     * @param  count        Number of elements in the table (including chained elements).
+     * @param  callerMethod The method invoking this one, for logging purpose only. The caller
class
+     *         will be inferred from the enclosing class of the {@code oldTable} component
type. This
+     *         uses the knowledge that all our implementations of {@code WeakEntry} are inner
classes.
+     * @return The new table array, or {@code oldTable} if no rehash were needed.
+     */
+    static <E> WeakEntry<E>[] rehash(final WeakEntry<E>[] oldTable, final
int count, final String callerMethod) {
+        final int capacity = Math.max(count*2, MIN_CAPACITY);
         if (capacity == oldTable.length) {
             return oldTable;
         }
-        final Entry[] table = newEntryTable(capacity);
-        threshold = Math.round(capacity * LOAD_FACTOR);
+        final Class<?> entryType = oldTable.getClass().getComponentType();
+        @SuppressWarnings("unchecked")
+        final WeakEntry<E>[] table = (WeakEntry<E>[]) Array.newInstance(entryType,
capacity);
         for (int i=0; i<oldTable.length; i++) {
-            for (Entry next=oldTable[i]; next!=null;) {
-                final Entry e = next;
+            for (WeakEntry<E> next=oldTable[i]; next!=null;) {
+                final WeakEntry<E> e = next;
                 next = next.next; // We keep 'next' right now because its value will change.
                 final int index = e.hash % table.length;
                 e.next = table[index];
                 table[index] = e;
             }
         }
-        final Logger logger = Logging.getLogger(WeakHashSet.class);
-        final Level   level = Level.FINEST;
-        if (logger.isLoggable(level)) {
-            final LogRecord record = new LogRecord(level,
+        final Logger logger = Collections.LOGGER;
+        if (logger.isLoggable(Level.FINEST)) {
+            final LogRecord record = new LogRecord(Level.FINEST,
                     "Rehash from " + oldTable.length + " to " + table.length);
-            record.setSourceMethodName(caller);
-            record.setSourceClassName(WeakHashSet.class.getName());
+            record.setSourceMethodName(callerMethod);
+            record.setSourceClassName(entryType.getEnclosingClass().getName());
             record.setLoggerName(logger.getName());
             logger.log(record);
         }
-        assert valid();
         return table;
     }
 
     /**
-     * Checks if this {@code WeakHashSet} is valid. This method counts the number of elements
and
-     * compares it to {@link #count}. If the check fails, the number of elements is corrected
(if
-     * we didn't, an {@link AssertionError} would be thrown for every operations after the
first
-     * error, which make debugging more difficult). The set is otherwise unchanged, which
should
-     * help to get similar behavior as if assertions hasn't been turned on.
-     */
-    @Debug
-    private boolean valid() {
-        int n = 0;
-        final Entry[] table = this.table;
-        for (int i=0; i<table.length; i++) {
-            for (Entry e=table[i]; e!=null; e=e.next) {
-                n++;
-            }
-        }
-        if (n != count) {
-            count = n;
-            return false;
-        } else {
-            return true;
-        }
-    }
-
-    /**
-     * Returns the count of element in this set.
+     * IF the number of elements is lower than this threshold, then the table should be
+     * rehashed for saving space.
      *
-     * @return Number of elements in this set.
+     * @param  capacity The table capacity.
+     * @return Minimal number of elements for not rehashing.
      */
-    @Override
-    public synchronized int size() {
-        assert valid();
-        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  obj Element to be added to this set.
-     * @return {@code true} if this set did not already contain the specified element.
-     */
-    @Override
-    public synchronized boolean add(final E obj) {
-        return intern(obj, ADD) == null;
-    }
-
-    /**
-     * Removes a single instance of the specified element from this set, if it is present
-     *
-     * @param  obj element to be removed from this set, if present.
-     * @return {@code true} if the set contained the specified element.
-     */
-    @Override
-    public synchronized boolean remove(final Object obj) {
-        return intern(elementType.cast(obj), REMOVE) != null;
-    }
-
-    /**
-     * Returns an object equals to the specified object, if present. If
-     * this set doesn't contains any object equals to {@code object},
-     * then this method returns {@code null}.
-     *
-     * @param  <T> The type of the element to get.
-     * @param  object 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 <T extends E> T get(final T object) {
-        return intern(object, GET);
-    }
-
-    /**
-     * Returns {@code true} if this set contains the specified element.
-     *
-     * @param  obj Object to be checked for containment in this set.
-     * @return {@code true} if this set contains the specified element.
-     */
-    @Override
-    public synchronized boolean contains(final Object obj) {
-        return obj != null && intern(elementType.cast(obj), GET) != null;
-    }
-
-    /**
-     * Returns an object equals to {@code object} if such an object already exist in this
-     * {@code WeakHashSet}. Otherwise, adds {@code object} to this {@code WeakHashSet}.
-     * This method is equivalents to the following code:
-     *
-     * {@preformat java
-     *     if (object != null) {
-     *         Object current = get(object);
-     *         if (current != null) {
-     *             return current;
-     *         } else {
-     *             add(object);
-     *         }
-     *     }
-     *     return object;
-     * }
-     *
-     * @param  <T> The type of the element to get.
-     * @param  object The element to get or to add in the set if not already presents.
-     * @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 object) {
-        return intern(object, INTERN);
-    }
-
-    /**
-     * Iteratively call {@link #unique(Object)} for an array of objects.
-     * This method is equivalents to the following code:
-     *
-     * {@preformat java
-     *     for (int i=0; i<objects.length; i++) {
-     *         objects[i] = unique(objects[i]);
-     *     }
-     * }
-     *
-     * @param objects
-     *          On input, the objects to add to this set if not already present. On output,
-     *          elements that are {@linkplain Object#equals(Object) equal}, but where every
-     *          reference to an instance already presents in this set has been replaced by
-     *          a reference to the existing instance.
-     */
-    public synchronized void uniques(final E[] objects) {
-        for (int i=0; i<objects.length; i++) {
-            objects[i] = intern(objects[i], 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;
-
-    /**
-     * Returns an object equals to {@code obj} if such an object already exist in this
-     * {@code WeakHashSet}. Otherwise, add {@code obj} to this {@code WeakHashSet}.
-     * This method is equivalents to the following code:
-     *
-     * {@preformat java
-     *     if (object!=null) {
-     *         final Object current = get(object);
-     *         if (current != null) {
-     *             return current;
-     *         } else {
-     *             add(object);
-     *         }
-     *     }
-     *     return object;
-     * }
-     */
-    private <T extends E> T intern(final T obj, final int operation) {
-        assert Thread.holdsLock(this);
-        assert ReferenceQueueConsumer.DEFAULT.isAlive();
-        assert valid() : count;
-        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())
& 0x7FFFFFFF;
-            int index = hash % table.length;
-            for (Entry e=table[index]; e!=null; e=e.next) {
-                final E candidate = e.get();
-                if (mayContainArrays ? Objects.deepEquals(candidate, obj) : obj.equals(candidate))
{
-                    if (operation == REMOVE) {
-                        e.dispose();
-                    }
-                    assert candidate.getClass() == obj.getClass() : candidate;
-                    @SuppressWarnings("unchecked")
-                    final T result = (T) candidate;
-                    return result;
-                }
-                // 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 >= threshold) {
-                    table = rehash("add");
-                    index = hash % table.length;
-                }
-                table[index] = new Entry(obj, table[index], hash);
-                count++;
-            }
-        }
-        assert valid();
-        return (operation == INTERN) ? obj : 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 valid();
-        @SuppressWarnings("unchecked")
-        final E[] elements = (E[]) Array.newInstance(elementType, count);
-        int index = 0;
-        final Entry[] table = this.table;
-        for (int i=0; i<table.length; i++) {
-            for (Entry el=table[i]; el!=null; el=el.next) {
-                if ((elements[index] = el.get()) != null) {
-                    index++;
-                }
-            }
-        }
-        return resize(elements, index);
+    static int lowerCapacityThreshold(final int capacity) {
+        return capacity >>> 2;
     }
 
     /**
-     * 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.
+     * IF the number of elements is upper than this threshold, then the table should be
+     * rehashed for better performance.
      *
-     * @return An iterator over all elements in this set.
+     * @param  capacity The table capacity.
+     * @return Maximal number of elements for not rehashing.
      */
-    @Override
-    public Iterator<E> iterator() {
-        return Arrays.asList(toArray()).iterator();
+    static int upperCapacityThreshold(final int capacity) {
+        return capacity + (capacity >>> 2);
     }
 }

Modified: sis/trunk/sis-utility/src/main/java/org/apache/sis/util/collection/WeakHashSet.java
URL: http://svn.apache.org/viewvc/sis/trunk/sis-utility/src/main/java/org/apache/sis/util/collection/WeakHashSet.java?rev=1394005&r1=1394004&r2=1394005&view=diff
==============================================================================
--- sis/trunk/sis-utility/src/main/java/org/apache/sis/util/collection/WeakHashSet.java (original)
+++ sis/trunk/sis-utility/src/main/java/org/apache/sis/util/collection/WeakHashSet.java Thu
Oct  4 11:57:40 2012
@@ -19,21 +19,17 @@ package org.apache.sis.util.collection;
 import java.util.Arrays;
 import java.util.Iterator;
 import java.util.AbstractSet;
-import java.util.logging.Level;
-import java.util.logging.Logger;
-import java.util.logging.LogRecord;
 import java.lang.reflect.Array;
-import java.lang.ref.WeakReference;
 import net.jcip.annotations.ThreadSafe;
 
 import org.apache.sis.util.Debug;
 import org.apache.sis.util.Utilities;
-import org.apache.sis.util.Disposable;
 import org.apache.sis.util.Workaround;
-import org.apache.sis.util.logging.Logging;
-import org.apache.sis.internal.util.ReferenceQueueConsumer;
+import org.apache.sis.util.ArgumentChecks;
+import org.apache.sis.util.NullArgumentException;
 
 import static org.apache.sis.util.Arrays.resize;
+import static org.apache.sis.util.collection.WeakEntry.*;
 
 // Related to JDK7
 import org.apache.sis.internal.util.Objects;
@@ -83,42 +79,20 @@ import org.apache.sis.internal.util.Obje
 @ThreadSafe
 public class WeakHashSet<E> extends AbstractSet<E> implements CheckedContainer<E>
{
     /**
-     * Minimal capacity for {@link #table}.
-     */
-    private static final int MIN_CAPACITY = 21;
-
-    /**
-     * Load factor. Control the moment where {@link #table} must be rebuild.
-     */
-    private static final float LOAD_FACTOR = 0.75f;
-
-    /**
      * 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 WeakReference<E> implements Disposable {
-        /**
-         * The next entry, or {@code null} if there is none.
-         */
-        Entry next;
-
-        /**
-         * The hash value of this element.
-         */
-        final int hash;
-
+    private final class Entry extends WeakEntry<E> {
         /**
          * Constructs a new weak reference.
          */
         Entry(final E obj, final Entry next, final int hash) {
-            super(obj, ReferenceQueueConsumer.DEFAULT.queue);
-            assert ReferenceQueueConsumer.DEFAULT.isAlive();
-            this.next = next;
-            this.hash = hash;
+            super(obj, next, hash);
         }
 
         /**
-         * Clears the reference.
+         * Invoked by {@link org.apache.sis.internal.util.ReferenceQueueConsumer}
+         * for removing the reference from the enclosing collection.
          */
         @Override
         public void dispose() {
@@ -149,13 +123,7 @@ public class WeakHashSet<E> extends Abst
     private final boolean mayContainArrays;
 
     /**
-     * The next size value at which to resize. This value should
-     * be <code>{@link #table}.length*{@link #LOAD_FACTOR}</code>.
-     */
-    private int threshold;
-
-    /**
-     * Constructs a {@code WeakHashSet} for elements of the specified type.
+     * Creates a {@code WeakHashSet} for elements of the specified type.
      *
      * @param <E>  The type of elements in the set.
      * @param type The type of elements in the set.
@@ -166,30 +134,22 @@ public class WeakHashSet<E> extends Abst
     }
 
     /**
-     * Constructs a {@code WeakHashSet} for elements of the specified type.
+     * Creates a {@code WeakHashSet} for elements of the specified type.
      *
      * @param type The type of the element to be included in this set.
      */
     protected WeakHashSet(final Class<E> type) {
-        this.elementType = type;
+        elementType      = type;
         mayContainArrays = type.isArray() || type.equals(Object.class);
-        final Entry[] table = newEntryTable(MIN_CAPACITY);
-        threshold = Math.round(table.length * LOAD_FACTOR);
-    }
-
-    /**
-     * Sets the {@link #table} array to the specified size. The content of the old array
is lost.
-     * The value is returned for convenience (this is actually a paranoiac safety for making
sure
-     * that the caller will really use the new array, in case of synchronization bug).
-     * <p>
-     * This method is a workaround for the "<cite>generic array creation</cite>"
compiler error.
-     * Otherwise we would use the commented-out line instead.
-     */
-    @Workaround(library="JDK", version="1.7")
-    @SuppressWarnings("unchecked")
-    private Entry[] newEntryTable(final int size) {
+        /*
+         * 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];
-        return table = (Entry[]) Array.newInstance(Entry.class, size);
+        this.table = table;
     }
 
     /**
@@ -202,82 +162,19 @@ public class WeakHashSet<E> extends Abst
 
     /**
      * Invoked by {@link Entry} when an element has been collected by the garbage
-     * collector. This method will remove the weak reference from {@link #table}.
+     * collector. This method removes the weak reference from the {@link #table}.
      */
     private synchronized void removeEntry(final Entry toRemove) {
-        assert valid() : count;
-        final Entry[] table = this.table;
-        final int i = toRemove.hash % table.length;
-        Entry prev = null;
-        Entry e = table[i];
-        while (e != null) {
-            if (e == toRemove) {
-                if (prev != null) {
-                    prev.next = e.next;
-                } else {
-                    table[i] = e.next;
-                }
-                count--;
-                assert valid();
-                /*
-                 * If the number of elements has dimunished significatively, rehash the table.
-                 * We can't continue the loop pass that point, since 'e' is no longer valid.
-                 */
-                if (count <= threshold/4) {
-                    this.table = rehash("remove");
-                }
-                return;
-            }
-            prev = e;
-            e = e.next;
-        }
-        assert valid();
-        /*
-         * If we reach this point, its mean that reference 'toRemove' has not
-         * been found. This situation may occurs if 'toRemove' has already been
-         * removed in a previous run of 'rehash'.
-         */
-    }
-
-    /**
-     * Rehash {@link #table}.
-     *
-     * @param  caller The method invoking this one. User for logging purpose only.
-     * @return The new table array. This is actually the value of the {@link #table} field,
but is
-     *         returned as a paranoiac safety for making sure that the caller uses the table
we just
-     *         created (in case of synchronization bug).
-     */
-    private Entry[] rehash(final String caller) {
-        assert Thread.holdsLock(this);
-        assert valid();
-        final Entry[] oldTable = table;
-        final int capacity = Math.max(Math.round(count / (LOAD_FACTOR/2)), count + MIN_CAPACITY);
-        if (capacity == oldTable.length) {
-            return oldTable;
-        }
-        final Entry[] table = newEntryTable(capacity);
-        threshold = Math.round(capacity * LOAD_FACTOR);
-        for (int i=0; i<oldTable.length; i++) {
-            for (Entry next=oldTable[i]; next!=null;) {
-                final Entry e = next;
-                next = next.next; // We keep 'next' right now because its value will change.
-                final int index = e.hash % table.length;
-                e.next = table[index];
-                table[index] = e;
+        assert isValid();
+        final int capacity = table.length;
+        if (toRemove.removeFrom(table, toRemove.hash % capacity)) {
+            count--;
+            assert isValid();
+            if (count < lowerCapacityThreshold(capacity)) {
+                table = (Entry[]) WeakEntry.rehash(table, count, "remove");
+                assert isValid();
             }
         }
-        final Logger logger = Logging.getLogger(WeakHashSet.class);
-        final Level   level = Level.FINEST;
-        if (logger.isLoggable(level)) {
-            final LogRecord record = new LogRecord(level,
-                    "Rehash from " + oldTable.length + " to " + table.length);
-            record.setSourceMethodName(caller);
-            record.setSourceClassName(WeakHashSet.class.getName());
-            record.setLoggerName(logger.getName());
-            logger.log(record);
-        }
-        assert valid();
-        return table;
     }
 
     /**
@@ -288,14 +185,10 @@ public class WeakHashSet<E> extends Abst
      * help to get similar behavior as if assertions hasn't been turned on.
      */
     @Debug
-    private boolean valid() {
-        int n = 0;
-        final Entry[] table = this.table;
-        for (int i=0; i<table.length; i++) {
-            for (Entry e=table[i]; e!=null; e=e.next) {
-                n++;
-            }
-        }
+    private boolean isValid() {
+        assert Thread.holdsLock(this);
+        assert count <= upperCapacityThreshold(table.length);
+        final int n = count(table);
         if (n != count) {
             count = n;
             return false;
@@ -311,7 +204,7 @@ public class WeakHashSet<E> extends Abst
      */
     @Override
     public synchronized int size() {
-        assert valid();
+        assert isValid();
         return count;
     }
 
@@ -320,76 +213,81 @@ public class WeakHashSet<E> extends Abst
      * If this set already contains the specified element, the call leaves
      * this set unchanged and returns {@code false}.
      *
-     * @param  obj Element to be added to this set.
+     * @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 obj) {
-        return intern(obj, ADD) == null;
+    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  obj element to be removed from this set, if 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 obj) {
-        return intern(elementType.cast(obj), REMOVE) != null;
+    public synchronized boolean remove(final Object element) {
+        return intern(elementType.cast(element), REMOVE) != null;
     }
 
     /**
-     * Returns an object equals to the specified object, if present. If
-     * this set doesn't contains any object equals to {@code object},
-     * then this method returns {@code 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  <T> The type of the element to get.
-     * @param  object The element to get.
+     * @param  <T> The type of the element to get. Can be {@code null}.
+     * @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 <T extends E> T get(final T object) {
-        return intern(object, GET);
+    public synchronized <T extends E> T get(final T element) {
+        return intern(element, GET);
     }
 
     /**
      * Returns {@code true} if this set contains the specified element.
+     * Null values are considered never present.
      *
-     * @param  obj Object to be checked for containment in this set.
+     * @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 obj) {
-        return obj != null && intern(elementType.cast(obj), GET) != null;
+    public synchronized boolean contains(final Object element) {
+        return intern(element, GET) != null;
     }
 
     /**
-     * Returns an object equals to {@code object} if such an object already exist in this
-     * {@code WeakHashSet}. Otherwise, adds {@code object} to this {@code WeakHashSet}.
-     * This method is equivalents to the following code:
+     * 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 (object != null) {
-     *         Object current = get(object);
+     *     if (element != null) {
+     *         T current = get(element);
      *         if (current != null) {
      *             return current;
      *         } else {
-     *             add(object);
+     *             add(element);
      *         }
      *     }
-     *     return object;
+     *     return element;
      * }
      *
-     * @param  <T> The type of the element to get.
-     * @param  object The element to get or to add in the set if not already presents.
+     * @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 object) {
-        return intern(object, INTERN);
+    public synchronized <T extends E> T unique(final T element) {
+        return intern(element, INTERN);
     }
 
     /**
@@ -397,20 +295,19 @@ public class WeakHashSet<E> extends Abst
      * This method is equivalents to the following code:
      *
      * {@preformat java
-     *     for (int i=0; i<objects.length; i++) {
-     *         objects[i] = unique(objects[i]);
+     *     for (int i=0; i<elements.length; i++) {
+     *         elements[i] = unique(elements[i]);
      *     }
      * }
      *
-     * @param objects
+     * @param elements
      *          On input, the objects to add to this set if not already present. On output,
-     *          elements that are {@linkplain Object#equals(Object) equal}, but where every
-     *          reference to an instance already presents in this set has been replaced by
-     *          a reference to the existing instance.
-     */
-    public synchronized void uniques(final E[] objects) {
-        for (int i=0; i<objects.length; i++) {
-            objects[i] = intern(objects[i], INTERN);
+     *          elements that are equal, but where every reference to an instance already
+     *          presents in this set has been replaced by a reference to the existing instance.
+     */
+    public synchronized void uniques(final E[] elements) {
+        for (int i=0; i<elements.length; i++) {
+            elements[i] = intern(elements[i], INTERN);
         }
     }
 
@@ -437,28 +334,26 @@ public class WeakHashSet<E> extends Abst
      *     return object;
      * }
      */
-    private <T extends E> T intern(final T obj, final int operation) {
-        assert Thread.holdsLock(this);
-        assert ReferenceQueueConsumer.DEFAULT.isAlive();
-        assert valid() : count;
+    private <T> T intern(final T 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())
& 0x7FFFFFFF;
+            final int hash = (mayContainArrays ? Utilities.deepHashCode(obj) : obj.hashCode())
& HASH_MASK;
             int index = hash % table.length;
-            for (Entry e=table[index]; e!=null; e=e.next) {
+            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();
                     }
-                    assert candidate.getClass() == obj.getClass() : candidate;
-                    @SuppressWarnings("unchecked")
-                    final T result = (T) candidate;
-                    return result;
+                    // 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) candidate;
                 }
                 // Do not remove the null element; lets ReferenceQueue do its job
                 // (it was a bug to remove element here as an "optimization")
@@ -467,15 +362,15 @@ public class WeakHashSet<E> extends Abst
                 /*
                  * Check if the table needs to be rehashed, and add {@code obj} to the table.
                  */
-                if (count >= threshold) {
-                    table = rehash("add");
+                if (count >= upperCapacityThreshold(table.length)) {
+                    this.table = table = (Entry[]) rehash(table, count, "add");
                     index = hash % table.length;
                 }
-                table[index] = new Entry(obj, table[index], hash);
+                table[index] = new Entry(elementType.cast(obj), table[index], hash);
                 count++;
             }
         }
-        assert valid();
+        assert isValid();
         return (operation == INTERN) ? obj : null;
     }
 
@@ -497,13 +392,13 @@ public class WeakHashSet<E> extends Abst
      */
     @Override
     public synchronized E[] toArray() {
-        assert valid();
+        assert isValid();
         @SuppressWarnings("unchecked")
         final E[] elements = (E[]) Array.newInstance(elementType, count);
         int index = 0;
         final Entry[] table = this.table;
         for (int i=0; i<table.length; i++) {
-            for (Entry el=table[i]; el!=null; el=el.next) {
+            for (Entry el=table[i]; el!=null; el=(Entry) el.next) {
                 if ((elements[index] = el.get()) != null) {
                     index++;
                 }



Mime
View raw message