Changeset 12967


Ignore:
Timestamp:
10/09/10 21:39:29 (11 years ago)
Author:
ehuelsmann
Message:

Convert HashTable? synchronized access to read/write locked
access through ReentrantReadWriteLock?: this will allow multiple
readers across threads.

Also add my name to the copyright notice.

File:
1 edited

Legend:

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

    r12966 r12967  
    33 *
    44 * Copyright (C) 2002-2007 Peter Graves
     5 * Copyright (C) 2010 Erik Huelsmann
    56 * $Id$
    67 *
     
    3334package org.armedbear.lisp;
    3435
     36import java.util.concurrent.locks.ReentrantReadWriteLock;
    3537import static org.armedbear.lisp.Lisp.*;
    3638
    3739public abstract class HashTable extends LispObject {
    3840
    39     private static final int DEFAULT_SIZE = 16;
    4041    protected static final float loadFactor = 0.75f;
    4142    protected final LispObject rehashSize;
     
    5051    private int mask;
    5152    final Comparator comparator;
     53    final private ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
    5254
    5355    protected HashTable(Comparator c, int size, LispObject rehashSize,
     
    148150    }
    149151
    150     public synchronized void clear() {
    151         for (int i = buckets.length; i-- > 0;) {
    152             buckets[i] = null;
    153         }
    154         count = 0;
     152    public void clear() {
     153        lock.writeLock().lock();
     154        try {
     155            buckets = new HashEntry[buckets.length];
     156            count = 0;
     157        } finally {
     158            lock.writeLock().unlock();
     159        }
    155160    }
    156161
    157162    // gethash key hash-table &optional default => value, present-p
    158     public synchronized LispObject gethash(LispObject key) {
     163    public LispObject gethash(LispObject key) {
    159164        LispObject value = get(key);
    160165        final LispObject presentp;
     
    168173
    169174    // gethash key hash-table &optional default => value, present-p
    170     public synchronized LispObject gethash(LispObject key,
    171             LispObject defaultValue) {
     175    public LispObject gethash(LispObject key, LispObject defaultValue) {
    172176        LispObject value = get(key);
    173177        final LispObject presentp;
     
    181185    }
    182186
    183     public synchronized LispObject gethash1(LispObject key) {
     187    public LispObject gethash1(LispObject key) {
    184188        final LispObject value = get(key);
    185189        return value != null ? value : NIL;
    186190    }
    187191
    188     public synchronized LispObject puthash(LispObject key, LispObject newValue) {
     192    public LispObject puthash(LispObject key, LispObject newValue) {
    189193        put(key, newValue);
    190194        return newValue;
     
    192196
    193197    // remhash key hash-table => generalized-boolean
    194     public synchronized LispObject remhash(LispObject key) {
     198    public LispObject remhash(LispObject key) {
    195199        // A value in a Lisp hash table can never be null, so...
    196200        return remove(key) != null ? T : NIL;
     
    223227    }
    224228
    225     synchronized public LispObject get(LispObject key) {
    226         int index = comparator.hash(key) & mask;
    227         HashEntry e = buckets[index];
    228         while (e != null) {
    229             if (comparator.keysEqual(key, e.key)) {
    230                 return e.value;
    231             }
    232             e = e.next;
    233         }
    234         return null;
    235     }
    236 
    237     synchronized public void put(LispObject key, LispObject value) {
    238         int index = comparator.hash(key) & mask;
    239         for (HashEntry e = buckets[index]; e != null; e = e.next) {
    240             if (comparator.keysEqual(key, e.key)) {
    241                 e.value = value;
    242                 return;
    243             }
    244         }
    245         // Not found. We need to add a new entry.
    246         if (++count > threshold) {
    247             rehash();
    248             // Need a new hash value to suit the bigger table.
    249             index = comparator.hash(key) & mask;
    250         }
    251         buckets[index] = new HashEntry(key, value, buckets[index]);
    252     }
    253 
    254     synchronized public LispObject remove(LispObject key) {
    255         int index = comparator.hash(key) & mask;
    256 
    257         HashEntry e = buckets[index];
    258         HashEntry last = null;
    259         while (e != null) {
    260             if (comparator.keysEqual(key, e.key)) {
    261                 if (last == null) {
    262                     buckets[index] = e.next;
    263                 } else {
    264                     last.next = e.next;
     229    public LispObject get(LispObject key) {
     230        lock.readLock().lock();
     231        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;
    265237                }
    266                 --count;
    267                 return e.value;
    268             }
    269             last = e;
    270             e = e.next;
    271         }
    272         return null;
    273     }
    274 
    275     synchronized protected void rehash() {
    276         final int newCapacity = buckets.length * 2;
    277         threshold = (int) (newCapacity * loadFactor);
    278         mask = newCapacity - 1;
    279         HashEntry[] newBuckets = new HashEntry[newCapacity];
    280 
    281         for (int i = buckets.length; i-- > 0;) {
    282             HashEntry e = buckets[i];
     238                e = e.next;
     239            }
     240            return null;
     241        } finally {
     242            lock.readLock().unlock();
     243        }
     244    }
     245
     246    public void put(LispObject key, LispObject value) {
     247        lock.writeLock().lock();
     248        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;
     254                }
     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]);
     263        } finally {
     264            lock.writeLock().unlock();
     265        }
     266    }
     267
     268    public LispObject remove(LispObject key) {
     269        lock.writeLock().lock();
     270        try {
     271            int index = comparator.hash(key) & mask;
     272
     273            HashEntry e = buckets[index];
     274            HashEntry last = null;
    283275            while (e != null) {
    284                 final int index = comparator.hash(e.key) & mask;
    285                 newBuckets[index] = new HashEntry(e.key,e.value, newBuckets[index]);
     276                if (comparator.keysEqual(key, e.key)) {
     277                    if (last == null) {
     278                        buckets[index] = e.next;
     279                    } else {
     280                        last.next = e.next;
     281                    }
     282                    --count;
     283                    return e.value;
     284                }
     285                last = e;
    286286                e = e.next;
    287287            }
    288         }
    289         buckets = newBuckets;
     288            return null;
     289        } finally {
     290            lock.writeLock().unlock();
     291        }
     292    }
     293
     294    protected void rehash() {
     295        lock.writeLock().lock();
     296        try {
     297            final int newCapacity = buckets.length * 2;
     298            threshold = (int) (newCapacity * loadFactor);
     299            mask = newCapacity - 1;
     300            HashEntry[] newBuckets = new HashEntry[newCapacity];
     301
     302            for (int i = buckets.length; i-- > 0;) {
     303                HashEntry e = buckets[i];
     304                while (e != null) {
     305                    final int index = comparator.hash(e.key) & mask;
     306                    newBuckets[index] = new HashEntry(e.key, e.value, newBuckets[index]);
     307                    e = e.next;
     308                }
     309            }
     310            buckets = newBuckets;
     311        } finally {
     312            lock.writeLock().unlock();
     313        }
    290314    }
    291315
     
    315339
    316340    protected static class Comparator {
     341
    317342        Symbol getTest() {
    318343            return Symbol.EQ;
     
    329354
    330355    protected static class EqlComparator extends Comparator {
     356
    331357        @Override
    332358        Symbol getTest() {
     
    341367
    342368    protected static class EqualComparator extends Comparator {
     369
    343370        @Override
    344371        Symbol getTest() {
     
    353380
    354381    protected static class EqualpComparator extends Comparator {
     382
    355383        @Override
    356384        Symbol getTest() {
Note: See TracChangeset for help on using the changeset viewer.