diff options
| -rw-r--r-- | plugins/org.eclipse.net4j.util/src/org/eclipse/net4j/util/ref/Interner.java | 249 |
1 files changed, 249 insertions, 0 deletions
diff --git a/plugins/org.eclipse.net4j.util/src/org/eclipse/net4j/util/ref/Interner.java b/plugins/org.eclipse.net4j.util/src/org/eclipse/net4j/util/ref/Interner.java new file mode 100644 index 0000000000..6c85849b2b --- /dev/null +++ b/plugins/org.eclipse.net4j.util/src/org/eclipse/net4j/util/ref/Interner.java @@ -0,0 +1,249 @@ +/* + * Copyright (c) 2004 - 2012 Eike Stepper (Berlin, Germany) 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: + * Ed Merks - initial API and implementation + */ +package org.eclipse.net4j.util.ref; + +import java.lang.ref.ReferenceQueue; +import java.lang.ref.WeakReference; + +/** + * @author Ed Merks + * @since 3.3 + */ +public class Interner<E> +{ + private static final int[] PRIME_CAPACITIES = new int[] { 17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209, 16411, + 32771, 65537, 131101, 262147, 524309, 1048583, 2097169, 4194319, 8388617, 16777259, 33554467, 67108879, + 134217757, 268435459, 536870923, 1073741827, 2147483629 }; + + private int size; + + private int capacityIndex; + + private Entry<E>[] entries; + + private ReferenceQueue<E> queue = new ReferenceQueue<E>(); + + public Interner() + { + } + + public E intern(E object) + { + cleanup(); + + int hashCode = hashCode(object); + if (entries != null) + { + int index = index(hashCode); + for (Entry<E> entry = entries[index]; entry != null; entry = entry.next) + { + if (hashCode == entry.hashCode) + { + E otherObject = entry.get(); + if (equals(object, otherObject)) + { + return otherObject; + } + } + } + } + + Entry<E> entry = createEntry(object, hashCode); + addEntry(entry); + return object; + } + + /** + * Gets the first entry in the table with exactly the given hash code. + * It's very useful to call {@link Entry#getNextEntry()} to yield the next entry with exactly this same hash code. + */ + protected Entry<E> getEntry(int hashCode) + { + cleanup(); + + if (entries != null) + { + int index = index(hashCode); + for (Entry<E> entry = entries[index]; entry != null; entry = entry.next) + { + if (hashCode == entry.hashCode) + { + return entry; + } + } + } + + return null; + } + + protected int hashCode(E object) + { + return object.hashCode(); + } + + /** + * Returns true if the two objects are to be considered equal. + * The first object will always be the one passed in as an argument to {@link #add(Object) add}, + * {@link #contains(Object) contains}, {@link #get(Object) get}, {@link #intern(Object)}, {@link #remove(Object)}. + */ + protected boolean equals(E object, E otherObject) + { + return object == otherObject || object.equals(otherObject); + } + + protected Entry<E> createEntry(E object, int hashCode) + { + return new Entry<E>(object, hashCode, queue); + } + + /** + * Adds a new entry, {@link #ensureCapacity() ensures} the capacity is sufficient and increases the {@link #size}. + */ + protected void addEntry(Entry<E> entry) + { + ensureCapacity(); + ++size; + putEntry(entry); + } + + private Entry<E>[] newEntries(int capacity) + { + @SuppressWarnings("unchecked") + Entry<E>[] newEntries = new Entry[capacity]; + return newEntries; + } + + private void ensureCapacity() + { + int capacity = PRIME_CAPACITIES[capacityIndex]; + if (entries == null) + { + entries = newEntries(capacity); + } + else if (size > (capacity >> 2) * 3) + { + // The current size is more the 3/4 of the current capacity + ++capacityIndex; + rehash(newEntries(PRIME_CAPACITIES[capacityIndex])); + } + } + + private void rehash(Entry<E>[] newEntries) + { + Entry<E>[] oldEntries = entries; + entries = newEntries; + if (oldEntries != null) + { + for (int i = 0, length = oldEntries.length; i < length; ++i) + { + Entry<E> entry = oldEntries[i]; + while (entry != null) + { + Entry<E> nextEntry = entry.next; + putEntry(entry); + entry = nextEntry; + } + } + } + } + + private int index(int hashCode) + { + return (hashCode & 0x7FFFFFFF) % entries.length; + } + + private void putEntry(Entry<E> entry) + { + int index = index(entry.hashCode); + Entry<E> otherEntry = entries[index]; + entries[index] = entry; + entry.next = otherEntry; + } + + private void cleanup() + { + for (;;) + { + @SuppressWarnings("unchecked") + Entry<E> entry = (Entry<E>)queue.poll(); + if (entry == null) + { + return; + } + + removeEntry(entry); + } + } + + private void removeEntry(Entry<E> entry) + { + int index = index(entry.hashCode); + Entry<E> otherEntry = entries[index]; + --size; + if (entry == otherEntry) + { + entries[index] = entry.next; + } + else + { + for (Entry<E> nextOtherEntry = otherEntry.next; nextOtherEntry != null; otherEntry = nextOtherEntry, nextOtherEntry = nextOtherEntry.next) + { + if (nextOtherEntry == entry) + { + otherEntry.next = entry.next; + break; + } + } + } + + // Make life easier for the garbage collector. + entry.next = null; + entry.clear(); + } + + /** + * A weak reference holder that caches the hash code of the referent and is chained in the {@link Interner#entries} to handle collisions. + * + * @author Ed Merks + */ + protected static class Entry<E> extends WeakReference<E> + { + public final int hashCode; + + public Entry<E> next; + + public Entry(E object, int hashCode, ReferenceQueue<? super E> queue) + { + super(object, queue); + this.hashCode = hashCode; + } + + public Entry<E> getNextEntry() + { + for (Entry<E> entry = next; entry != null; entry = entry.next) + { + if (entry.hashCode == hashCode) + { + return entry; + } + } + + return null; + } + + @Override + public String toString() + { + E object = get(); + return object == null ? "null" : object.toString(); + } + } +} |