    1   /* SoftHashMap
    2    *
    3    * $Id: SoftSettingsHash.java 4665 2006-09-26 00:20:33Z paul_jack $
    4    *
    5    * Created on Mar 18, 2004
    6    *
    7    * Copyright (C) 2004 Internet Archive.
    8    *
    9    * This file is part of the Heritrix web crawler (crawler.archive.org).
    10   *
    11   * Heritrix is free software; you can redistribute it and/or modify
    12   * it under the terms of the GNU Lesser Public License as published by
    13   * the Free Software Foundation; either version 2.1 of the License, or
    14   * any later version.
    15   *
    16   * Heritrix is distributed in the hope that it will be useful,
    17   * but WITHOUT ANY WARRANTY; without even the implied warranty of
    18   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    19   * GNU Lesser Public License for more details.
    20   *
    21   * You should have received a copy of the GNU Lesser Public License
    22   * along with Heritrix; if not, write to the Free Software
    23   * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
    24   */
    25  package org.archive.crawler.settings;
    26
    27  import java.lang.ref.Reference;
    28  import java.lang.ref.ReferenceQueue;
    29  import java.lang.ref.SoftReference;
    30  import java.util.ConcurrentModificationException;
    31  import java.util.Iterator;
    32  import java.util.NoSuchElementException;
    33
    34
    35  public class SoftSettingsHash {
    36
    37      /***
    38       * The maximum capacity, used if a higher value is implicitly specified
    39       * by either of the constructors with arguments.
    40       * MUST be a power of two <= 1<<30.
    41       */
    42      private static final int MAXIMUM_CAPACITY = 1 << 30;
    43
    44      /***
    45       * The load fast used.
    46       */
    47      private static final float LOAD_FACTOR = 0.75f;
    48
    49      /***
    50       * The table, resized as necessary. Length MUST Always be a power of two.
    51       */
    52      private SettingsEntry[] table;
    53
    54      /***
    55       * The number of key-value mappings contained in this hash.
    56       */
    57      private int size;
    58
    59      /***
    60       * The next size value at which to resize (capacity * load factor).
    61       */
    62      private int threshold;
    63
    64      /***
    65       * Reference queue for cleared entries
    66       */
    67      private final ReferenceQueue<? super String> queue
    68       = new ReferenceQueue<String>();
    69
    70      /***
    71       * The number of times this HashMap has been structurally modified
    72       * Structural modifications are those that change the number of mappings in
    73       * the HashMap or otherwise modify its internal structure (e.g.,
    74       * rehash).  This field is used to make iterators on Collection-views of
    75       * the HashMap fail-fast.  (See ConcurrentModificationException).
    76       */
    77      private volatile int modCount;
    78
    79      /***
    80       * Constructs a new, empty <tt>SoftSettingsHash</tt> with the given initial
    81       * capacity.
    82       *
    83       * @param  initialCapacity The initial capacity of the
    84       *         <tt>SoftSettingsHash</tt>
    85       * @throws IllegalArgumentException  If the initial capacity is negative.
    86       */
    87      public SoftSettingsHash(int initialCapacity) {
    88          if (initialCapacity < 0)
    89              throw new IllegalArgumentException("Illegal Initial Capacity: "+
    90                                                 initialCapacity);
    91          if (initialCapacity > MAXIMUM_CAPACITY)
    92              initialCapacity = MAXIMUM_CAPACITY;
    93
    94          int capacity = 1;
    95          while (capacity < initialCapacity)
    96              capacity <<= 1;
    97          table = new SettingsEntry[capacity];
    98          threshold = (int)(capacity * LOAD_FACTOR);
    99      }
    100
    101     /***
    102      * Check for equality of non-null reference x and possibly-null y.  By
    103      * default uses Object.equals.
    104      */
    105     static boolean eq(Object x, Object y) {
    106         return x == y || x.equals(y);
    107     }
    108
    109     /***
    110      * Return index for hash code h.
    111      */
    112     static int indexFor(int h, int length) {
    113         return h & (length-1);
    114     }
    115
    116     /***
    117      * Expunge stale entries from the table.
    118      */
    119     private void expungeStaleEntries() {
    120         SettingsEntry entry;
    121         Reference ref;
    122         while ( (ref = queue.poll()) != null) {
    123             entry = (SettingsEntry)ref;
    124             int h = entry.hash;
    125             int i = indexFor(h, table.length);
    126
    127             SettingsEntry prev = table[i];
    128             SettingsEntry p = prev;
    129             while (p != null) {
    130                 SettingsEntry next = p.next;
    131                 if (p == entry) {
    132                     if (prev == entry)
    133                         table[i] = next;
    134                     else
    135                         prev.next = next;
    136                     entry.next = null;  // Help GC
    137                     entry.settings = null; //  "   "
    138                     size--;
    139                     break;
    140                 }
    141                 prev = p;
    142                 p = next;
    143             }
    144         }
    145     }
    146
    147     /***
    148      * Returns the number of key-value mappings in this map.
    149      * This result is a snapshot, and may not reflect unprocessed
    150      * entries that will be removed before next attempted access
    151      * because they are no longer referenced.
    152      */
    153     public int size() {
    154         if (size == 0)
    155             return 0;
    156         expungeStaleEntries();
    157         return size;
    158     }
    159
    160     /***
    161      * Returns the value to which the specified key is mapped in this weak
    162      * hash map, or <tt>null</tt> if the map contains no mapping for
    163      * this key. Null is also returned if the element has been GC'ed.
    164      *
    165      * @param   key the key whose associated settings object is to be returned.
    166      * @return  the settings object represented by the key, or
    167      *          <tt>null</tt> if the map contains no mapping for this key.
    168      * @see #put(String, CrawlerSettings)
    169      */
    170     public CrawlerSettings get(String key) {
    171         if (key == null) {
    172             throw new NullPointerException("Null key");
    173         }
    174         int hash = hash(key);
    175         expungeStaleEntries();
    176         int index = indexFor(hash, table.length);
    177         SettingsEntry e = table[index];
    178         while (e != null) {
    179             if (e.hash == hash && eq(key, e.get()))
    180                 return e.settings;
    181             e = e.next;
    182         }
    183         return null;
    184     }
    185
    186     /***
    187      * Associates the specified settings object with the specified key in this
    188      * hash.
    189      *
    190      * If the hash previously contained a settings object for this key, the old
    191      * object is replaced.
    192      *
    193      * @param key key with which the specified settings object is to be
    194      *            associated.
    195      * @param settings settings object to be associated with the specified key.
    196      * @return previous value associated with specified key, or <tt>null</tt>
    197      *         if there was no mapping for key.
    198      */
    199     public CrawlerSettings put(String key, CrawlerSettings settings) {
    200         if (settings == null) {
    201             throw new NullPointerException("Settings object was null");
    202         }
    203         if (key == null) {
    204             throw new NullPointerException("Null key");
    205         }
    206         int hash = hash(key);
    207         expungeStaleEntries();
    208         int i = indexFor(hash, table.length);
    209
    210         for (SettingsEntry entry = table[i]; entry != null; entry = entry.next) {
    211             if (hash == entry.hash && eq(key, entry.get())) {
    212                 CrawlerSettings oldValue = entry.settings;
    213                 if (settings != oldValue)
    214                     entry.settings = settings;
    215                 return oldValue;
    216             }
    217         }
    218
    219         modCount++;
    220         table[i] = new SettingsEntry(key, settings, queue, hash, table[i]);
    221         if (++size >= threshold)
    222             resize(table.length * 2);
    223         return null;
    224     }
    225
    226     public CrawlerSettings put(SettingsEntry entry) {
    227         return put(entry.getKey(), entry.getValue());
    228     }
    229
    230     /***
    231      * Rehashes the contents of this hash into a new <tt>HashMap</tt> instance
    232      * with a larger capacity. This method is called automatically when the
    233      * number of keys in this map exceeds its capacity and load factor.
    234      *
    235      * Note that this method is a no-op if it's called with newCapacity ==
    236      * 2*MAXIMUM_CAPACITY (which is Integer.MIN_VALUE).
    237      *
    238      * @param newCapacity the new capacity, MUST be a power of two.
    239      */
    240     void resize(int newCapacity) {
    241         expungeStaleEntries();
    242         SettingsEntry[] oldTable = table;
    243         int oldCapacity = oldTable.length;
    244
    245         // check if needed
    246         if (size < threshold || oldCapacity > newCapacity)
    247             return;
    248
    249         SettingsEntry[] newTable = new SettingsEntry[newCapacity];
    250
    251         transfer(oldTable, newTable);
    252         table = newTable;
    253
    254         /*
    255          * If ignoring null elements and processing ref queue caused massive
    256          * shrinkage, then restore old table.  This should be rare, but avoids
    257          * unbounded expansion of garbage-filled tables.
    258          */
    259         if (size >= threshold / 2) {
    260             threshold = (int)(newCapacity * LOAD_FACTOR);
    261         } else {
    262             expungeStaleEntries();
    263             transfer(newTable, oldTable);
    264             table = oldTable;
    265         }
    266     }
    267
    268     /*** Transfer all entries from src to dest tables */
    269     private void transfer(SettingsEntry[] src, SettingsEntry[] dest) {
    270         for (int j = 0; j < src.length; ++j) {
    271             SettingsEntry entry = src[j];
    272             src[j] = null;
    273             while (entry != null) {
    274                 SettingsEntry next = entry.next;
    275                 Object key = entry.get();
    276                 if (key == null) {
    277                     entry.next = null;  // Help GC
    278                     entry.settings = null; //  "   "
    279                     size--;
    280                 } else {
    281                     int i = indexFor(entry.hash, dest.length);
    282                     entry.next = dest[i];
    283                     dest[i] = entry;
    284                 }
    285                 entry = next;
    286             }
    287         }
    288     }
    289
    290     /***
    291      * Removes the settings object identified by the key from this hash if
    292      * present.
    293      *
    294      * @param key key whose element is to be removed from the hash.
    295      * @return previous value associated with specified key, or <tt>null</tt>
    296      *         if there was no mapping for key.
    297      */
    298     public Object remove(String key) {
    299         if (key == null) {
    300             throw new NullPointerException("Null key");
    301         }
    302         int hash = hash(key);
    303         expungeStaleEntries();
    304         int i = indexFor(hash, table.length);
    305         SettingsEntry prev = table[i];
    306         SettingsEntry entry = prev;
    307
    308         while (entry != null) {
    309             SettingsEntry next = entry.next;
    310             if (hash == entry.hash && eq(key, entry.get())) {
    311                 modCount++;
    312                 size--;
    313                 if (prev == entry)
    314                     table[i] = next;
    315                 else
    316                     prev.next = next;
    317                 return entry.settings;
    318             }
    319             prev = entry;
    320             entry = next;
    321         }
    322
    323         return null;
    324     }
    325
    326     /***
    327      * Removes all settings object from this hash.
    328      */
    329     public void clear() {
    330         // clear out ref queue. We don't need to expunge entries
    331         // since table is getting cleared.
    332         while (queue.poll() != null)
    333             ;
    334
    335         modCount++;
    336         SettingsEntry tab[] = table;
    337         for (int i = 0; i < tab.length; ++i)
    338             tab[i] = null;
    339         size = 0;
    340
    341         // Allocation of array may have caused GC, which may have caused
    342         // additional entries to go stale.  Removing these entries from the
    343         // reference queue will make them eligible for reclamation.
    344         while (queue.poll() != null)
    345             ;
    346    }
    347
    348     /***
    349      * The entries in this hash extend SoftReference, using the host string
    350      * as the key.
    351      */
    352     static class SettingsEntry extends SoftReference<String> {
    353         private CrawlerSettings settings;
    354         private final int hash;
    355         private SettingsEntry next;
    356
    357         /***
    358          * Create new entry.
    359          */
    360         SettingsEntry(String key, CrawlerSettings settings,
    361               ReferenceQueue<? super String> queue,
    362               int hash, SettingsEntry next) {
    363             super(key, queue);
    364             this.settings = settings;
    365             this.hash  = hash;
    366             this.next  = next;
    367         }
    368
    369         public String getKey() {
    370             return (String) this.get();
    371         }
    372
    373         public CrawlerSettings getValue() {
    374             return settings;
    375         }
    376
    377         public boolean equals(Object o) {
    378             if (!(o instanceof SettingsEntry))
    379                 return false;
    380             SettingsEntry e = (SettingsEntry)o;
    381             String key1 = getKey();
    382             String key2 = e.getKey();
    383             if (key1 == key2 || (key1 != null && key1.equals(key2))) {
    384                 CrawlerSettings setting1 = getValue();
    385                 CrawlerSettings setting2 = e.getValue();
    386                 if (setting1 == setting2 || (setting1 != null && setting1.equals(setting2)))
    387                     return true;
    388             }
    389             return false;
    390         }
    391     }
    392
    393     /*** Iterator over all elements in hash.
    394      */
    395     class EntryIterator implements Iterator {
    396         int index;
    397         SettingsEntry entry = null;
    398         SettingsEntry lastReturned = null;
    399         int expectedModCount = modCount;
    400
    401         /***
    402          * Strong reference needed to avoid disappearance of key
    403          * between hasNext and next
    404          */
    405         String nextKey = null;
    406
    407         /***
    408          * Strong reference needed to avoid disappearance of key
    409          * between nextEntry() and any use of the entry
    410          */
    411         String currentKey = null;
    412
    413         EntryIterator() {
    414             index = (size() != 0 ? table.length : 0);
    415         }
    416
    417         public boolean hasNext() {
    418             SettingsEntry[] t = table;
    419
    420             while (nextKey == null) {
    421                 SettingsEntry e = entry;
    422                 int i = index;
    423                 while (e == null && i > 0)
    424                     e = t[--i];
    425                 entry = e;
    426                 index = i;
    427                 if (e == null) {
    428                     currentKey = null;
    429                     return false;
    430                 }
    431                 nextKey = (String) e.get(); // hold on to key in strong ref
    432                 if (nextKey == null)
    433                     entry = entry.next;
    434             }
    435             return true;
    436         }
    437
    438         /*** The common parts of next() across different types of iterators */
    439         public Object next() {
    440             return nextEntry();
    441         }
    442
    443         public SettingsEntry nextEntry() {
    444             if (modCount != expectedModCount)
    445                 throw new ConcurrentModificationException();
    446             if (nextKey == null && !hasNext())
    447                 throw new NoSuchElementException();
    448
    449             lastReturned = entry;
    450             entry = entry.next;
    451             currentKey = nextKey;
    452             nextKey = null;
    453             return lastReturned;
    454         }
    455
    456         public void remove() {
    457             if (lastReturned == null)
    458                 throw new IllegalStateException();
    459             if (modCount != expectedModCount)
    460                 throw new ConcurrentModificationException();
    461
    462             SoftSettingsHash.this.remove(currentKey);
    463             expectedModCount = modCount;
    464             lastReturned = null;
    465             currentKey = null;
    466         }
    467
    468     }
    469
    470     /*** Make hash value from a String.
    471      *
    472      * @param key the string for which to create hash value.
    473      * @return the hash value.
    474      */
    475     static int hash(String key) {
    476         int hash = key.hashCode();
    477
    478         hash += ~(hash << 9);
    479         hash ^=  (hash >>> 14);
    480         hash +=  (hash << 4);
    481         hash ^=  (hash >>> 10);
    482         return hash;
    483     }
    484
    485     public EntryIterator iterator() {
    486         return new EntryIterator();
    487     }
    488
    489 }