Changeset 10368


Ignore:
Timestamp:
11/05/05 19:15:07 (16 years ago)
Author:
piso
Message:

Force size to be a power of 2.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/j/src/org/armedbear/lisp/EqHashTable.java

    r9801 r10368  
    33 *
    44 * Copyright (C) 2004-2005 Peter Graves
    5  * $Id: EqHashTable.java,v 1.7 2005-08-05 19:51:18 piso Exp $
     5 * $Id: EqHashTable.java,v 1.8 2005-11-05 19:15:07 piso Exp $
    66 *
    77 * This program is free software; you can redistribute it and/or
     
    2727    private int cachedIndex;
    2828
     29    private int mask;
     30
    2931    public EqHashTable(int size, LispObject rehashSize,
    3032                       LispObject rehashThreshold)
    3133    {
    32         super(size, rehashSize, rehashThreshold);
     34        super(calculateInitialCapacity(size), rehashSize, rehashThreshold);
     35        mask = buckets.length - 1;
     36    }
     37
     38    private static int calculateInitialCapacity(int size)
     39    {
     40        int capacity = 1;
     41        while (capacity < size)
     42            capacity <<= 1;
     43        return capacity;
    3344    }
    3445
     
    4455            index = cachedIndex;
    4556        } else {
    46             index = key.sxhash() % buckets.length;
     57            index = key.sxhash() & mask;
    4758            cachedKey = key;
    4859            cachedIndex = index;
     
    6374            index = cachedIndex;
    6475        } else {
    65             index = key.sxhash() % buckets.length;
     76            index = key.sxhash() & mask;
    6677            cachedKey = key;
    6778            cachedIndex = index;
     
    7990            rehash();
    8091            // Need a new hash value to suit the bigger table.
    81             index = key.sxhash() % buckets.length;
     92            index = key.sxhash() & mask;
    8293            cachedKey = key;
    8394            cachedIndex = index;
     
    94105            index = cachedIndex;
    95106        } else {
    96             index = key.sxhash() % buckets.length;
     107            index = key.sxhash() & mask;
    97108            cachedKey = key;
    98109            cachedIndex = index;
     
    119130        cachedKey = null; // Invalidate the cache!
    120131        HashEntry[] oldBuckets = buckets;
    121         int newCapacity = buckets.length * 2 + 1;
     132        final int newCapacity = buckets.length * 2;
    122133        threshold = (int) (newCapacity * loadFactor);
    123134        buckets = new HashEntry[newCapacity];
     135        mask = buckets.length - 1;
    124136        for (int i = oldBuckets.length; i-- > 0;) {
    125137            HashEntry e = oldBuckets[i];
    126138            while (e != null) {
    127                 final int index = e.key.sxhash() % buckets.length;
     139                final int index = e.key.sxhash() & mask;
    128140                HashEntry dest = buckets[index];
    129141                if (dest != null) {
Note: See TracChangeset for help on using the changeset viewer.