concurrentreaderhashmap.java

解决如何把XML应用到JAVA里问题

                }

            }

            else if (e.hash == hash && eq(key, e.key)) {
                Object value = e.value;
                if (value != null)
                    return value;

                // Entry was invalidated during deletion. But it could
                // have been re-inserted, so we must retraverse.
                // To avoid useless contention, get lock to wait out
                // modifications
                // before retraversing.

                synchronized (this) {
                    tab = table;
                }
                e = first = tab[index = hash & (tab.length - 1)];

            } else
                e = e.next;
        }
    }

    /**
     * Tests if the specified object is a key in this table.
     * 
     * @param key
     *            possible key.
     * @return <code>true</code> if and only if the specified object is a key
     *         in this table, as determined by the <tt>equals</tt> method;
     *         <code>false</code> otherwise.
     * @exception NullPointerException
     *                if the key is <code>null</code>.
     * @see #contains(Object)
     */

    public boolean containsKey(Object key) {
        return get(key) != null;
    }

    /**
     * Maps the specified <code>key</code> to the specified <code>value</code>
     * in this table. Neither the key nor the value can be <code>null</code>.
     * <p>
     * 
     * The value can be retrieved by calling the <code>get</code> method with
     * a key that is equal to the original key.
     * 
     * @param key
     *            the table key.
     * @param value
     *            the value.
     * @return the previous value of the specified key in this table, or
     *         <code>null</code> if it did not have one.
     * @exception NullPointerException
     *                if the key or value is <code>null</code>.
     * @see Object#equals(Object)
     * @see #get(Object)
     */

    public Object put(Object key, Object value) {
        if (value == null)
            throw new NullPointerException();

        int hash = hash(key);
        Entry[] tab = table;
        int index = hash & (tab.length - 1);
        Entry first = tab[index];
        Entry e;

        for (e = first; e != null; e = e.next)
            if (e.hash == hash && eq(key, e.key))
                break;

        synchronized (this) {
            if (tab == table) {
                if (e == null) {
                    // make sure we are adding to correct list
                    if (first == tab[index]) {
                        // Add to front of list
                        Entry newEntry = new Entry(hash, key, value, first);
                        tab[index] = newEntry;
                        if (++count >= threshold)
                            rehash();
                        else
                            recordModification(newEntry);
                        return null;
                    }
                } else {
                    Object oldValue = e.value;
                    if (first == tab[index] && oldValue != null) {
                        e.value = value;
                        return oldValue;
                    }
                }
            }

            // retry if wrong list or lost race against concurrent remove
            return sput(key, value, hash);
        }
    }

    /**
     * Continuation of put(), called only when synch lock is held and
     * interference has been detected.
     */
    protected Object sput(Object key, Object value, int hash) {

        Entry[] tab = table;
        int index = hash & (tab.length - 1);
        Entry first = tab[index];
        Entry e = first;

        for (;;) {
            if (e == null) {
                Entry newEntry = new Entry(hash, key, value, first);
                tab[index] = newEntry;
                if (++count >= threshold)
                    rehash();
                else
                    recordModification(newEntry);
                return null;
            } else if (e.hash == hash && eq(key, e.key)) {
                Object oldValue = e.value;
                e.value = value;
                return oldValue;
            } else
                e = e.next;
        }
    }

    /**
     * Rehashes the contents of this map into a new table with a larger
     * capacity. This method is called automatically when the number of keys in
     * this map exceeds its capacity and load factor.
     */
    protected void rehash() {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE; // avoid retriggering
            return;
        }

        int newCapacity = oldCapacity << 1;
        int mask = newCapacity - 1;
        threshold = (int) (newCapacity * loadFactor);

        Entry[] newTable = new Entry[newCapacity];
        /*
         * Reclassify nodes in each list to new Map. Because we are using
         * power-of-two expansion, the elements from each bin must either stay
         * at same index, or move to oldCapacity+index. We also eliminate
         * unnecessary node creation by catching cases where old nodes can be
         * reused because their next fields won't change. Statistically, at the
         * default threshhold, only about one-sixth of them need cloning. (The
         * nodes they replace will be garbage collectable as soon as they are no
         * longer referenced by any reader thread that may be in the midst of
         * traversing table right now.)
         */

        for (int i = 0; i < oldCapacity; i++) {
            // We need to guarantee that any existing reads of old Map can
            // proceed. So we cannot yet null out each bin.
            Entry e = oldTable[i];

            if (e != null) {
                int idx = e.hash & mask;
                Entry next = e.next;

                // Single node on list
                if (next == null)
                    newTable[idx] = e;

                else {
                    // Reuse trailing consecutive sequence of all same bit
                    Entry lastRun = e;
                    int lastIdx = idx;
                    for (Entry last = next; last != null; last = last.next) {
                        int k = last.hash & mask;
                        if (k != lastIdx) {
                            lastIdx = k;
                            lastRun = last;
                        }
                    }
                    newTable[lastIdx] = lastRun;

                    // Clone all remaining nodes
                    for (Entry p = e; p != lastRun; p = p.next) {
                        int k = p.hash & mask;
                        newTable[k] = new Entry(p.hash, p.key, p.value,
                                newTable[k]);
                    }
                }
            }
        }

        table = newTable;
        recordModification(newTable);
    }

    /**
     * Removes the key (and its corresponding value) from this table. This
     * method does nothing if the key is not in the table.
     * 
     * @param key
     *            the key that needs to be removed.
     * @return the value to which the key had been mapped in this table, or
     *         <code>null</code> if the key did not have a mapping.
     * @exception NullPointerException
     *                if the key is <code>null</code>.
     */

    public Object remove(Object key) {
        /*
         * Find the entry, then 1. Set value field to null, to force get() to
         * retry 2. Rebuild the list without this entry. All entries following
         * removed node can stay in list, but all preceeding ones need to be
         * cloned. Traversals rely on this strategy to ensure that elements will
         * not be repeated during iteration.
         */

        int hash = hash(key);
        Entry[] tab = table;
        int index = hash & (tab.length - 1);
        Entry first = tab[index];
        Entry e = first;

        for (e = first; e != null; e = e.next)
            if (e.hash == hash && eq(key, e.key))
                break;

        synchronized (this) {
            if (tab == table) {
                if (e == null) {
                    if (first == tab[index])
                        return null;
                } else {
                    Object oldValue = e.value;
                    if (first == tab[index] && oldValue != null) {
                        e.value = null;
                        count--;

                        Entry head = e.next;
                        for (Entry p = first; p != e; p = p.next)
                            head = new Entry(p.hash, p.key, p.value, head);

                        tab[index] = head;
                        recordModification(head);
                        return oldValue;
                    }
                }
            }

            // Wrong list or interference
            return sremove(key, hash);
        }
    }

    /**
     * Continuation of remove(), called only when synch lock is held and
     * interference has been detected.
     */

    protected Object sremove(Object key, int hash) {
        Entry[] tab = table;
        int index = hash & (tab.length - 1);
        Entry first = tab[index];

        for (Entry e = first; e != null; e = e.next) {
            if (e.hash == hash && eq(key, e.key)) {
                Object oldValue = e.value;
                e.value = null;
                count--;
                Entry head = e.next;
                for (Entry p = first; p != e; p = p.next)
                    head = new Entry(p.hash, p.key, p.value, head);

                tab[index] = head;
                recordModification(head);
                return oldValue;
            }
        }
        return null;
    }

    /**
     * Returns <tt>true</tt> if this map maps one or more keys to the
     * specified value. Note: This method requires a full internal traversal of
     * the hash table, and so is much slower than method <tt>containsKey</tt>.
     * 
     * @param value
     *            value whose presence in this map is to be tested.
     * @return <tt>true</tt> if this map maps one or more keys to the
     *         specified value.
     * @exception NullPointerException
     *                if the value is <code>null</code>.
     */

    public boolean containsValue(Object value) {
        if (value == null)
            throw new NullPointerException();

        Entry tab[] = getTableForReading();

        for (int i = 0; i < tab.length; ++i) {
            for (Entry e = tab[i]; e != null; e = e.next)
                if (value.equals(e.value))
                    return true;
        }

        return false;
    }

    /**
     * Tests if some key maps into the specified value in this table. This
     * operation is more expensive than the <code>containsKey</code> method.
     * <p>
     * 
     * Note that this method is identical in functionality to containsValue,
     * (which is part of the Map interface in the collections framework).
     * 
     * @param value
     *            a value to search for.
     * @return <code>true</code> if and only if some key maps to the
     *         <code>value</code> argument in this table as determined by the
     *         <tt>equals</tt> method; <code>false</code> otherwise.
     * @exception NullPointerException
     *                if the value is <code>null</code>.
     * @see #containsKey(Object)
     * @see #containsValue(Object)
     * @see Map
     */

    public boolean contains(Object value) {
        return containsValue(value);
    }

    /**
     * Copies all of the mappings from the specified map to this one.
     * 
     * These mappings replace any mappings that this map had for any of the keys
     * currently in the specified Map.
     * 
     * @param t
     *            Mappings to be stored in this map.
     */

    public synchronized void putAll(Map t) {
        int n = t.size();
        if (n == 0)
            return;

        // Expand enough to hold at least n elements without resizing.
        // We can only resize table by factor of two at a time.
        // It is faster to rehash with fewer elements, so do it now.
        while (n >= threshold)
            rehash();

        for (Iterator it = t.entrySet().iterator(); it.hasNext();) {
            Map.Entry entry = (Map.Entry) it.next();
            Object key = entry.getKey();
            Object value = entry.getValue();
            put(key, value);
        }
    }

    /**
     * Removes all mappings from this map.
     */
    public synchronized void clear() {
        Entry tab[] = table;
        for (int i = 0; i < tab.length; ++i) {

            // must invalidate all to force concurrent get's to wait and then
            // retry
            for (Entry e = tab[i]; e != null; e = e.next)
                e.value = null;

            tab[i] = null;
        }
        count = 0;
        recordModification(tab);
    }

    /**
     * Returns a shallow copy of this <tt>ConcurrentReaderHashMap</tt>
     * instance: the keys and values themselves are not cloned.
     * 
     * @return a shallow copy of this map.
     */

    public synchronized Object clone() {
        try {
            ConcurrentReaderHashMap t = (ConcurrentReaderHashMap) super.clone();

            t.keySet = null;
            t.entrySet = null;
            t.values = null;

            Entry[] tab = table;
            t.table = new Entry[tab.length];
            Entry[] ttab = t.table;

            for (int i = 0; i < tab.length; ++i) {
                Entry first = null;
                for (Entry e = tab[i]; e != null; e = e.next)
                    first = new Entry(e.hash, e.key, e.value, first);
                ttab[i] = first;
            }

            return t;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError();
        }
    }

    // Views

    protected transient Set keySet = null;

    protected transient Set entrySet = null;

    protected transient Collection values = null;

    /**