Code:
/ 4.0 / 4.0 / DEVDIV_TFS / Dev10 / Releases / RTMRel / ndp / clr / src / BCL / System / Collections / Concurrent / ConcurrentDictionary.cs / 1305376 / ConcurrentDictionary.cs
// ==++==
//
// Copyright (c) Microsoft Corporation. All rights reserved.
//
// ==--==
//
// [....]
/*============================================================
**
** Class: ConcurrentDictionary
**
**
** Purpose: A scalable dictionary for concurrent access
**
**
===========================================================*/
// If CDS_COMPILE_JUST_THIS symbol is defined, the ConcurrentDictionary.cs file compiles separately,
// with no dependencies other than .NET Framework 3.5.
//#define CDS_COMPILE_JUST_THIS
using System;
using System.Collections.Generic;
using System.Text;
using System.Threading;
using System.Runtime.InteropServices;
using System.Diagnostics;
using System.Collections;
using System.Runtime.Serialization;
using System.Security;
using System.Security.Permissions;
using System.Collections.ObjectModel;
#if !CDS_COMPILE_JUST_THIS
using System.Diagnostics.Contracts;
#endif
namespace System.Collections.Concurrent
{
///
/// Represents a thread-safe collection of keys and values.
///
/// The type of the keys in the dictionary.
/// The type of the values in the dictionary.
///
/// All public and protected members of
[Serializable]
[ComVisible(false)]
[DebuggerTypeProxy(typeof(Mscorlib_DictionaryDebugView<,>))]
[DebuggerDisplay("Count = {Count}")]
[HostProtection(Synchronization = true, ExternalThreading = true)]
public class ConcurrentDictionary : IDictionary, IDictionary
{
[NonSerialized]
private volatile Node[] m_buckets; // A singly-linked list for each bucket.
[NonSerialized]
private object[] m_locks; // A set of locks, each guarding a section of the table.
[NonSerialized]
private volatile int[] m_countPerLock; // The number of elements guarded by each lock.
private IEqualityComparer m_comparer; // Key equality comparer
private KeyValuePair[] m_serializationArray; // Used for custom serialization
private int m_serializationConcurrencyLevel; // used to save the concurrency level in serialization
private int m_serializationCapacity; // used to save the capacity in serialization
// The default concurrency level is DEFAULT_CONCURRENCY_MULTIPLIER * #CPUs. The higher the
// DEFAULT_CONCURRENCY_MULTIPLIER, the more concurrent writes can take place without interference
// and blocking, but also the more expensive operations that require all locks become (e.g. table
// resizing, ToArray, Count, etc). According to brief benchmarks that we ran, 4 seems like a good
// compromise.
private const int DEFAULT_CONCURRENCY_MULTIPLIER = 4;
// The default capacity, i.e. the initial # of buckets. When choosing this value, we are making
// a trade-off between the size of a very small dictionary, and the number of resizes when
// constructing a large dictionary. Also, the capacity should not be divisible by a small prime.
private const int DEFAULT_CAPACITY = 31;
///
/// Initializes a new instance of the
public ConcurrentDictionary() : this(DefaultConcurrencyLevel, DEFAULT_CAPACITY) { }
///
/// Initializes a new instance of the
/// The estimated number of threads that will update the
///
public ConcurrentDictionary(int concurrencyLevel, int capacity) : this(concurrencyLevel, capacity, EqualityComparer.Default) { }
///
/// Initializes a new instance of the
/// The > collection) : this(collection, EqualityComparer.Default) { }
///
/// Initializes a new instance of the
/// The comparer) : this(DefaultConcurrencyLevel, DEFAULT_CAPACITY, comparer) { }
///
/// Initializes a new instance of the
/// The > collection, IEqualityComparer comparer)
: this(DefaultConcurrencyLevel, collection, comparer) { }
///
/// Initializes a new instance of the
/// The estimated number of threads that will update the
///
///
///
///
/// > collection, IEqualityComparer comparer)
: this(concurrencyLevel, DEFAULT_CAPACITY, comparer)
{
if (collection == null) throw new ArgumentNullException("collection");
if (comparer == null) throw new ArgumentNullException("comparer");
InitializeFromCollection(collection);
}
private void InitializeFromCollection(IEnumerable> collection)
{
TValue dummy;
foreach (KeyValuePair pair in collection)
{
if (pair.Key == null) throw new ArgumentNullException("key");
if (!TryAddInternal(pair.Key, pair.Value, false, false, out dummy))
{
throw new ArgumentException(GetResource("ConcurrentDictionary_SourceContainsDuplicateKeys"));
}
}
}
///
/// Initializes a new instance of the
/// The estimated number of threads that will update the
///
///
/// comparer)
{
if (concurrencyLevel < 1)
{
throw new ArgumentOutOfRangeException("concurrencyLevel", GetResource("ConcurrentDictionary_ConcurrencyLevelMustBePositive"));
}
if (capacity < 0)
{
throw new ArgumentOutOfRangeException("capacity", GetResource("ConcurrentDictionary_CapacityMustNotBeNegative"));
}
if (comparer == null) throw new ArgumentNullException("comparer");
// The capacity should be at least as large as the concurrency level. Otherwise, we would have locks that don't guard
// any buckets.
if (capacity < concurrencyLevel)
{
capacity = concurrencyLevel;
}
m_locks = new object[concurrencyLevel];
for (int i = 0; i < m_locks.Length; i++)
{
m_locks[i] = new object();
}
m_countPerLock = new int[m_locks.Length];
m_buckets = new Node[capacity];
m_comparer = comparer;
}
///
/// Attempts to add the specified key and value to the
/// The key of the element to add.
/// The value of the element to add. The value can be a null reference (Nothing
/// in Visual Basic) for reference types.
/// true if the key/value pair was added to the
/// The
public bool TryAdd(TKey key, TValue value)
{
if (key == null) throw new ArgumentNullException("key");
TValue dummy;
return TryAddInternal(key, value, false, true, out dummy);
}
///
/// Determines whether the
/// The key to locate in the true if the
///
/// Attempts to remove and return the the value with the specified key from the
///
/// The key of the element to remove and return.
/// When this method returns, true if an object was removed successfully; otherwise, false.
///
/// Removes the specified key from the dictionary if it exists and returns its associated value.
/// If matchValue flag is set, the key will be removed only if is associated with a particular
/// value.
///
/// The key to search for and remove if it exists.
/// The variable into which the removed value, if found, is stored.
/// Whether removal of the key is conditional on its value.
/// The conditional value to compare against if .Default.Equals(oldValue, curr.m_value);
if (!valuesMatch)
{
value = default(TValue);
return false;
}
}
if (prev == null)
{
m_buckets[bucketNo] = curr.m_next;
}
else
{
prev.m_next = curr.m_next;
}
value = curr.m_value;
m_countPerLock[lockNo]--;
return true;
}
prev = curr;
}
}
value = default(TValue);
return false;
}
}
///
/// Attempts to get the value associated with the specified key from the
/// The key of the value to get.
/// When this method returns, true if the key was found in the
///
/// Compares the existing value for the specified key with a specified value, and if they’re equal,
/// updates the key with a third value.
///
/// The key whose value is compared with true if the value with
/// valueComparer = EqualityComparer.Default;
while (true)
{
int bucketNo;
int lockNo;
Node[] buckets = m_buckets;
GetBucketAndLockNo(hashcode, out bucketNo, out lockNo, buckets.Length);
lock (m_locks[lockNo])
{
// If the table just got resized, we may not be holding the right lock, and must retry.
// This should be a rare occurence.
if (buckets != m_buckets)
{
continue;
}
// Try to find this key in the bucket
Node prev = null;
for (Node node = buckets[bucketNo]; node != null; node = node.m_next)
{
Assert((prev == null && node == m_buckets[bucketNo]) || prev.m_next == node);
if (m_comparer.Equals(node.m_key, key))
{
if (valueComparer.Equals(node.m_value, comparisonValue))
{
// Replace the old node with a new node. Unfortunately, we cannot simply
// change node.m_value in place. We don't know the size of TValue, so
// its writes may not be atomic.
Node newNode = new Node(node.m_key, newValue, hashcode, node.m_next);
if (prev == null)
{
buckets[bucketNo] = newNode;
}
else
{
prev.m_next = newNode;
}
return true;
}
return false;
}
prev = node;
}
//didn't find the key
return false;
}
}
}
///
/// Removes all keys and values from the
public void Clear()
{
int locksAcquired = 0;
try
{
AcquireAllLocks(ref locksAcquired);
m_buckets = new Node[DEFAULT_CAPACITY];
Array.Clear(m_countPerLock, 0, m_countPerLock.Length);
}
finally
{
ReleaseLocks(0, locksAcquired);
}
}
///
/// Copies the elements of the
/// The one-dimensional array of type >.CopyTo(KeyValuePair[] array, int index)
{
if (array == null) throw new ArgumentNullException("array");
if (index < 0) throw new ArgumentOutOfRangeException("index", GetResource("ConcurrentDictionary_IndexIsNegative"));
int locksAcquired = 0;
try
{
AcquireAllLocks(ref locksAcquired);
int count = 0;
for (int i = 0; i < m_locks.Length; i++)
{
count += m_countPerLock[i];
}
if (array.Length - count < index || count < 0) //"count" itself or "count + index" can overflow
{
throw new ArgumentException(GetResource("ConcurrentDictionary_ArrayNotLargeEnough"));
}
CopyToPairs(array, index);
}
finally
{
ReleaseLocks(0, locksAcquired);
}
}
///
/// Copies the key and value pairs stored in the
/// A new array containing a snapshot of key and value pairs copied from the
public KeyValuePair[] ToArray()
{
int locksAcquired = 0;
try
{
AcquireAllLocks(ref locksAcquired);
int count = 0;
checked
{
for (int i = 0; i < m_locks.Length; i++)
{
count += m_countPerLock[i];
}
}
KeyValuePair[] array = new KeyValuePair[count];
CopyToPairs(array, 0);
return array;
}
finally
{
ReleaseLocks(0, locksAcquired);
}
}
///
/// Copy dictionary contents to an array - shared implementation between ToArray and CopyTo.
///
/// Important: the caller must hold all locks in m_locks before calling CopyToPairs.
///
private void CopyToPairs(KeyValuePair[] array, int index)
{
Node[] buckets = m_buckets;
for (int i = 0; i < buckets.Length; i++)
{
for (Node current = buckets[i]; current != null; current = current.m_next)
{
array[index] = new KeyValuePair(current.m_key, current.m_value);
index++; //this should never flow, CopyToPairs is only called when there's no overflow risk
}
}
}
///
/// Copy dictionary contents to an array - shared implementation between ToArray and CopyTo.
///
/// Important: the caller must hold all locks in m_locks before calling CopyToEntries.
///
private void CopyToEntries(DictionaryEntry[] array, int index)
{
Node[] buckets = m_buckets;
for (int i = 0; i < buckets.Length; i++)
{
for (Node current = buckets[i]; current != null; current = current.m_next)
{
array[index] = new DictionaryEntry(current.m_key, current.m_value);
index++; //this should never flow, CopyToEntries is only called when there's no overflow risk
}
}
}
///
/// Copy dictionary contents to an array - shared implementation between ToArray and CopyTo.
///
/// Important: the caller must hold all locks in m_locks before calling CopyToObjects.
///
private void CopyToObjects(object[] array, int index)
{
Node[] buckets = m_buckets;
for (int i = 0; i < buckets.Length; i++)
{
for (Node current = buckets[i]; current != null; current = current.m_next)
{
array[index] = new KeyValuePair(current.m_key, current.m_value);
index++; //this should never flow, CopyToObjects is only called when there's no overflow risk
}
}
}
/// Returns an enumerator that iterates through the
/// An enumerator for the
///
/// The enumerator returned from the dictionary is safe to use concurrently with
/// reads and writes to the dictionary, however it does not represent a moment-in-time snapshot
/// of the dictionary. The contents exposed through the enumerator may contain modifications
/// made to the dictionary after
public IEnumerator> GetEnumerator()
{
Node[] buckets = m_buckets;
for (int i = 0; i < buckets.Length; i++)
{
Node current = buckets[i];
// The memory barrier ensures that the load of the fields of 'current' doesn’t move before the load from buckets[i].
Thread.MemoryBarrier();
while (current != null)
{
yield return new KeyValuePair(current.m_key, current.m_value);
current = current.m_next;
}
}
}
///
/// Shared internal implementation for inserts and updates.
/// If key exists, we always return false; and if updateIfExists == true we force update with value;
/// If key doesn't exist, we always add value and return true;
///
private bool TryAddInternal(TKey key, TValue value, bool updateIfExists, bool acquireLock, out TValue resultingValue)
{
int hashcode = m_comparer.GetHashCode(key);
while (true)
{
int bucketNo, lockNo;
Node[] buckets = m_buckets;
GetBucketAndLockNo(hashcode, out bucketNo, out lockNo, buckets.Length);
bool resizeDesired = false;
bool lockTaken = false;
try
{
if (acquireLock)
Monitor.Enter(m_locks[lockNo], ref lockTaken);
// If the table just got resized, we may not be holding the right lock, and must retry.
// This should be a rare occurence.
if (buckets != m_buckets)
{
continue;
}
// Try to find this key in the bucket
Node prev = null;
for (Node node = buckets[bucketNo]; node != null; node = node.m_next)
{
Assert((prev == null && node == m_buckets[bucketNo]) || prev.m_next == node);
if (m_comparer.Equals(node.m_key, key))
{
// The key was found in the dictionary. If updates are allowed, update the value for that key.
// We need to create a new node for the update, in order to support TValue types that cannot
// be written atomically, since lock-free reads may be happening concurrently.
if (updateIfExists)
{
Node newNode = new Node(node.m_key, value, hashcode, node.m_next);
if (prev == null)
{
buckets[bucketNo] = newNode;
}
else
{
prev.m_next = newNode;
}
resultingValue = value;
}
else
{
resultingValue = node.m_value;
}
return false;
}
prev = node;
}
// The key was not found in the bucket. Insert the key-value pair.
buckets[bucketNo] = new Node(key, value, hashcode, buckets[bucketNo]);
checked
{
m_countPerLock[lockNo]++;
}
//
// If this lock has element / bucket ratio greater than 1, resize the entire table.
// Note: the formula is chosen to avoid overflow, but has a small inaccuracy due to
// rounding.
//
if (m_countPerLock[lockNo] > buckets.Length / m_locks.Length)
{
resizeDesired = true;
}
}
finally
{
if (lockTaken)
Monitor.Exit(m_locks[lockNo]);
}
//
// The fact that we got here means that we just performed an insertion. If necessary, we will grow the table.
//
// Concurrency notes:
// - Notice that we are not holding any locks at when calling GrowTable. This is necessary to prevent deadlocks.
// - As a result, it is possible that GrowTable will be called unnecessarily. But, GrowTable will obtain lock 0
// and then verify that the table we passed to it as the argument is still the current table.
//
if (resizeDesired)
{
GrowTable(buckets);
}
resultingValue = value;
return true;
}
}
///
/// Gets or sets the value associated with the specified key.
///
/// The key of the value to get or set.
/// The value associated with the specified key. If the specified key is not found, a get
/// operation throws a
///
/// The property is retrieved and
///
public TValue this[TKey key]
{
get
{
TValue value;
if (!TryGetValue(key, out value))
{
throw new KeyNotFoundException();
}
return value;
}
set
{
if (key == null) throw new ArgumentNullException("key");
TValue dummy;
TryAddInternal(key, value, true, true, out dummy);
}
}
///
/// Gets the number of key/value pairs contained in the
/// The dictionary contains too many
/// elements.
/// The number of key/value paris contained in the
/// Count has snapshot semantics and represents the number of items in the
public int Count
{
get
{
int count = 0;
int acquiredLocks = 0;
try
{
// Acquire all locks
AcquireAllLocks(ref acquiredLocks);
// Compute the count, we allow overflow
for (int i = 0; i < m_countPerLock.Length; i++)
{
count += m_countPerLock[i];
}
}
finally
{
// Release locks that have been acquired earlier
ReleaseLocks(0, acquiredLocks);
}
return count;
}
}
///
/// Adds a key/value pair to the
/// The key of the element to add.
/// The function used to generate a value for the key
/// The dictionary contains too many
/// elements.
/// The value for the key. This will be either the existing value for the key if the
/// key is already in the dictionary, or the new value for the key as returned by valueFactory
/// if the key was not in the dictionary.
public TValue GetOrAdd(TKey key, Func valueFactory)
{
if (key == null) throw new ArgumentNullException("key");
if (valueFactory == null) throw new ArgumentNullException("valueFactory");
TValue resultingValue;
if (TryGetValue(key, out resultingValue))
{
return resultingValue;
}
TryAddInternal(key, valueFactory(key), false, true, out resultingValue);
return resultingValue;
}
///
/// Adds a key/value pair to the
/// The key of the element to add.
/// the value to be added, if the key does not already exist
/// The dictionary contains too many
/// elements.
/// The value for the key. This will be either the existing value for the key if the
/// key is already in the dictionary, or the new value if the key was not in the dictionary.
public TValue GetOrAdd(TKey key, TValue value)
{
if (key == null) throw new ArgumentNullException("key");
TValue resultingValue;
TryAddInternal(key, value, false, true, out resultingValue);
return resultingValue;
}
///
/// Adds a key/value pair to the
/// The key to be added or whose value should be updated
/// The function used to generate a value for an absent key
/// The function used to generate a new value for an existing key
/// based on the key's existing value
/// The dictionary contains too many
/// elements.
/// The new value for the key. This will be either be the result of addValueFactory (if the key was
/// absent) or the result of updateValueFactory (if the key was present).
public TValue AddOrUpdate(TKey key, Func addValueFactory, Func updateValueFactory)
{
if (key == null) throw new ArgumentNullException("key");
if (addValueFactory == null) throw new ArgumentNullException("addValueFactory");
if (updateValueFactory == null) throw new ArgumentNullException("updateValueFactory");
TValue newValue, resultingValue;
while (true)
{
TValue oldValue;
if (TryGetValue(key, out oldValue))
//key exists, try to update
{
newValue = updateValueFactory(key, oldValue);
if (TryUpdate(key, newValue, oldValue))
{
return newValue;
}
}
else //try add
{
newValue = addValueFactory(key);
if (TryAddInternal(key, newValue, false, true, out resultingValue))
{
return resultingValue;
}
}
}
}
///
/// Adds a key/value pair to the
/// The key to be added or whose value should be updated
/// The value to be added for an absent key
/// The function used to generate a new value for an existing key based on
/// the key's existing value
/// The dictionary contains too many
/// elements.
/// The new value for the key. This will be either be the result of addValueFactory (if the key was
/// absent) or the result of updateValueFactory (if the key was present).
public TValue AddOrUpdate(TKey key, TValue addValue, Func updateValueFactory)
{
if (key == null) throw new ArgumentNullException("key");
if (updateValueFactory == null) throw new ArgumentNullException("updateValueFactory");
TValue newValue, resultingValue;
while (true)
{
TValue oldValue;
if (TryGetValue(key, out oldValue))
//key exists, try to update
{
newValue = updateValueFactory(key, oldValue);
if (TryUpdate(key, newValue, oldValue))
{
return newValue;
}
}
else //try add
{
if (TryAddInternal(key, addValue, false, true, out resultingValue))
{
return resultingValue;
}
}
}
}
///
/// Gets a value that indicates whether the
/// true if the
public bool IsEmpty
{
get
{
int acquiredLocks = 0;
try
{
// Acquire all locks
AcquireAllLocks(ref acquiredLocks);
for (int i = 0; i < m_countPerLock.Length; i++)
{
if (m_countPerLock[i] != 0)
{
return false;
}
}
}
finally
{
// Release locks that have been acquired earlier
ReleaseLocks(0, acquiredLocks);
}
return true;
}
}
#region IDictionary members
///
/// Adds the specified key and value to the
/// The object to use as the key of the element to add.
/// The object to use as the value of the element to add.
/// The dictionary contains too many
/// elements.
///
/// An element with the same key already exists in the
void IDictionary.Add(TKey key, TValue value)
{
if (!TryAdd(key, value))
{
throw new ArgumentException(GetResource("ConcurrentDictionary_KeyAlreadyExisted"));
}
}
///
/// Removes the element with the specified key from the
/// The key of the element to remove.
/// true if the element is successfully remove; otherwise false. This method also returns
/// false if
///
/// .Remove(TKey key)
{
TValue throwAwayValue;
return TryRemove(key, out throwAwayValue);
}
///
/// Gets a collection containing the keys in the
/// An
public ICollection Keys
{
get { return GetKeys(); }
}
///
/// Gets a collection containing the values in the
/// An
public ICollection Values
{
get { return GetValues(); }
}
#endregion
#region ICollection> Members
///
/// Adds the specified value to the
/// The The
/// The
/// An element with the same key already exists in the
///
void ICollection>.Add(KeyValuePair keyValuePair)
{
((IDictionary)this).Add(keyValuePair.Key, keyValuePair.Value);
}
///
/// Determines whether the
/// The true if the
bool ICollection>.Contains(KeyValuePair keyValuePair)
{
TValue value;
if (!TryGetValue(keyValuePair.Key, out value))
{
return false;
}
return EqualityComparer.Default.Equals(value, keyValuePair.Value);
}
///
/// Gets a value indicating whether the dictionary is read-only.
///
/// true if the
bool ICollection>.IsReadOnly
{
get { return false; }
}
///
/// Removes a key and value from the dictionary.
///
/// The true if the key and value represented by
/// The Key property of
bool ICollection>.Remove(KeyValuePair keyValuePair)
{
if (keyValuePair.Key == null) throw new ArgumentNullException(GetResource("ConcurrentDictionary_ItemKeyIsNull"));
TValue throwAwayValue;
return TryRemoveInternal(keyValuePair.Key, out throwAwayValue, true, keyValuePair.Value);
}
#endregion
#region IEnumerable Members
/// Returns an enumerator that iterates through the
/// An enumerator for the
///
/// The enumerator returned from the dictionary is safe to use concurrently with
/// reads and writes to the dictionary, however it does not represent a moment-in-time snapshot
/// of the dictionary. The contents exposed through the enumerator may contain modifications
/// made to the dictionary after
IEnumerator IEnumerable.GetEnumerator()
{
return ((ConcurrentDictionary)this).GetEnumerator();
}
#endregion
#region IDictionary Members
///
/// Adds the specified key and value to the dictionary.
///
/// The object to use as the key.
/// The object to use as the value.
/// The dictionary contains too many
/// elements.
///
///
void IDictionary.Add(object key, object value)
{
if (key == null) throw new ArgumentNullException("key");
if (!(key is TKey)) throw new ArgumentException(GetResource("ConcurrentDictionary_TypeOfKeyIncorrect"));
TValue typedValue;
try
{
typedValue = (TValue)value;
}
catch (InvalidCastException)
{
throw new ArgumentException(GetResource("ConcurrentDictionary_TypeOfValueIncorrect"));
}
((IDictionary)this).Add((TKey)key, typedValue);
}
///
/// Gets whether the
/// The key to locate in the true if the
///
bool IDictionary.Contains(object key)
{
if (key == null) throw new ArgumentNullException("key");
return (key is TKey) && ((ConcurrentDictionary)this).ContainsKey((TKey)key);
}
/// Provides an
/// An
IDictionaryEnumerator IDictionary.GetEnumerator()
{
return new DictionaryEnumerator(this);
}
///
/// Gets a value indicating whether the
/// true if the
bool IDictionary.IsFixedSize
{
get { return false; }
}
///
/// Gets a value indicating whether the
/// true if the
bool IDictionary.IsReadOnly
{
get { return false; }
}
///
/// Gets an
/// An
ICollection IDictionary.Keys
{
get { return GetKeys(); }
}
///
/// Removes the element with the specified key from the
/// The key of the element to remove.
///
/// Gets an
/// An
ICollection IDictionary.Values
{
get { return GetValues(); }
}
///
/// Gets or sets the value associated with the specified key.
///
/// The key of the value to get or set.
/// The value associated with the specified key, or a null reference (Nothing in Visual Basic)
/// if
///
/// A value is being assigned, and
object IDictionary.this[object key]
{
get
{
if (key == null) throw new ArgumentNullException("key");
TValue value;
if (key is TKey && this.TryGetValue((TKey)key, out value))
{
return value;
}
return null;
}
set
{
if (key == null) throw new ArgumentNullException("key");
if (!(key is TKey)) throw new ArgumentException(GetResource("ConcurrentDictionary_TypeOfKeyIncorrect"));
if (!(value is TValue)) throw new ArgumentException(GetResource("ConcurrentDictionary_TypeOfValueIncorrect"));
((ConcurrentDictionary)this)[(TKey)key] = (TValue)value;
}
}
#endregion
#region ICollection Members
///
/// Copies the elements of the
/// The one-dimensional array that is the destination of the elements copied from
/// the ,
// we recognize three types of target arrays:
// - an array of KeyValuePair structs
// - an array of DictionaryEntry structs
// - an array of objects
KeyValuePair[] pairs = array as KeyValuePair[];
if (pairs != null)
{
CopyToPairs(pairs, index);
return;
}
DictionaryEntry[] entries = array as DictionaryEntry[];
if (entries != null)
{
CopyToEntries(entries, index);
return;
}
object[] objects = array as object[];
if (objects != null)
{
CopyToObjects(objects, index);
return;
}
throw new ArgumentException(GetResource("ConcurrentDictionary_ArrayIncorrectType"), "array");
}
finally
{
ReleaseLocks(0, locksAcquired);
}
}
///
/// Gets a value indicating whether access to the
/// true if access to the
bool ICollection.IsSynchronized
{
get { return false; }
}
///
/// Gets an object that can be used to synchronize access to the
/// The SyncRoot property is not supported.
object ICollection.SyncRoot
{
get
{
throw new NotSupportedException(Environment.GetResourceString("ConcurrentCollection_SyncRoot_NotSupported"));
}
}
#endregion
///
/// Replaces the internal table with a larger one. To prevent multiple threads from resizing the
/// table as a result of ----s, the table of buckets that was deemed too small is passed in as
/// an argument to GrowTable(). GrowTable() obtains a lock, and then checks whether the bucket
/// table has been replaced in the meantime or not.
///
/// Reference to the bucket table that was deemed too small.
private void GrowTable(Node[] buckets)
{
int locksAcquired = 0;
try
{
// The thread that first obtains m_locks[0] will be the one doing the resize operation
AcquireLocks(0, 1, ref locksAcquired);
// Make sure nobody resized the table while we were waiting for lock 0:
if (buckets != m_buckets)
{
// We assume that since the table reference is different, it was already resized. If we ever
// decide to do table shrinking, or replace the table for other reasons, we will have to revisit
// this logic.
return;
}
// Compute the new table size. We find the smallest integer larger than twice the previous table size, and not divisible by
// 2,3,5 or 7. We can consider a different table-sizing policy in the future.
int newLength;
try
{
checked
{
// Double the size of the buckets table and add one, so that we have an odd integer.
newLength = buckets.Length * 2 + 1;
// Now, we only need to check odd integers, and find the first that is not divisible
// by 3, 5 or 7.
while (newLength % 3 == 0 || newLength % 5 == 0 || newLength % 7 == 0)
{
newLength += 2;
}
Assert(newLength % 2 != 0);
}
}
catch (OverflowException)
{
// If we were to resize the table, its new size will not fit into a 32-bit signed int. Just return.
return;
}
Node[] newBuckets = new Node[newLength];
int[] newCountPerLock = new int[m_locks.Length];
// Now acquire all other locks for the table
AcquireLocks(1, m_locks.Length, ref locksAcquired);
// Copy all data into a new table, creating new nodes for all elements
for (int i = 0; i < buckets.Length; i++)
{
Node current = buckets[i];
while (current != null)
{
Node next = current.m_next;
int newBucketNo, newLockNo;
GetBucketAndLockNo(current.m_hashcode, out newBucketNo, out newLockNo, newBuckets.Length);
newBuckets[newBucketNo] = new Node(current.m_key, current.m_value, current.m_hashcode, newBuckets[newBucketNo]);
checked
{
newCountPerLock[newLockNo]++;
}
current = next;
}
}
// And finally adjust m_buckets and m_countPerLock to point to data for the new table
m_buckets = newBuckets;
m_countPerLock = newCountPerLock;
}
finally
{
// Release all locks that we took earlier
ReleaseLocks(0, locksAcquired);
}
}
///
/// Computes the bucket and lock number for a particular key.
///
private void GetBucketAndLockNo(
int hashcode, out int bucketNo, out int lockNo, int bucketCount)
{
bucketNo = (hashcode & 0x7fffffff) % bucketCount;
lockNo = bucketNo % m_locks.Length;
Assert(bucketNo >= 0 && bucketNo < bucketCount);
Assert(lockNo >= 0 && lockNo < m_locks.Length);
}
///
/// The number of concurrent writes for which to optimize by default.
///
private static int DefaultConcurrencyLevel
{
get { return DEFAULT_CONCURRENCY_MULTIPLIER * Environment.ProcessorCount; }
}
///
/// Acquires all locks for this hash table, and increments locksAcquired by the number
/// of locks that were successfully acquired. The locks are acquired in an increasing
/// order.
///
private void AcquireAllLocks(ref int locksAcquired)
{
#if !FEATURE_PAL
if (CDSCollectionETWBCLProvider.Log.IsEnabled())
{
CDSCollectionETWBCLProvider.Log.ConcurrentDictionary_AcquiringAllLocks(m_buckets.Length);
}
#endif //!FEATURE_PAL
AcquireLocks(0, m_locks.Length, ref locksAcquired);
Assert(locksAcquired == m_locks.Length);
}
///
/// Acquires a contiguous range of locks for this hash table, and increments locksAcquired
/// by the number of locks that were successfully acquired. The locks are acquired in an
/// increasing order.
///
private void AcquireLocks(int fromInclusive, int toExclusive, ref int locksAcquired)
{
Assert(fromInclusive <= toExclusive);
for (int i = fromInclusive; i < toExclusive; i++)
{
bool lockTaken = false;
try
{
#if CDS_COMPILE_JUST_THIS
Monitor.Enter(m_locks[i]);
lockTaken = true;
#else
Monitor.Enter(m_locks[i], ref lockTaken);
#endif
}
finally
{
if (lockTaken)
{
locksAcquired++;
}
}
}
}
///
/// Releases a contiguous range of locks.
///
private void ReleaseLocks(int fromInclusive, int toExclusive)
{
Assert(fromInclusive <= toExclusive);
for (int i = fromInclusive; i < toExclusive; i++)
{
Monitor.Exit(m_locks[i]);
}
}
///
/// Gets a collection containing the keys in the dictionary.
///
private ReadOnlyCollection GetKeys()
{
int locksAcquired = 0;
try
{
AcquireAllLocks(ref locksAcquired);
List keys = new List();
for (int i = 0; i < m_buckets.Length; i++)
{
Node current = m_buckets[i];
while (current != null)
{
keys.Add(current.m_key);
current = current.m_next;
}
}
return new ReadOnlyCollection(keys);
}
finally
{
ReleaseLocks(0, locksAcquired);
}
}
///
/// Gets a collection containing the values in the dictionary.
///
private ReadOnlyCollection GetValues()
{
int locksAcquired = 0;
try
{
AcquireAllLocks(ref locksAcquired);
List values = new List();
for (int i = 0; i < m_buckets.Length; i++)
{
Node current = m_buckets[i];
while (current != null)
{
values.Add(current.m_value);
current = current.m_next;
}
}
return new ReadOnlyCollection(values);
}
finally
{
ReleaseLocks(0, locksAcquired);
}
}
///
/// A helper method for asserts.
///
[Conditional("DEBUG")]
private void Assert(bool condition)
{
#if CDS_COMPILE_JUST_THIS
if (!condition)
{
throw new Exception("Assertion failed.");
}
#else
Contract.Assert(condition);
#endif
}
///
/// A helper function to obtain the string for a particular resource key.
///
///
///
/// A node in a singly-linked list representing a particular hash table bucket.
///
private class Node
{
internal TKey m_key;
internal TValue m_value;
internal volatile Node m_next;
internal int m_hashcode;
internal Node(TKey key, TValue value, int hashcode)
: this(key, value, hashcode, null)
{
}
internal Node(TKey key, TValue value, int hashcode, Node next)
{
m_key = key;
m_value = value;
m_next = next;
m_hashcode = hashcode;
}
}
///
/// A private class to represent enumeration over the dictionary that implements the
/// IDictionaryEnumerator interface.
///
private class DictionaryEnumerator : IDictionaryEnumerator
{
IEnumerator> m_enumerator; // Enumerator over the dictionary.
internal DictionaryEnumerator(ConcurrentDictionary dictionary)
{
m_enumerator = dictionary.GetEnumerator();
}
public DictionaryEntry Entry
{
get { return new DictionaryEntry(m_enumerator.Current.Key, m_enumerator.Current.Value); }
}
public object Key
{
get { return m_enumerator.Current.Key; }
}
public object Value
{
get { return m_enumerator.Current.Value; }
}
public object Current
{
get { return this.Entry; }
}
public bool MoveNext()
{
return m_enumerator.MoveNext();
}
public void Reset()
{
m_enumerator.Reset();
}
}
///
/// Get the data array to be serialized
///
[OnSerializing]
private void OnSerializing(StreamingContext context)
{
// save the data into the serialization array to be saved
m_serializationArray = ToArray();
m_serializationConcurrencyLevel = m_locks.Length;
m_serializationCapacity = m_buckets.Length;
}
///
/// Construct the dictionary from a previously seiralized one
///
[OnDeserialized]
private void OnDeserialized(StreamingContext context)
{
KeyValuePair[] array = m_serializationArray;
m_buckets = new Node[m_serializationCapacity];
m_countPerLock = new int[m_serializationConcurrencyLevel];
m_locks = new object[m_serializationConcurrencyLevel];
for (int i = 0; i < m_locks.Length; i++)
{
m_locks[i] = new object();
}
InitializeFromCollection(array);
m_serializationArray = null;
}
}
}
// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
// ==++==
//
// Copyright (c) Microsoft Corporation. All rights reserved.
//
// ==--==
//
// [....]
/*============================================================
**
** Class: ConcurrentDictionary
**
**
** Purpose: A scalable dictionary for concurrent access
**
**
===========================================================*/
// If CDS_COMPILE_JUST_THIS symbol is defined, the ConcurrentDictionary.cs file compiles separately,
// with no dependencies other than .NET Framework 3.5.
//#define CDS_COMPILE_JUST_THIS
using System;
using System.Collections.Generic;
using System.Text;
using System.Threading;
using System.Runtime.InteropServices;
using System.Diagnostics;
using System.Collections;
using System.Runtime.Serialization;
using System.Security;
using System.Security.Permissions;
using System.Collections.ObjectModel;
#if !CDS_COMPILE_JUST_THIS
using System.Diagnostics.Contracts;
#endif
namespace System.Collections.Concurrent
{
///
/// Represents a thread-safe collection of keys and values.
///
/// The type of the keys in the dictionary.
/// The type of the values in the dictionary.
///
/// All public and protected members of
[Serializable]
[ComVisible(false)]
[DebuggerTypeProxy(typeof(Mscorlib_DictionaryDebugView<,>))]
[DebuggerDisplay("Count = {Count}")]
[HostProtection(Synchronization = true, ExternalThreading = true)]
public class ConcurrentDictionary : IDictionary, IDictionary
{
[NonSerialized]
private volatile Node[] m_buckets; // A singly-linked list for each bucket.
[NonSerialized]
private object[] m_locks; // A set of locks, each guarding a section of the table.
[NonSerialized]
private volatile int[] m_countPerLock; // The number of elements guarded by each lock.
private IEqualityComparer m_comparer; // Key equality comparer
private KeyValuePair[] m_serializationArray; // Used for custom serialization
private int m_serializationConcurrencyLevel; // used to save the concurrency level in serialization
private int m_serializationCapacity; // used to save the capacity in serialization
// The default concurrency level is DEFAULT_CONCURRENCY_MULTIPLIER * #CPUs. The higher the
// DEFAULT_CONCURRENCY_MULTIPLIER, the more concurrent writes can take place without interference
// and blocking, but also the more expensive operations that require all locks become (e.g. table
// resizing, ToArray, Count, etc). According to brief benchmarks that we ran, 4 seems like a good
// compromise.
private const int DEFAULT_CONCURRENCY_MULTIPLIER = 4;
// The default capacity, i.e. the initial # of buckets. When choosing this value, we are making
// a trade-off between the size of a very small dictionary, and the number of resizes when
// constructing a large dictionary. Also, the capacity should not be divisible by a small prime.
private const int DEFAULT_CAPACITY = 31;
///
/// Initializes a new instance of the
public ConcurrentDictionary() : this(DefaultConcurrencyLevel, DEFAULT_CAPACITY) { }
///
/// Initializes a new instance of the
/// The estimated number of threads that will update the
///
public ConcurrentDictionary(int concurrencyLevel, int capacity) : this(concurrencyLevel, capacity, EqualityComparer.Default) { }
///
/// Initializes a new instance of the
/// The > collection) : this(collection, EqualityComparer.Default) { }
///
/// Initializes a new instance of the
/// The comparer) : this(DefaultConcurrencyLevel, DEFAULT_CAPACITY, comparer) { }
///
/// Initializes a new instance of the
/// The > collection, IEqualityComparer comparer)
: this(DefaultConcurrencyLevel, collection, comparer) { }
///
/// Initializes a new instance of the
/// The estimated number of threads that will update the
///
///
///
///
/// > collection, IEqualityComparer comparer)
: this(concurrencyLevel, DEFAULT_CAPACITY, comparer)
{
if (collection == null) throw new ArgumentNullException("collection");
if (comparer == null) throw new ArgumentNullException("comparer");
InitializeFromCollection(collection);
}
private void InitializeFromCollection(IEnumerable> collection)
{
TValue dummy;
foreach (KeyValuePair pair in collection)
{
if (pair.Key == null) throw new ArgumentNullException("key");
if (!TryAddInternal(pair.Key, pair.Value, false, false, out dummy))
{
throw new ArgumentException(GetResource("ConcurrentDictionary_SourceContainsDuplicateKeys"));
}
}
}
///
/// Initializes a new instance of the
/// The estimated number of threads that will update the
///
///
/// comparer)
{
if (concurrencyLevel < 1)
{
throw new ArgumentOutOfRangeException("concurrencyLevel", GetResource("ConcurrentDictionary_ConcurrencyLevelMustBePositive"));
}
if (capacity < 0)
{
throw new ArgumentOutOfRangeException("capacity", GetResource("ConcurrentDictionary_CapacityMustNotBeNegative"));
}
if (comparer == null) throw new ArgumentNullException("comparer");
// The capacity should be at least as large as the concurrency level. Otherwise, we would have locks that don't guard
// any buckets.
if (capacity < concurrencyLevel)
{
capacity = concurrencyLevel;
}
m_locks = new object[concurrencyLevel];
for (int i = 0; i < m_locks.Length; i++)
{
m_locks[i] = new object();
}
m_countPerLock = new int[m_locks.Length];
m_buckets = new Node[capacity];
m_comparer = comparer;
}
///
/// Attempts to add the specified key and value to the
/// The key of the element to add.
/// The value of the element to add. The value can be a null reference (Nothing
/// in Visual Basic) for reference types.
/// true if the key/value pair was added to the
/// The
public bool TryAdd(TKey key, TValue value)
{
if (key == null) throw new ArgumentNullException("key");
TValue dummy;
return TryAddInternal(key, value, false, true, out dummy);
}
///
/// Determines whether the
/// The key to locate in the true if the
///
/// Attempts to remove and return the the value with the specified key from the
///
/// The key of the element to remove and return.
/// When this method returns, true if an object was removed successfully; otherwise, false.
///
/// Removes the specified key from the dictionary if it exists and returns its associated value.
/// If matchValue flag is set, the key will be removed only if is associated with a particular
/// value.
///
/// The key to search for and remove if it exists.
/// The variable into which the removed value, if found, is stored.
/// Whether removal of the key is conditional on its value.
/// The conditional value to compare against if .Default.Equals(oldValue, curr.m_value);
if (!valuesMatch)
{
value = default(TValue);
return false;
}
}
if (prev == null)
{
m_buckets[bucketNo] = curr.m_next;
}
else
{
prev.m_next = curr.m_next;
}
value = curr.m_value;
m_countPerLock[lockNo]--;
return true;
}
prev = curr;
}
}
value = default(TValue);
return false;
}
}
///
/// Attempts to get the value associated with the specified key from the
/// The key of the value to get.
/// When this method returns, true if the key was found in the
///
/// Compares the existing value for the specified key with a specified value, and if they’re equal,
/// updates the key with a third value.
///
/// The key whose value is compared with true if the value with
/// valueComparer = EqualityComparer.Default;
while (true)
{
int bucketNo;
int lockNo;
Node[] buckets = m_buckets;
GetBucketAndLockNo(hashcode, out bucketNo, out lockNo, buckets.Length);
lock (m_locks[lockNo])
{
// If the table just got resized, we may not be holding the right lock, and must retry.
// This should be a rare occurence.
if (buckets != m_buckets)
{
continue;
}
// Try to find this key in the bucket
Node prev = null;
for (Node node = buckets[bucketNo]; node != null; node = node.m_next)
{
Assert((prev == null && node == m_buckets[bucketNo]) || prev.m_next == node);
if (m_comparer.Equals(node.m_key, key))
{
if (valueComparer.Equals(node.m_value, comparisonValue))
{
// Replace the old node with a new node. Unfortunately, we cannot simply
// change node.m_value in place. We don't know the size of TValue, so
// its writes may not be atomic.
Node newNode = new Node(node.m_key, newValue, hashcode, node.m_next);
if (prev == null)
{
buckets[bucketNo] = newNode;
}
else
{
prev.m_next = newNode;
}
return true;
}
return false;
}
prev = node;
}
//didn't find the key
return false;
}
}
}
///
/// Removes all keys and values from the
public void Clear()
{
int locksAcquired = 0;
try
{
AcquireAllLocks(ref locksAcquired);
m_buckets = new Node[DEFAULT_CAPACITY];
Array.Clear(m_countPerLock, 0, m_countPerLock.Length);
}
finally
{
ReleaseLocks(0, locksAcquired);
}
}
///
/// Copies the elements of the
/// The one-dimensional array of type >.CopyTo(KeyValuePair[] array, int index)
{
if (array == null) throw new ArgumentNullException("array");
if (index < 0) throw new ArgumentOutOfRangeException("index", GetResource("ConcurrentDictionary_IndexIsNegative"));
int locksAcquired = 0;
try
{
AcquireAllLocks(ref locksAcquired);
int count = 0;
for (int i = 0; i < m_locks.Length; i++)
{
count += m_countPerLock[i];
}
if (array.Length - count < index || count < 0) //"count" itself or "count + index" can overflow
{
throw new ArgumentException(GetResource("ConcurrentDictionary_ArrayNotLargeEnough"));
}
CopyToPairs(array, index);
}
finally
{
ReleaseLocks(0, locksAcquired);
}
}
///
/// Copies the key and value pairs stored in the
/// A new array containing a snapshot of key and value pairs copied from the
public KeyValuePair[] ToArray()
{
int locksAcquired = 0;
try
{
AcquireAllLocks(ref locksAcquired);
int count = 0;
checked
{
for (int i = 0; i < m_locks.Length; i++)
{
count += m_countPerLock[i];
}
}
KeyValuePair[] array = new KeyValuePair[count];
CopyToPairs(array, 0);
return array;
}
finally
{
ReleaseLocks(0, locksAcquired);
}
}
///
/// Copy dictionary contents to an array - shared implementation between ToArray and CopyTo.
///
/// Important: the caller must hold all locks in m_locks before calling CopyToPairs.
///
private void CopyToPairs(KeyValuePair[] array, int index)
{
Node[] buckets = m_buckets;
for (int i = 0; i < buckets.Length; i++)
{
for (Node current = buckets[i]; current != null; current = current.m_next)
{
array[index] = new KeyValuePair(current.m_key, current.m_value);
index++; //this should never flow, CopyToPairs is only called when there's no overflow risk
}
}
}
///
/// Copy dictionary contents to an array - shared implementation between ToArray and CopyTo.
///
/// Important: the caller must hold all locks in m_locks before calling CopyToEntries.
///
private void CopyToEntries(DictionaryEntry[] array, int index)
{
Node[] buckets = m_buckets;
for (int i = 0; i < buckets.Length; i++)
{
for (Node current = buckets[i]; current != null; current = current.m_next)
{
array[index] = new DictionaryEntry(current.m_key, current.m_value);
index++; //this should never flow, CopyToEntries is only called when there's no overflow risk
}
}
}
///
/// Copy dictionary contents to an array - shared implementation between ToArray and CopyTo.
///
/// Important: the caller must hold all locks in m_locks before calling CopyToObjects.
///
private void CopyToObjects(object[] array, int index)
{
Node[] buckets = m_buckets;
for (int i = 0; i < buckets.Length; i++)
{
for (Node current = buckets[i]; current != null; current = current.m_next)
{
array[index] = new KeyValuePair(current.m_key, current.m_value);
index++; //this should never flow, CopyToObjects is only called when there's no overflow risk
}
}
}
/// Returns an enumerator that iterates through the
/// An enumerator for the
///
/// The enumerator returned from the dictionary is safe to use concurrently with
/// reads and writes to the dictionary, however it does not represent a moment-in-time snapshot
/// of the dictionary. The contents exposed through the enumerator may contain modifications
/// made to the dictionary after
public IEnumerator> GetEnumerator()
{
Node[] buckets = m_buckets;
for (int i = 0; i < buckets.Length; i++)
{
Node current = buckets[i];
// The memory barrier ensures that the load of the fields of 'current' doesn’t move before the load from buckets[i].
Thread.MemoryBarrier();
while (current != null)
{
yield return new KeyValuePair(current.m_key, current.m_value);
current = current.m_next;
}
}
}
///
/// Shared internal implementation for inserts and updates.
/// If key exists, we always return false; and if updateIfExists == true we force update with value;
/// If key doesn't exist, we always add value and return true;
///
private bool TryAddInternal(TKey key, TValue value, bool updateIfExists, bool acquireLock, out TValue resultingValue)
{
int hashcode = m_comparer.GetHashCode(key);
while (true)
{
int bucketNo, lockNo;
Node[] buckets = m_buckets;
GetBucketAndLockNo(hashcode, out bucketNo, out lockNo, buckets.Length);
bool resizeDesired = false;
bool lockTaken = false;
try
{
if (acquireLock)
Monitor.Enter(m_locks[lockNo], ref lockTaken);
// If the table just got resized, we may not be holding the right lock, and must retry.
// This should be a rare occurence.
if (buckets != m_buckets)
{
continue;
}
// Try to find this key in the bucket
Node prev = null;
for (Node node = buckets[bucketNo]; node != null; node = node.m_next)
{
Assert((prev == null && node == m_buckets[bucketNo]) || prev.m_next == node);
if (m_comparer.Equals(node.m_key, key))
{
// The key was found in the dictionary. If updates are allowed, update the value for that key.
// We need to create a new node for the update, in order to support TValue types that cannot
// be written atomically, since lock-free reads may be happening concurrently.
if (updateIfExists)
{
Node newNode = new Node(node.m_key, value, hashcode, node.m_next);
if (prev == null)
{
buckets[bucketNo] = newNode;
}
else
{
prev.m_next = newNode;
}
resultingValue = value;
}
else
{
resultingValue = node.m_value;
}
return false;
}
prev = node;
}
// The key was not found in the bucket. Insert the key-value pair.
buckets[bucketNo] = new Node(key, value, hashcode, buckets[bucketNo]);
checked
{
m_countPerLock[lockNo]++;
}
//
// If this lock has element / bucket ratio greater than 1, resize the entire table.
// Note: the formula is chosen to avoid overflow, but has a small inaccuracy due to
// rounding.
//
if (m_countPerLock[lockNo] > buckets.Length / m_locks.Length)
{
resizeDesired = true;
}
}
finally
{
if (lockTaken)
Monitor.Exit(m_locks[lockNo]);
}
//
// The fact that we got here means that we just performed an insertion. If necessary, we will grow the table.
//
// Concurrency notes:
// - Notice that we are not holding any locks at when calling GrowTable. This is necessary to prevent deadlocks.
// - As a result, it is possible that GrowTable will be called unnecessarily. But, GrowTable will obtain lock 0
// and then verify that the table we passed to it as the argument is still the current table.
//
if (resizeDesired)
{
GrowTable(buckets);
}
resultingValue = value;
return true;
}
}
///
/// Gets or sets the value associated with the specified key.
///
/// The key of the value to get or set.
/// The value associated with the specified key. If the specified key is not found, a get
/// operation throws a
///
/// The property is retrieved and
///
public TValue this[TKey key]
{
get
{
TValue value;
if (!TryGetValue(key, out value))
{
throw new KeyNotFoundException();
}
return value;
}
set
{
if (key == null) throw new ArgumentNullException("key");
TValue dummy;
TryAddInternal(key, value, true, true, out dummy);
}
}
///
/// Gets the number of key/value pairs contained in the
/// The dictionary contains too many
/// elements.
/// The number of key/value paris contained in the
/// Count has snapshot semantics and represents the number of items in the
public int Count
{
get
{
int count = 0;
int acquiredLocks = 0;
try
{
// Acquire all locks
AcquireAllLocks(ref acquiredLocks);
// Compute the count, we allow overflow
for (int i = 0; i < m_countPerLock.Length; i++)
{
count += m_countPerLock[i];
}
}
finally
{
// Release locks that have been acquired earlier
ReleaseLocks(0, acquiredLocks);
}
return count;
}
}
///
/// Adds a key/value pair to the
/// The key of the element to add.
/// The function used to generate a value for the key
/// The dictionary contains too many
/// elements.
/// The value for the key. This will be either the existing value for the key if the
/// key is already in the dictionary, or the new value for the key as returned by valueFactory
/// if the key was not in the dictionary.
public TValue GetOrAdd(TKey key, Func valueFactory)
{
if (key == null) throw new ArgumentNullException("key");
if (valueFactory == null) throw new ArgumentNullException("valueFactory");
TValue resultingValue;
if (TryGetValue(key, out resultingValue))
{
return resultingValue;
}
TryAddInternal(key, valueFactory(key), false, true, out resultingValue);
return resultingValue;
}
///
/// Adds a key/value pair to the
/// The key of the element to add.
/// the value to be added, if the key does not already exist
/// The dictionary contains too many
/// elements.
/// The value for the key. This will be either the existing value for the key if the
/// key is already in the dictionary, or the new value if the key was not in the dictionary.
public TValue GetOrAdd(TKey key, TValue value)
{
if (key == null) throw new ArgumentNullException("key");
TValue resultingValue;
TryAddInternal(key, value, false, true, out resultingValue);
return resultingValue;
}
///
/// Adds a key/value pair to the
/// The key to be added or whose value should be updated
/// The function used to generate a value for an absent key
/// The function used to generate a new value for an existing key
/// based on the key's existing value
/// The dictionary contains too many
/// elements.
/// The new value for the key. This will be either be the result of addValueFactory (if the key was
/// absent) or the result of updateValueFactory (if the key was present).
public TValue AddOrUpdate(TKey key, Func addValueFactory, Func updateValueFactory)
{
if (key == null) throw new ArgumentNullException("key");
if (addValueFactory == null) throw new ArgumentNullException("addValueFactory");
if (updateValueFactory == null) throw new ArgumentNullException("updateValueFactory");
TValue newValue, resultingValue;
while (true)
{
TValue oldValue;
if (TryGetValue(key, out oldValue))
//key exists, try to update
{
newValue = updateValueFactory(key, oldValue);
if (TryUpdate(key, newValue, oldValue))
{
return newValue;
}
}
else //try add
{
newValue = addValueFactory(key);
if (TryAddInternal(key, newValue, false, true, out resultingValue))
{
return resultingValue;
}
}
}
}
///
/// Adds a key/value pair to the
/// The key to be added or whose value should be updated
/// The value to be added for an absent key
/// The function used to generate a new value for an existing key based on
/// the key's existing value
/// The dictionary contains too many
/// elements.
/// The new value for the key. This will be either be the result of addValueFactory (if the key was
/// absent) or the result of updateValueFactory (if the key was present).
public TValue AddOrUpdate(TKey key, TValue addValue, Func updateValueFactory)
{
if (key == null) throw new ArgumentNullException("key");
if (updateValueFactory == null) throw new ArgumentNullException("updateValueFactory");
TValue newValue, resultingValue;
while (true)
{
TValue oldValue;
if (TryGetValue(key, out oldValue))
//key exists, try to update
{
newValue = updateValueFactory(key, oldValue);
if (TryUpdate(key, newValue, oldValue))
{
return newValue;
}
}
else //try add
{
if (TryAddInternal(key, addValue, false, true, out resultingValue))
{
return resultingValue;
}
}
}
}
///
/// Gets a value that indicates whether the
/// true if the
public bool IsEmpty
{
get
{
int acquiredLocks = 0;
try
{
// Acquire all locks
AcquireAllLocks(ref acquiredLocks);
for (int i = 0; i < m_countPerLock.Length; i++)
{
if (m_countPerLock[i] != 0)
{
return false;
}
}
}
finally
{
// Release locks that have been acquired earlier
ReleaseLocks(0, acquiredLocks);
}
return true;
}
}
#region IDictionary members
///
/// Adds the specified key and value to the
/// The object to use as the key of the element to add.
/// The object to use as the value of the element to add.
/// The dictionary contains too many
/// elements.
///
/// An element with the same key already exists in the
void IDictionary.Add(TKey key, TValue value)
{
if (!TryAdd(key, value))
{
throw new ArgumentException(GetResource("ConcurrentDictionary_KeyAlreadyExisted"));
}
}
///
/// Removes the element with the specified key from the
/// The key of the element to remove.
/// true if the element is successfully remove; otherwise false. This method also returns
/// false if
///
/// .Remove(TKey key)
{
TValue throwAwayValue;
return TryRemove(key, out throwAwayValue);
}
///
/// Gets a collection containing the keys in the
/// An
public ICollection Keys
{
get { return GetKeys(); }
}
///
/// Gets a collection containing the values in the
/// An
public ICollection Values
{
get { return GetValues(); }
}
#endregion
#region ICollection> Members
///
/// Adds the specified value to the
/// The The
/// The
/// An element with the same key already exists in the
///
void ICollection>.Add(KeyValuePair keyValuePair)
{
((IDictionary)this).Add(keyValuePair.Key, keyValuePair.Value);
}
///
/// Determines whether the
/// The true if the
bool ICollection>.Contains(KeyValuePair keyValuePair)
{
TValue value;
if (!TryGetValue(keyValuePair.Key, out value))
{
return false;
}
return EqualityComparer.Default.Equals(value, keyValuePair.Value);
}
///
/// Gets a value indicating whether the dictionary is read-only.
///
/// true if the
bool ICollection>.IsReadOnly
{
get { return false; }
}
///
/// Removes a key and value from the dictionary.
///
/// The true if the key and value represented by
/// The Key property of
bool ICollection>.Remove(KeyValuePair keyValuePair)
{
if (keyValuePair.Key == null) throw new ArgumentNullException(GetResource("ConcurrentDictionary_ItemKeyIsNull"));
TValue throwAwayValue;
return TryRemoveInternal(keyValuePair.Key, out throwAwayValue, true, keyValuePair.Value);
}
#endregion
#region IEnumerable Members
/// Returns an enumerator that iterates through the
/// An enumerator for the
///
/// The enumerator returned from the dictionary is safe to use concurrently with
/// reads and writes to the dictionary, however it does not represent a moment-in-time snapshot
/// of the dictionary. The contents exposed through the enumerator may contain modifications
/// made to the dictionary after
IEnumerator IEnumerable.GetEnumerator()
{
return ((ConcurrentDictionary)this).GetEnumerator();
}
#endregion
#region IDictionary Members
///
/// Adds the specified key and value to the dictionary.
///
/// The object to use as the key.
/// The object to use as the value.
/// The dictionary contains too many
/// elements.
///
///
void IDictionary.Add(object key, object value)
{
if (key == null) throw new ArgumentNullException("key");
if (!(key is TKey)) throw new ArgumentException(GetResource("ConcurrentDictionary_TypeOfKeyIncorrect"));
TValue typedValue;
try
{
typedValue = (TValue)value;
}
catch (InvalidCastException)
{
throw new ArgumentException(GetResource("ConcurrentDictionary_TypeOfValueIncorrect"));
}
((IDictionary)this).Add((TKey)key, typedValue);
}
///
/// Gets whether the
/// The key to locate in the true if the
///
bool IDictionary.Contains(object key)
{
if (key == null) throw new ArgumentNullException("key");
return (key is TKey) && ((ConcurrentDictionary)this).ContainsKey((TKey)key);
}
/// Provides an
/// An
IDictionaryEnumerator IDictionary.GetEnumerator()
{
return new DictionaryEnumerator(this);
}
///
/// Gets a value indicating whether the
/// true if the
bool IDictionary.IsFixedSize
{
get { return false; }
}
///
/// Gets a value indicating whether the
/// true if the
bool IDictionary.IsReadOnly
{
get { return false; }
}
///
/// Gets an
/// An
ICollection IDictionary.Keys
{
get { return GetKeys(); }
}
///
/// Removes the element with the specified key from the
/// The key of the element to remove.
///
/// Gets an
/// An
ICollection IDictionary.Values
{
get { return GetValues(); }
}
///
/// Gets or sets the value associated with the specified key.
///
/// The key of the value to get or set.
/// The value associated with the specified key, or a null reference (Nothing in Visual Basic)
/// if
///
/// A value is being assigned, and
object IDictionary.this[object key]
{
get
{
if (key == null) throw new ArgumentNullException("key");
TValue value;
if (key is TKey && this.TryGetValue((TKey)key, out value))
{
return value;
}
return null;
}
set
{
if (key == null) throw new ArgumentNullException("key");
if (!(key is TKey)) throw new ArgumentException(GetResource("ConcurrentDictionary_TypeOfKeyIncorrect"));
if (!(value is TValue)) throw new ArgumentException(GetResource("ConcurrentDictionary_TypeOfValueIncorrect"));
((ConcurrentDictionary)this)[(TKey)key] = (TValue)value;
}
}
#endregion
#region ICollection Members
///
/// Copies the elements of the
/// The one-dimensional array that is the destination of the elements copied from
/// the ,
// we recognize three types of target arrays:
// - an array of KeyValuePair structs
// - an array of DictionaryEntry structs
// - an array of objects
KeyValuePair[] pairs = array as KeyValuePair[];
if (pairs != null)
{
CopyToPairs(pairs, index);
return;
}
DictionaryEntry[] entries = array as DictionaryEntry[];
if (entries != null)
{
CopyToEntries(entries, index);
return;
}
object[] objects = array as object[];
if (objects != null)
{
CopyToObjects(objects, index);
return;
}
throw new ArgumentException(GetResource("ConcurrentDictionary_ArrayIncorrectType"), "array");
}
finally
{
ReleaseLocks(0, locksAcquired);
}
}
///
/// Gets a value indicating whether access to the
/// true if access to the
bool ICollection.IsSynchronized
{
get { return false; }
}
///
/// Gets an object that can be used to synchronize access to the
/// The SyncRoot property is not supported.
object ICollection.SyncRoot
{
get
{
throw new NotSupportedException(Environment.GetResourceString("ConcurrentCollection_SyncRoot_NotSupported"));
}
}
#endregion
///
/// Replaces the internal table with a larger one. To prevent multiple threads from resizing the
/// table as a result of ----s, the table of buckets that was deemed too small is passed in as
/// an argument to GrowTable(). GrowTable() obtains a lock, and then checks whether the bucket
/// table has been replaced in the meantime or not.
///
/// Reference to the bucket table that was deemed too small.
private void GrowTable(Node[] buckets)
{
int locksAcquired = 0;
try
{
// The thread that first obtains m_locks[0] will be the one doing the resize operation
AcquireLocks(0, 1, ref locksAcquired);
// Make sure nobody resized the table while we were waiting for lock 0:
if (buckets != m_buckets)
{
// We assume that since the table reference is different, it was already resized. If we ever
// decide to do table shrinking, or replace the table for other reasons, we will have to revisit
// this logic.
return;
}
// Compute the new table size. We find the smallest integer larger than twice the previous table size, and not divisible by
// 2,3,5 or 7. We can consider a different table-sizing policy in the future.
int newLength;
try
{
checked
{
// Double the size of the buckets table and add one, so that we have an odd integer.
newLength = buckets.Length * 2 + 1;
// Now, we only need to check odd integers, and find the first that is not divisible
// by 3, 5 or 7.
while (newLength % 3 == 0 || newLength % 5 == 0 || newLength % 7 == 0)
{
newLength += 2;
}
Assert(newLength % 2 != 0);
}
}
catch (OverflowException)
{
// If we were to resize the table, its new size will not fit into a 32-bit signed int. Just return.
return;
}
Node[] newBuckets = new Node[newLength];
int[] newCountPerLock = new int[m_locks.Length];
// Now acquire all other locks for the table
AcquireLocks(1, m_locks.Length, ref locksAcquired);
// Copy all data into a new table, creating new nodes for all elements
for (int i = 0; i < buckets.Length; i++)
{
Node current = buckets[i];
while (current != null)
{
Node next = current.m_next;
int newBucketNo, newLockNo;
GetBucketAndLockNo(current.m_hashcode, out newBucketNo, out newLockNo, newBuckets.Length);
newBuckets[newBucketNo] = new Node(current.m_key, current.m_value, current.m_hashcode, newBuckets[newBucketNo]);
checked
{
newCountPerLock[newLockNo]++;
}
current = next;
}
}
// And finally adjust m_buckets and m_countPerLock to point to data for the new table
m_buckets = newBuckets;
m_countPerLock = newCountPerLock;
}
finally
{
// Release all locks that we took earlier
ReleaseLocks(0, locksAcquired);
}
}
///
/// Computes the bucket and lock number for a particular key.
///
private void GetBucketAndLockNo(
int hashcode, out int bucketNo, out int lockNo, int bucketCount)
{
bucketNo = (hashcode & 0x7fffffff) % bucketCount;
lockNo = bucketNo % m_locks.Length;
Assert(bucketNo >= 0 && bucketNo < bucketCount);
Assert(lockNo >= 0 && lockNo < m_locks.Length);
}
///
/// The number of concurrent writes for which to optimize by default.
///
private static int DefaultConcurrencyLevel
{
get { return DEFAULT_CONCURRENCY_MULTIPLIER * Environment.ProcessorCount; }
}
///
/// Acquires all locks for this hash table, and increments locksAcquired by the number
/// of locks that were successfully acquired. The locks are acquired in an increasing
/// order.
///
private void AcquireAllLocks(ref int locksAcquired)
{
#if !FEATURE_PAL
if (CDSCollectionETWBCLProvider.Log.IsEnabled())
{
CDSCollectionETWBCLProvider.Log.ConcurrentDictionary_AcquiringAllLocks(m_buckets.Length);
}
#endif //!FEATURE_PAL
AcquireLocks(0, m_locks.Length, ref locksAcquired);
Assert(locksAcquired == m_locks.Length);
}
///
/// Acquires a contiguous range of locks for this hash table, and increments locksAcquired
/// by the number of locks that were successfully acquired. The locks are acquired in an
/// increasing order.
///
private void AcquireLocks(int fromInclusive, int toExclusive, ref int locksAcquired)
{
Assert(fromInclusive <= toExclusive);
for (int i = fromInclusive; i < toExclusive; i++)
{
bool lockTaken = false;
try
{
#if CDS_COMPILE_JUST_THIS
Monitor.Enter(m_locks[i]);
lockTaken = true;
#else
Monitor.Enter(m_locks[i], ref lockTaken);
#endif
}
finally
{
if (lockTaken)
{
locksAcquired++;
}
}
}
}
///
/// Releases a contiguous range of locks.
///
private void ReleaseLocks(int fromInclusive, int toExclusive)
{
Assert(fromInclusive <= toExclusive);
for (int i = fromInclusive; i < toExclusive; i++)
{
Monitor.Exit(m_locks[i]);
}
}
///
/// Gets a collection containing the keys in the dictionary.
///
private ReadOnlyCollection GetKeys()
{
int locksAcquired = 0;
try
{
AcquireAllLocks(ref locksAcquired);
List keys = new List();
for (int i = 0; i < m_buckets.Length; i++)
{
Node current = m_buckets[i];
while (current != null)
{
keys.Add(current.m_key);
current = current.m_next;
}
}
return new ReadOnlyCollection(keys);
}
finally
{
ReleaseLocks(0, locksAcquired);
}
}
///
/// Gets a collection containing the values in the dictionary.
///
private ReadOnlyCollection GetValues()
{
int locksAcquired = 0;
try
{
AcquireAllLocks(ref locksAcquired);
List values = new List();
for (int i = 0; i < m_buckets.Length; i++)
{
Node current = m_buckets[i];
while (current != null)
{
values.Add(current.m_value);
current = current.m_next;
}
}
return new ReadOnlyCollection(values);
}
finally
{
ReleaseLocks(0, locksAcquired);
}
}
///
/// A helper method for asserts.
///
[Conditional("DEBUG")]
private void Assert(bool condition)
{
#if CDS_COMPILE_JUST_THIS
if (!condition)
{
throw new Exception("Assertion failed.");
}
#else
Contract.Assert(condition);
#endif
}
///
/// A helper function to obtain the string for a particular resource key.
///
///
///
/// A node in a singly-linked list representing a particular hash table bucket.
///
private class Node
{
internal TKey m_key;
internal TValue m_value;
internal volatile Node m_next;
internal int m_hashcode;
internal Node(TKey key, TValue value, int hashcode)
: this(key, value, hashcode, null)
{
}
internal Node(TKey key, TValue value, int hashcode, Node next)
{
m_key = key;
m_value = value;
m_next = next;
m_hashcode = hashcode;
}
}
///
/// A private class to represent enumeration over the dictionary that implements the
/// IDictionaryEnumerator interface.
///
private class DictionaryEnumerator : IDictionaryEnumerator
{
IEnumerator> m_enumerator; // Enumerator over the dictionary.
internal DictionaryEnumerator(ConcurrentDictionary dictionary)
{
m_enumerator = dictionary.GetEnumerator();
}
public DictionaryEntry Entry
{
get { return new DictionaryEntry(m_enumerator.Current.Key, m_enumerator.Current.Value); }
}
public object Key
{
get { return m_enumerator.Current.Key; }
}
public object Value
{
get { return m_enumerator.Current.Value; }
}
public object Current
{
get { return this.Entry; }
}
public bool MoveNext()
{
return m_enumerator.MoveNext();
}
public void Reset()
{
m_enumerator.Reset();
}
}
///
/// Get the data array to be serialized
///
[OnSerializing]
private void OnSerializing(StreamingContext context)
{
// save the data into the serialization array to be saved
m_serializationArray = ToArray();
m_serializationConcurrencyLevel = m_locks.Length;
m_serializationCapacity = m_buckets.Length;
}
///
/// Construct the dictionary from a previously seiralized one
///
[OnDeserialized]
private void OnDeserialized(StreamingContext context)
{
KeyValuePair[] array = m_serializationArray;
m_buckets = new Node[m_serializationCapacity];
m_countPerLock = new int[m_serializationConcurrencyLevel];
m_locks = new object[m_serializationConcurrencyLevel];
for (int i = 0; i < m_locks.Length; i++)
{
m_locks[i] = new object();
}
InitializeFromCollection(array);
m_serializationArray = null;
}
}
}
// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
Link Menu
This book is available now!
Buy at Amazon US or
Buy at Amazon UK
- ComponentResourceKey.cs
- BaseCodePageEncoding.cs
- ValidationSummary.cs
- XmlHierarchyData.cs
- KerberosTokenFactoryCredential.cs
- AxisAngleRotation3D.cs
- SizeChangedEventArgs.cs
- PermissionSet.cs
- DataSysAttribute.cs
- DiscoveryClientProtocol.cs
- DatePickerDateValidationErrorEventArgs.cs
- FlowDocumentPaginator.cs
- shaperfactoryquerycachekey.cs
- BitmapEffectDrawingContextState.cs
- hresults.cs
- KnownBoxes.cs
- ProcessInputEventArgs.cs
- Utils.cs
- DnsElement.cs
- SuppressMessageAttribute.cs
- ManualWorkflowSchedulerService.cs
- CompilerResults.cs
- LicenseProviderAttribute.cs
- TypeConverter.cs
- ComAwareEventInfo.cs
- SqlDataSourceRefreshSchemaForm.cs
- MarkupExtensionParser.cs
- CursorConverter.cs
- SharedUtils.cs
- ServiceOperationUIEditor.cs
- ThumbAutomationPeer.cs
- Mappings.cs
- LinqDataSourceDisposeEventArgs.cs
- Vector3D.cs
- UrlAuthorizationModule.cs
- FontDifferentiator.cs
- ToolStripDropDownItem.cs
- XXXOnTypeBuilderInstantiation.cs
- TextSimpleMarkerProperties.cs
- TypeSystemProvider.cs
- OLEDB_Enum.cs
- DataGridViewColumnHeaderCell.cs
- ClusterRegistryConfigurationProvider.cs
- ModelItemDictionaryImpl.cs
- InArgument.cs
- MouseWheelEventArgs.cs
- FocusTracker.cs
- ManagedWndProcTracker.cs
- TextTabProperties.cs
- CodeTypeOfExpression.cs
- SafeEventHandle.cs
- IList.cs
- CompositeActivityTypeDescriptor.cs
- _ListenerRequestStream.cs
- ComponentEditorForm.cs
- _HeaderInfo.cs
- XmlValueConverter.cs
- ButtonBaseAutomationPeer.cs
- Array.cs
- KerberosSecurityTokenProvider.cs
- NumericUpDown.cs
- TextEndOfLine.cs
- StaticExtension.cs
- MetadataItem.cs
- TableStyle.cs
- DoubleLink.cs
- TimeIntervalCollection.cs
- RegexCode.cs
- FlowDocumentPage.cs
- EdmTypeAttribute.cs
- AnnotationResourceCollection.cs
- XmlAttributeAttribute.cs
- ImpersonationContext.cs
- DependencyPropertyConverter.cs
- CapabilitiesUse.cs
- RequestResizeEvent.cs
- ManagedFilter.cs
- DictionaryTraceRecord.cs
- Activity.cs
- XPathConvert.cs
- ResponseBodyWriter.cs
- WindowsAuthenticationEventArgs.cs
- EndOfStreamException.cs
- MultipleViewProviderWrapper.cs
- SafeBitVector32.cs
- XmlSchemaSet.cs
- SystemParameters.cs
- SqlConnectionFactory.cs
- SystemTcpConnection.cs
- MsmqMessage.cs
- FormParameter.cs
- StackBuilderSink.cs
- SqlMethods.cs
- DataControlReference.cs
- CatalogPartCollection.cs
- TextPattern.cs
- ExecutionContext.cs
- CanonicalFontFamilyReference.cs
- DataObjectEventArgs.cs
- PersonalizationStateInfoCollection.cs