< Summary

Class:GDX.Collections.Generic.StringKeyDictionary[TValue]
Assembly:GDX
File(s):./Packages/com.dotbunny.gdx/GDX/Collections/Generic/StringKeyDictionary.cs
Covered lines:319
Uncovered lines:102
Coverable lines:421
Total lines:726
Line coverage:75.7% (319 of 421)
Covered branches:0
Total branches:0
Covered methods:16
Total methods:19
Method coverage:84.2% (16 of 19)

Coverage History

Metrics

MethodBranch coverage Crap Score Cyclomatic complexity NPath complexity Sequence coverage
StringKeyDictionary(...)0%330100%
AddWithExpandCheck(...)0%3.013090.48%
AddWithUniqueCheck(...)0%4.024088.89%
AddSafe(...)0%5.055087.1%
AddUnchecked(...)0%110100%
ContainsKey(...)0%4.034088.24%
ExpandWhenFull()0%440100%
Reserve(...)0%6.146084.21%
IndexOf(...)0%4.094082.35%
TryModifyValue(...)0%20400%
TryRemove(...)0%6.116085.37%
TryRemoveNoValueClear(...)0%42600%
TryGetValue(...)0%4.064084.21%
MoveNext(...)0%4.034087.5%
MoveNext(...)0%330100%
MoveNext(...)0%12300%
Clear()0%330100%

File(s)

./Packages/com.dotbunny.gdx/GDX/Collections/Generic/StringKeyDictionary.cs

#LineLine coverage
 1using System;
 2using System.Collections.Generic;
 3
 4namespace GDX.Collections.Generic
 5{
 6    /// <summary>
 7    ///     An optimized <see cref="System.Collections.Generic.Dictionary{T,T}" />-like data structure with a
 8    ///     <see cref="string" /> key requirement.
 9    /// </summary>
 10    [Serializable]
 11    public struct StringKeyDictionary<TValue>
 12    {
 13        public int[] Buckets;
 14        public StringKeyEntry<TValue>[] Entries;
 15        public int FreeListHead;
 16        public int Count;
 17
 18        /// <summary>
 19        ///     Initializes the dictionary with at least <paramref name="minCapacity" /> capacity.
 20        /// </summary>
 21        /// <param name="minCapacity">The minimal initial capacity to reserve.</param>
 22        public StringKeyDictionary(int minCapacity)
 9723        {
 9724            int primeCapacity = DictionaryPrimes.GetPrime(minCapacity);
 25
 9726            Buckets = new int[primeCapacity];
 444027            for (int i = 0; i < primeCapacity; i++)
 212328            {
 212329                Buckets[i] = -1;
 212330            }
 31
 9732            Entries = new StringKeyEntry<TValue>[primeCapacity];
 33
 444034            for (int i = 0; i < primeCapacity; i++)
 212335            {
 212336                Entries[i].Next = (1 << 31) | (i + 1);
 212337            }
 38
 9739            Count = 0;
 9740            FreeListHead = 0;
 9741        }
 42
 43        /// <summary>
 44        ///     Directly access a value by key.
 45        /// </summary>
 46        /// <param name="key">The target key to look for a value identified by.</param>
 47        /// <exception cref="ArgumentNullException">Thrown when a null <paramref name="key" /> is provided to lookup.</e
 48        /// <exception cref="System.Collections.Generic.KeyNotFoundException">
 49        ///     Thrown when the <paramref name="key" /> is not found
 50        ///     in the <see cref="StringKeyDictionary{TValue}" />.
 51        /// </exception>
 52        public TValue this[string key]
 53        {
 54            get
 2755            {
 2756                if (key == null)
 057                {
 058                    throw new ArgumentNullException();
 59                }
 60
 2761                int hashCode = key.GetStableHashCode() & 0x7FFFFFFF;
 2762                int bucketIndex = hashCode % Buckets.Length;
 2763                int nextKeyIndex = Buckets[bucketIndex];
 64
 65
 2766                while (nextKeyIndex != -1)
 2767                {
 2768                    ref StringKeyEntry<TValue> currEntry = ref Entries[nextKeyIndex];
 2769                    nextKeyIndex = currEntry.Next;
 70
 2771                    if (currEntry.Key == key)
 2772                    {
 2773                        return currEntry.Value;
 74                    }
 075                }
 76
 077                throw new KeyNotFoundException();
 2778            }
 79
 80            set
 3881            {
 3882                if (key == null)
 083                {
 084                    throw new ArgumentNullException();
 85                }
 86
 3887                int freeIndex = FreeListHead;
 88
 3889                if (freeIndex >= Buckets.Length)
 290                {
 291                    ExpandWhenFull();
 292                }
 93
 3894                int hashCode = key.GetStableHashCode() & 0x7FFFFFFF;
 3895                int bucketIndex = hashCode % Buckets.Length;
 3896                int indexAtBucket = Buckets[bucketIndex];
 97
 3898                int nextKeyIndex = indexAtBucket;
 99
 60100                while (nextKeyIndex != -1)
 22101                {
 22102                    ref StringKeyEntry<TValue> currEntry = ref Entries[nextKeyIndex];
 22103                    nextKeyIndex = currEntry.Next;
 22104                    if (currEntry.Key == key)
 0105                    {
 0106                        currEntry.Value = value;
 0107                        return;
 108                    }
 22109                }
 110
 38111                ref StringKeyEntry<TValue> entry = ref Entries[freeIndex];
 112
 38113                FreeListHead = entry.Next & 0x7FFFFFFF;
 38114                entry.Next = indexAtBucket;
 38115                entry.Key = key;
 38116                entry.Value = value;
 38117                entry.HashCode = hashCode;
 38118                Buckets[bucketIndex] = freeIndex;
 119
 38120                ++Count;
 38121            }
 122        }
 123
 124        /// <summary>
 125        ///     Adds the key value pair to the dictionary, expanding if necessary but not checking for duplicate entries
 126        /// </summary>
 127        /// <param name="key">The key to add.</param>
 128        /// <param name="value">The value to add.</param>
 129        public void AddWithExpandCheck(string key, TValue value)
 86130        {
 86131            if (key == null)
 0132            {
 0133                throw new ArgumentNullException();
 134            }
 135
 86136            int freeIndex = FreeListHead;
 137
 86138            if (freeIndex >= Buckets.Length)
 2139            {
 2140                ExpandWhenFull();
 2141            }
 142
 86143            int hashCode = key.GetStableHashCode() & 0x7FFFFFFF;
 86144            int hashIndex = hashCode % Buckets.Length;
 86145            int indexAtBucket = Buckets[hashIndex];
 86146            ref StringKeyEntry<TValue> entry = ref Entries[freeIndex];
 147
 86148            FreeListHead = entry.Next & 0x7FFFFFFF;
 86149            entry.Next = indexAtBucket;
 86150            entry.Key = key;
 86151            entry.Value = value;
 86152            entry.HashCode = hashCode;
 86153            Buckets[hashIndex] = freeIndex;
 154
 86155            ++Count;
 86156        }
 157
 158        /// <summary>
 159        ///     Adds the key value pair to the dictionary, checking for duplicates but not expanding if necessary.
 160        /// </summary>
 161        /// <param name="key">The key to add.</param>
 162        /// <param name="value">The value to add.</param>
 163        /// <returns>True if the entry was successfully created.</returns>
 164        public bool AddWithUniqueCheck(string key, TValue value)
 3165        {
 3166            if (key == null)
 0167            {
 0168                throw new ArgumentNullException();
 169            }
 170
 3171            int freeIndex = FreeListHead;
 3172            int hashCode = key.GetStableHashCode() & 0x7FFFFFFF;
 3173            int hashIndex = hashCode % Buckets.Length;
 3174            int indexAtBucket = Buckets[hashIndex];
 175
 3176            int nextKeyIndex = indexAtBucket;
 177
 3178            while (nextKeyIndex > -1)
 1179            {
 1180                ref StringKeyEntry<TValue> currEntry = ref Entries[nextKeyIndex];
 1181                nextKeyIndex = currEntry.Next;
 1182                if (currEntry.Key == key)
 1183                {
 1184                    return false;
 185                }
 0186            }
 187
 2188            ref StringKeyEntry<TValue> entry = ref Entries[freeIndex];
 189
 2190            FreeListHead = entry.Next & 0x7FFFFFFF;
 2191            entry.Next = indexAtBucket;
 2192            entry.Key = key;
 2193            entry.Value = value;
 2194            entry.HashCode = hashCode;
 2195            Buckets[hashIndex] = freeIndex;
 196
 2197            ++Count;
 2198            return true;
 3199        }
 200
 201        /// <summary>
 202        ///     Adds the key value pair to the dictionary, checking for duplicate entries and expanding if necessary.
 203        /// </summary>
 204        /// <param name="key">The key to add.</param>
 205        /// <param name="value">The value to add.</param>
 206        /// <returns>True if the entry was successfully created.</returns>
 207        public bool AddSafe(string key, TValue value)
 42208        {
 42209            if (key == null)
 0210            {
 0211                throw new ArgumentNullException();
 212            }
 213
 42214            int freeIndex = FreeListHead;
 215
 42216            if (freeIndex >= Buckets.Length)
 2217            {
 2218                ExpandWhenFull();
 2219            }
 220
 42221            int hashCode = key.GetStableHashCode() & 0x7FFFFFFF;
 42222            int hashIndex = hashCode % Buckets.Length;
 42223            int indexAtBucket = Buckets[hashIndex];
 224
 42225            int nextKeyIndex = indexAtBucket;
 226
 65227            while (nextKeyIndex != -1)
 23228            {
 23229                StringKeyEntry<TValue> currEntry = Entries[nextKeyIndex];
 23230                nextKeyIndex = currEntry.Next;
 23231                if (currEntry.Key == key)
 0232                {
 0233                    return false;
 234                }
 23235            }
 236
 42237            ref StringKeyEntry<TValue> entry = ref Entries[freeIndex];
 238
 42239            FreeListHead = entry.Next & 0x7FFFFFFF;
 42240            entry.Next = indexAtBucket;
 42241            entry.Key = key;
 42242            entry.Value = value;
 42243            entry.HashCode = hashCode;
 42244            Buckets[hashIndex] = freeIndex;
 245
 42246            ++Count;
 42247            return true;
 42248        }
 249
 250        /// <summary>
 251        ///     Adds the key value pair to the dictionary, without checking for available capacity or duplicate entries.
 252        /// </summary>
 253        /// <param name="key">The key to add.</param>
 254        /// <param name="value">The value to add.</param>
 255        public void AddUnchecked(string key, TValue value)
 312256        {
 312257            int dataIndex = FreeListHead;
 312258            int hashCode = key.GetStableHashCode() & 0x7FFFFFFF;
 312259            int bucketIndex = hashCode % Buckets.Length;
 312260            int initialBucketValue = Buckets[bucketIndex];
 261
 312262            ref StringKeyEntry<TValue> entry = ref Entries[dataIndex];
 263
 312264            FreeListHead = entry.Next & 0x7FFFFFFF;
 312265            entry.Next = initialBucketValue;
 312266            entry.Key = key;
 312267            entry.Value = value;
 312268            entry.HashCode = hashCode;
 312269            Buckets[bucketIndex] = dataIndex;
 312270        }
 271
 272
 273        /// <summary>
 274        ///     Checks if the dictionary contains the given key.
 275        /// </summary>
 276        /// <param name="key">The key to check for.</param>
 277        /// <returns>True if the dictionary contains the key.</returns>
 278        public bool ContainsKey(string key)
 165279        {
 165280            if (key == null)
 0281            {
 0282                throw new ArgumentNullException();
 283            }
 284
 165285            int hashCode = key.GetStableHashCode() & 0x7FFFFFFF;
 165286            int bucketIndex = hashCode % Buckets.Length;
 165287            int nextKeyIndex = Buckets[bucketIndex];
 288
 179289            while (nextKeyIndex != -1)
 119290            {
 119291                ref StringKeyEntry<TValue> currEntry = ref Entries[nextKeyIndex];
 292
 119293                if (currEntry.Key == key)
 105294                {
 105295                    return true;
 296                }
 297
 14298                nextKeyIndex = currEntry.Next;
 14299            }
 300
 60301            return false;
 165302        }
 303
 304        /// <summary>
 305        ///     Resizes the dictionary with the assumption that it is full. Do not use otherwise.
 306        /// </summary>
 307        public void ExpandWhenFull()
 6308        {
 6309            int oldCapacity = Buckets.Length;
 6310            int nextPrimeCapacity = DictionaryPrimes.GetNextSize(oldCapacity);
 311
 6312            int[] newBuckets = new int[nextPrimeCapacity];
 456313            for (int i = 0; i < nextPrimeCapacity; i++)
 222314            {
 222315                newBuckets[i] = -1;
 222316            }
 317
 6318            StringKeyEntry<TValue>[] newEntries = new StringKeyEntry<TValue>[nextPrimeCapacity];
 6319            Array.Copy(Entries, 0, newEntries, 0, oldCapacity);
 320
 216321            for (int i = 0; i < oldCapacity; i++)
 102322            {
 102323                ref StringKeyEntry<TValue> entry = ref newEntries[i];
 324
 102325                int newBucketIndex = (entry.HashCode & 0x7FFFFFFF) % nextPrimeCapacity;
 326
 102327                int indexAtBucket = newBuckets[newBucketIndex];
 102328                entry.Next = indexAtBucket;
 102329                newBuckets[newBucketIndex] = i;
 102330            }
 331
 252332            for (int i = oldCapacity; i < nextPrimeCapacity; i++)
 120333            {
 120334                newEntries[i].Next = (1 << 31) | (i + 1);
 120335            }
 336
 6337            Buckets = newBuckets;
 6338            Entries = newEntries;
 6339        }
 340
 341        /// <summary>
 342        ///     Expands the dictionary if it does not have enough empty space for <paramref name="capacityToReserve" />.
 343        /// </summary>
 344        /// <param name="capacityToReserve"></param>
 345        public void Reserve(int capacityToReserve)
 1346        {
 1347            int oldCapacity = Entries.Length;
 1348            if (Count + capacityToReserve > oldCapacity)
 1349            {
 1350                int minCapacity = Count + capacityToReserve;
 1351                int nextPrimeCapacity = DictionaryPrimes.GetNextSize(minCapacity);
 352
 1353                int[] newBuckets = new int[nextPrimeCapacity];
 328354                for (int i = 0; i < nextPrimeCapacity; i++)
 163355                {
 163356                    newBuckets[i] = -1;
 163357                }
 358
 1359                StringKeyEntry<TValue>[] newEntries = new StringKeyEntry<TValue>[nextPrimeCapacity];
 1360                Array.Copy(Entries, 0, newEntries, 0, oldCapacity);
 361
 36362                for (int i = 0; i < oldCapacity; i++)
 17363                {
 17364                    ref StringKeyEntry<TValue> entry = ref newEntries[i];
 365
 17366                    if (entry.Key != null)
 0367                    {
 0368                        int newBucketIndex = (entry.HashCode & 0x7FFFFFFF) % nextPrimeCapacity;
 369
 0370                        int indexAtBucket = newBuckets[newBucketIndex];
 0371                        entry.Next = indexAtBucket;
 0372                        newBuckets[newBucketIndex] = i;
 0373                    }
 17374                }
 375
 294376                for (int i = oldCapacity; i < nextPrimeCapacity; i++)
 146377                {
 146378                    newEntries[i].Next = (1 << 31) | (i + 1);
 146379                }
 380
 1381                Buckets = newBuckets;
 1382                Entries = newEntries;
 1383            }
 1384        }
 385
 386        /// <summary>
 387        ///     Finds the index of the entry corresponding to a key.
 388        /// </summary>
 389        /// <param name="key">The key to find the index of.</param>
 390        /// <returns>The index of the entry, or -1 if the entry does not exist.</returns>
 391        public int IndexOf(string key)
 62392        {
 62393            if (key == null)
 0394            {
 0395                throw new ArgumentNullException();
 396            }
 397
 62398            int hashCode = key.GetStableHashCode() & 0x7FFFFFFF;
 62399            int bucketIndex = hashCode % Buckets.Length;
 62400            int nextKeyIndex = Buckets[bucketIndex];
 401
 73402            while (nextKeyIndex != -1)
 72403            {
 72404                ref StringKeyEntry<TValue> currEntry = ref Entries[nextKeyIndex];
 405
 72406                if (currEntry.Key == key)
 61407                {
 61408                    return nextKeyIndex;
 409                }
 410
 11411                nextKeyIndex = currEntry.Next;
 11412            }
 413
 1414            return -1;
 62415        }
 416
 417        /// <summary>
 418        ///     Replaces the value of the entry if the entry exists.
 419        /// </summary>
 420        /// <param name="key">The key of the entry to modify.</param>
 421        /// <param name="value">The new value of the entry.</param>
 422        /// <returns>True if the entry was found.</returns>
 423        public bool TryModifyValue(string key, TValue value)
 0424        {
 0425            if (key == null)
 0426            {
 0427                throw new ArgumentNullException();
 428            }
 429
 0430            int hashCode = key.GetStableHashCode() & 0x7FFFFFFF;
 0431            int bucketIndex = hashCode % Buckets.Length;
 0432            int nextKeyIndex = Buckets[bucketIndex];
 433
 0434            while (nextKeyIndex != -1)
 0435            {
 0436                ref StringKeyEntry<TValue> currEntry = ref Entries[nextKeyIndex];
 0437                nextKeyIndex = currEntry.Next;
 438
 0439                if (currEntry.Key == key)
 0440                {
 0441                    currEntry.Value = value;
 0442                    return true;
 443                }
 0444            }
 445
 0446            return false;
 0447        }
 448
 449        /// <summary>
 450        ///     Removes the entry if it exists.
 451        /// </summary>
 452        /// <param name="key">The key to remove.</param>
 453        /// <returns>True if the entry was found.</returns>
 454        public bool TryRemove(string key)
 5455        {
 5456            if (key == null)
 0457            {
 0458                throw new ArgumentNullException();
 459            }
 460
 5461            int hashCode = key.GetStableHashCode() & 0x7FFFFFFF;
 5462            int bucketIndex = hashCode % Buckets.Length;
 5463            int indexAtBucket = Buckets[bucketIndex];
 5464            int indexOfKey = indexAtBucket;
 5465            int previousIndex = indexAtBucket;
 466
 5467            bool foundIndex = false;
 468
 6469            while (indexOfKey != -1)
 5470            {
 5471                ref StringKeyEntry<TValue> currEntry = ref Entries[indexOfKey];
 472
 5473                if (currEntry.Key == key)
 4474                {
 4475                    foundIndex = true;
 4476                    break;
 477                }
 478
 1479                previousIndex = indexOfKey;
 1480                indexOfKey = currEntry.Next;
 1481            }
 482
 5483            if (foundIndex)
 4484            {
 4485                ref StringKeyEntry<TValue> currEntry = ref Entries[indexOfKey];
 4486                int nextUsedIndex = currEntry.Next;
 4487                int nextFreeIndex = FreeListHead;
 488
 4489                currEntry.Key = null;
 4490                currEntry.Value = default;
 4491                currEntry.HashCode = 0;
 4492                currEntry.Next = nextFreeIndex | (1 << 31);
 4493                Entries[indexOfKey] = currEntry;
 4494                FreeListHead = indexOfKey;
 495
 4496                if (indexOfKey == indexAtBucket)
 3497                {
 3498                    Buckets[bucketIndex] = nextUsedIndex;
 3499                }
 500                else
 1501                {
 1502                    Entries[previousIndex].Next = nextUsedIndex;
 1503                }
 504
 4505                return true;
 506            }
 507
 1508            return false;
 5509        }
 510
 511        /// <summary>
 512        ///     Removes the entry if it exists, but does not remove the value of the key value pair.
 513        /// </summary>
 514        /// <param name="key">The key to remove.</param>
 515        /// <returns>True if the entry was found.</returns>
 516        public bool TryRemoveNoValueClear(string key)
 0517        {
 0518            if (key == null)
 0519            {
 0520                throw new ArgumentNullException();
 521            }
 522
 0523            int hashCode = key.GetStableHashCode() & 0x7FFFFFFF;
 0524            int bucketIndex = hashCode % Buckets.Length;
 0525            int indexAtBucket = Buckets[bucketIndex];
 0526            int indexOfKey = indexAtBucket;
 0527            int previousIndex = indexAtBucket;
 528
 0529            bool foundIndex = false;
 530
 0531            while (indexOfKey != -1)
 0532            {
 0533                ref StringKeyEntry<TValue> currEntry = ref Entries[indexOfKey];
 534
 0535                if (currEntry.Key == key)
 0536                {
 0537                    foundIndex = true;
 0538                    break;
 539                }
 540
 0541                previousIndex = indexOfKey;
 0542                indexOfKey = currEntry.Next;
 0543            }
 544
 0545            if (foundIndex)
 0546            {
 0547                ref StringKeyEntry<TValue> currEntry = ref Entries[indexOfKey];
 0548                int nextUsedIndex = currEntry.Next;
 0549                int nextFreeIndex = FreeListHead;
 550
 0551                currEntry.Key = null;
 0552                currEntry.HashCode = 0;
 0553                currEntry.Next = nextFreeIndex | (1 << 31);
 0554                Entries[indexOfKey] = currEntry;
 0555                FreeListHead = indexOfKey;
 556
 0557                if (indexOfKey == indexAtBucket)
 0558                {
 0559                    Buckets[bucketIndex] = nextUsedIndex;
 0560                }
 561                else
 0562                {
 0563                    Entries[previousIndex].Next = nextUsedIndex;
 0564                }
 565
 0566                return true;
 567            }
 568
 0569            return false;
 0570        }