Changeset 12968 for trunk/abcl/src/org


Ignore:
Timestamp:
10/09/10 22:59:01 (11 years ago)
Author:
ehuelsmann
Message:

Factor out getEntry from get() and put().

Also, declare the 'buckets' field volatile and decide
not to use read-locking in some cases.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/abcl/src/org/armedbear/lisp/HashTable.java

    r12967 r12968  
    3434package org.armedbear.lisp;
    3535
     36import java.util.concurrent.ConcurrentHashMap;
    3637import java.util.concurrent.locks.ReentrantReadWriteLock;
    3738import static org.armedbear.lisp.Lisp.*;
     
    4647    protected int threshold;
    4748    // Array containing the actual key-value mappings.
    48     protected HashEntry[] buckets;
     49   
     50    @SuppressWarnings("VolatileArrayField")
     51    protected volatile HashEntry[] buckets;
     52   
    4953    // The number of key-value pairs.
    5054    protected int count;
     
    138142    @Override
    139143    public LispObject getParts() {
     144        // No need to take out a read lock, for the same reason as MAPHASH
     145        HashEntry[] b = buckets;
    140146        LispObject parts = NIL;
    141         for (int i = 0; i < buckets.length; i++) {
    142             HashEntry e = buckets[i];
     147        for (int i = 0; i < b.length; i++) {
     148            HashEntry e = b[i];
    143149            while (e != null) {
    144150                parts = parts.push(new Cons("KEY [bucket " + i + "]", e.key));
     
    227233    }
    228234
     235    protected HashEntry getEntry(LispObject key) {
     236        int index = comparator.hash(key) & mask;
     237        HashEntry e = buckets[index];
     238        while (e != null) {
     239            if (comparator.keysEqual(key, e.key)) {
     240                return e;
     241            }
     242            e = e.next;
     243        }
     244        return null;
     245    }
     246
    229247    public LispObject get(LispObject key) {
    230248        lock.readLock().lock();
    231249        try {
    232             int index = comparator.hash(key) & mask;
    233             HashEntry e = buckets[index];
    234             while (e != null) {
    235                 if (comparator.keysEqual(key, e.key)) {
    236                     return e.value;
    237                 }
    238                 e = e.next;
    239             }
    240             return null;
     250            HashEntry e = getEntry(key);
     251            return (e == null) ? null : e.value;
    241252        } finally {
    242253            lock.readLock().unlock();
     
    247258        lock.writeLock().lock();
    248259        try {
    249             int index = comparator.hash(key) & mask;
    250             for (HashEntry e = buckets[index]; e != null; e = e.next) {
    251                 if (comparator.keysEqual(key, e.key)) {
    252                     e.value = value;
    253                     return;
     260            HashEntry e = getEntry(key);
     261            if (e == null) {
     262                e.value = value;
     263            } else {
     264                // Not found. We need to add a new entry.
     265                if (++count > threshold) {
     266                    rehash();
    254267                }
    255             }
    256             // Not found. We need to add a new entry.
    257             if (++count > threshold) {
    258                 rehash();
    259                 // Need a new hash value to suit the bigger table.
    260                 index = comparator.hash(key) & mask;
    261             }
    262             buckets[index] = new HashEntry(key, value, buckets[index]);
     268
     269                int index = comparator.hash(key) & mask;
     270                buckets[index] = new HashEntry(key, value, buckets[index]);
     271            }
    263272        } finally {
    264273            lock.writeLock().unlock();
     
    316325    // Returns a list of (key . value) pairs.
    317326    public LispObject ENTRIES() {
     327        // No need to take out a read lock, for the same reason as MAPHASH
     328        HashEntry[] b = buckets;
    318329        LispObject list = NIL;
    319         for (int i = buckets.length; i-- > 0;) {
    320             HashEntry e = buckets[i];
     330        for (int i = b.length; i-- > 0;) {
     331            HashEntry e = b[i];
    321332            while (e != null) {
    322333                list = new Cons(new Cons(e.key, e.value), list);
     
    328339
    329340    public LispObject MAPHASH(LispObject function) {
    330         for (int i = buckets.length; i-- > 0;) {
    331             HashEntry e = buckets[i];
     341        // Don't take out a read lock: it can't be upgraded to a write
     342        // lock, which would block the scenario where put() is called to
     343        // set the value of the current entry
     344
     345        HashEntry[] b = buckets;
     346        for (int i = b.length; i-- > 0;) {
     347            HashEntry e = b[i];
    332348            while (e != null) {
    333349                function.execute(e.key, e.value);
Note: See TracChangeset for help on using the changeset viewer.