bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/types/HashConsing.java

   1 package org.simantics.scl.compiler.internal.types;
   2
   3 import java.lang.ref.ReferenceQueue;
   4 import java.lang.ref.WeakReference;
   5
   6 public class HashConsing<T> {
   7
   8     private static class Entry<T> extends WeakReference<T> {
   9         private final int hash;
  10         private Entry<T> next;
  11
  12         Entry(T value, ReferenceQueue<T> queue, int hash, Entry<T> next) {
  13             super(value, queue);
  14             this.hash  = hash;
  15             this.next  = next;
  16         }
  17     }
  18
  19     private double loadFactor = 0.75;
  20     @SuppressWarnings("unchecked")
  21     private Entry<T>[] table = new Entry[16];
  22     private int size = 0;
  23     private int threshold = (int)(table.length * loadFactor);
  24     private final ReferenceQueue<T> queue = new ReferenceQueue<T>();
  25
  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);
  31
  32         for (Entry<T> e = tab[i]; e != null; e = e.next) {
  33             T cur = e.get();
  34             if (h == e.hash && cur != null && equals(cur, candidate))
  35                 return cur;
  36         }
  37
  38         Entry<T> e = tab[i];
  39         tab[i] = new Entry<T>(candidate, queue, h, e);
  40         if (++size >= threshold)
  41             resize(tab.length * 2);
  42         return candidate;
  43     }
  44
  45     private void resize(int newCapacity) {
  46         expungeStaleEntries();
  47         Entry<T>[] oldTable = table;
  48
  49         @SuppressWarnings("unchecked")
  50         Entry<T>[] newTable = new Entry[newCapacity];
  51         transfer(oldTable, newTable);
  52         table = newTable;
  53
  54         if (size >= threshold / 2) {
  55             threshold = (int)(newCapacity * loadFactor);
  56         } else {
  57             expungeStaleEntries();
  58             transfer(newTable, oldTable);
  59             table = oldTable;
  60         }
  61     }
  62
  63     private void transfer(Entry<T>[] src, Entry<T>[] dest) {
  64         for (int j = 0; j < src.length; ++j) {
  65             Entry<T> e = src[j];
  66             src[j] = null;
  67             while (e != null) {
  68                 Entry<T> next = e.next;
  69                 Object key = e.get();
  70                 if (key == null) {
  71                     e.next = null;
  72                     size--;
  73                 } else {
  74                     int i = indexFor(e.hash, dest.length);
  75                     e.next = dest[i];
  76                     dest[i] = e;
  77                 }
  78                 e = next;
  79             }
  80         }
  81     }
  82
  83     @SuppressWarnings("unchecked")
  84     private void expungeStaleEntries() {
  85         Entry<T> e;
  86         while ( (e = (Entry<T>) queue.poll()) != null) {
  87             int h = e.hash;
  88             int i = indexFor(h, table.length);
  89
  90             Entry<T> prev = table[i];
  91             Entry<T> p = prev;
  92             while (p != null) {
  93                 Entry<T> next = p.next;
  94                 if (p == e) {
  95                     if (prev == e)
  96                         table[i] = next;
  97                     else
  98                         prev.next = next;
  99                     e.next = null;
 100                     size--;
 101                     break;
 102                 }
 103                 prev = p;
 104                 p = next;
 105             }
 106         }
 107     }
 108
 109     private static int indexFor(int h, int length) {
 110         return h & (length-1);
 111     }
 112
 113     protected int hashCode(T obj) {
 114         return obj.hashCode();
 115     }
 116
 117     protected boolean equals(T a, T b) {
 118         return a.equals(b);
 119     }
 120
 121 }