1 package org.simantics.scl.compiler.internal.types;
3 import java.lang.ref.ReferenceQueue;
4 import java.lang.ref.WeakReference;
6 public class HashConsing<T> {
8 private static class Entry<T> extends WeakReference<T> {
9 private final int hash;
10 private Entry<T> next;
12 Entry(T value, ReferenceQueue<T> queue, int hash, Entry<T> next) {
19 private double loadFactor = 0.75;
20 @SuppressWarnings("unchecked")
21 private Entry<T>[] table = new Entry[16];
23 private int threshold = (int)(table.length * loadFactor);
24 private final ReferenceQueue<T> queue = new ReferenceQueue<T>();
26 public synchronized T canonical(T candidate) {
27 int h = hashCode(candidate);
28 expungeStaleEntries();
29 Entry<T>[] tab = table;
30 int i = indexFor(h, tab.length);
32 for (Entry<T> e = tab[i]; e != null; e = e.next) {
34 if (h == e.hash && cur != null && equals(cur, candidate))
39 tab[i] = new Entry<T>(candidate, queue, h, e);
40 if (++size >= threshold)
41 resize(tab.length * 2);
45 private void resize(int newCapacity) {
46 expungeStaleEntries();
47 Entry<T>[] oldTable = table;
49 @SuppressWarnings("unchecked")
50 Entry<T>[] newTable = new Entry[newCapacity];
51 transfer(oldTable, newTable);
54 if (size >= threshold / 2) {
55 threshold = (int)(newCapacity * loadFactor);
57 expungeStaleEntries();
58 transfer(newTable, oldTable);
63 private void transfer(Entry<T>[] src, Entry<T>[] dest) {
64 for (int j = 0; j < src.length; ++j) {
68 Entry<T> next = e.next;
74 int i = indexFor(e.hash, dest.length);
83 @SuppressWarnings("unchecked")
84 private void expungeStaleEntries() {
86 while ( (e = (Entry<T>) queue.poll()) != null) {
88 int i = indexFor(h, table.length);
90 Entry<T> prev = table[i];
93 Entry<T> next = p.next;
109 private static int indexFor(int h, int length) {
110 return h & (length-1);
113 protected int hashCode(T obj) {
114 return obj.hashCode();
117 protected boolean equals(T a, T b) {