Welcome to mirror list, hosted at ThFree Co, Russian Federation.

github.com/mono/corert.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
path: root/src/System.Private.CoreLib/shared/System/Collections/Generic/Dictionary.cs
diff options
context:
space:
mode:
Diffstat (limited to 'src/System.Private.CoreLib/shared/System/Collections/Generic/Dictionary.cs')
-rw-r--r--src/System.Private.CoreLib/shared/System/Collections/Generic/Dictionary.cs320
1 files changed, 250 insertions, 70 deletions
diff --git a/src/System.Private.CoreLib/shared/System/Collections/Generic/Dictionary.cs b/src/System.Private.CoreLib/shared/System/Collections/Generic/Dictionary.cs
index ab7f0dba8..8fd8d91f0 100644
--- a/src/System.Private.CoreLib/shared/System/Collections/Generic/Dictionary.cs
+++ b/src/System.Private.CoreLib/shared/System/Collections/Generic/Dictionary.cs
@@ -77,11 +77,15 @@ namespace System.Collections.Generic
{
if (capacity < 0) ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity);
if (capacity > 0) Initialize(capacity);
- _comparer = comparer ?? EqualityComparer<TKey>.Default;
+ if (comparer != EqualityComparer<TKey>.Default)
+ {
+ _comparer = comparer;
+ }
#if !MONO
- if (_comparer == EqualityComparer<string>.Default)
+ if (typeof(TKey) == typeof(string) && _comparer == null)
{
+ // To start, move off default comparer for string which is randomised
_comparer = (IEqualityComparer<TKey>)NonRandomizedStringEqualityComparer.Default;
}
#endif
@@ -150,7 +154,7 @@ namespace System.Collections.Generic
{
get
{
- return _comparer;
+ return (_comparer == null || _comparer is NonRandomizedStringEqualityComparer) ? EqualityComparer<TKey>.Default : _comparer;
}
}
@@ -266,11 +270,7 @@ namespace System.Collections.Generic
int count = _count;
if (count > 0)
{
- int[] buckets = _buckets;
- for (int i = 0; i < buckets.Length; i++)
- {
- buckets[i] = -1;
- }
+ Array.Clear(_buckets, 0, _buckets.Length);
_count = 0;
_freeList = -1;
@@ -296,10 +296,9 @@ namespace System.Collections.Generic
}
else
{
- EqualityComparer<TValue> c = EqualityComparer<TValue>.Default;
for (int i = 0; i < _count; i++)
{
- if (_entries[i].hashCode >= 0 && c.Equals(_entries[i].value, value)) return true;
+ if (_entries[i].hashCode >= 0 && EqualityComparer<TValue>.Default.Equals(_entries[i].value, value)) return true;
}
}
return false;
@@ -351,7 +350,7 @@ namespace System.Collections.Generic
}
info.AddValue(VersionName, _version);
- info.AddValue(ComparerName, _comparer, typeof(IEqualityComparer<TKey>));
+ info.AddValue(ComparerName, _comparer ?? EqualityComparer<TKey>.Default, typeof(IEqualityComparer<TKey>));
info.AddValue(HashSizeName, _buckets == null ? 0 : _buckets.Length); // This is the length of the bucket array
if (_buckets != null)
@@ -369,29 +368,61 @@ namespace System.Collections.Generic
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
}
- if (_buckets != null)
+ int i = -1;
+ int[] buckets = _buckets;
+ Entry[] entries = _entries;
+ if (buckets != null)
{
- int hashCode = _comparer.GetHashCode(key) & 0x7FFFFFFF;
- for (int i = _buckets[hashCode % _buckets.Length]; i >= 0; i = _entries[i].next)
+ IEqualityComparer<TKey> comparer = _comparer;
+ if (comparer == null)
+ {
+ int hashCode = key.GetHashCode() & 0x7FFFFFFF;
+ // Value in _buckets is 1-based
+ i = buckets[hashCode % buckets.Length] - 1;
+ do
+ {
+ // Should be a while loop https://github.com/dotnet/coreclr/issues/15476
+ // Test in if to drop range check for following array access
+ if ((uint)i >= (uint)entries.Length || (entries[i].hashCode == hashCode && EqualityComparer<TKey>.Default.Equals(entries[i].key, key)))
+ {
+ break;
+ }
+
+ i = entries[i].next;
+ } while (true);
+ }
+ else
{
- if (_entries[i].hashCode == hashCode && _comparer.Equals(_entries[i].key, key)) return i;
+ int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
+ // Value in _buckets is 1-based
+ i = buckets[hashCode % buckets.Length] - 1;
+ do
+ {
+ // Should be a while loop https://github.com/dotnet/coreclr/issues/15476
+ // Test in if to drop range check for following array access
+ if ((uint)i >= (uint)entries.Length ||
+ (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)))
+ {
+ break;
+ }
+
+ i = entries[i].next;
+ } while (true);
}
}
- return -1;
+
+ return i;
}
- private void Initialize(int capacity)
+ private int Initialize(int capacity)
{
int size = HashHelpers.GetPrime(capacity);
- int[] buckets = new int[size];
- for (int i = 0; i < buckets.Length; i++)
- {
- buckets[i] = -1;
- }
_freeList = -1;
- _buckets = buckets;
+ _buckets = new int[size];
_entries = new Entry[size];
+
+ return size;
}
private bool TryInsert(TKey key, TValue value, InsertionBehavior behavior)
@@ -401,65 +432,135 @@ namespace System.Collections.Generic
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
}
- if (_buckets == null) Initialize(0);
- int hashCode = _comparer.GetHashCode(key) & 0x7FFFFFFF;
- int targetBucket = hashCode % _buckets.Length;
+ if (_buckets == null)
+ {
+ Initialize(0);
+ }
+
+ Entry[] entries = _entries;
+ IEqualityComparer<TKey> comparer = _comparer;
+
+ int hashCode = ((comparer == null) ? key.GetHashCode() : comparer.GetHashCode(key)) & 0x7FFFFFFF;
+
int collisionCount = 0;
+ ref int bucket = ref _buckets[hashCode % _buckets.Length];
+ // Value in _buckets is 1-based
+ int i = bucket - 1;
- for (int i = _buckets[targetBucket]; i >= 0; i = _entries[i].next)
+ if (comparer == null)
{
- if (_entries[i].hashCode == hashCode && _comparer.Equals(_entries[i].key, key))
+ do
{
- if (behavior == InsertionBehavior.OverwriteExisting)
+ // Should be a while loop https://github.com/dotnet/coreclr/issues/15476
+ // Test uint in if rather than loop condition to drop range check for following array access
+ if ((uint)i >= (uint)entries.Length)
{
- _entries[i].value = value;
- _version++;
- return true;
+ break;
}
- if (behavior == InsertionBehavior.ThrowOnExisting)
+ if (entries[i].hashCode == hashCode && EqualityComparer<TKey>.Default.Equals(entries[i].key, key))
{
- ThrowHelper.ThrowAddingDuplicateWithKeyArgumentException(key);
+ if (behavior == InsertionBehavior.OverwriteExisting)
+ {
+ entries[i].value = value;
+ _version++;
+ return true;
+ }
+
+ if (behavior == InsertionBehavior.ThrowOnExisting)
+ {
+ ThrowHelper.ThrowAddingDuplicateWithKeyArgumentException(key);
+ }
+
+ return false;
}
- return false;
- }
- collisionCount++;
+ i = entries[i].next;
+ collisionCount++;
+ } while (true);
}
+ else
+ {
+ do
+ {
+ // Should be a while loop https://github.com/dotnet/coreclr/issues/15476
+ // Test uint in if rather than loop condition to drop range check for following array access
+ if ((uint)i >= (uint)entries.Length)
+ {
+ break;
+ }
+ if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key))
+ {
+ if (behavior == InsertionBehavior.OverwriteExisting)
+ {
+ entries[i].value = value;
+ _version++;
+ return true;
+ }
+
+ if (behavior == InsertionBehavior.ThrowOnExisting)
+ {
+ ThrowHelper.ThrowAddingDuplicateWithKeyArgumentException(key);
+ }
+
+ return false;
+ }
+
+ i = entries[i].next;
+ collisionCount++;
+ } while (true);
+
+ }
+
+ // Can be improved with "Ref Local Reassignment"
+ // https://github.com/dotnet/csharplang/blob/master/proposals/ref-local-reassignment.md
+ bool resized = false;
+ bool updateFreeList = false;
int index;
if (_freeCount > 0)
{
index = _freeList;
- _freeList = _entries[index].next;
+ updateFreeList = true;
_freeCount--;
}
else
{
- if (_count == _entries.Length)
+ int count = _count;
+ if (count == entries.Length)
{
Resize();
- targetBucket = hashCode % _buckets.Length;
+ resized = true;
}
- index = _count;
- _count++;
+ index = count;
+ _count = count + 1;
+ entries = _entries;
}
- _entries[index].hashCode = hashCode;
- _entries[index].next = _buckets[targetBucket];
- _entries[index].key = key;
- _entries[index].value = value;
- _buckets[targetBucket] = index;
+ ref int targetBucket = ref resized ? ref _buckets[hashCode % _buckets.Length] : ref bucket;
+ ref Entry entry = ref entries[index];
+
+ if (updateFreeList)
+ {
+ _freeList = entry.next;
+ }
+ entry.hashCode = hashCode;
+ // Value in _buckets is 1-based
+ entry.next = targetBucket - 1;
+ entry.key = key;
+ entry.value = value;
+ // Value in _buckets is 1-based
+ targetBucket = index + 1;
_version++;
#if !MONO
- // If we hit the collision threshold we'll need to switch to the comparer which is using randomized string hashing
- // i.e. EqualityComparer<string>.Default.
-
- if (collisionCount > HashHelpers.HashCollisionThreshold && _comparer is NonRandomizedStringEqualityComparer)
+ // Value types never rehash
+ if (default(TKey) == null && collisionCount > HashHelpers.HashCollisionThreshold && comparer is NonRandomizedStringEqualityComparer)
{
- _comparer = (IEqualityComparer<TKey>)EqualityComparer<string>.Default;
- Resize(_entries.Length, true);
+ // If we hit the collision threshold we'll need to switch to the comparer which is using randomized string hashing
+ // i.e. EqualityComparer<string>.Default.
+ _comparer = null;
+ Resize(entries.Length, true);
}
#endif
@@ -519,25 +620,24 @@ namespace System.Collections.Generic
private void Resize(int newSize, bool forceNewHashCodes)
{
+ // Value types never rehash
+ Debug.Assert(!forceNewHashCodes || default(TKey) == null);
Debug.Assert(newSize >= _entries.Length);
int[] buckets = new int[newSize];
- for (int i = 0; i < buckets.Length; i++)
- {
- buckets[i] = -1;
- }
Entry[] entries = new Entry[newSize];
int count = _count;
Array.Copy(_entries, 0, entries, 0, count);
- if (forceNewHashCodes)
+ if (default(TKey) == null && forceNewHashCodes)
{
for (int i = 0; i < count; i++)
{
- if (entries[i].hashCode != -1)
+ if (entries[i].hashCode >= 0)
{
- entries[i].hashCode = (_comparer.GetHashCode(entries[i].key) & 0x7FFFFFFF);
+ Debug.Assert(_comparer == null);
+ entries[i].hashCode = (entries[i].key.GetHashCode() & 0x7FFFFFFF);
}
}
}
@@ -547,8 +647,10 @@ namespace System.Collections.Generic
if (entries[i].hashCode >= 0)
{
int bucket = entries[i].hashCode % newSize;
- entries[i].next = buckets[bucket];
- buckets[bucket] = i;
+ // Value in _buckets is 1-based
+ entries[i].next = buckets[bucket] - 1;
+ // Value in _buckets is 1-based
+ buckets[bucket] = i + 1;
}
}
@@ -568,19 +670,21 @@ namespace System.Collections.Generic
if (_buckets != null)
{
- int hashCode = _comparer.GetHashCode(key) & 0x7FFFFFFF;
+ int hashCode = (_comparer?.GetHashCode(key) ?? key.GetHashCode()) & 0x7FFFFFFF;
int bucket = hashCode % _buckets.Length;
int last = -1;
- int i = _buckets[bucket];
+ // Value in _buckets is 1-based
+ int i = _buckets[bucket] - 1;
while (i >= 0)
{
ref Entry entry = ref _entries[i];
- if (entry.hashCode == hashCode && _comparer.Equals(entry.key, key))
+ if (entry.hashCode == hashCode && (_comparer?.Equals(entry.key, key) ?? EqualityComparer<TKey>.Default.Equals(entry.key, key)))
{
if (last < 0)
{
- _buckets[bucket] = entry.next;
+ // Value in _buckets is 1-based
+ _buckets[bucket] = entry.next + 1;
}
else
{
@@ -622,19 +726,21 @@ namespace System.Collections.Generic
if (_buckets != null)
{
- int hashCode = _comparer.GetHashCode(key) & 0x7FFFFFFF;
+ int hashCode = (_comparer?.GetHashCode(key) ?? key.GetHashCode()) & 0x7FFFFFFF;
int bucket = hashCode % _buckets.Length;
int last = -1;
- int i = _buckets[bucket];
+ // Value in _buckets is 1-based
+ int i = _buckets[bucket] - 1;
while (i >= 0)
{
ref Entry entry = ref _entries[i];
- if (entry.hashCode == hashCode && _comparer.Equals(entry.key, key))
+ if (entry.hashCode == hashCode && (_comparer?.Equals(entry.key, key) ?? EqualityComparer<TKey>.Default.Equals(entry.key, key)))
{
if (last < 0)
{
- _buckets[bucket] = entry.next;
+ // Value in _buckets is 1-based
+ _buckets[bucket] = entry.next + 1;
}
else
{
@@ -768,6 +874,80 @@ namespace System.Collections.Generic
return new Enumerator(this, Enumerator.KeyValuePair);
}
+ /// <summary>
+ /// Ensures that the dictionary can hold up to 'capacity' entries without any further expansion of its backing storage
+ /// </summary>
+ public int EnsureCapacity(int capacity)
+ {
+ if (capacity < 0)
+ ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity);
+ int currentCapacity = _entries == null ? 0 : _entries.Length;
+ if (currentCapacity >= capacity)
+ return currentCapacity;
+ if (_buckets == null)
+ return Initialize(capacity);
+ int newSize = HashHelpers.GetPrime(capacity);
+ Resize(newSize, forceNewHashCodes: false);
+ return newSize;
+ }
+
+ /// <summary>
+ /// Sets the capacity of this dictionary to what it would be if it had been originally initialized with all its entries
+ ///
+ /// This method can be used to minimize the memory overhead
+ /// once it is known that no new elements will be added.
+ ///
+ /// To allocate minimum size storage array, execute the following statements:
+ ///
+ /// dictionary.Clear();
+ /// dictionary.TrimExcess();
+ /// </summary>
+ public void TrimExcess()
+ {
+ TrimExcess(Count);
+ }
+
+ /// <summary>
+ /// Sets the capacity of this dictionary to hold up 'capacity' entries without any further expansion of its backing storage
+ ///
+ /// This method can be used to minimize the memory overhead
+ /// once it is known that no new elements will be added.
+ /// </summary>
+ public void TrimExcess(int capacity)
+ {
+ if (capacity < Count)
+ ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity);
+ int newSize = HashHelpers.GetPrime(capacity);
+
+ Entry[] oldEntries = _entries;
+ int currentCapacity = oldEntries == null ? 0 : oldEntries.Length;
+ if (newSize >= currentCapacity)
+ return;
+
+ int oldCount = _count;
+ Initialize(newSize);
+ Entry[] entries = _entries;
+ int[] buckets = _buckets;
+ int count = 0;
+ for (int i = 0; i < oldCount; i++)
+ {
+ int hashCode = oldEntries[i].hashCode;
+ if (hashCode >= 0)
+ {
+ ref Entry entry = ref entries[count];
+ entry = oldEntries[i];
+ int bucket = hashCode % newSize;
+ // Value in _buckets is 1-based
+ entry.next = buckets[bucket] - 1;
+ // Value in _buckets is 1-based
+ buckets[bucket] = count + 1;
+ count++;
+ }
+ }
+ _count = count;
+ _freeCount = 0;
+ }
+
bool ICollection.IsSynchronized
{
get { return false; }
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-26 09:15:46 +0300