softsettingshash.java

最强的爬虫工程

/* SoftHashMap
 *
 * $Id: SoftSettingsHash.java,v 1.2 2004/05/28 22:33:05 stack-sf Exp $
 *
 * Created on Mar 18, 2004
 *
 * Copyright (C) 2004 Internet Archive.
 *
 * This file is part of the Heritrix web crawler (crawler.archive.org).
 *
 * Heritrix is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Lesser Public License as published by
 * the Free Software Foundation; either version 2.1 of the License, or
 * any later version.
 *
 * Heritrix is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser Public License for more details.
 *
 * You should have received a copy of the GNU Lesser Public License
 * along with Heritrix; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */
package org.archive.crawler.settings;

import java.lang.ref.ReferenceQueue;
import java.lang.ref.SoftReference;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;


public class SoftSettingsHash {

    /**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */
    private static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * The load fast used.
     */
    private static final float LOAD_FACTOR = 0.75f;

    /**
     * The table, resized as necessary. Length MUST Always be a power of two.
     */
    private SettingsEntry[] table;

    /**
     * The number of key-value mappings contained in this hash.
     */
    private int size;

    /**
     * The next size value at which to resize (capacity * load factor).
     */
    private int threshold;

    /**
     * Reference queue for cleared entries
     */
    private final ReferenceQueue queue = new ReferenceQueue();

    /**
     * The number of times this HashMap has been structurally modified
     * Structural modifications are those that change the number of mappings in
     * the HashMap or otherwise modify its internal structure (e.g.,
     * rehash).  This field is used to make iterators on Collection-views of
     * the HashMap fail-fast.  (See ConcurrentModificationException).
     */
    private volatile int modCount;

    /**
     * Constructs a new, empty <tt>SoftSettingsHash</tt> with the given initial
     * capacity.
     *
     * @param  initialCapacity The initial capacity of the
     *         <tt>SoftSettingsHash</tt>
     * @throws IllegalArgumentException  If the initial capacity is negative.
     */
    public SoftSettingsHash(int initialCapacity) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Initial Capacity: "+
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;

        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;
        table = new SettingsEntry[capacity];
        threshold = (int)(capacity * LOAD_FACTOR);
    }

    /**
     * Check for equality of non-null reference x and possibly-null y.  By
     * default uses Object.equals.
     */
    static boolean eq(Object x, Object y) {
        return x == y || x.equals(y);
    }

    /**
     * Return index for hash code h.
     */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

    /**
     * Expunge stale entries from the table.
     */
    private void expungeStaleEntries() {
        SettingsEntry entry;
        while ( (entry = (SettingsEntry) queue.poll()) != null) {
            int h = entry.hash;
            int i = indexFor(h, table.length);

            SettingsEntry prev = table[i];
            SettingsEntry p = prev;
            while (p != null) {
                SettingsEntry next = p.next;
                if (p == entry) {
                    if (prev == entry)
                        table[i] = next;
                    else
                        prev.next = next;
                    entry.next = null;  // Help GC
                    entry.settings = null; //  "   "
                    size--;
                    break;
                }
                prev = p;
                p = next;
            }
        }
    }

    /**
     * Returns the number of key-value mappings in this map.
     * This result is a snapshot, and may not reflect unprocessed
     * entries that will be removed before next attempted access
     * because they are no longer referenced.
     */
    public int size() {
        if (size == 0)
            return 0;
        expungeStaleEntries();
        return size;
    }

    /**
     * Returns the value to which the specified key is mapped in this weak
     * hash map, or <tt>null</tt> if the map contains no mapping for
     * this key. Null is also returned if the element has been GC'ed.
     *
     * @param   key the key whose associated settings object is to be returned.
     * @return  the settings object represented by the key, or
     *          <tt>null</tt> if the map contains no mapping for this key.
     * @see #put(String, CrawlerSettings)
     */
    public CrawlerSettings get(String key) {
        if (key == null) {
            throw new NullPointerException("Null key");
        }
        int hash = hash(key);
        expungeStaleEntries();
        int index = indexFor(hash, table.length);
        SettingsEntry e = table[index];
        while (e != null) {
            if (e.hash == hash && eq(key, e.get()))
                return e.settings;
            e = e.next;
        }
        return null;
    }

    /**
     * Associates the specified settings object with the specified key in this
     * hash.
     *
     * If the hash previously contained a settings object for this key, the old
     * object is replaced.
     *
     * @param key key with which the specified settings object is to be
     *            associated.
     * @param settings settings object to be associated with the specified key.
     * @return previous value associated with specified key, or <tt>null</tt>
     *         if there was no mapping for key.
     */
    public CrawlerSettings put(String key, CrawlerSettings settings) {
        if (settings == null) {
            throw new NullPointerException("Settings object was null");
        }
        if (key == null) {
            throw new NullPointerException("Null key");
        }
        int hash = hash(key);
        expungeStaleEntries();
        int i = indexFor(hash, table.length);

        for (SettingsEntry entry = table[i]; entry != null; entry = entry.next) {
            if (hash == entry.hash && eq(key, entry.get())) {
                CrawlerSettings oldValue = entry.settings;
                if (settings != oldValue)
                    entry.settings = settings;
                return oldValue;
            }
        }

        modCount++;
        table[i] = new SettingsEntry(key, settings, queue, hash, table[i]);
        if (++size >= threshold)
            resize(table.length * 2);
        return null;
    }

    public CrawlerSettings put(SettingsEntry entry) {
        return put(entry.getKey(), entry.getValue());
    }

    /**
     * Rehashes the contents of this hash into a new <tt>HashMap</tt> instance
     * with a larger capacity. This method is called automatically when the
     * number of keys in this map exceeds its capacity and load factor.
     *
     * Note that this method is a no-op if it's called with newCapacity ==
     * 2*MAXIMUM_CAPACITY (which is Integer.MIN_VALUE).
     *
     * @param newCapacity the new capacity, MUST be a power of two.
     */
    void resize(int newCapacity) {
        expungeStaleEntries();
        SettingsEntry[] oldTable = table;
        int oldCapacity = oldTable.length;

        // check if needed
        if (size < threshold || oldCapacity > newCapacity)
            return;