Migrated source code from Simantics SVN

[simantics/platform.git] / bundles / org.simantics.scl.compiler / src / org / simantics / scl / compiler / internal / types / HashConsing.java

diff --git a/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/types/HashConsing.java b/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/types/HashConsing.java
new file mode 100644 (file)
index 0000000..b81478a
--- /dev/null
+++ b/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/types/HashConsing.java
@@ -0,0 +1,121 @@
+package org.simantics.scl.compiler.internal.types;
+
+import java.lang.ref.ReferenceQueue;
+import java.lang.ref.WeakReference;
+
+public class HashConsing<T> {
+
+    private static class Entry<T> extends WeakReference<T> {
+        private final int hash;
+        private Entry<T> next;
+
+        Entry(T value, ReferenceQueue<T> queue, int hash, Entry<T> next) {
+            super(value, queue);
+            this.hash  = hash;
+            this.next  = next;
+        }
+    }
+    
+    private double loadFactor = 0.75;
+    @SuppressWarnings("unchecked")
+    private Entry<T>[] table = new Entry[16];
+    private int size = 0;
+    private int threshold = (int)(table.length * loadFactor);    
+    private final ReferenceQueue<T> queue = new ReferenceQueue<T>();
+    
+    public synchronized T canonical(T candidate) {        
+        int h = hashCode(candidate);
+        expungeStaleEntries();
+        Entry<T>[] tab = table;
+        int i = indexFor(h, tab.length);
+
+        for (Entry<T> e = tab[i]; e != null; e = e.next) {
+            T cur = e.get();
+            if (h == e.hash && cur != null && equals(cur, candidate))
+                return cur;
+        }
+
+        Entry<T> e = tab[i];
+        tab[i] = new Entry<T>(candidate, queue, h, e);
+        if (++size >= threshold)
+            resize(tab.length * 2);
+        return candidate;
+    }
+    
+    private void resize(int newCapacity) {
+        expungeStaleEntries();
+        Entry<T>[] oldTable = table;
+
+        @SuppressWarnings("unchecked")
+        Entry<T>[] newTable = new Entry[newCapacity];
+        transfer(oldTable, newTable);
+        table = newTable;
+
+        if (size >= threshold / 2) {
+            threshold = (int)(newCapacity * loadFactor);
+        } else {
+            expungeStaleEntries();
+            transfer(newTable, oldTable);
+            table = oldTable;
+        }
+    }
+
+    private void transfer(Entry<T>[] src, Entry<T>[] dest) {
+        for (int j = 0; j < src.length; ++j) {
+            Entry<T> e = src[j];
+            src[j] = null;
+            while (e != null) {
+                Entry<T> next = e.next;
+                Object key = e.get();
+                if (key == null) {
+                    e.next = null;
+                    size--;
+                } else {
+                    int i = indexFor(e.hash, dest.length);
+                    e.next = dest[i];
+                    dest[i] = e;
+                }
+                e = next;
+            }
+        }
+    }
+
+    @SuppressWarnings("unchecked")
+    private void expungeStaleEntries() {
+        Entry<T> e;
+        while ( (e = (Entry<T>) queue.poll()) != null) {
+            int h = e.hash;
+            int i = indexFor(h, table.length);
+
+            Entry<T> prev = table[i];
+            Entry<T> p = prev;
+            while (p != null) {
+                Entry<T> next = p.next;
+                if (p == e) {
+                    if (prev == e)
+                        table[i] = next;
+                    else
+                        prev.next = next;
+                    e.next = null;
+                    size--;
+                    break;
+                }
+                prev = p;
+                p = next;
+            }
+        }
+    }
+
+    private static int indexFor(int h, int length) {
+        return h & (length-1);
+    }
+    
+    protected int hashCode(T obj) {
+        return obj.hashCode();
+    }
+    
+    protected boolean equals(T a, T b) {
+        return a.equals(b);
+    }
+    
+}