concurrentreaderhashmap.java

Wicket一个开发Java Web应用程序框架。它使得开发web应用程序变得容易而轻松。 Wicket利用一个POJO data beans组件使得它可以与任何持久层技术相结合。

	{
		if (value == null)
		{
			throw new IllegalArgumentException("Value must not be null");
		}
		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.
	 * 
	 * @param key
	 * @param value
	 * @param hash
	 * @return continuation object
	 */
	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 threshold,
		 * 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.
	 * 
	 * @param key
	 * @param hash
	 * @return continuation object
	 */
	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 IllegalArgumentException("Value must not be null");
		}

		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() throws CloneNotSupportedException
	{
		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;

	/**
	 * 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()
	{
		Set ks = keySet;
		return (ks != null) ? ks : (keySet = new KeySet());
	}

	private class KeySet extends AbstractSet
	{
		/**
		 * @see Collection#iterator()
		 */
		public Iterator iterator()
		{
			return new KeyIterator();
		}

		/**
		 * @see Collection#size()
		 */
		public int size()
		{
			return ConcurrentReaderHashMap.this.size();
		}

		/**
		 * @see Collection#contains(java.lang.Object)
		 */
		public boolean contains(Object o)
		{
			return containsKey(o);
		}

		/**
		 * @see Collection#remove(java.lang.Object)
		 */
		public boolean remove(Object o)
		{
			return ConcurrentReaderHashMap.this.remove(o) != null;
		}

		/**
		 * @see Collection#clear()
		 */
		public void clear()
		{
			ConcurrentReaderHashMap.this.clear();
		}