Changeset 12965


Ignore:
Timestamp:
10/09/10 20:50:41 (12 years ago)
Author:
ehuelsmann
Message:

Reduce our number of hash table implementations to 1 (from 4)
by abstracting out the concept of "key equality" and "hash code
retrieval" into a Comparator class.

The other classes are left in place for now, but have been reduced
to simple wrappers around the HashTable? class.

While at it, reformat HashTable?.java (sorry about that -

it obfuscates the functional changes).

Location:
trunk/abcl/src/org/armedbear/lisp
Files:
5 edited

Legend:

Unmodified
Added
Removed

  • trunk/abcl/src/org/armedbear/lisp/EqHashTable.java

    r12946 r12965  
    3636public final class EqHashTable extends HashTable
    3737{
    38     private LispObject cachedKey;
    39     private int cachedIndex;
    40 
    41     private int mask;
    42 
    4338    public EqHashTable(int size, LispObject rehashSize,
    4439                       LispObject rehashThreshold)
    4540    {
    46         super(calculateInitialCapacity(size), rehashSize, rehashThreshold);
    47         mask = buckets.length - 1;
    48     }
    49 
    50     @Override
    51     public Symbol getTest()
    52     {
    53         return Symbol.EQ;
    54     }
    55 
    56     @Override
    57     public synchronized LispObject get(LispObject key)
    58     {
    59         final int index;
    60         if (key == cachedKey) {
    61             index = cachedIndex;
    62         } else {
    63             index = key.sxhash() & mask;
    64             cachedKey = key;
    65             cachedIndex = index;
    66         }
    67         HashEntry e = buckets[index];
    68         while (e != null) {
    69             if (key == e.key)
    70                 return e.value;
    71             e = e.next;
    72         }
    73         return null;
    74     }
    75 
    76     @Override
    77     public synchronized void put(LispObject key, LispObject value)
    78     {
    79         int index;
    80         if (key == cachedKey) {
    81             index = cachedIndex;
    82         } else {
    83             index = key.sxhash() & mask;
    84             cachedKey = key;
    85             cachedIndex = index;
    86         }
    87         HashEntry e = buckets[index];
    88         while (e != null) {
    89             if (key == e.key) {
    90                 e.value = value;
    91                 return;
    92             }
    93             e = e.next;
    94         }
    95         // Not found. We need to add a new entry.
    96         if (++count > threshold) {
    97             rehash();
    98             // Need a new hash value to suit the bigger table.
    99             index = key.sxhash() & mask;
    100             cachedKey = key;
    101             cachedIndex = index;
    102         }
    103         e = new HashEntry(key, value);
    104         e.next = buckets[index];
    105         buckets[index] = e;
    106     }
    107 
    108     @Override
    109     public LispObject remove(LispObject key)
    110     {
    111         final int index;
    112         if (key == cachedKey) {
    113             index = cachedIndex;
    114         } else {
    115             index = key.sxhash() & mask;
    116             cachedKey = key;
    117             cachedIndex = index;
    118         }
    119         HashEntry e = buckets[index];
    120         HashEntry last = null;
    121         while (e != null) {
    122             if (key == e.key) {
    123                 if (last == null)
    124                     buckets[index] = e.next;
    125                 else
    126                     last.next = e.next;
    127                 --count;
    128                 return e.value;
    129             }
    130             last = e;
    131             e = e.next;
    132         }
    133         return null;
    134     }
    135 
    136     @Override
    137     protected void rehash()
    138     {
    139         cachedKey = null; // Invalidate the cache!
    140         HashEntry[] oldBuckets = buckets;
    141         final int newCapacity = buckets.length * 2;
    142         threshold = (int) (newCapacity * loadFactor);
    143         buckets = new HashEntry[newCapacity];
    144         mask = buckets.length - 1;
    145         for (int i = oldBuckets.length; i-- > 0;) {
    146             HashEntry e = oldBuckets[i];
    147             while (e != null) {
    148                 final int index = e.key.sxhash() & mask;
    149                 HashEntry dest = buckets[index];
    150                 if (dest != null) {
    151                     while (dest.next != null)
    152                         dest = dest.next;
    153                     dest.next = e;
    154                 } else
    155                     buckets[index] = e;
    156                 HashEntry next = e.next;
    157                 e.next = null;
    158                 e = next;
    159             }
    160         }
     41        super(new Comparator(), calculateInitialCapacity(size),
     42                rehashSize, rehashThreshold);
    16143    }
    16244}

  • trunk/abcl/src/org/armedbear/lisp/EqlHashTable.java

    r12963 r12965  
    3636public final class EqlHashTable extends HashTable
    3737{
    38   private int mask;
    39 
    4038  public EqlHashTable(int size, LispObject rehashSize,
    4139                      LispObject rehashThreshold)
    4240  {
    43     super(calculateInitialCapacity(size), rehashSize, rehashThreshold);
    44     mask = buckets.length - 1;
    45   }
    46 
    47   @Override
    48   public Symbol getTest()
    49   {
    50     return Symbol.EQL;
    51   }
    52 
    53   @Override
    54   public synchronized LispObject get(LispObject key)
    55   {
    56     HashEntry e = buckets[key.sxhash() & mask];
    57     while (e != null)
    58       {
    59         if (key.eql(e.key))
    60           return e.value;
    61         e = e.next;
    62       }
    63     return null;
    64   }
    65 
    66   @Override
    67   public synchronized void put(LispObject key, LispObject value)
    68   {
    69     int index = key.sxhash() & mask;
    70     HashEntry e = buckets[index];
    71     while (e != null)
    72       {
    73         if (key.eql(e.key))
    74           {
    75             e.value = value;
    76             return;
    77           }
    78         e = e.next;
    79       }
    80     // Not found. We need to add a new entry.
    81     if (++count > threshold)
    82       {
    83         rehash();
    84         // Need a new hash value to suit the bigger table.
    85         index = key.sxhash() & mask;
    86       }
    87     e = new HashEntry(key, value);
    88     e.next = buckets[index];
    89     buckets[index] = e;
    90   }
    91 
    92   @Override
    93   public LispObject remove(LispObject key)
    94   {
    95     final int index = key.sxhash() & mask;
    96     HashEntry e = buckets[index];
    97     HashEntry last = null;
    98     while (e != null)
    99       {
    100         if (key.eql(e.key))
    101           {
    102             if (last == null)
    103               buckets[index] = e.next;
    104             else
    105               last.next = e.next;
    106             --count;
    107             return e.value;
    108           }
    109         last = e;
    110         e = e.next;
    111       }
    112     return null;
    113   }
    114 
    115   @Override
    116   protected void rehash()
    117   {
    118     HashEntry[] oldBuckets = buckets;
    119     int newCapacity = buckets.length * 2;
    120     threshold = (int) (newCapacity * loadFactor);
    121     buckets = new HashEntry[newCapacity];
    122     mask = buckets.length - 1;
    123     for (int i = oldBuckets.length; i-- > 0;)
    124       {
    125         HashEntry e = oldBuckets[i];
    126         while (e != null)
    127           {
    128             final int index = e.key.sxhash() & mask;
    129             HashEntry dest = buckets[index];
    130             if (dest != null)
    131               {
    132                 while (dest.next != null)
    133                   dest = dest.next;
    134                 dest.next = e;
    135               }
    136             else
    137               buckets[index] = e;
    138             HashEntry next = e.next;
    139             e.next = null;
    140             e = next;
    141           }
    142       }
     41    super(new EqlComparator(), calculateInitialCapacity(size),
     42            rehashSize, rehashThreshold);
    14343  }
    14444}

  • trunk/abcl/src/org/armedbear/lisp/EqualHashTable.java

    r12946 r12965  
    3636public final class EqualHashTable extends HashTable
    3737{
    38   private int mask;
    39 
    4038  public EqualHashTable(int size, LispObject rehashSize,
    4139                        LispObject rehashThreshold)
    4240  {
    43     super(calculateInitialCapacity(size), rehashSize, rehashThreshold);
    44     mask = buckets.length - 1;
    45   }
    46 
    47   @Override
    48   public Symbol getTest()
    49   {
    50     return Symbol.EQUAL;
    51   }
    52 
    53   @Override
    54   public synchronized LispObject get(LispObject key)
    55   {
    56     HashEntry e = buckets[key.sxhash() & mask];
    57     while (e != null)
    58       {
    59         if (key == e.key || key.equal(e.key))
    60           return e.value;
    61         e = e.next;
    62       }
    63     return null;
    64   }
    65 
    66   @Override
    67   public synchronized void put(LispObject key, LispObject value)
    68   {
    69     int index = key.sxhash() & mask;
    70     HashEntry e = buckets[index];
    71     while (e != null)
    72       {
    73         if (key == e.key || key.equal(e.key))
    74           {
    75             e.value = value;
    76             return;
    77           }
    78         e = e.next;
    79       }
    80     // Not found. We need to add a new entry.
    81     if (++count > threshold)
    82       {
    83         rehash();
    84         // Need a new hash value to suit the bigger table.
    85         index = key.sxhash() & mask;
    86       }
    87     e = new HashEntry(key, value);
    88     e.next = buckets[index];
    89     buckets[index] = e;
    90   }
    91 
    92   @Override
    93   public LispObject remove(LispObject key)
    94   {
    95     final int index = key.sxhash() & mask;
    96     HashEntry e = buckets[index];
    97     HashEntry last = null;
    98     while (e != null)
    99       {
    100         if (key == e.key || key.equal(e.key))
    101           {
    102             if (last == null)
    103               buckets[index] = e.next;
    104             else
    105               last.next = e.next;
    106             --count;
    107             return e.value;
    108           }
    109         last = e;
    110         e = e.next;
    111       }
    112     return null;
    113   }
    114 
    115   @Override
    116   protected void rehash()
    117   {
    118     HashEntry[] oldBuckets = buckets;
    119     int newCapacity = buckets.length * 2;
    120     threshold = (int) (newCapacity * loadFactor);
    121     buckets = new HashEntry[newCapacity];
    122     mask = buckets.length - 1;
    123     for (int i = oldBuckets.length; i-- > 0;)
    124       {
    125         HashEntry e = oldBuckets[i];
    126         while (e != null)
    127           {
    128             final int index = e.key.sxhash() & mask;
    129             HashEntry dest = buckets[index];
    130             if (dest != null)
    131               {
    132                 while (dest.next != null)
    133                   dest = dest.next;
    134                 dest.next = e;
    135               }
    136             else
    137               buckets[index] = e;
    138             HashEntry next = e.next;
    139             e.next = null;
    140             e = next;
    141           }
    142       }
     41    super(new EqualComparator(), calculateInitialCapacity(size),
     42            rehashSize, rehashThreshold);
    14343  }
    14444}

  • trunk/abcl/src/org/armedbear/lisp/EqualpHashTable.java

    r12946 r12965  
    3939                         LispObject rehashThreshold)
    4040  {
    41     super(size, rehashSize, rehashThreshold);
    42   }
    43 
    44   @Override
    45   public Symbol getTest()
    46   {
    47     return Symbol.EQUALP;
    48   }
    49 
    50   @Override
    51   public synchronized LispObject get(LispObject key)
    52   {
    53     final int index = key.psxhash() % buckets.length;
    54     HashEntry e = buckets[index];
    55     while (e != null)
    56       {
    57         if (key.equalp(e.key))
    58           return e.value;
    59         e = e.next;
    60       }
    61     return null;
    62   }
    63 
    64   @Override
    65   public synchronized void put(LispObject key, LispObject value)
    66   {
    67     int index = key.psxhash() % buckets.length;
    68     HashEntry e = buckets[index];
    69     while (e != null)
    70       {
    71         if (key.equalp(e.key))
    72           {
    73             e.value = value;
    74             return;
    75           }
    76         e = e.next;
    77       }
    78     // Not found. We need to add a new entry.
    79     if (++count > threshold)
    80       {
    81         rehash();
    82         // Need a new hash value to suit the bigger table.
    83         index = key.psxhash() % buckets.length;
    84       }
    85     e = new HashEntry(key, value);
    86     e.next = buckets[index];
    87     buckets[index] = e;
    88   }
    89 
    90   @Override
    91   public LispObject remove(LispObject key)
    92   {
    93     final int index = key.psxhash() % buckets.length;
    94     HashEntry e = buckets[index];
    95     HashEntry last = null;
    96     while (e != null)
    97       {
    98         if (key.equalp(e.key))
    99           {
    100             if (last == null)
    101               buckets[index] = e.next;
    102             else
    103               last.next = e.next;
    104             --count;
    105             return e.value;
    106           }
    107         last = e;
    108         e = e.next;
    109       }
    110     return null;
    111   }
    112 
    113   @Override
    114   protected void rehash()
    115   {
    116     HashEntry[] oldBuckets = buckets;
    117     int newCapacity = buckets.length * 2 + 1;
    118     threshold = (int) (newCapacity * loadFactor);
    119     buckets = new HashEntry[newCapacity];
    120     for (int i = oldBuckets.length; i-- > 0;)
    121       {
    122         HashEntry e = oldBuckets[i];
    123         while (e != null)
    124           {
    125             final int index = e.key.psxhash() % buckets.length;
    126             HashEntry dest = buckets[index];
    127             if (dest != null)
    128               {
    129                 while (dest.next != null)
    130                   dest = dest.next;
    131                 dest.next = e;
    132               }
    133             else
    134               buckets[index] = e;
    135             HashEntry next = e.next;
    136             e.next = null;
    137             e = next;
    138           }
    139       }
     41    super(new EqualpComparator(), size, rehashSize, rehashThreshold);
    14042  }
    14143}

  • trunk/abcl/src/org/armedbear/lisp/HashTable.java

    r12962 r12965  
    3131 * exception statement from your version.
    3232 */
    33 
    3433package org.armedbear.lisp;
    3534
    3635import static org.armedbear.lisp.Lisp.*;
    3736
    38 public abstract class HashTable extends LispObject
    39 {
    40   private static final int DEFAULT_SIZE = 16;
    41 
    42   protected static final float loadFactor = 0.75f;
    43 
    44   protected final LispObject rehashSize;
    45   protected final LispObject rehashThreshold;
    46 
    47   // The rounded product of the capacity and the load factor. When the number
    48   // of elements exceeds the threshold, the implementation calls rehash().
    49   protected int threshold;
    50 
    51   // Array containing the actual key-value mappings.
    52   protected HashEntry[] buckets;
    53 
    54   // The number of key-value pairs.
    55   protected int count;
     37public abstract class HashTable extends LispObject {
     38
     39    private static final int DEFAULT_SIZE = 16;
     40    protected static final float loadFactor = 0.75f;
     41    protected final LispObject rehashSize;
     42    protected final LispObject rehashThreshold;
     43    // The rounded product of the capacity and the load factor. When the number
     44    // of elements exceeds the threshold, the implementation calls rehash().
     45    protected int threshold;
     46    // Array containing the actual key-value mappings.
     47    protected HashEntry[] buckets;
     48    // The number of key-value pairs.
     49    protected int count;
     50    private int mask;
     51    final Comparator comparator;
    5652
    5753  protected HashTable(int size, LispObject rehashSize,
    5854                      LispObject rehashThreshold)
    5955  {
    60     this.rehashSize = rehashSize;
    61     this.rehashThreshold = rehashThreshold;
    62     buckets = new HashEntry[size];
    63     threshold = (int) (size * loadFactor);
    64   }
    65 
    66   protected static int calculateInitialCapacity(int size)
    67   {
    68     int capacity = 1;
    69     while (capacity < size)
    70       capacity <<= 1;
    71     return capacity;
    72   }
    73 
    74   public final LispObject getRehashSize()
    75   {
    76     return rehashSize;
    77   }
    78 
    79   public final LispObject getRehashThreshold()
    80   {
    81     return rehashThreshold;
    82   }
    83 
    84   public int getSize()
    85   {
    86     return buckets.length;
    87   }
    88 
    89   public int getCount()
    90   {
    91     return count;
    92   }
    93 
    94   public abstract Symbol getTest();
    95 
    96   @Override
    97   public LispObject typeOf()
    98   {
    99     return Symbol.HASH_TABLE;
    100   }
    101 
    102   @Override
    103   public LispObject classOf()
    104   {
    105     return BuiltInClass.HASH_TABLE;
    106   }
    107 
    108   @Override
    109   public LispObject typep(LispObject type)
    110   {
    111     if (type == Symbol.HASH_TABLE)
    112       return T;
    113     if (type == BuiltInClass.HASH_TABLE)
    114       return T;
    115     return super.typep(type);
    116   }
    117 
    118   @Override
    119   public boolean equalp(LispObject obj)
    120   {
    121     if (this == obj)
    122       return true;
    123     if (obj instanceof HashTable)
    124       {
    125         HashTable ht = (HashTable) obj;
    126         if (count != ht.count)
    127           return false;
    128         if (getTest() != ht.getTest())
    129           return false;
    130         LispObject entries = ENTRIES();
    131         while (entries != NIL)
    132           {
    133             LispObject entry = entries.car();
    134             LispObject key = entry.car();
    135             LispObject value = entry.cdr();
    136             if (!value.equalp(ht.get(key)))
    137               return false;
    138             entries = entries.cdr();
    139           }
    140         return true;
    141       }
    142     return false;
    143   }
    144 
    145   @Override
    146   public LispObject getParts()
    147   {
    148     LispObject parts = NIL;
    149     for (int i = 0; i < buckets.length; i++)
    150       {
    151         HashEntry e = buckets[i];
    152         while (e != null)
    153           {
    154             parts = parts.push(new Cons("KEY [bucket " + i + "]", e.key));
    155             parts = parts.push(new Cons("VALUE", e.value));
     56    protected HashTable(Comparator c, int size, LispObject rehashSize,
     57            LispObject rehashThreshold) {
     58        this.rehashSize = rehashSize;
     59        this.rehashThreshold = rehashThreshold;
     60        buckets = new HashEntry[size];
     61        threshold = (int) (size * loadFactor);
     62        comparator = c;
     63        mask = buckets.length - 1;
     64    }
     65
     66    protected static int calculateInitialCapacity(int size) {
     67        int capacity = 1;
     68        while (capacity < size) {
     69            capacity <<= 1;
     70        }
     71        return capacity;
     72    }
     73
     74    public final LispObject getRehashSize() {
     75        return rehashSize;
     76    }
     77
     78    public final LispObject getRehashThreshold() {
     79        return rehashThreshold;
     80    }
     81
     82    public int getSize() {
     83        return buckets.length;
     84    }
     85
     86    public int getCount() {
     87        return count;
     88    }
     89
     90    @Override
     91    public LispObject typeOf() {
     92        return Symbol.HASH_TABLE;
     93    }
     94
     95    @Override
     96    public LispObject classOf() {
     97        return BuiltInClass.HASH_TABLE;
     98    }
     99
     100    @Override
     101    public LispObject typep(LispObject type) {
     102        if (type == Symbol.HASH_TABLE) {
     103            return T;
     104        }
     105        if (type == BuiltInClass.HASH_TABLE) {
     106            return T;
     107        }
     108        return super.typep(type);
     109    }
     110
     111    @Override
     112    public boolean equalp(LispObject obj) {
     113        if (this == obj) {
     114            return true;
     115        }
     116        if (obj instanceof HashTable) {
     117            HashTable ht = (HashTable) obj;
     118            if (count != ht.count) {
     119                return false;
     120            }
     121            if (getTest() != ht.getTest()) {
     122                return false;
     123            }
     124            LispObject entries = ENTRIES();
     125            while (entries != NIL) {
     126                LispObject entry = entries.car();
     127                LispObject key = entry.car();
     128                LispObject value = entry.cdr();
     129                if (!value.equalp(ht.get(key))) {
     130                    return false;
     131                }
     132                entries = entries.cdr();
     133            }
     134            return true;
     135        }
     136        return false;
     137    }
     138
     139    @Override
     140    public LispObject getParts() {
     141        LispObject parts = NIL;
     142        for (int i = 0; i < buckets.length; i++) {
     143            HashEntry e = buckets[i];
     144            while (e != null) {
     145                parts = parts.push(new Cons("KEY [bucket " + i + "]", e.key));
     146                parts = parts.push(new Cons("VALUE", e.value));
     147                e = e.next;
     148            }
     149        }
     150        return parts.nreverse();
     151    }
     152
     153    public synchronized void clear() {
     154        for (int i = buckets.length; i-- > 0;) {
     155            buckets[i] = null;
     156        }
     157        count = 0;
     158    }
     159
     160    // gethash key hash-table &optional default => value, present-p
     161    public synchronized LispObject gethash(LispObject key) {
     162        LispObject value = get(key);
     163        final LispObject presentp;
     164        if (value == null) {
     165            value = presentp = NIL;
     166        } else {
     167            presentp = T;
     168        }
     169        return LispThread.currentThread().setValues(value, presentp);
     170    }
     171
     172    // gethash key hash-table &optional default => value, present-p
     173    public synchronized LispObject gethash(LispObject key,
     174            LispObject defaultValue) {
     175        LispObject value = get(key);
     176        final LispObject presentp;
     177        if (value == null) {
     178            value = defaultValue;
     179            presentp = NIL;
     180        } else {
     181            presentp = T;
     182        }
     183        return LispThread.currentThread().setValues(value, presentp);
     184    }
     185
     186    public synchronized LispObject gethash1(LispObject key) {
     187        final LispObject value = get(key);
     188        return value != null ? value : NIL;
     189    }
     190
     191    public synchronized LispObject puthash(LispObject key, LispObject newValue) {
     192        put(key, newValue);
     193        return newValue;
     194    }
     195
     196    // remhash key hash-table => generalized-boolean
     197    public synchronized LispObject remhash(LispObject key) {
     198        // A value in a Lisp hash table can never be null, so...
     199        return remove(key) != null ? T : NIL;
     200    }
     201
     202    @Override
     203    public String writeToString() {
     204        if (Symbol.PRINT_READABLY.symbolValue(LispThread.currentThread()) != NIL) {
     205            error(new PrintNotReadable(list(Keyword.OBJECT, this)));
     206            return null; // Not reached.
     207        }
     208        StringBuilder sb = new StringBuilder(getTest().writeToString());
     209        sb.append(' ');
     210        sb.append(Symbol.HASH_TABLE.writeToString());
     211        sb.append(' ');
     212        sb.append(count);
     213        if (count == 1) {
     214            sb.append(" entry");
     215        } else {
     216            sb.append(" entries");
     217        }
     218        sb.append(", ");
     219        sb.append(buckets.length);
     220        sb.append(" buckets");
     221        return unreadableString(sb.toString());
     222    }
     223
     224    public Symbol getTest() {
     225        return comparator.getTest();
     226    }
     227
     228    synchronized public LispObject get(LispObject key) {
     229        int index = comparator.hash(key) & mask;
     230        HashEntry e = buckets[index];
     231        while (e != null) {
     232            if (comparator.keysEqual(key, e.key)) {
     233                return e.value;
     234            }
    156235            e = e.next;
    157           }
    158       }
    159     return parts.nreverse();
    160   }
    161 
    162   public synchronized void clear()
    163   {
    164     for (int i = buckets.length; i-- > 0;)
    165       buckets[i] = null;
    166     count = 0;
    167   }
    168 
    169   // gethash key hash-table &optional default => value, present-p
    170   public synchronized LispObject gethash(LispObject key)
    171 
    172   {
    173     LispObject value = get(key);
    174     final LispObject presentp;
    175     if (value == null)
    176       value = presentp = NIL;
    177     else
    178       presentp = T;
    179     return LispThread.currentThread().setValues(value, presentp);
    180   }
    181 
    182   // gethash key hash-table &optional default => value, present-p
    183   public synchronized LispObject gethash(LispObject key,
    184                                          LispObject defaultValue)
    185 
    186   {
    187     LispObject value = get(key);
    188     final LispObject presentp;
    189     if (value == null)
    190       {
    191         value = defaultValue;
    192         presentp = NIL;
    193       }
    194     else
    195       presentp = T;
    196     return LispThread.currentThread().setValues(value, presentp);
    197   }
    198 
    199   public synchronized LispObject gethash1(LispObject key)
    200 
    201   {
    202     final LispObject value = get(key);
    203     return value != null ? value : NIL;
    204   }
    205 
    206   public synchronized LispObject puthash(LispObject key, LispObject newValue)
    207 
    208   {
    209     put(key, newValue);
    210     return newValue;
    211   }
    212 
    213   // remhash key hash-table => generalized-boolean
    214   public synchronized LispObject remhash(LispObject key)
    215 
    216   {
    217     // A value in a Lisp hash table can never be null, so...
    218     return remove(key) != null ? T : NIL;
    219   }
    220 
    221   @Override
    222   public String writeToString()
    223   {
    224     if (Symbol.PRINT_READABLY.symbolValue(LispThread.currentThread()) != NIL)
    225       {
    226         error(new PrintNotReadable(list(Keyword.OBJECT, this)));
    227         return null; // Not reached.
    228       }
    229     StringBuilder sb = new StringBuilder(getTest().writeToString());
    230     sb.append(' ');
    231     sb.append(Symbol.HASH_TABLE.writeToString());
    232     sb.append(' ');
    233     sb.append(count);
    234     if (count == 1)
    235       sb.append(" entry");
    236     else
    237       sb.append(" entries");
    238     sb.append(", ");
    239     sb.append(buckets.length);
    240     sb.append(" buckets");
    241     return unreadableString(sb.toString());
    242   }
    243 
    244   public abstract LispObject get(LispObject key);
    245 
    246   public abstract void put(LispObject key, LispObject value)
    247    ;
    248 
    249   public abstract LispObject remove(LispObject key);
    250 
    251   protected abstract void rehash();
    252 
    253   // Returns a list of (key . value) pairs.
    254   public LispObject ENTRIES()
    255   {
    256     LispObject list = NIL;
    257     for (int i = buckets.length; i-- > 0;)
    258       {
    259         HashEntry e = buckets[i];
    260         while (e != null)
    261           {
    262             list = new Cons(new Cons(e.key, e.value), list);
     236        }
     237        return null;
     238    }
     239
     240    synchronized public void put(LispObject key, LispObject value) {
     241        int index = comparator.hash(key) & mask;
     242        for (HashEntry e = buckets[index]; e != null; e = e.next) {
     243            if (comparator.keysEqual(key, e.key)) {
     244                e.value = value;
     245                return;
     246            }
     247        }
     248        // Not found. We need to add a new entry.
     249        if (++count > threshold) {
     250            rehash();
     251            // Need a new hash value to suit the bigger table.
     252            index = comparator.hash(key) & mask;
     253        }
     254        buckets[index] = new HashEntry(key, value, buckets[index]);
     255    }
     256
     257    synchronized public LispObject remove(LispObject key) {
     258        int index = comparator.hash(key) & mask;
     259
     260        HashEntry e = buckets[index];
     261        HashEntry last = null;
     262        while (e != null) {
     263            if (comparator.keysEqual(key, e.key)) {
     264                if (last == null) {
     265                    buckets[index] = e.next;
     266                } else {
     267                    last.next = e.next;
     268                }
     269                --count;
     270                return e.value;
     271            }
     272            last = e;
    263273            e = e.next;
    264           }
    265       }
    266     return list;
    267   }
    268 
    269   public LispObject MAPHASH(LispObject function)
    270   {
    271     for (int i = buckets.length; i-- > 0;)
    272       {
    273         HashEntry e = buckets[i];
    274         while (e != null)
    275           {
    276             function.execute(e.key, e.value);
    277             e = e.next;
    278           }
    279       }
    280     return NIL;
    281   }
    282 
    283   protected static class HashEntry
    284   {
    285     LispObject key;
    286     LispObject value;
    287     HashEntry next;
    288 
    289     HashEntry(LispObject key, LispObject value)
    290     {
    291       this.key = key;
    292       this.value = value;
    293     }
    294   }
    295 
    296   // For EQUALP hash tables.
    297   @Override
    298   public int psxhash()
    299   {
    300     long result = 2062775257; // Chosen at random.
    301     result = mix(result, count);
    302     result = mix(result, getTest().sxhash());
    303     return (int) (result & 0x7fffffff);
    304   }
     274        }
     275        return null;
     276    }
     277
     278    synchronized protected void rehash() {
     279        final int newCapacity = buckets.length * 2;
     280        threshold = (int) (newCapacity * loadFactor);
     281        mask = newCapacity - 1;
     282        HashEntry[] newBuckets = new HashEntry[newCapacity];
     283
     284        for (int i = buckets.length; i-- > 0;) {
     285            HashEntry e = buckets[i];
     286            while (e != null) {
     287                final int index = comparator.hash(e.key) & mask;
     288                newBuckets[index] = new HashEntry(e.key,e.value, newBuckets[index]);
     289                e = e.next;
     290            }
     291        }
     292        buckets = newBuckets;
     293    }
     294
     295    // Returns a list of (key . value) pairs.
     296    public LispObject ENTRIES() {
     297        LispObject list = NIL;
     298        for (int i = buckets.length; i-- > 0;) {
     299            HashEntry e = buckets[i];
     300            while (e != null) {
     301                list = new Cons(new Cons(e.key, e.value), list);
     302                e = e.next;
     303            }
     304        }
     305        return list;
     306    }
     307
     308    public LispObject MAPHASH(LispObject function) {
     309        for (int i = buckets.length; i-- > 0;) {
     310            HashEntry e = buckets[i];
     311            while (e != null) {
     312                function.execute(e.key, e.value);
     313                e = e.next;
     314            }
     315        }
     316        return NIL;
     317    }
     318
     319    protected static class Comparator {
     320        Symbol getTest() {
     321            return Symbol.EQ;
     322        }
     323
     324        boolean keysEqual(LispObject key1, LispObject key2) {
     325            return key1 == key2;
     326        }
     327
     328        int hash(LispObject key) {
     329            return key.sxhash();
     330        }
     331    }
     332
     333    protected static class EqlComparator extends Comparator {
     334        @Override
     335        Symbol getTest() {
     336            return Symbol.EQL;
     337        }
     338
     339        @Override
     340        boolean keysEqual(LispObject key1, LispObject key2) {
     341            return key1.eql(key2);
     342        }
     343    }
     344
     345    protected static class EqualComparator extends Comparator {
     346        @Override
     347        Symbol getTest() {
     348            return Symbol.EQUAL;
     349        }
     350
     351        @Override
     352        boolean keysEqual(LispObject key1, LispObject key2) {
     353            return key1.equal(key2);
     354        }
     355    }
     356
     357    protected static class EqualpComparator extends Comparator {
     358        @Override
     359        Symbol getTest() {
     360            return Symbol.EQUALP;
     361        }
     362
     363        @Override
     364        boolean keysEqual(LispObject key1, LispObject key2) {
     365            return key1.equalp(key2);
     366        }
     367
     368        @Override
     369        int hash(LispObject key) {
     370            return key.psxhash();
     371        }
     372    }
     373
     374    protected static class HashEntry {
     375
     376        LispObject key;
     377        LispObject value;
     378        HashEntry next;
     379
     380        HashEntry(LispObject key, LispObject value, HashEntry next) {
     381            this.key = key;
     382            this.value = value;
     383            this.next = next;
     384        }
     385    }
     386
     387    // For EQUALP hash tables.
     388    @Override
     389    public int psxhash() {
     390        long result = 2062775257; // Chosen at random.
     391        result = mix(result, count);
     392        result = mix(result, getTest().sxhash());
     393        return (int) (result & 0x7fffffff);
     394    }
    305395}
Note: See TracChangeset for help on using the changeset viewer.