identityhashmap.java

freemaker安装软件

     */
    public Object clone()
    {
        try
        {
            IdentityHashMap t = (IdentityHashMap) super.clone();
            t.table = new Entry[table.length];
            for (int i = table.length; i-- > 0;)
            {
                t.table[i] =
                    (table[i] != null) ? (Entry) table[i].clone() : null;
            }
            t.keySet = null;
            t.entrySet = null;
            t.values = null;
            t.modCount = 0;
            return t;
        }
        catch (CloneNotSupportedException e)
        {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError();
        }
    }

    // Views

    private transient Set keySet = null;
    private transient Set entrySet = null;
    private transient Collection values = null;

    /**
     * Returns a set view of the keys contained in this map.  The set is
     * backed by the map, so changes to the map are reflected in the set, and
     * vice versa.  The set supports element removal, which removes the
     * corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
     * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
     * <tt>clear</tt> operations.  It does not support the <tt>add</tt> or
     * <tt>addAll</tt> operations.
     *
     * @return a set view of the keys contained in this map.
     */
    public Set keySet()
    {
        if (keySet == null)
        {
            keySet = new AbstractSet()
            {
                public Iterator iterator()
                {
                    return getHashIterator(KEYS);
                }
                public int size()
                {
                    return count;
                }
                public boolean contains(Object o)
                {
                    return containsKey(o);
                }
                public boolean remove(Object o)
                {
                    int oldSize = count;
                    IdentityHashMap.this.remove(o);
                    return count != oldSize;
                }
                public void clear()
                {
                    IdentityHashMap.this.clear();
                }
            };
        }
        return keySet;
    }

    /**
     * Returns a collection view of the values contained in this map.  The
     * collection is backed by the map, so changes to the map are reflected in
     * the collection, and vice versa.  The collection supports element
     * removal, which removes the corresponding mapping from this map, via the
     * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
     * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
     * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
     *
     * @return a collection view of the values contained in this map.
     */
    public Collection values()
    {
        if (values == null)
        {
            values = new AbstractCollection()
            {
                public Iterator iterator()
                {
                    return getHashIterator(VALUES);
                }
                public int size()
                {
                    return count;
                }
                public boolean contains(Object o)
                {
                    return containsValue(o);
                }
                public void clear()
                {
                    IdentityHashMap.this.clear();
                }
            };
        }
        return values;
    }

    /**
     * Returns a collection view of the mappings contained in this map.  Each
     * element in the returned collection is a <tt>Map.Entry</tt>.  The
     * collection is backed by the map, so changes to the map are reflected in
     * the collection, and vice versa.  The collection supports element
     * removal, which removes the corresponding mapping from the map, via the
     * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
     * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
     * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
     *
     * @return a collection view of the mappings contained in this map.
     * @see java.util.Map.Entry
     */
    public Set entrySet()
    {
        if (entrySet == null)
        {
            entrySet = new AbstractSet()
            {
                public Iterator iterator()
                {
                    return getHashIterator(ENTRIES);
                }

                public boolean contains(Object o)
                {
                    if (!(o instanceof Map.Entry))
                        return false;
                    Map.Entry entry = (Map.Entry) o;
                    Object key = entry.getKey();
                    Entry tab[] = table;
                    int hash = (key == null ? 0 : System.identityHashCode(key));
                    int index = (hash & 0x7FFFFFFF) % tab.length;

                    for (Entry e = tab[index]; e != null; e = e.next)
                        if (e.hash == hash && e.equals(entry))
                            return true;
                    return false;
                }

                public boolean remove(Object o)
                {
                    if (!(o instanceof Map.Entry))
                        return false;
                    Map.Entry entry = (Map.Entry) o;
                    Object key = entry.getKey();
                    Entry tab[] = table;
                    int hash = (key == null ? 0 : System.identityHashCode(key));
                    int index = (hash & 0x7FFFFFFF) % tab.length;

                    for (Entry e = tab[index], prev = null;
                        e != null;
                        prev = e, e = e.next)
                    {
                        if (e.hash == hash && e.equals(entry))
                        {
                            modCount++;
                            if (prev != null)
                                prev.next = e.next;
                            else
                                tab[index] = e.next;

                            count--;
                            e.value = null;
                            return true;
                        }
                    }
                    return false;
                }

                public int size()
                {
                    return count;
                }

                public void clear()
                {
                    IdentityHashMap.this.clear();
                }
            };
        }

        return entrySet;
    }

    private Iterator getHashIterator(int type)
    {
        if (count == 0)
        {
            return emptyHashIterator;
        }
        else
        {
            return new HashIterator(type);
        }
    }

    /**
     * IdentityHashMap collision list entry.
     */
    private static class Entry implements Map.Entry
    {
        int hash;
        Object key;
        Object value;
        Entry next;

        Entry(int hash, Object key, Object value, Entry next)
        {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        protected Object clone()
        {
            return new Entry(
                hash,
                key,
                value,
                (next == null ? null : (Entry) next.clone()));
        }

        // Map.Entry Ops

        public Object getKey()
        {
            return key;
        }

        public Object getValue()
        {
            return value;
        }

        public Object setValue(Object value)
        {
            Object oldValue = this.value;
            this.value = value;
            return oldValue;
        }

        public boolean equals(Object o)
        {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry e = (Map.Entry) o;

            return (key == e.getKey())
                && (value == null
                    ? e.getValue() == null
                    : value.equals(e.getValue()));
        }

        public int hashCode()
        {
            return hash ^ (value == null ? 0 : value.hashCode());
        }

        public String toString()
        {
            return key + "=" + value;
        }
    }

    // Types of Iterators
    private static final int KEYS = 0;
    private static final int VALUES = 1;
    private static final int ENTRIES = 2;

    private static EmptyHashIterator emptyHashIterator =
        new EmptyHashIterator();

    private static class EmptyHashIterator implements Iterator
    {

        EmptyHashIterator()
        {

        }

        public boolean hasNext()
        {
            return false;
        }

        public Object next()
        {
            throw new NoSuchElementException();
        }

        public void remove()
        {
            throw new IllegalStateException();
        }

    }

    private class HashIterator implements Iterator
    {
        Entry[] table = IdentityHashMap.this.table;
        int index = table.length;
        Entry entry = null;
        Entry lastReturned = null;
        int type;

        /**
         * The modCount value that the iterator believes that the backing
         * List should have.  If this expectation is violated, the iterator
         * has detected concurrent modification.
         */
        private int expectedModCount = modCount;

        HashIterator(int type)
        {
            this.type = type;
        }

        public boolean hasNext()
        {
            Entry e = entry;
            int i = index;
            Entry t[] = table;
            /* Use locals for faster loop iteration */
            while (e == null && i > 0)
                e = t[--i];
            entry = e;
            index = i;
            return e != null;
        }

        public Object next()
        {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();

            Entry et = entry;
            int i = index;
            Entry t[] = table;

            /* Use locals for faster loop iteration */
            while (et == null && i > 0)
                et = t[--i];

            entry = et;
            index = i;
            if (et != null)
            {
                Entry e = lastReturned = entry;
                entry = e.next;
                return type == KEYS ? e.key : (type == VALUES ? e.value : e);
            }
            throw new NoSuchElementException();
        }

        public void remove()
        {
            if (lastReturned == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();

            Entry[] tab = IdentityHashMap.this.table;
            int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length;

            for (Entry e = tab[index], prev = null;
                e != null;
                prev = e, e = e.next)
            {
                if (e == lastReturned)
                {
                    modCount++;
                    expectedModCount++;
                    if (prev == null)
                        tab[index] = e.next;
                    else
                        prev.next = e.next;
                    count--;
                    lastReturned = null;
                    return;
                }
            }
            throw new ConcurrentModificationException();
        }
    }

    /**
     * Save the state of the <tt>IdentityHashMap</tt> instance to a stream (i.e.,
     * serialize it).
     *
     * @serialData The <i>capacity</i> of the IdentityHashMap (the length of the
     *		   bucket array) is emitted (int), followed  by the
     *		   <i>size</i> of the IdentityHashMap (the number of key-value
     *		   mappings), followed by the key (Object) and value (Object)
     *		   for each key-value mapping represented by the IdentityHashMap
     * The key-value mappings are emitted in no particular order.
     */
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException
    {
        // Write out the threshold, loadfactor, and any hidden stuff
        s.defaultWriteObject();

        // Write out number of buckets
        s.writeInt(table.length);

        // Write out size (number of Mappings)
        s.writeInt(count);

        // Write out keys and values (alternating)
        for (int index = table.length - 1; index >= 0; index--)
        {
            Entry entry = table[index];

            while (entry != null)
            {
                s.writeObject(entry.key);
                s.writeObject(entry.value);
                entry = entry.next;
            }
        }
    }

    /**
     * Reconstitute the <tt>IdentityHashMap</tt> instance from a stream (i.e.,
     * deserialize it).
     */
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException
    {
        // Read in the threshold, loadfactor, and any hidden stuff
        s.defaultReadObject();

        // Read in number of buckets and allocate the bucket array;
        int numBuckets = s.readInt();
        table = new Entry[numBuckets];

        // Read in size (number of Mappings)
        int size = s.readInt();

        // Read the keys and values, and put the mappings in the IdentityHashMap
        for (int i = 0; i < size; i++)
        {
            Object key = s.readObject();
            Object value = s.readObject();
            put(key, value);
        }
    }

    int capacity()
    {
        return table.length;
    }

    float loadFactor()
    {
        return loadFactor;
    }
}