< Summary

Class:GDX.Collections.UnsafeSparseSet
Assembly:GDX
File(s):./Packages/com.dotbunny.gdx/GDX/Collections/UnsafeSparseSet.cs
Covered lines:558
Uncovered lines:49
Coverable lines:607
Total lines:1242
Line coverage:91.9% (558 of 607)
Covered branches:0
Total branches:0
Covered methods:32
Total methods:37
Method coverage:86.4% (32 of 37)

Coverage History

Metrics

MethodBranch coverage Crap Score Cyclomatic complexity NPath complexity Sequence coverage
UnsafeSparseSet(...)0%440100%
UnsafeSparseSet(...)0%440100%
AddWithExpandCheck(...)0%660100%
AddWithExpandCheck(...)0%770100%
AddUnchecked(...)0%110100%
AddUnchecked(...)0%110100%
GetDenseIndexUnchecked(...)0%110100%
GetDenseIndexWithBoundsCheck(...)0%6.016092.86%
GetDenseIndexWithVersionCheck(...)0%220100%
GetDenseIndexWithBoundsAndVersionCheck(...)0%7.017093.33%
RemoveWithBoundsCheck(...)0%770100%
RemoveWithBoundsAndVersionChecks(...)0%880100%
RemoveUnchecked(...)0%110100%
RemoveUnchecked(...)0%110100%
RemoveUnchecked(...)0%110100%
RemoveUnchecked(...)0%110100%
RemoveUncheckedFromDenseIndex(...)0%110100%
RemoveUncheckedFromDenseIndex(...)0%110100%
RemoveUncheckedFromDenseIndex(...)0%110100%
RemoveUncheckedFromDenseIndex(...)0%110100%
RemoveWithVersionCheck(...)0%220100%
Clear()0%220100%
Clear(...)0%220100%
ClearWithVersionArrayReset(...)0%220100%
Expand(...)0%550100%
Expand(...)0%660100%
Reserve(...)0%660100%
Reserve(...)0%770100%
Dispose()0%220100%
Dispose(...)0%6200%
Dispose(...)0%6200%
DisposeVersionArray(...)0%110100%
DisposeVersionArray(...)0%6200%

File(s)

./Packages/com.dotbunny.gdx/GDX/Collections/UnsafeSparseSet.cs

#LineLine coverage
 1#if GDX_UNSAFE_COLLECTIONS
 2// Copyright (c) 2020-2024 dotBunny Inc.
 3// dotBunny licenses this file to you under the BSL-1.0 license.
 4// See the LICENSE file in the project root for more information.
 5
 6using System.Runtime.CompilerServices;
 7using Unity.Collections;
 8using Unity.Collections.LowLevel.Unsafe;
 9using Unity.Jobs;
 10using Unity.Jobs.LowLevel.Unsafe;
 11using System.Diagnostics;
 12using System.Runtime.InteropServices;
 13using Unity.Burst;
 14
 15namespace GDX.Collections
 16{
 17    /// <summary>
 18    ///     An adapter collection for external data arrays that allows constant-time insertion, deletion, and lookup by
 19    ///     handle, as well as array-like iteration.
 20    /// </summary>
 21    [DebuggerDisplay("Count = {Count}, Length = {Length}, IsCreated = {IsCreated}, IsEmpty = {IsEmpty}")]
 22    [DebuggerTypeProxy(typeof(UnsafeSparseSetDebugView))]
 23    [StructLayout(LayoutKind.Sequential)]
 24    [BurstCompatible(GenericTypeArguments = new[] { typeof(int) })]
 25    public unsafe struct UnsafeSparseSet : INativeDisposable
 26    {
 27        public const int MinimumCapacity = JobsUtility.CacheLineSize / (sizeof(int) * 2);
 28
 29        [NativeDisableUnsafePtrRestriction]
 30        public void* Data;
 31        /// <summary>
 32        ///     Holds references to the sparse array for swapping indices.
 33        /// </summary>
 34        public int* DenseArray
 35        {
 36            [MethodImpl(MethodImplOptions.AggressiveInlining)]
 39837            get => (int*)Data + Length;
 38        }
 39
 40        /// <summary>
 41        ///     Holds references to dense array indices.
 42        /// </summary>
 43        /// <remarks>
 44        ///     Its own indices are claimed and freed via a free-list.
 45        /// </remarks>
 46        public int* SparseArray
 47        {
 48            [MethodImpl(MethodImplOptions.AggressiveInlining)]
 46049            get => (int*)Data;
 50        }
 51
 52        /// <summary>
 53        ///     How many indices are being used currently?
 54        /// </summary>
 55        public int Count;
 56
 57        /// <summary>
 58        ///     The first free (currently unused) index in the sparse array.
 59        /// </summary>
 60        public int FreeIndex;
 61
 62        /// <summary>
 63        ///     The current capacity of both the sparse and dense arrays.
 64        /// </summary>
 65        public int Length;
 66
 67        public AllocatorManager.AllocatorHandle Allocator;
 68
 69        /// <summary>
 70        /// Whether this Sparse Set has been allocated (and not yet deallocated).
 71        /// </summary>
 72        /// <value>True if this list has been allocated (and not yet deallocated).</value>
 073        public bool IsCreated { [MethodImpl(MethodImplOptions.AggressiveInlining)] get { return Data != null; } }
 74
 75        /// <summary>
 76        /// Whether the Sparse Set is empty.
 77        /// </summary>
 78        /// <value>True if the Sparse Set is empty or has not been constructed.</value>
 079        public bool IsEmpty { [MethodImpl(MethodImplOptions.AggressiveInlining)] get { return !IsCreated || Length == 0;
 80
 81        /// <summary>
 82        ///     Create an <see cref="UnsafeSparseSet" /> with an <paramref name="initialCapacity" />.
 83        /// </summary>
 84        /// <param name="initialCapacity">The initial capacity of the sparse and dense int arrays.</param>
 85        /// <param name="allocator">The <see cref="AllocatorManager.AllocatorHandle" /> type to use.</param>
 86        public UnsafeSparseSet(int initialCapacity, AllocatorManager.AllocatorHandle allocator)
 1487        {
 1488            initialCapacity = initialCapacity > MinimumCapacity ? initialCapacity : MinimumCapacity;
 1489            --initialCapacity;
 1490            initialCapacity |= initialCapacity >> 1;
 1491            initialCapacity |= initialCapacity >> 2;
 1492            initialCapacity |= initialCapacity >> 4;
 1493            initialCapacity |= initialCapacity >> 8;
 1494            initialCapacity |= initialCapacity >> 16;
 1495            ++initialCapacity;
 96
 1497            Data = allocator.Allocate(sizeof(int), JobsUtility.CacheLineSize, initialCapacity * 2);
 1498            Count = 0;
 1499            FreeIndex = 0;
 14100            Length = initialCapacity;
 14101            Allocator = allocator;
 102
 252103            for (int i = 0; i < initialCapacity; i++)
 112104            {
 112105                DenseArray[i] = -1;
 112106                SparseArray[i] = i + 1;
 112107            }
 14108        }
 109
 110        /// <summary>
 111        ///     Create an <see cref="UnsafeSparseSet" /> with an <paramref name="initialCapacity" />.
 112        /// </summary>
 113        /// <param name="initialCapacity">The initial capacity of the sparse and dense int arrays.</param>
 114        /// <param name="allocator">The <see cref="Unity.Collections.Allocator" /> type to use.</param>
 115        /// <param name="versionArray">Enables detection of use-after-free errors when using sparse indices as reference
 116        public UnsafeSparseSet(int initialCapacity, AllocatorManager.AllocatorHandle allocator, out ulong* versionArray)
 16117        {
 16118            initialCapacity = initialCapacity > MinimumCapacity ? initialCapacity : MinimumCapacity;
 16119            --initialCapacity;
 16120            initialCapacity |= initialCapacity >> 1;
 16121            initialCapacity |= initialCapacity >> 2;
 16122            initialCapacity |= initialCapacity >> 4;
 16123            initialCapacity |= initialCapacity >> 8;
 16124            initialCapacity |= initialCapacity >> 16;
 16125            ++initialCapacity;
 126
 16127            Data = allocator.Allocate(sizeof(int), JobsUtility.CacheLineSize, initialCapacity * 2);
 16128            Count = 0;
 16129            FreeIndex = 0;
 16130            Length = initialCapacity;
 16131            Allocator = allocator;
 16132            versionArray = (ulong*)allocator.Allocate(sizeof(ulong), JobsUtility.CacheLineSize, initialCapacity);
 133
 288134            for (int i = 0; i < initialCapacity; i++)
 128135            {
 128136                DenseArray[i] = -1;
 128137                SparseArray[i] = i + 1;
 128138                versionArray[i] = 1;
 128139            }
 16140        }
 141
 142        /// <summary>
 143        ///     Adds a sparse/dense index pair to the set and expands the arrays if necessary.
 144        /// </summary>
 145        /// <param name="expandBy">How many indices to expand by.</param>
 146        /// <param name="sparseIndex">The sparse index allocated.</param>
 147        /// <param name="denseIndex">The dense index allocated.</param>
 148        /// <returns>True if the index pool expanded.</returns>
 149        public bool AddWithExpandCheck(int expandBy, out int sparseIndex, out int denseIndex)
 18150        {
 18151            int indexToClaim = FreeIndex;
 18152            int currentCapacity = Length;
 18153            bool needsExpansion = false;
 154
 18155            if (indexToClaim >= currentCapacity)
 2156            {
 157                // We're out of space, the last free index points to nothing. Allocate more indices.
 2158                needsExpansion = true;
 159
 2160                int newCapacity = currentCapacity + expandBy;
 161
 2162                newCapacity = newCapacity > MinimumCapacity ? newCapacity : MinimumCapacity;
 2163                --newCapacity;
 2164                newCapacity |= newCapacity >> 1;
 2165                newCapacity |= newCapacity >> 2;
 2166                newCapacity |= newCapacity >> 4;
 2167                newCapacity |= newCapacity >> 8;
 2168                newCapacity |= newCapacity >> 16;
 2169                ++newCapacity;
 170
 2171                void* newData = Allocator.Allocate(sizeof(int), JobsUtility.CacheLineSize, newCapacity * 2);
 172
 2173                UnsafeUtility.MemCpy(newData, Data, sizeof(int) * currentCapacity);
 2174                int* newSparseArray = (int*)newData;
 36175                for (int i = currentCapacity; i < newCapacity; i++)
 16176                {
 16177                    newSparseArray[i] = i + 1;
 16178                }
 179
 2180                int* newDenseArray = newSparseArray + newCapacity;
 2181                UnsafeUtility.MemCpy(newDenseArray, DenseArray, sizeof(int) * currentCapacity);
 36182                for (int i = currentCapacity; i < newCapacity; i++)
 16183                {
 16184                    newDenseArray[i] = -1;
 16185                }
 186
 2187                Allocator.Free(Data, sizeof(int), JobsUtility.CacheLineSize, currentCapacity * 2);
 188
 2189                Data = newData;
 2190                Length = newCapacity;
 2191            }
 192
 18193            int nextFreeIndex = SparseArray[indexToClaim];
 18194            DenseArray[Count] = indexToClaim; // Point the next dense id at our newly claimed sparse index.
 18195            SparseArray[indexToClaim] = Count; // Point our newly claimed sparse index at the dense index.
 18196            denseIndex = Count;
 197
 18198            ++Count;
 18199            FreeIndex = nextFreeIndex; // Set the free list head for next time.
 200
 18201            sparseIndex = indexToClaim;
 18202            return needsExpansion;
 18203        }
 204
 205        /// <summary>
 206        ///     Adds a sparse/dense index pair to the set and expands the arrays if necessary.
 207        /// </summary>
 208        /// <param name="expandBy">How many indices to expand by.</param>
 209        /// <param name="sparseIndex">The sparse index allocated.</param>
 210        /// <param name="denseIndex">The dense index allocated.</param>
 211        /// <param name="versionArray">Enables detection of use-after-free errors when using sparse indices as reference
 212        /// <returns>True if the index pool expanded.</returns>
 213        public bool AddWithExpandCheck(int expandBy, out int sparseIndex, out int denseIndex, ref ulong* versionArray)
 9214        {
 9215            int indexToClaim = FreeIndex;
 9216            int currentCapacity = Length;
 9217            bool needsExpansion = false;
 218
 9219            if (indexToClaim >= currentCapacity)
 1220            {
 221                // We're out of space, the last free index points to nothing. Allocate more indices.
 1222                needsExpansion = true;
 223
 1224                int newCapacity = currentCapacity + expandBy;
 225
 1226                newCapacity = newCapacity > MinimumCapacity ? newCapacity : MinimumCapacity;
 1227                --newCapacity;
 1228                newCapacity |= newCapacity >> 1;
 1229                newCapacity |= newCapacity >> 2;
 1230                newCapacity |= newCapacity >> 4;
 1231                newCapacity |= newCapacity >> 8;
 1232                newCapacity |= newCapacity >> 16;
 1233                ++newCapacity;
 234
 1235                void* newData = Allocator.Allocate(sizeof(int), JobsUtility.CacheLineSize, newCapacity * 2);
 236
 1237                UnsafeUtility.MemCpy(newData, Data, sizeof(int) * currentCapacity);
 1238                int* newSparseArray = (int*)newData;
 18239                for (int i = currentCapacity; i < newCapacity; i++)
 8240                {
 8241                    newSparseArray[i] = i + 1;
 8242                }
 243
 1244                int* newDenseArray = newSparseArray + newCapacity;
 1245                UnsafeUtility.MemCpy(newDenseArray, DenseArray, sizeof(int) * currentCapacity);
 18246                for (int i = currentCapacity; i < newCapacity; i++)
 8247                {
 8248                    newDenseArray[i] = -1;
 8249                }
 250
 1251                ulong* newVersionArray =
 252                                                                                                                        
 1253                UnsafeUtility.MemCpy(newVersionArray, versionArray, sizeof(ulong) * currentCapacity);
 18254                for (int i = currentCapacity; i < newCapacity; i++)
 8255                {
 8256                    newVersionArray[i] = 1;
 8257                }
 258
 1259                Allocator.Free(Data, sizeof(int), JobsUtility.CacheLineSize, currentCapacity * 2);
 1260                Allocator.Free(versionArray, sizeof(ulong), JobsUtility.CacheLineSize, currentCapacity);
 1261                versionArray = newVersionArray;
 262
 1263                Data = newData;
 1264                Length = newCapacity;
 1265            }
 266
 9267            int nextFreeIndex = SparseArray[indexToClaim];
 9268            DenseArray[Count] = indexToClaim; // Point the next dense id at our newly claimed sparse index.
 9269            SparseArray[indexToClaim] = Count; // Point our newly claimed sparse index at the dense index.
 9270            denseIndex = Count;
 271
 9272            ++Count;
 9273            FreeIndex = nextFreeIndex; // Set the free list head for next time.
 274
 9275            sparseIndex = indexToClaim;
 9276            return needsExpansion;
 9277        }
 278
 279        /// <summary>
 280        ///     Adds a sparse/dense index pair to the set without checking if the set needs to expand.
 281        /// </summary>
 282        /// <param name="sparseIndex">The sparse index allocated.</param>
 283        /// <param name="denseIndex">The dense index allocated.</param>
 284        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 285        public void AddUnchecked(out int sparseIndex, out int denseIndex)
 18286        {
 18287            int indexToClaim = FreeIndex;
 18288            int nextFreeIndex = SparseArray[indexToClaim];
 18289            DenseArray[Count] = indexToClaim; // Point the next dense id at our newly claimed sparse index.
 18290            SparseArray[indexToClaim] = Count; // Point our newly claimed sparse index at the dense index.
 291
 18292            sparseIndex = indexToClaim;
 18293            denseIndex = Count;
 18294            ++Count;
 18295            FreeIndex = nextFreeIndex; // Set the free list head for next time.
 18296        }
 297
 298        /// <summary>
 299        ///     Adds a sparse/dense index pair to the set without checking if the set needs to expand.
 300        /// </summary>
 301        /// <param name="sparseIndex">The sparse index allocated.</param>
 302        /// <param name="denseIndex">The dense index allocated.</param>
 303        /// <param name="versionArray">The array containing the version number to check against.</param>
 304        /// <param name="version">Enables detection of use-after-free errors when using the sparse index as a reference.
 305        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 306        public void AddUnchecked(out int sparseIndex, out int denseIndex, ulong* versionArray, out ulong version)
 22307        {
 22308            int indexToClaim = FreeIndex;
 22309            int nextFreeIndex = SparseArray[indexToClaim];
 22310            DenseArray[Count] = indexToClaim; // Point the next dense id at our newly claimed sparse index.
 22311            SparseArray[indexToClaim] = Count; // Point our newly claimed sparse index at the dense index.
 312
 22313            version = versionArray[indexToClaim];
 22314            sparseIndex = indexToClaim;
 22315            denseIndex = Count;
 316
 22317            ++Count;
 22318            FreeIndex = nextFreeIndex; // Set the free list head for next time.
 22319        }
 320
 321        /// <summary>
 322        ///     Gets the value of the sparse array at the given index without any data validation.
 323        /// </summary>
 324        /// <param name="sparseIndex">The index to check in the sparse array.</param>
 325        /// <returns>The dense index at the given sparse index.</returns>
 326        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 327        public int GetDenseIndexUnchecked(int sparseIndex)
 1328        {
 1329            return SparseArray[sparseIndex];
 1330        }
 331
 332        /// <summary>
 333        ///     Gets the value of the sparse array at the given index,
 334        ///     or -1 if the dense and sparse indices don't point to each other or if the dense index is outside the den
 335        /// </summary>
 336        /// <param name="sparseIndex">The index in the sparse array to check against.</param>
 337        /// <returns>The dense index pointed to by the current sparse index, or -1 if invalid.</returns>
 338        public int GetDenseIndexWithBoundsCheck(int sparseIndex)
 4339        {
 4340            if (sparseIndex >= 0 && sparseIndex < Length)
 3341            {
 3342                int denseIndex = SparseArray[sparseIndex];
 343
 3344                if (denseIndex < Count && denseIndex >= 0)
 1345                {
 1346                    int sparseIndexAtDenseIndex = DenseArray[denseIndex];
 347
 1348                    if (sparseIndex == sparseIndexAtDenseIndex)
 1349                    {
 1350                        return denseIndex;
 351                    }
 0352                }
 2353            }
 354
 3355            return -1;
 4356        }
 357
 358        /// <summary>
 359        ///     Gets the value of the sparse array at the given index,
 360        ///     or -1 if the version number does not match.
 361        /// </summary>
 362        /// <param name="sparseIndex">The index in the sparse array to check against.</param>
 363        /// <param name="version">The version number associated with the sparse index.</param>
 364        /// <param name="versionArray">The array containing the version number to check against.</param>
 365        /// <returns>The dense index pointed to by the current sparse index, or -1 if invalid.</returns>
 366        public int GetDenseIndexWithVersionCheck(int sparseIndex, ulong version, ulong* versionArray)
 4367        {
 4368            int denseIndex = SparseArray[sparseIndex];
 4369            ulong versionAtSparseIndex = versionArray[sparseIndex];
 370
 4371            if (version == versionAtSparseIndex)
 2372            {
 2373                return denseIndex;
 374            }
 375
 2376            return -1;
 4377        }
 378
 379        /// <summary>
 380        ///     Gets the value of the sparse array at the given index,
 381        ///     or -1 if the given sparse index is invalid..
 382        /// </summary>
 383        /// <param name="sparseIndex">The index in the sparse array to check against.</param>
 384        /// <param name="version">The version number associated with the sparse index.</param>
 385        /// <param name="versionArray">The array containing the version number to check against.</param>
 386        /// <returns>The dense index pointed to by the current sparse index, or -1 if invalid.</returns>
 387        public int GetDenseIndexWithBoundsAndVersionCheck(int sparseIndex, ulong version, ulong* versionArray)
 7388        {
 7389            if (sparseIndex >= 0 && sparseIndex < Length)
 5390            {
 5391                int denseIndex = SparseArray[sparseIndex];
 5392                ulong versionAtSparseIndex = versionArray[sparseIndex];
 393
 5394                if (versionAtSparseIndex == version && denseIndex < Count && denseIndex >= 0)
 2395                {
 2396                    int sparseIndexAtDenseIndex = DenseArray[denseIndex];
 397
 2398                    if (sparseIndex == sparseIndexAtDenseIndex)
 2399                    {
 2400                        return denseIndex;
 401                    }
 0402                }
 3403            }
 404
 5405            return -1;
 7406        }
 407
 408        /// <summary>
 409        ///     Removes the entry corresponding to the sparse index if the entry is within bounds and currently in use.
 410        /// </summary>
 411        /// <param name="sparseIndexToRemove">The sparse index corresponding to the entry to remove. Cleared to -1 in th
 412        /// <param name="dataIndexToSwapFrom">
 413        ///     Set the data array value at this index to default after swapping with the data array
 414        ///     value at indexToSwapTo.
 415        /// </param>
 416        /// <param name="dataIndexToSwapTo">Replace the data array value at this index with the data array value at inde
 417        /// <returns>True if the index reference was valid, and thus removed.</returns>
 418        public bool RemoveWithBoundsCheck(ref int sparseIndexToRemove, out int dataIndexToSwapFrom, out int dataIndexToS
 4419        {
 4420            dataIndexToSwapFrom = -1;
 4421            dataIndexToSwapTo = -1;
 4422            bool didRemove = false;
 4423            if (sparseIndexToRemove >= 0 && sparseIndexToRemove < Length)
 2424            {
 2425                int denseIndexToRemove = SparseArray[sparseIndexToRemove];
 426
 2427                if (denseIndexToRemove >= 0 && denseIndexToRemove < Count)
 1428                {
 1429                    int sparseIndexAtDenseIndex = DenseArray[denseIndexToRemove];
 1430                    int newLength = Count - 1;
 1431                    int sparseIndexBeingSwapped = DenseArray[newLength];
 432
 1433                    if (denseIndexToRemove < Count && sparseIndexAtDenseIndex == sparseIndexToRemove)
 1434                    {
 1435                        didRemove = true;
 436                        // Swap the entry being removed with the last entry.
 1437                        SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
 1438                        DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
 439
 1440                        dataIndexToSwapFrom = newLength;
 1441                        dataIndexToSwapTo = denseIndexToRemove;
 442
 443                        // Clear the dense index, for debugging purposes
 1444                        DenseArray[newLength] = -1;
 445
 446                        // Add the sparse index to the free list.
 1447                        SparseArray[sparseIndexToRemove] = FreeIndex;
 1448                        FreeIndex = sparseIndexToRemove;
 449
 1450                        Count = newLength;
 1451                    }
 1452                }
 2453            }
 454
 4455            sparseIndexToRemove = -1;
 456
 4457            return didRemove;
 4458        }
 459
 460        /// <summary>
 461        ///     Removes the associated sparse/dense index pair from active use.
 462        ///     calls.
 463        /// </summary>
 464        /// <param name="sparseIndexToRemove">The sparse index to remove.</param>
 465        /// <param name="version">
 466        ///     The version number of the int used to access the sparse index. Used to guard against accessing
 467        ///     indices that have been removed and reused.
 468        /// </param>
 469        /// <param name="versionArray">The array containing the version number to check against.</param>
 470        /// <param name="indexToSwapFrom">
 471        ///     Set the data array value at this index to default after swapping with the data array
 472        ///     value at indexToSwapTo.
 473        /// </param>
 474        /// <param name="indexToSwapTo">Replace the data array value at this index with the data array value at indexToS
 475        /// <returns>True if the element was successfully removed.</returns>
 476        public bool RemoveWithBoundsAndVersionChecks(ref int sparseIndexToRemove, ulong version, ulong* versionArray, ou
 6477        {
 6478            indexToSwapFrom = -1;
 6479            indexToSwapTo = -1;
 6480            bool didRemove = false;
 6481            if (sparseIndexToRemove >= 0 && sparseIndexToRemove < Length)
 3482            {
 3483                ulong sparseIndexVersion = versionArray[sparseIndexToRemove];
 3484                int denseIndexToRemove = SparseArray[sparseIndexToRemove];
 485
 3486                if (sparseIndexVersion == version && denseIndexToRemove >= 0 && denseIndexToRemove < Count)
 2487                {
 2488                    int sparseIndexAtDenseIndex = DenseArray[denseIndexToRemove];
 2489                    int newLength = Count - 1;
 2490                    int sparseIndexBeingSwapped = DenseArray[newLength];
 491
 2492                    if (denseIndexToRemove < Count && sparseIndexAtDenseIndex == sparseIndexToRemove)
 2493                    {
 2494                        didRemove = true;
 2495                        versionArray[sparseIndexToRemove] = sparseIndexVersion + 1;
 496                        // Swap the entry being removed with the last entry.
 2497                        SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
 2498                        DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
 499
 2500                        indexToSwapFrom = newLength;
 2501                        indexToSwapTo = denseIndexToRemove;
 502
 503                        // Clear the dense index, for debugging purposes
 2504                        DenseArray[newLength] = -1;
 505
 506                        // Add the sparse index to the free list.
 2507                        SparseArray[sparseIndexToRemove] = FreeIndex;
 2508                        FreeIndex = sparseIndexToRemove;
 509
 2510                        Count = newLength;
 2511                    }
 2512                }
 3513            }
 514
 6515            sparseIndexToRemove = -1;
 516
 6517            return didRemove;
 6518        }
 519
 520        /// <summary>
 521        ///     Removes the associated sparse/dense index pair from active use.
 522        /// </summary>
 523        /// <param name="sparseIndexToRemove">The sparse index to remove.</param>
 524        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 525        public void RemoveUnchecked(int sparseIndexToRemove)
 1526        {
 1527            int denseIndexToRemove = SparseArray[sparseIndexToRemove];
 1528            int newLength = Count - 1;
 1529            int sparseIndexBeingSwapped = DenseArray[newLength];
 530
 531            // Swap the entry being removed with the last entry.
 1532            SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
 1533            DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
 534
 535            // Clear the dense  index, for debugging purposes
 1536            DenseArray[newLength] = -1;
 537
 538            // Add the sparse index to the free list.
 1539            SparseArray[sparseIndexToRemove] = FreeIndex;
 1540            FreeIndex = sparseIndexToRemove;
 541
 1542            Count = newLength;
 1543        }
 544
 545        /// <summary>
 546        ///     Removes the associated sparse/dense index pair from active use and increments the version.
 547        /// </summary>
 548        /// <param name="sparseIndexToRemove">The sparse index to remove.</param>
 549        /// <param name="versionArray">Enables detection of use-after-free errors when using sparse indices as reference
 550        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 551        public void RemoveUnchecked(int sparseIndexToRemove, ulong* versionArray)
 1552        {
 1553            int denseIndexToRemove = SparseArray[sparseIndexToRemove];
 1554            int newLength = Count - 1;
 1555            int sparseIndexBeingSwapped = DenseArray[newLength];
 556
 557            // Swap the entry being removed with the last entry.
 1558            SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
 1559            DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
 560
 561            // Clear the dense  index, for debugging purposes
 1562            DenseArray[newLength] = -1;
 563
 564            // Add the sparse index to the free list.
 1565            SparseArray[sparseIndexToRemove] = FreeIndex;
 1566            versionArray[sparseIndexToRemove] += 1;
 1567            FreeIndex = sparseIndexToRemove;
 568
 1569            Count = newLength;
 1570        }
 571
 572        /// <summary>
 573        ///     Removes the associated sparse/dense index pair from active use.
 574        ///     Out parameters used to manage parallel data arrays.
 575        /// </summary>
 576        /// <param name="sparseIndexToRemove">The sparse index to remove.</param>
 577        /// <param name="indexToSwapTo">Replace the data array value at this index with the data array value at indexToS
 578        /// <param name="indexToSwapFrom">
 579        ///     Set the data array value at this index to default after swapping with the data array
 580        ///     value at indexToSwapTo.
 581        /// </param>
 582        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 583        public void RemoveUnchecked(int sparseIndexToRemove, out int indexToSwapFrom, out int indexToSwapTo)
 1584        {
 1585            int denseIndexToRemove = SparseArray[sparseIndexToRemove];
 1586            int newLength = Count - 1;
 1587            int sparseIndexBeingSwapped = DenseArray[newLength];
 588
 589            // Swap the entry being removed with the last entry.
 1590            SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
 1591            DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
 592
 593            // Clear the dense  index, for debugging purposes
 1594            DenseArray[newLength] = -1;
 595
 596            // Add the sparse index to the free list.
 1597            SparseArray[sparseIndexToRemove] = FreeIndex;
 1598            FreeIndex = sparseIndexToRemove;
 599
 1600            Count = newLength;
 601
 1602            indexToSwapTo = denseIndexToRemove;
 1603            indexToSwapFrom = newLength;
 1604        }
 605
 606        /// <summary>
 607        ///     Removes the associated sparse/dense index pair from active use and increments the version.
 608        ///     Out parameters used to manage parallel data arrays.
 609        /// </summary>
 610        /// <param name="sparseIndexToRemove">The sparse index to remove.</param>
 611        /// <param name="versionArray">Enables detection of use-after-free errors when using sparse indices as reference
 612        /// <param name="indexToSwapTo">Replace the data array value at this index with the data array value at indexToS
 613        /// <param name="indexToSwapFrom">
 614        ///     Set the data array value at this index to default after swapping with the data array
 615        ///     value at indexToSwapTo.
 616        /// </param>
 617        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 618        public void RemoveUnchecked(int sparseIndexToRemove, ulong* versionArray, out int indexToSwapFrom, out int index
 2619        {
 2620            int denseIndexToRemove = SparseArray[sparseIndexToRemove];
 2621            int newLength = Count - 1;
 2622            int sparseIndexBeingSwapped = DenseArray[newLength];
 623
 624            // Swap the entry being removed with the last entry.
 2625            SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
 2626            DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
 627
 628            // Clear the dense  index, for debugging purposes
 2629            DenseArray[newLength] = -1;
 630
 631            // Add the sparse index to the free list.
 2632            SparseArray[sparseIndexToRemove] = FreeIndex;
 2633            versionArray[sparseIndexToRemove] += 1;
 2634            FreeIndex = sparseIndexToRemove;
 635
 2636            Count = newLength;
 637
 2638            indexToSwapTo = denseIndexToRemove;
 2639            indexToSwapFrom = newLength;
 2640        }
 641
 642        /// <summary>
 643        ///     Removes the associated sparse/dense index pair from active use.
 644        /// </summary>
 645        /// <param name="denseIndexToRemove">The dense index associated with the sparse index to remove.</param>
 646        public void RemoveUncheckedFromDenseIndex(int denseIndexToRemove)
 1647        {
 1648            int sparseIndexToRemove = DenseArray[denseIndexToRemove];
 1649            int newLength = Count - 1;
 1650            int sparseIndexBeingSwapped = DenseArray[newLength];
 651
 652            // Swap the entry being removed with the last entry.
 1653            SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
 1654            DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
 655
 656            // Clear the dense  index, for debugging purposes
 1657            DenseArray[newLength] = -1;
 658
 659            // Add the sparse index to the free list.
 1660            SparseArray[sparseIndexToRemove] = FreeIndex;
 1661            FreeIndex = sparseIndexToRemove;
 662
 1663            Count = newLength;
 1664        }
 665
 666        /// <summary>
 667        ///     Removes the associated sparse/dense index pair from active use.
 668        /// </summary>
 669        /// <param name="denseIndexToRemove">The dense index associated with the sparse index to remove.</param>
 670        /// <param name="versionArray">Enables detection of use-after-free errors when using sparse indices as reference
 671        public void RemoveUncheckedFromDenseIndex(int denseIndexToRemove, ulong* versionArray)
 1672        {
 1673            int sparseIndexToRemove = DenseArray[denseIndexToRemove];
 1674            int newLength = Count - 1;
 1675            int sparseIndexBeingSwapped = DenseArray[newLength];
 676
 677            // Swap the entry being removed with the last entry.
 1678            SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
 1679            DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
 680
 681            // Clear the dense  index, for debugging purposes
 1682            DenseArray[newLength] = -1;
 683
 684            // Add the sparse index to the free list.
 1685            SparseArray[sparseIndexToRemove] = FreeIndex;
 1686            versionArray[sparseIndexToRemove] += 1;
 1687            FreeIndex = sparseIndexToRemove;
 688
 1689            Count = newLength;
 1690        }
 691
 692        /// <summary>
 693        ///     Removes the associated sparse/dense index pair from active use.
 694        ///     Out parameter used to manage parallel data arrays.
 695        /// </summary>
 696        /// <param name="denseIndexToRemove">The sparse index to remove.</param>
 697        /// <param name="indexToSwapFrom">
 698        ///     Set the data array value at this index to default after swapping with the data array
 699        ///     value at denseIndexToRemove.
 700        /// </param>
 701        public void RemoveUncheckedFromDenseIndex(int denseIndexToRemove, out int indexToSwapFrom)
 1702        {
 1703            int sparseIndexToRemove = DenseArray[denseIndexToRemove];
 1704            int newLength = Count - 1;
 1705            int sparseIndexBeingSwapped = DenseArray[newLength];
 706
 707            // Swap the entry being removed with the last entry.
 1708            SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
 1709            DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
 710
 711            // Clear the dense  index, for debugging purposes
 1712            DenseArray[newLength] = -1;
 713
 714            // Add the sparse index to the free list.
 1715            SparseArray[sparseIndexToRemove] = FreeIndex;
 1716            FreeIndex = sparseIndexToRemove;
 717
 1718            Count = newLength;
 719
 1720            indexToSwapFrom = newLength;
 1721        }
 722
 723        /// <summary>
 724        ///     Removes the associated sparse/dense index pair from active use.
 725        ///     Out parameter used to manage parallel data arrays.
 726        /// </summary>
 727        /// <param name="denseIndexToRemove">The sparse index to remove.</param>
 728        /// <param name="versionArray">Enables detection of use-after-free errors when using sparse indices as reference
 729        /// <param name="indexToSwapFrom">
 730        ///     Set the data array value at this index to default after swapping with the data array
 731        ///     value at denseIndexToRemove.
 732        /// </param>
 733        public void RemoveUncheckedFromDenseIndex(int denseIndexToRemove, ulong* versionArray, out int indexToSwapFrom)
 1734        {
 1735            int sparseIndexToRemove = DenseArray[denseIndexToRemove];
 1736            int newLength = Count - 1;
 1737            int sparseIndexBeingSwapped = DenseArray[newLength];
 738
 739            // Swap the entry being removed with the last entry.
 1740            SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
 1741            DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
 742
 743            // Clear the dense  index, for debugging purposes
 1744            DenseArray[newLength] = -1;
 745
 746            // Add the sparse index to the free list.
 1747            SparseArray[sparseIndexToRemove] = FreeIndex;
 1748            versionArray[sparseIndexToRemove] += 1;
 1749            FreeIndex = sparseIndexToRemove;
 750
 1751            Count = newLength;
 752
 1753            indexToSwapFrom = newLength;
 1754        }
 755
 756        /// <summary>
 757        ///     Attempts to remove the associated sparse/dense index pair from active use and increments the version if 
 758        ///     Out parameters used to manage parallel data arrays.
 759        /// </summary>
 760        /// <param name="sparseIndexToRemove">The sparse index to remove.</param>
 761        /// <param name="version">
 762        ///     The version number of the int used to access the sparse index. Used to guard against accessing
 763        ///     indices that have been removed and reused.
 764        /// </param>
 765        /// <param name="versionArray">The array containing the version number to check against.</param>
 766        /// <param name="indexToSwapTo">Replace the data array value at this index with the data array value at indexToS
 767        /// <param name="indexToSwapFrom">
 768        ///     Set the data array value at this index to default after swapping with the data array
 769        ///     value at indexToSwapTo.
 770        /// </param>
 771        /// <returns>True if the entry was valid and thus removed.</returns>
 772        public bool RemoveWithVersionCheck(int sparseIndexToRemove, ulong version, ulong* versionArray, out int indexToS
 2773        {
 2774            int denseIndexToRemove = SparseArray[sparseIndexToRemove];
 2775            ulong versionAtSparseIndex = versionArray[sparseIndexToRemove];
 776
 2777            indexToSwapFrom = -1;
 2778            indexToSwapTo = -1;
 779
 2780            bool succeeded = versionAtSparseIndex == version;
 781
 2782            if (succeeded)
 1783            {
 1784                int newLength = Count - 1;
 1785                int sparseIndexBeingSwapped = DenseArray[newLength];
 786
 787                // Swap the entry being removed with the last entry.
 1788                SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
 1789                DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
 790
 791                // Clear the dense  index, for debugging purposes
 1792                DenseArray[newLength] = -1;
 793
 794                // Add the sparse index to the free list.
 1795                SparseArray[sparseIndexToRemove] = FreeIndex;
 1796                versionArray[sparseIndexToRemove] += 1;
 1797                FreeIndex = sparseIndexToRemove;
 798
 1799                Count = newLength;
 800
 1801                indexToSwapTo = denseIndexToRemove;
 1802                indexToSwapFrom = newLength;
 1803            }
 804
 2805            return succeeded;
 2806        }
 807
 808        /// <summary>
 809        ///     Clear the dense and sparse arrays.
 810        /// </summary>
 811        public void Clear()
 1812        {
 1813            int capacity = Length;
 18814            for (int i = 0; i < capacity; i++)
 8815            {
 8816                DenseArray[i] = -1;
 8817                SparseArray[i] = i + 1;
 8818            }
 819
 1820            FreeIndex = 0;
 1821            Count = 0;
 1822        }
 823
 824        /// <summary>
 825        ///     Clear the dense and sparse arrays.
 826        /// </summary>
 827        /// <param name="versionArray">Enables detection of use-after-free errors when using sparse indices as reference
 828        public void Clear(ulong* versionArray)
 1829        {
 1830            int capacity = Length;
 18831            for (int i = 0; i < capacity; i++)
 8832            {
 8833                DenseArray[i] = -1;
 8834                SparseArray[i] = i + 1;
 8835                versionArray[i] += 1;
 8836            }
 837
 1838            FreeIndex = 0;
 1839            Count = 0;
 1840        }
 841
 842        /// <summary>
 843        ///     Clear the dense and sparse arrays and reset the version array.
 844        ///     Note: Only clear the version array if you are sure there are no outstanding dependencies on version numb
 845        /// </summary>
 846        /// ///
 847        /// <param name="versionArray">Enables detection of use-after-free errors when using sparse indices as reference
 848        public void ClearWithVersionArrayReset(ulong* versionArray)
 1849        {
 1850            int capacity = Length;
 18851            for (int i = 0; i < capacity; i++)
 8852            {
 8853                DenseArray[i] = -1;
 8854                SparseArray[i] = i + 1;
 8855                versionArray[i] = 1;
 8856            }
 857
 1858            FreeIndex = 0;
 1859            Count = 0;
 1860        }
 861
 862        /// <summary>
 863        ///     Reallocate the dense and sparse arrays with additional capacity.
 864        /// </summary>
 865        /// <param name="extraCapacity">How many indices to expand the dense and sparse arrays by.</param>
 866        public void Expand(int extraCapacity)
 1867        {
 1868            int currentCapacity = Length;
 1869            int newCapacity = currentCapacity + extraCapacity;
 870
 1871            newCapacity = newCapacity > MinimumCapacity ? newCapacity : MinimumCapacity;
 1872            --newCapacity;
 1873            newCapacity |= newCapacity >> 1;
 1874            newCapacity |= newCapacity >> 2;
 1875            newCapacity |= newCapacity >> 4;
 1876            newCapacity |= newCapacity >> 8;
 1877            newCapacity |= newCapacity >> 16;
 1878            ++newCapacity;
 879
 1880            void* newData = Allocator.Allocate(sizeof(int), JobsUtility.CacheLineSize, newCapacity * 2);
 881
 1882            UnsafeUtility.MemCpy(newData, Data, sizeof(int) * currentCapacity);
 1883            int* newSparseArray = (int*)newData;
 18884            for (int i = currentCapacity; i < newCapacity; i++)
 8885            {
 8886                newSparseArray[i] = i + 1;
 8887            }
 888
 1889            int* newDenseArray = newSparseArray + newCapacity;
 1890            UnsafeUtility.MemCpy(newDenseArray, DenseArray, sizeof(int) * currentCapacity);
 18891            for (int i = currentCapacity; i < newCapacity; i++)
 8892            {
 8893                newDenseArray[i] = -1;
 8894            }
 895
 1896            Allocator.Free(Data, sizeof(int), JobsUtility.CacheLineSize, currentCapacity * 2);
 897
 1898            Data = newData;
 1899            Length = newCapacity;
 1900        }
 901
 902        /// <summary>
 903        ///     Reallocate the dense and sparse arrays with additional capacity.
 904        /// </summary>
 905        /// <param name="extraCapacity">How many indices to expand the dense and sparse arrays by.</param>
 906        /// <param name="versionArray">Enables detection of use-after-free errors when using sparse indices as reference
 907        public void Expand(int extraCapacity, ref ulong* versionArray)
 1908        {
 1909            int currentCapacity = Length;
 1910            int newCapacity = currentCapacity + extraCapacity;
 911
 1912            newCapacity = newCapacity > MinimumCapacity ? newCapacity : MinimumCapacity;
 1913            --newCapacity;
 1914            newCapacity |= newCapacity >> 1;
 1915            newCapacity |= newCapacity >> 2;
 1916            newCapacity |= newCapacity >> 4;
 1917            newCapacity |= newCapacity >> 8;
 1918            newCapacity |= newCapacity >> 16;
 1919            ++newCapacity;
 920
 1921            void* newData = Allocator.Allocate(sizeof(int), JobsUtility.CacheLineSize, newCapacity * 2);
 922
 1923            UnsafeUtility.MemCpy(newData, Data, sizeof(int) * currentCapacity);
 1924            int* newSparseArray = (int*)newData;
 18925            for (int i = currentCapacity; i < newCapacity; i++)
 8926            {
 8927                newSparseArray[i] = i + 1;
 8928            }
 929
 1930            int* newDenseArray = newSparseArray + newCapacity;
 1931            UnsafeUtility.MemCpy(newDenseArray, DenseArray, sizeof(int) * currentCapacity);
 18932            for (int i = currentCapacity; i < newCapacity; i++)
 8933            {
 8934                newDenseArray[i] = -1;
 8935            }
 936
 1937            ulong* newVersionArray =
 938                                                                                                                        
 1939            UnsafeUtility.MemCpy(newVersionArray, versionArray, sizeof(ulong) * currentCapacity);
 18940            for (int i = currentCapacity; i < newCapacity; i++)
 8941            {
 8942                newVersionArray[i] = 1;
 8943            }
 944
 1945            Allocator.Free(Data, sizeof(int), JobsUtility.CacheLineSize, currentCapacity * 2);
 1946            Allocator.Free(versionArray, sizeof(ulong), JobsUtility.CacheLineSize, currentCapacity);
 1947            versionArray = newVersionArray;
 948
 1949            Data = newData;
 1950            Length = newCapacity;
 1951        }
 952
 953        /// <summary>
 954        /// Reallocate the dense and sparse arrays with additional capacity if there are not at least <paramref name="nu
 955        /// </summary>
 956        /// <param name="numberToReserve">The number of unused entries to ensure capacity for.</param>
 957        public void Reserve(int numberToReserve)
 1958        {
 1959            int currentCapacity = Length;
 1960            int currentCount = Count;
 1961            int newCapacity = currentCount + numberToReserve;
 962
 1963            if (newCapacity > currentCapacity)
 1964            {
 1965                newCapacity = newCapacity > MinimumCapacity ? newCapacity : MinimumCapacity;
 1966                --newCapacity;
 1967                newCapacity |= newCapacity >> 1;
 1968                newCapacity |= newCapacity >> 2;
 1969                newCapacity |= newCapacity >> 4;
 1970                newCapacity |= newCapacity >> 8;
 1971                newCapacity |= newCapacity >> 16;
 1972                ++newCapacity;
 973
 1974                void* newData = Allocator.Allocate(sizeof(int), JobsUtility.CacheLineSize, newCapacity * 2);
 975
 1976                UnsafeUtility.MemCpy(newData, Data, sizeof(int) * currentCapacity);
 1977                int* newSparseArray = (int*)newData;
 18978                for (int i = currentCapacity; i < newCapacity; i++)
 8979                {
 8980                    newSparseArray[i] = i + 1;
 8981                }
 982
 1983                int* newDenseArray = newSparseArray + newCapacity;
 1984                UnsafeUtility.MemCpy(newDenseArray, DenseArray, sizeof(int) * currentCapacity);
 18985                for (int i = currentCapacity; i < newCapacity; i++)
 8986                {
 8987                    newDenseArray[i] = -1;
 8988                }
 989
 1990                Allocator.Free(Data, sizeof(int), JobsUtility.CacheLineSize, currentCapacity * 2);
 991
 1992                Data = newData;
 1993                Length = newCapacity;
 1994            }
 1995        }
 996
 997        /// <summary>
 998        /// Reallocate the dense and sparse arrays with additional capacity if there are not at least <paramref name="nu
 999        /// </summary>
 1000        /// <param name="numberToReserve">The number of unused entries to ensure capacity for.</param>
 1001        /// <param name="versionArray">Enables detection of use-after-free errors when using sparse indices as reference
 1002        public void Reserve(int numberToReserve,  ref ulong* versionArray)
 11003        {
 11004            int currentCapacity = Length;
 11005            int currentCount = Count;
 11006            int newCapacity = currentCount + numberToReserve;
 1007
 11008            if (newCapacity > currentCapacity)
 11009            {
 11010                newCapacity = newCapacity > MinimumCapacity ? newCapacity : MinimumCapacity;
 11011                --newCapacity;
 11012                newCapacity |= newCapacity >> 1;
 11013                newCapacity |= newCapacity >> 2;
 11014                newCapacity |= newCapacity >> 4;
 11015                newCapacity |= newCapacity >> 8;
 11016                newCapacity |= newCapacity >> 16;
 11017                ++newCapacity;
 1018
 11019                void* newData = Allocator.Allocate(sizeof(int), JobsUtility.CacheLineSize, newCapacity * 2);
 1020
 11021                UnsafeUtility.MemCpy(newData, Data, sizeof(int) * currentCapacity);
 11022                int* newSparseArray = (int*)newData;
 181023                for (int i = currentCapacity; i < newCapacity; i++)
 81024                {
 81025                    newSparseArray[i] = i + 1;
 81026                }
 1027
 11028                int* newDenseArray = newSparseArray + newCapacity;
 11029                UnsafeUtility.MemCpy(newDenseArray, DenseArray, sizeof(int) * currentCapacity);
 181030                for (int i = currentCapacity; i < newCapacity; i++)
 81031                {
 81032                    newDenseArray[i] = -1;
 81033                }
 1034
 11035                ulong* newVersionArray =
 1036                                                                                                                        
 11037                UnsafeUtility.MemCpy(newVersionArray, versionArray, sizeof(ulong) * currentCapacity);
 181038                for (int i = currentCapacity; i < newCapacity; i++)
 81039                {
 81040                    newVersionArray[i] = 1;
 81041                }
 1042
 11043                Allocator.Free(Data, sizeof(int), JobsUtility.CacheLineSize, currentCapacity * 2);
 11044                Allocator.Free(versionArray, sizeof(ulong), JobsUtility.CacheLineSize, currentCapacity);
 11045                versionArray = newVersionArray;
 1046
 11047                Data = newData;
 11048                Length = newCapacity;
 11049            }
 11050        }
 1051
 1052        /// <summary>
 1053        /// Disposes the memory of this Sparse Set.
 1054        /// </summary>
 1055        public void Dispose()
 11056        {
 11057            if (Data != null)
 11058            {
 11059                Allocator.Free(Data, sizeof(int), JobsUtility.CacheLineSize, Length * 2);
 11060                Data = null;
 11061                Length = 0;
 11062                Count = 0;
 11063                FreeIndex = 0;
 11064                Allocator = Unity.Collections.Allocator.Invalid;
 11065            }
 11066        }
 1067
 1068        /// <summary>
 1069        /// Creates and schedules a job that disposes the memory of this Sparse Set.
 1070        /// </summary>
 1071        /// <param name="inputDeps">The dependency for the new job.</param>
 1072        /// <returns>The handle of the new job. The job depends upon `inputDeps` and frees the memory of this Sparse Set
 1073        [NotBurstCompatible /* This is not burst compatible because of IJob's use of a static IntPtr. Should switch to I
 1074        public JobHandle Dispose(JobHandle inputDeps)
 01075        {
 01076            if (CollectionHelper.ShouldDeallocate(Allocator))
 01077            {
 01078                var jobHandle = new DisposeUnsafeSparseSetJob { Ptr = Data, Capacity = Length, Allocator =
 1079                                                                                                                        
 1080
 01081                Data = null;
 01082                Length = 0;
 01083                Count = 0;
 01084                FreeIndex = 0;
 01085                Allocator = Unity.Collections.Allocator.Invalid;
 1086
 01087                return jobHandle;
 1088            }
 1089
 01090            Data = null;
 01091            Length = 0;
 01092            Count = 0;
 01093            FreeIndex = 0;
 01094            Allocator = Unity.Collections.Allocator.Invalid;
 1095
 01096            return inputDeps;
 01097        }
 1098
 1099        /// <summary>
 1100        /// Creates and schedules a job that disposes the memory of this Sparse Set.
 1101        /// </summary>
 1102        /// <param name="inputDeps">The dependency for the new job.</param>
 1103        /// <returns>The handle of the new job. The job depends upon `inputDeps` and frees the memory of this Sparse Set
 1104        [NotBurstCompatible /* This is not burst compatible because of IJob's use of a static IntPtr. Should switch to I
 1105        public JobHandle Dispose(JobHandle inputDeps, ref ulong* versionArray)
 01106        {
 01107            if (CollectionHelper.ShouldDeallocate(Allocator))
 01108            {
 01109                var jobHandle = new DisposeUnsafeSparseSetAndVersionArrayJob { Ptr = Data, VersionArrayPtr =
 1110                                                                                                                        
 1111
 01112                Data = null;
 01113                Length = 0;
 01114                Count = 0;
 01115                FreeIndex = 0;
 01116                Allocator = Unity.Collections.Allocator.Invalid;
 01117                versionArray = null;
 1118
 01119                return jobHandle;
 1120            }
 1121
 01122            Data = null;
 01123            Length = 0;
 01124            Count = 0;
 01125            FreeIndex = 0;
 01126            Allocator = Unity.Collections.Allocator.Invalid;
 01127            versionArray = null;
 1128
 01129            return inputDeps;
 01130        }
 1131
 1132        /// <summary>
 1133        /// Disposes the memory of the version array for this Sparse Set.
 1134        /// </summary>
 1135        /// <param name="versionArray">The pointer of the versionArray to dispose of.</param>
 1136        public void DisposeVersionArray(ref ulong* versionArray)
 11137        {
 11138            Allocator.Free(versionArray, sizeof(ulong), JobsUtility.CacheLineSize, Length);
 11139            versionArray = null;
 11140        }
 1141
 1142        /// <summary>
 1143        /// Creates and schedules a job that disposes the memory of this Sparse Set.
 1144        /// </summary>
 1145        /// <param name="inputDeps">The dependency for the new job.</param>
 1146        /// <returns>The handle of the new job. The job depends upon `inputDeps` and disposes the memory of this Sparse 
 1147        [NotBurstCompatible /* This is not burst compatible because of IJob's use of a static IntPtr. Should switch to I
 1148        public JobHandle DisposeVersionArray(JobHandle inputDeps, ref ulong* versionArray)
 01149        {
 01150            if (CollectionHelper.ShouldDeallocate(Allocator))
 01151            {
 01152                var jobHandle = new DisposeUnsafeVersionArrayJob { Ptr = versionArray, Capacity = Length, Allocator =
 1153                                                                                                                        
 1154
 01155                versionArray = null;
 1156
 01157                return jobHandle;
 1158            }
 1159
 01160            versionArray = null;
 1161
 01162            return inputDeps;
 01163        }
 1164    }
 1165
 1166    [BurstCompile]
 1167    internal unsafe struct DisposeUnsafeSparseSetJob : IJob
 1168    {
 1169        [NativeDisableUnsafePtrRestriction]
 1170        public void* Ptr;
 1171        public int Capacity;
 1172        public AllocatorManager.AllocatorHandle Allocator;
 1173
 1174        public void Execute()
 1175        {
 1176            Allocator.Free(Ptr, UnsafeUtility.SizeOf<int>(), JobsUtility.CacheLineSize, Capacity * 2);
 1177        }
 1178    }
 1179
 1180    [BurstCompile]
 1181    internal unsafe struct DisposeUnsafeVersionArrayJob : IJob
 1182    {
 1183        [NativeDisableUnsafePtrRestriction]
 1184        public void* Ptr;
 1185        public int Capacity;
 1186        public AllocatorManager.AllocatorHandle Allocator;
 1187
 1188        public void Execute()
 1189        {
 1190            Allocator.Free(Ptr, UnsafeUtility.SizeOf<ulong>(), JobsUtility.CacheLineSize, Capacity);
 1191        }
 1192    }
 1193
 1194    [BurstCompile]
 1195    internal unsafe struct DisposeUnsafeSparseSetAndVersionArrayJob : IJob
 1196    {
 1197        [NativeDisableUnsafePtrRestriction]
 1198        public void* Ptr;
 1199        [NativeDisableUnsafePtrRestriction]
 1200        public void* VersionArrayPtr;
 1201        public int Capacity;
 1202        public AllocatorManager.AllocatorHandle Allocator;
 1203
 1204        public void Execute()
 1205        {
 1206            Allocator.Free(Ptr, UnsafeUtility.SizeOf<int>(), JobsUtility.CacheLineSize, Capacity * 2);
 1207            Allocator.Free(VersionArrayPtr, UnsafeUtility.SizeOf<ulong>(), JobsUtility.CacheLineSize, Capacity);
 1208        }
 1209    }
 1210
 1211    public struct SparseDenseIndexPair
 1212    {
 1213        public int SparseIndex;
 1214        public int DenseIndex;
 1215    }
 1216
 1217    internal sealed class UnsafeSparseSetDebugView
 1218    {
 1219        UnsafeSparseSet Data;
 1220
 1221        public UnsafeSparseSetDebugView(UnsafeSparseSet data)
 1222        {
 1223            Data = data;
 1224        }
 1225
 1226        public unsafe SparseDenseIndexPair[] Items
 1227        {
 1228            get
 1229            {
 1230                SparseDenseIndexPair[] result = new SparseDenseIndexPair[Data.Count];
 1231
 1232                for (var i = 0; i < Data.Count; ++i)
 1233                {
 1234                    result[i] = new SparseDenseIndexPair() { DenseIndex = i, SparseIndex = Data.DenseArray[i] };
 1235                }
 1236
 1237                return result;
 1238            }
 1239        }
 1240    }
 1241}
 1242#endif // GDX_UNSAFE_COLLECTIONS

Coverage by test methods































Methods/Properties

DenseArray()
SparseArray()
IsCreated()
IsEmpty()
UnsafeSparseSet(System.Int32, Unity.Collections.AllocatorManager/AllocatorHandle)
UnsafeSparseSet(System.Int32, Unity.Collections.AllocatorManager/AllocatorHandle, System.UInt64*&)
AddWithExpandCheck(System.Int32, System.Int32&, System.Int32&)
AddWithExpandCheck(System.Int32, System.Int32&, System.Int32&, System.UInt64*&)
AddUnchecked(System.Int32&, System.Int32&)
AddUnchecked(System.Int32&, System.Int32&, System.UInt64*, System.UInt64&)
GetDenseIndexUnchecked(System.Int32)
GetDenseIndexWithBoundsCheck(System.Int32)
GetDenseIndexWithVersionCheck(System.Int32, System.UInt64, System.UInt64*)
GetDenseIndexWithBoundsAndVersionCheck(System.Int32, System.UInt64, System.UInt64*)
RemoveWithBoundsCheck(System.Int32&, System.Int32&, System.Int32&)
RemoveWithBoundsAndVersionChecks(System.Int32&, System.UInt64, System.UInt64*, System.Int32&, System.Int32&)
RemoveUnchecked(System.Int32)
RemoveUnchecked(System.Int32, System.UInt64*)
RemoveUnchecked(System.Int32, System.Int32&, System.Int32&)
RemoveUnchecked(System.Int32, System.UInt64*, System.Int32&, System.Int32&)
RemoveUncheckedFromDenseIndex(System.Int32)
RemoveUncheckedFromDenseIndex(System.Int32, System.UInt64*)
RemoveUncheckedFromDenseIndex(System.Int32, System.Int32&)
RemoveUncheckedFromDenseIndex(System.Int32, System.UInt64*, System.Int32&)
RemoveWithVersionCheck(System.Int32, System.UInt64, System.UInt64*, System.Int32&, System.Int32&)
Clear()
Clear(System.UInt64*)
ClearWithVersionArrayReset(System.UInt64*)
Expand(System.Int32)
Expand(System.Int32, System.UInt64*&)
Reserve(System.Int32)
Reserve(System.Int32, System.UInt64*&)
Dispose()
Dispose(Unity.Jobs.JobHandle)
Dispose(Unity.Jobs.JobHandle, System.UInt64*&)
DisposeVersionArray(System.UInt64*&)
DisposeVersionArray(Unity.Jobs.JobHandle, System.UInt64*&)