< Summary

Class:GDX.Collections.NativeArraySparseSet
Assembly:GDX
File(s):D:/BuildAgent/work/GDX-Documentation/Projects/GDX_Development/Packages/com.dotbunny.gdx/GDX/Collections/NativeArraySparseSet.cs
Covered lines:473
Uncovered lines:2
Coverable lines:475
Total lines:931
Line coverage:99.5% (473 of 475)
Covered branches:0
Total branches:0
Covered methods:29
Total methods:29
Method coverage:100% (29 of 29)

Coverage History

Metrics

MethodBranch coverage Crap Score Cyclomatic complexity NPath complexity Sequence coverage
NativeArraySparseSet(...)0%220100%
NativeArraySparseSet(...)0%220100%
AddWithExpandCheck(...)0%330100%
AddWithExpandCheck(...)0%330100%
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%220100%
Expand(...)0%220100%
Reserve(...)0%330100%
Reserve(...)0%330100%
Dispose()0%330100%

File(s)

D:/BuildAgent/work/GDX-Documentation/Projects/GDX_Development/Packages/com.dotbunny.gdx/GDX/Collections/NativeArraySparseSet.cs

#LineLine coverage
 1// Copyright (c) 2020-2022 dotBunny Inc.
 2// dotBunny licenses this file to you under the BSL-1.0 license.
 3// See the LICENSE file in the project root for more information.
 4
 5using System.Runtime.CompilerServices;
 6using Unity.Collections;
 7
 8namespace GDX.Collections
 9{
 10    /// <summary>
 11    ///     An adapter collection for external data arrays that allows constant-time insertion, deletion, and lookup by
 12    ///     handle, as well as array-like iteration.
 13    /// </summary>
 14    public struct NativeArraySparseSet : System.IDisposable
 15    {
 16        /// <summary>
 17        ///     Holds references to the sparse array for swapping indices.
 18        /// </summary>
 19        public NativeArray<int> DenseArray;
 20
 21        /// <summary>
 22        ///     Holds references to dense array indices.
 23        /// </summary>
 24        /// <remarks>
 25        ///     Its own indices are claimed and freed via a free-list.
 26        /// </remarks>
 27        public NativeArray<int> SparseArray;
 28
 29        /// <summary>
 30        ///     How many indices are being used currently?
 31        /// </summary>
 32        public int Count;
 33
 34        /// <summary>
 35        ///     The first free (currently unused) index in the sparse array.
 36        /// </summary>
 37        public int FreeIndex;
 38
 39        /// <summary>
 40        ///     Create a <see cref="NativeArraySparseSet" /> with an <paramref name="initialCapacity" />.
 41        /// </summary>
 42        /// <param name="initialCapacity">The initial capacity of the sparse and dense int arrays.</param>
 43        /// <param name="allocator">The <see cref="Unity.Collections.Allocator" /> type to use.</param>
 44        public NativeArraySparseSet(int initialCapacity, Allocator allocator)
 1445        {
 1446            DenseArray = new NativeArray<int>(initialCapacity, allocator, NativeArrayOptions.UninitializedMemory);
 1447            SparseArray = new NativeArray<int>(initialCapacity, allocator, NativeArrayOptions.UninitializedMemory);
 1448            Count = 0;
 1449            FreeIndex = 0;
 50
 10051            for (int i = 0; i < initialCapacity; i++)
 3652            {
 3653                DenseArray[i] = -1;
 3654                SparseArray[i] = i + 1;
 3655            }
 1456        }
 57
 58        /// <summary>
 59        ///     Create a <see cref="NativeArraySparseSet" /> with an <paramref name="initialCapacity" />.
 60        /// </summary>
 61        /// <param name="initialCapacity">The initial capacity of the sparse and dense int arrays.</param>
 62        /// <param name="allocator">The <see cref="Unity.Collections.Allocator" /> type to use.</param>
 63        /// <param name="versionArray">Enables detection of use-after-free errors when using sparse indices as reference
 64        public NativeArraySparseSet(int initialCapacity, Allocator allocator, out NativeArray<ulong> versionArray)
 1765        {
 1766            DenseArray = new NativeArray<int>(initialCapacity, allocator, NativeArrayOptions.UninitializedMemory);
 1767            SparseArray = new NativeArray<int>(initialCapacity, allocator, NativeArrayOptions.UninitializedMemory);
 1768            versionArray = new NativeArray<ulong>(initialCapacity, allocator, NativeArrayOptions.UninitializedMemory);
 1769            Count = 0;
 1770            FreeIndex = 0;
 71
 12472            for (int i = 0; i < initialCapacity; i++)
 4573            {
 4574                DenseArray[i] = -1;
 4575                SparseArray[i] = i + 1;
 4576                versionArray[i] = 1;
 4577            }
 1778        }
 79
 80        /// <summary>
 81        ///     Adds a sparse/dense index pair to the set and expands the arrays if necessary.
 82        /// </summary>
 83        /// <param name="expandBy">How many indices to expand by.</param>
 84        /// <param name="sparseIndex">The sparse index allocated.</param>
 85        /// <param name="denseIndex">The dense index allocated.</param>
 86        /// <param name="allocator">The <see cref="Unity.Collections.Allocator" /> type to use.</param>
 87        /// <returns>True if the index pool expanded.</returns>
 88        public bool AddWithExpandCheck(int expandBy, out int sparseIndex, out int denseIndex, Allocator allocator)
 489        {
 490            int indexToClaim = FreeIndex;
 491            int currentCapacity = SparseArray.Length;
 492            bool needsExpansion = false;
 93
 494            if (indexToClaim >= currentCapacity)
 295            {
 96                // We're out of space, the last free index points to nothing. Allocate more indices.
 297                needsExpansion = true;
 98
 299                int newCapacity = currentCapacity + expandBy;
 100
 2101                NativeArray<int> newSparseArray = new NativeArray<int>(newCapacity, allocator, NativeArrayOptions.Uninit
 2102                NativeSlice<int> newSparseArraySlice = new NativeSlice<int>(newSparseArray, 0, currentCapacity);
 2103                newSparseArraySlice.CopyFrom(SparseArray);
 2104                SparseArray.Dispose();
 2105                SparseArray = newSparseArray;
 106
 2107                NativeArray<int> newDenseArray = new NativeArray<int>(newCapacity, allocator, NativeArrayOptions.Uniniti
 2108                NativeSlice<int> newDenseArraySlice = new NativeSlice<int>(newDenseArray, 0, currentCapacity);
 2109                newDenseArraySlice.CopyFrom(DenseArray);
 2110                DenseArray.Dispose();
 2111                DenseArray = newDenseArray;
 112
 24113                for (int i = currentCapacity; i < newCapacity; i++)
 10114                {
 10115                    SparseArray[i] = i + 1; // Build the free list chain.
 10116                    DenseArray[i] = -1; // Set new dense indices as unclaimed.
 10117                }
 2118            }
 119
 4120            int nextFreeIndex = SparseArray[indexToClaim];
 4121            DenseArray[Count] = indexToClaim; // Point the next dense id at our newly claimed sparse index.
 4122            SparseArray[indexToClaim] = Count; // Point our newly claimed sparse index at the dense index.
 4123            denseIndex = Count;
 124
 4125            ++Count;
 4126            FreeIndex = nextFreeIndex; // Set the free list head for next time.
 127
 4128            sparseIndex = indexToClaim;
 4129            return needsExpansion;
 4130        }
 131
 132        /// <summary>
 133        ///     Adds a sparse/dense index pair to the set and expands the arrays if necessary.
 134        /// </summary>
 135        /// <param name="expandBy">How many indices to expand by.</param>
 136        /// <param name="sparseIndex">The sparse index allocated.</param>
 137        /// <param name="denseIndex">The dense index allocated.</param>
 138        /// <param name="allocator">The <see cref="Unity.Collections.Allocator" /> type to use.</param>
 139        /// <param name="versionArray">Enables detection of use-after-free errors when using sparse indices as reference
 140        /// <returns>True if the index pool expanded.</returns>
 141        public bool AddWithExpandCheck(int expandBy, out int sparseIndex, out int denseIndex, Allocator allocator, ref N
 2142        {
 2143            int indexToClaim = FreeIndex;
 2144            int currentCapacity = SparseArray.Length;
 2145            bool needsExpansion = false;
 146
 2147            if (indexToClaim >= currentCapacity)
 1148            {
 149                // We're out of space, the last free index points to nothing. Allocate more indices.
 1150                needsExpansion = true;
 151
 1152                int newCapacity = currentCapacity + expandBy;
 153
 1154                NativeArray<int> newSparseArray = new NativeArray<int>(newCapacity, allocator, NativeArrayOptions.Uninit
 1155                NativeSlice<int> newSparseArraySlice = new NativeSlice<int>(newSparseArray, 0, currentCapacity);
 1156                newSparseArraySlice.CopyFrom(SparseArray);
 1157                SparseArray.Dispose();
 1158                SparseArray = newSparseArray;
 159
 1160                NativeArray<int> newDenseArray = new NativeArray<int>(newCapacity, allocator, NativeArrayOptions.Uniniti
 1161                NativeSlice<int> newDenseArraySlice = new NativeSlice<int>(newDenseArray, 0, currentCapacity);
 1162                newDenseArraySlice.CopyFrom(DenseArray);
 1163                DenseArray.Dispose();
 1164                DenseArray = newDenseArray;
 165
 1166                NativeArray<ulong> newVersionArray = new NativeArray<ulong>(newCapacity, allocator, NativeArrayOptions.U
 1167                NativeSlice<ulong> newVersionArraySlice = new NativeSlice<ulong>(newVersionArray, 0, currentCapacity);
 1168                newVersionArraySlice.CopyFrom(versionArray);
 1169                versionArray.Dispose();
 1170                versionArray = newVersionArray;
 171
 12172                for (int i = currentCapacity; i < newCapacity; i++)
 5173                {
 5174                    SparseArray[i] = i + 1; // Build the free list chain.
 5175                    DenseArray[i] = -1; // Set new dense indices as unclaimed.
 5176                    versionArray[i] = 1;
 5177                }
 1178            }
 179
 2180            int nextFreeIndex = SparseArray[indexToClaim];
 2181            DenseArray[Count] = indexToClaim; // Point the next dense id at our newly claimed sparse index.
 2182            SparseArray[indexToClaim] = Count; // Point our newly claimed sparse index at the dense index.
 2183            denseIndex = Count;
 184
 2185            ++Count;
 2186            FreeIndex = nextFreeIndex; // Set the free list head for next time.
 187
 2188            sparseIndex = indexToClaim;
 2189            return needsExpansion;
 2190        }
 191
 192        /// <summary>
 193        ///     Adds a sparse/dense index pair to the set without checking if the set needs to expand.
 194        /// </summary>
 195        /// <param name="sparseIndex">The sparse index allocated.</param>
 196        /// <param name="denseIndex">The dense index allocated.</param>
 197        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 198        public void AddUnchecked(out int sparseIndex, out int denseIndex)
 20199        {
 20200            int indexToClaim = FreeIndex;
 20201            int nextFreeIndex = SparseArray[indexToClaim];
 19202            DenseArray[Count] = indexToClaim; // Point the next dense id at our newly claimed sparse index.
 19203            SparseArray[indexToClaim] = Count; // Point our newly claimed sparse index at the dense index.
 204
 19205            sparseIndex = indexToClaim;
 19206            denseIndex = Count;
 19207            ++Count;
 19208            FreeIndex = nextFreeIndex; // Set the free list head for next time.
 19209        }
 210
 211        /// <summary>
 212        ///     Adds a sparse/dense index pair to the set without checking if the set needs to expand.
 213        /// </summary>
 214        /// <param name="sparseIndex">The sparse index allocated.</param>
 215        /// <param name="denseIndex">The dense index allocated.</param>
 216        /// <param name="versionArray">The array containing the version number to check against.</param>
 217        /// <param name="version">Enables detection of use-after-free errors when using the sparse index as a reference.
 218        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 219        public void AddUnchecked(out int sparseIndex, out int denseIndex, NativeArray<ulong> versionArray, out ulong ver
 24220        {
 24221            int indexToClaim = FreeIndex;
 24222            int nextFreeIndex = SparseArray[indexToClaim];
 23223            DenseArray[Count] = indexToClaim; // Point the next dense id at our newly claimed sparse index.
 23224            SparseArray[indexToClaim] = Count; // Point our newly claimed sparse index at the dense index.
 225
 23226            version = versionArray[indexToClaim];
 23227            sparseIndex = indexToClaim;
 23228            denseIndex = Count;
 229
 23230            ++Count;
 23231            FreeIndex = nextFreeIndex; // Set the free list head for next time.
 23232        }
 233
 234        /// <summary>
 235        ///     Gets the value of the sparse array at the given index without any data validation.
 236        /// </summary>
 237        /// <param name="sparseIndex">The index to check in the sparse array.</param>
 238        /// <returns>The dense index at the given sparse index.</returns>
 239        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 240        public int GetDenseIndexUnchecked(int sparseIndex)
 1241        {
 1242            return SparseArray[sparseIndex];
 1243        }
 244
 245        /// <summary>
 246        ///     Gets the value of the sparse array at the given index,
 247        ///     or -1 if the dense and sparse indices don't point to each other or if the dense index is outside the den
 248        /// </summary>
 249        /// <param name="sparseIndex">The index in the sparse array to check against.</param>
 250        /// <returns>The dense index pointed to by the current sparse index, or -1 if invalid.</returns>
 251        public int GetDenseIndexWithBoundsCheck(int sparseIndex)
 4252        {
 4253            if (sparseIndex >= 0 && sparseIndex < SparseArray.Length)
 2254            {
 2255                int denseIndex = SparseArray[sparseIndex];
 256
 2257                if (denseIndex < Count && denseIndex >= 0)
 1258                {
 1259                    int sparseIndexAtDenseIndex = DenseArray[denseIndex];
 260
 1261                    if (sparseIndex == sparseIndexAtDenseIndex)
 1262                    {
 1263                        return denseIndex;
 264                    }
 0265                }
 1266            }
 267
 3268            return -1;
 4269        }
 270
 271        /// <summary>
 272        ///     Gets the value of the sparse array at the given index,
 273        ///     or -1 if the version number does not match.
 274        /// </summary>
 275        /// <param name="sparseIndex">The index in the sparse array to check against.</param>
 276        /// <param name="version">The version number associated with the sparse index.</param>
 277        /// <param name="versionArray">The array containing the version number to check against.</param>
 278        /// <returns>The dense index pointed to by the current sparse index, or -1 if invalid.</returns>
 279        public int GetDenseIndexWithVersionCheck(int sparseIndex, ulong version, NativeArray<ulong> versionArray)
 4280        {
 4281            int denseIndex = SparseArray[sparseIndex];
 4282            ulong versionAtSparseIndex = versionArray[sparseIndex];
 283
 4284            if (version == versionAtSparseIndex)
 2285            {
 2286                return denseIndex;
 287            }
 288
 2289            return -1;
 4290        }
 291
 292        /// <summary>
 293        ///     Gets the value of the sparse array at the given index,
 294        ///     or -1 if the given sparse index is invalid..
 295        /// </summary>
 296        /// <param name="sparseIndex">The index in the sparse array to check against.</param>
 297        /// <param name="version">The version number associated with the sparse index.</param>
 298        /// <param name="versionArray">The array containing the version number to check against.</param>
 299        /// <returns>The dense index pointed to by the current sparse index, or -1 if invalid.</returns>
 300        public int GetDenseIndexWithBoundsAndVersionCheck(int sparseIndex, ulong version,
 301            NativeArray<ulong> versionArray)
 7302        {
 7303            if (sparseIndex >= 0 && sparseIndex < SparseArray.Length)
 5304            {
 5305                int denseIndex = SparseArray[sparseIndex];
 5306                ulong versionAtSparseIndex = versionArray[sparseIndex];
 307
 5308                if (versionAtSparseIndex == version && denseIndex < Count && denseIndex >= 0)
 2309                {
 2310                    int sparseIndexAtDenseIndex = DenseArray[denseIndex];
 311
 2312                    if (sparseIndex == sparseIndexAtDenseIndex)
 2313                    {
 2314                        return denseIndex;
 315                    }
 0316                }
 3317            }
 318
 5319            return -1;
 7320        }
 321
 322        /// <summary>
 323        ///     Removes the entry corresponding to the sparse index if the entry is within bounds and currently in use.
 324        /// </summary>
 325        /// <param name="sparseIndexToRemove">The sparse index corresponding to the entry to remove. Cleared to -1 in th
 326        /// <param name="dataIndexToSwapFrom">
 327        ///     Set the data array value at this index to default after swapping with the data array
 328        ///     value at indexToSwapTo.
 329        /// </param>
 330        /// <param name="dataIndexToSwapTo">Replace the data array value at this index with the data array value at inde
 331        /// <returns>True if the index reference was valid, and thus removed.</returns>
 332        public bool RemoveWithBoundsCheck(ref int sparseIndexToRemove, out int dataIndexToSwapFrom, out int dataIndexToS
 4333        {
 4334            dataIndexToSwapFrom = -1;
 4335            dataIndexToSwapTo = -1;
 4336            bool didRemove = false;
 4337            if (sparseIndexToRemove >= 0 && sparseIndexToRemove < SparseArray.Length)
 2338            {
 2339                int denseIndexToRemove = SparseArray[sparseIndexToRemove];
 340
 2341                if (denseIndexToRemove >= 0 && denseIndexToRemove < Count)
 1342                {
 1343                    int sparseIndexAtDenseIndex = DenseArray[denseIndexToRemove];
 1344                    int newLength = Count - 1;
 1345                    int sparseIndexBeingSwapped = DenseArray[newLength];
 346
 1347                    if (denseIndexToRemove < Count && sparseIndexAtDenseIndex == sparseIndexToRemove)
 1348                    {
 1349                        didRemove = true;
 350                        // Swap the entry being removed with the last entry.
 1351                        SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
 1352                        DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
 353
 1354                        dataIndexToSwapFrom = newLength;
 1355                        dataIndexToSwapTo = denseIndexToRemove;
 356
 357                        // Clear the dense index, for debugging purposes
 1358                        DenseArray[newLength] = -1;
 359
 360                        // Add the sparse index to the free list.
 1361                        SparseArray[sparseIndexToRemove] = FreeIndex;
 1362                        FreeIndex = sparseIndexToRemove;
 363
 1364                        Count = newLength;
 1365                    }
 1366                }
 2367            }
 368
 4369            sparseIndexToRemove = -1;
 370
 4371            return didRemove;
 4372        }
 373
 374        /// <summary>
 375        ///     Removes the associated sparse/dense index pair from active use.
 376        ///     calls.
 377        /// </summary>
 378        /// <param name="sparseIndexToRemove">The sparse index to remove.</param>
 379        /// <param name="version">
 380        ///     The version number of the int used to access the sparse index. Used to guard against accessing
 381        ///     indices that have been removed and reused.
 382        /// </param>
 383        /// <param name="versionArray">The array containing the version number to check against.</param>
 384        /// <param name="indexToSwapFrom">
 385        ///     Set the data array value at this index to default after swapping with the data array
 386        ///     value at indexToSwapTo.
 387        /// </param>
 388        /// <param name="indexToSwapTo">Replace the data array value at this index with the data array value at indexToS
 389        /// <returns>True if the element was successfully removed.</returns>
 390        public bool RemoveWithBoundsAndVersionChecks(ref int sparseIndexToRemove, ulong version,
 391            NativeArray<ulong> versionArray, out int indexToSwapFrom, out int indexToSwapTo)
 6392        {
 6393            indexToSwapFrom = -1;
 6394            indexToSwapTo = -1;
 6395            bool didRemove = false;
 6396            if (sparseIndexToRemove >= 0 && sparseIndexToRemove < SparseArray.Length)
 3397            {
 3398                ulong sparseIndexVersion = versionArray[sparseIndexToRemove];
 3399                int denseIndexToRemove = SparseArray[sparseIndexToRemove];
 400
 3401                if (sparseIndexVersion == version && denseIndexToRemove >= 0 && denseIndexToRemove < Count)
 2402                {
 2403                    int sparseIndexAtDenseIndex = DenseArray[denseIndexToRemove];
 2404                    int newLength = Count - 1;
 2405                    int sparseIndexBeingSwapped = DenseArray[newLength];
 406
 2407                    if (denseIndexToRemove < Count && sparseIndexAtDenseIndex == sparseIndexToRemove)
 2408                    {
 2409                        didRemove = true;
 2410                        versionArray[sparseIndexToRemove] = sparseIndexVersion + 1;
 411                        // Swap the entry being removed with the last entry.
 2412                        SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
 2413                        DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
 414
 2415                        indexToSwapFrom = newLength;
 2416                        indexToSwapTo = denseIndexToRemove;
 417
 418                        // Clear the dense index, for debugging purposes
 2419                        DenseArray[newLength] = -1;
 420
 421                        // Add the sparse index to the free list.
 2422                        SparseArray[sparseIndexToRemove] = FreeIndex;
 2423                        FreeIndex = sparseIndexToRemove;
 424
 2425                        Count = newLength;
 2426                    }
 2427                }
 3428            }
 429
 6430            sparseIndexToRemove = -1;
 431
 6432            return didRemove;
 6433        }
 434
 435        /// <summary>
 436        ///     Removes the associated sparse/dense index pair from active use.
 437        /// </summary>
 438        /// <param name="sparseIndexToRemove">The sparse index to remove.</param>
 439        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 440        public void RemoveUnchecked(int sparseIndexToRemove)
 1441        {
 1442            int denseIndexToRemove = SparseArray[sparseIndexToRemove];
 1443            int newLength = Count - 1;
 1444            int sparseIndexBeingSwapped = DenseArray[newLength];
 445
 446            // Swap the entry being removed with the last entry.
 1447            SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
 1448            DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
 449
 450            // Clear the dense  index, for debugging purposes
 1451            DenseArray[newLength] = -1;
 452
 453            // Add the sparse index to the free list.
 1454            SparseArray[sparseIndexToRemove] = FreeIndex;
 1455            FreeIndex = sparseIndexToRemove;
 456
 1457            Count = newLength;
 1458        }
 459
 460        /// <summary>
 461        ///     Removes the associated sparse/dense index pair from active use and increments the version.
 462        /// </summary>
 463        /// <param name="sparseIndexToRemove">The sparse index to remove.</param>
 464        /// <param name="versionArray">Enables detection of use-after-free errors when using sparse indices as reference
 465        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 466        public void RemoveUnchecked(int sparseIndexToRemove, NativeArray<ulong> versionArray)
 1467        {
 1468            int denseIndexToRemove = SparseArray[sparseIndexToRemove];
 1469            int newLength = Count - 1;
 1470            int sparseIndexBeingSwapped = DenseArray[newLength];
 471
 472            // Swap the entry being removed with the last entry.
 1473            SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
 1474            DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
 475
 476            // Clear the dense  index, for debugging purposes
 1477            DenseArray[newLength] = -1;
 478
 479            // Add the sparse index to the free list.
 1480            SparseArray[sparseIndexToRemove] = FreeIndex;
 1481            versionArray[sparseIndexToRemove] += 1;
 1482            FreeIndex = sparseIndexToRemove;
 483
 1484            Count = newLength;
 1485        }
 486
 487        /// <summary>
 488        ///     Removes the associated sparse/dense index pair from active use.
 489        ///     Out parameters used to manage parallel data arrays.
 490        /// </summary>
 491        /// <param name="sparseIndexToRemove">The sparse index to remove.</param>
 492        /// <param name="indexToSwapTo">Replace the data array value at this index with the data array value at indexToS
 493        /// <param name="indexToSwapFrom">
 494        ///     Set the data array value at this index to default after swapping with the data array
 495        ///     value at indexToSwapTo.
 496        /// </param>
 497        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 498        public void RemoveUnchecked(int sparseIndexToRemove, out int indexToSwapFrom, out int indexToSwapTo)
 1499        {
 1500            int denseIndexToRemove = SparseArray[sparseIndexToRemove];
 1501            int newLength = Count - 1;
 1502            int sparseIndexBeingSwapped = DenseArray[newLength];
 503
 504            // Swap the entry being removed with the last entry.
 1505            SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
 1506            DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
 507
 508            // Clear the dense  index, for debugging purposes
 1509            DenseArray[newLength] = -1;
 510
 511            // Add the sparse index to the free list.
 1512            SparseArray[sparseIndexToRemove] = FreeIndex;
 1513            FreeIndex = sparseIndexToRemove;
 514
 1515            Count = newLength;
 516
 1517            indexToSwapTo = denseIndexToRemove;
 1518            indexToSwapFrom = newLength;
 1519        }
 520
 521        /// <summary>
 522        ///     Removes the associated sparse/dense index pair from active use and increments the version.
 523        ///     Out parameters used to manage parallel data arrays.
 524        /// </summary>
 525        /// <param name="sparseIndexToRemove">The sparse index to remove.</param>
 526        /// <param name="versionArray">Enables detection of use-after-free errors when using sparse indices as reference
 527        /// <param name="indexToSwapTo">Replace the data array value at this index with the data array value at indexToS
 528        /// <param name="indexToSwapFrom">
 529        ///     Set the data array value at this index to default after swapping with the data array
 530        ///     value at indexToSwapTo.
 531        /// </param>
 532        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 533        public void RemoveUnchecked(int sparseIndexToRemove, NativeArray<ulong> versionArray, out int indexToSwapFrom, o
 2534        {
 2535            int denseIndexToRemove = SparseArray[sparseIndexToRemove];
 2536            int newLength = Count - 1;
 2537            int sparseIndexBeingSwapped = DenseArray[newLength];
 538
 539            // Swap the entry being removed with the last entry.
 2540            SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
 2541            DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
 542
 543            // Clear the dense  index, for debugging purposes
 2544            DenseArray[newLength] = -1;
 545
 546            // Add the sparse index to the free list.
 2547            SparseArray[sparseIndexToRemove] = FreeIndex;
 2548            versionArray[sparseIndexToRemove] += 1;
 2549            FreeIndex = sparseIndexToRemove;
 550
 2551            Count = newLength;
 552
 2553            indexToSwapTo = denseIndexToRemove;
 2554            indexToSwapFrom = newLength;
 2555        }
 556
 557        /// <summary>
 558        ///     Removes the associated sparse/dense index pair from active use.
 559        /// </summary>
 560        /// <param name="denseIndexToRemove">The dense index associated with the sparse index to remove.</param>
 561        public void RemoveUncheckedFromDenseIndex(int denseIndexToRemove)
 1562        {
 1563            int sparseIndexToRemove = DenseArray[denseIndexToRemove];
 1564            int newLength = Count - 1;
 1565            int sparseIndexBeingSwapped = DenseArray[newLength];
 566
 567            // Swap the entry being removed with the last entry.
 1568            SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
 1569            DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
 570
 571            // Clear the dense  index, for debugging purposes
 1572            DenseArray[newLength] = -1;
 573
 574            // Add the sparse index to the free list.
 1575            SparseArray[sparseIndexToRemove] = FreeIndex;
 1576            FreeIndex = sparseIndexToRemove;
 577
 1578            Count = newLength;
 1579        }
 580
 581        /// <summary>
 582        ///     Removes the associated sparse/dense index pair from active use.
 583        /// </summary>
 584        /// <param name="denseIndexToRemove">The dense index associated with the sparse index to remove.</param>
 585        /// <param name="versionArray">Enables detection of use-after-free errors when using sparse indices as reference
 586        public void RemoveUncheckedFromDenseIndex(int denseIndexToRemove, NativeArray<ulong> versionArray)
 1587        {
 1588            int sparseIndexToRemove = DenseArray[denseIndexToRemove];
 1589            int newLength = Count - 1;
 1590            int sparseIndexBeingSwapped = DenseArray[newLength];
 591
 592            // Swap the entry being removed with the last entry.
 1593            SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
 1594            DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
 595
 596            // Clear the dense  index, for debugging purposes
 1597            DenseArray[newLength] = -1;
 598
 599            // Add the sparse index to the free list.
 1600            SparseArray[sparseIndexToRemove] = FreeIndex;
 1601            versionArray[sparseIndexToRemove] += 1;
 1602            FreeIndex = sparseIndexToRemove;
 603
 1604            Count = newLength;
 1605        }
 606
 607        /// <summary>
 608        ///     Removes the associated sparse/dense index pair from active use.
 609        ///     Out parameter used to manage parallel data arrays.
 610        /// </summary>
 611        /// <param name="denseIndexToRemove">The sparse index to remove.</param>
 612        /// <param name="indexToSwapFrom">
 613        ///     Set the data array value at this index to default after swapping with the data array
 614        ///     value at denseIndexToRemove.
 615        /// </param>
 616        public void RemoveUncheckedFromDenseIndex(int denseIndexToRemove, out int indexToSwapFrom)
 1617        {
 1618            int sparseIndexToRemove = DenseArray[denseIndexToRemove];
 1619            int newLength = Count - 1;
 1620            int sparseIndexBeingSwapped = DenseArray[newLength];
 621
 622            // Swap the entry being removed with the last entry.
 1623            SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
 1624            DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
 625
 626            // Clear the dense  index, for debugging purposes
 1627            DenseArray[newLength] = -1;
 628
 629            // Add the sparse index to the free list.
 1630            SparseArray[sparseIndexToRemove] = FreeIndex;
 1631            FreeIndex = sparseIndexToRemove;
 632
 1633            Count = newLength;
 634
 1635            indexToSwapFrom = newLength;
 1636        }
 637
 638        /// <summary>
 639        ///     Removes the associated sparse/dense index pair from active use.
 640        ///     Out parameter used to manage parallel data arrays.
 641        /// </summary>
 642        /// <param name="denseIndexToRemove">The sparse index to remove.</param>
 643        /// <param name="versionArray">Enables detection of use-after-free errors when using sparse indices as reference
 644        /// <param name="indexToSwapFrom">
 645        ///     Set the data array value at this index to default after swapping with the data array
 646        ///     value at denseIndexToRemove.
 647        /// </param>
 648        public void RemoveUncheckedFromDenseIndex(int denseIndexToRemove, NativeArray<ulong> versionArray, out int index
 1649        {
 1650            int sparseIndexToRemove = DenseArray[denseIndexToRemove];
 1651            int newLength = Count - 1;
 1652            int sparseIndexBeingSwapped = DenseArray[newLength];
 653
 654            // Swap the entry being removed with the last entry.
 1655            SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
 1656            DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
 657
 658            // Clear the dense  index, for debugging purposes
 1659            DenseArray[newLength] = -1;
 660
 661            // Add the sparse index to the free list.
 1662            SparseArray[sparseIndexToRemove] = FreeIndex;
 1663            versionArray[sparseIndexToRemove] += 1;
 1664            FreeIndex = sparseIndexToRemove;
 665
 1666            Count = newLength;
 667
 1668            indexToSwapFrom = newLength;
 1669        }
 670
 671        /// <summary>
 672        ///     Attempts to remove the associated sparse/dense index pair from active use and increments the version if 
 673        ///     Out parameters used to manage parallel data arrays.
 674        /// </summary>
 675        /// <param name="sparseIndexToRemove">The sparse index to remove.</param>
 676        /// <param name="version">
 677        ///     The version number of the int used to access the sparse index. Used to guard against accessing
 678        ///     indices that have been removed and reused.
 679        /// </param>
 680        /// <param name="versionArray">The array containing the version number to check against.</param>
 681        /// <param name="indexToSwapTo">Replace the data array value at this index with the data array value at indexToS
 682        /// <param name="indexToSwapFrom">
 683        ///     Set the data array value at this index to default after swapping with the data array
 684        ///     value at indexToSwapTo.
 685        /// </param>
 686        /// <returns>True if the entry was valid and thus removed.</returns>
 687        public bool RemoveWithVersionCheck(int sparseIndexToRemove, ulong version, NativeArray<ulong> versionArray,
 688            out int indexToSwapFrom, out int indexToSwapTo)
 2689        {
 2690            int denseIndexToRemove = SparseArray[sparseIndexToRemove];
 2691            ulong versionAtSparseIndex = versionArray[sparseIndexToRemove];
 692
 2693            indexToSwapFrom = -1;
 2694            indexToSwapTo = -1;
 695
 2696            bool succeeded = versionAtSparseIndex == version;
 697
 2698            if (succeeded)
 1699            {
 1700                int newLength = Count - 1;
 1701                int sparseIndexBeingSwapped = DenseArray[newLength];
 702
 703                // Swap the entry being removed with the last entry.
 1704                SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
 1705                DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
 706
 707                // Clear the dense  index, for debugging purposes
 1708                DenseArray[newLength] = -1;
 709
 710                // Add the sparse index to the free list.
 1711                SparseArray[sparseIndexToRemove] = FreeIndex;
 1712                versionArray[sparseIndexToRemove] += 1;
 1713                FreeIndex = sparseIndexToRemove;
 714
 1715                Count = newLength;
 716
 1717                indexToSwapTo = denseIndexToRemove;
 1718                indexToSwapFrom = newLength;
 1719            }
 720
 2721            return succeeded;
 2722        }
 723
 724        /// <summary>
 725        ///     Clear the dense and sparse arrays.
 726        /// </summary>
 727        public void Clear()
 1728        {
 1729            int capacity = SparseArray.Length;
 8730            for (int i = 0; i < capacity; i++)
 3731            {
 3732                DenseArray[i] = -1;
 3733                SparseArray[i] = i + 1;
 3734            }
 735
 1736            FreeIndex = 0;
 1737            Count = 0;
 1738        }
 739
 740        /// <summary>
 741        ///     Clear the dense and sparse arrays.
 742        /// </summary>
 743        /// <param name="versionArray">Enables detection of use-after-free errors when using sparse indices as reference
 744        public void Clear(NativeArray<ulong> versionArray)
 1745        {
 1746            int capacity = SparseArray.Length;
 8747            for (int i = 0; i < capacity; i++)
 3748            {
 3749                DenseArray[i] = -1;
 3750                SparseArray[i] = i + 1;
 3751                versionArray[i] += 1;
 3752            }
 753
 1754            FreeIndex = 0;
 1755            Count = 0;
 1756        }
 757
 758        /// <summary>
 759        ///     Clear the dense and sparse arrays and reset the version array.
 760        ///     Note: Only clear the version array if you are sure there are no outstanding dependencies on version numb
 761        /// </summary>
 762        /// ///
 763        /// <param name="versionArray">Enables detection of use-after-free errors when using sparse indices as reference
 764        public void ClearWithVersionArrayReset(NativeArray<ulong> versionArray)
 1765        {
 1766            int capacity = SparseArray.Length;
 8767            for (int i = 0; i < capacity; i++)
 3768            {
 3769                DenseArray[i] = -1;
 3770                SparseArray[i] = i + 1;
 3771                versionArray[i] = 1;
 3772            }
 773
 1774            FreeIndex = 0;
 1775            Count = 0;
 1776        }
 777
 778        /// <summary>
 779        ///     Reallocate the dense and sparse arrays with additional capacity.
 780        /// </summary>
 781        /// <param name="extraCapacity">How many indices to expand the dense and sparse arrays by.</param>
 782        /// <param name="allocator">The <see cref="Unity.Collections.Allocator" /> type to use.</param>
 783        public void Expand(int extraCapacity, Allocator allocator)
 1784        {
 1785            int currentCapacity = SparseArray.Length;
 1786            int newCapacity = currentCapacity + extraCapacity;
 787
 1788            NativeArray<int> newSparseArray = new NativeArray<int>(newCapacity, allocator, NativeArrayOptions.Uninitiali
 1789            NativeSlice<int> newSparseArraySlice = new NativeSlice<int>(newSparseArray, 0, currentCapacity);
 1790            newSparseArraySlice.CopyFrom(SparseArray);
 1791            SparseArray.Dispose();
 1792            SparseArray = newSparseArray;
 793
 1794            NativeArray<int> newDenseArray = new NativeArray<int>(newCapacity, allocator, NativeArrayOptions.Uninitializ
 1795            NativeSlice<int> newDenseArraySlice = new NativeSlice<int>(newDenseArray, 0, currentCapacity);
 1796            newDenseArraySlice.CopyFrom(DenseArray);
 1797            DenseArray.Dispose();
 1798            DenseArray = newDenseArray;
 799
 8800            for (int i = currentCapacity; i < newCapacity; i++)
 3801            {
 3802                DenseArray[i] = -1; // Set new dense indices as unclaimed.
 3803                SparseArray[i] = i + 1; // Build the free list chain.
 3804            }
 1805        }
 806
 807        /// <summary>
 808        ///     Reallocate the dense and sparse arrays with additional capacity.
 809        /// </summary>
 810        /// <param name="extraCapacity">How many indices to expand the dense and sparse arrays by.</param>
 811        /// <param name="allocator">Which Unity memory allocator to use with the backing array.</param>
 812        /// <param name="versionArray">Enables detection of use-after-free errors when using sparse indices as reference
 813        public void Expand(int extraCapacity, Allocator allocator, ref NativeArray<ulong> versionArray)
 1814        {
 1815            int currentCapacity = SparseArray.Length;
 1816            int newCapacity = currentCapacity + extraCapacity;
 817
 1818            NativeArray<int> newSparseArray = new NativeArray<int>(newCapacity, allocator, NativeArrayOptions.Uninitiali
 1819            NativeSlice<int> newSparseArraySlice = new NativeSlice<int>(newSparseArray, 0, currentCapacity);
 1820            newSparseArraySlice.CopyFrom(SparseArray);
 1821            SparseArray.Dispose();
 1822            SparseArray = newSparseArray;
 823
 1824            NativeArray<int> newDenseArray = new NativeArray<int>(newCapacity, allocator, NativeArrayOptions.Uninitializ
 1825            NativeSlice<int> newDenseArraySlice = new NativeSlice<int>(newDenseArray, 0, currentCapacity);
 1826            newDenseArraySlice.CopyFrom(DenseArray);
 1827            DenseArray.Dispose();
 1828            DenseArray = newDenseArray;
 829
 1830            NativeArray<ulong> newVersionArray = new NativeArray<ulong>(newCapacity, allocator, NativeArrayOptions.Unini
 1831            NativeSlice<ulong> newVersionArraySlice = new NativeSlice<ulong>(newVersionArray, 0, currentCapacity);
 1832            newVersionArraySlice.CopyFrom(versionArray);
 1833            versionArray.Dispose();
 1834            versionArray = newVersionArray;
 835
 8836            for (int i = currentCapacity; i < newCapacity; i++)
 3837            {
 3838                DenseArray[i] = -1; // Set new dense indices as unclaimed.
 3839                SparseArray[i] = i + 1; // Build the free list chain.
 3840                versionArray[i] = 1;
 3841            }
 1842        }
 843
 844        /// <summary>
 845        /// Reallocate the dense and sparse arrays with additional capacity if there are not at least <paramref name="nu
 846        /// </summary>
 847        /// <param name="numberToReserve">The number of unused entries to ensure capacity for.</param>
 848        /// <param name="allocator">The allocator to use on expansion.</param>
 849        public void Reserve(int numberToReserve, Allocator allocator)
 1850        {
 1851            int currentCapacity = SparseArray.Length;
 1852            int currentCount = Count;
 1853            int newCapacity = currentCount + numberToReserve;
 854
 1855            if (newCapacity > currentCapacity)
 1856            {
 1857                NativeArray<int> newSparseArray = new NativeArray<int>(newCapacity, allocator, NativeArrayOptions.Uninit
 1858                NativeSlice<int> newSparseArraySlice = new NativeSlice<int>(newSparseArray, 0, currentCapacity);
 1859                newSparseArraySlice.CopyFrom(SparseArray);
 1860                SparseArray.Dispose();
 1861                SparseArray = newSparseArray;
 862
 1863                NativeArray<int> newDenseArray = new NativeArray<int>(newCapacity, allocator, NativeArrayOptions.Uniniti
 1864                NativeSlice<int> newDenseArraySlice = new NativeSlice<int>(newDenseArray, 0, currentCapacity);
 1865                newDenseArraySlice.CopyFrom(DenseArray);
 1866                DenseArray.Dispose();
 1867                DenseArray = newDenseArray;
 868
 4869                for (int i = currentCapacity; i < newCapacity; i++)
 1870                {
 1871                    DenseArray[i] = -1; // Set new dense indices as unclaimed.
 1872                    SparseArray[i] = i + 1; // Build the free list chain.
 1873                }
 1874            }
 1875        }
 876
 877        /// <summary>
 878        /// Reallocate the dense and sparse arrays with additional capacity if there are not at least <paramref name="nu
 879        /// </summary>
 880        /// <param name="numberToReserve">The number of unused entries to ensure capacity for.</param>
 881        /// <param name="allocator">The allocator to use on expansion.</param>
 882        /// <param name="versionArray">Enables detection of use-after-free errors when using sparse indices as reference
 883        public void Reserve(int numberToReserve, Allocator allocator, ref NativeArray<ulong> versionArray)
 1884        {
 1885            int currentCapacity = SparseArray.Length;
 1886            int currentCount = Count;
 1887            int newCapacity = currentCount + numberToReserve;
 888
 1889            if (newCapacity > currentCapacity)
 1890            {
 1891                NativeArray<int> newSparseArray = new NativeArray<int>(newCapacity, allocator, NativeArrayOptions.Uninit
 1892                NativeSlice<int> newSparseArraySlice = new NativeSlice<int>(newSparseArray, 0, currentCapacity);
 1893                newSparseArraySlice.CopyFrom(SparseArray);
 1894                SparseArray.Dispose();
 1895                SparseArray = newSparseArray;
 896
 1897                NativeArray<int> newDenseArray = new NativeArray<int>(newCapacity, allocator, NativeArrayOptions.Uniniti
 1898                NativeSlice<int> newDenseArraySlice = new NativeSlice<int>(newDenseArray, 0, currentCapacity);
 1899                newDenseArraySlice.CopyFrom(DenseArray);
 1900                DenseArray.Dispose();
 1901                DenseArray = newDenseArray;
 902
 1903                NativeArray<ulong> newVersionArray = new NativeArray<ulong>(newCapacity, allocator, NativeArrayOptions.U
 1904                NativeSlice<ulong> newVersionArraySlice = new NativeSlice<ulong>(newVersionArray, 0, currentCapacity);
 1905                newVersionArraySlice.CopyFrom(versionArray);
 1906                versionArray.Dispose();
 1907                versionArray = newVersionArray;
 908
 4909                for (int i = currentCapacity; i < newCapacity; i++)
 1910                {
 1911                    DenseArray[i] = -1; // Set new dense indices as unclaimed.
 1912                    SparseArray[i] = i + 1; // Build the free list chain.
 1913                    versionArray[i] = 1;
 1914                }
 1915            }
 1916        }
 917
 918        public void Dispose()
 1919        {
 1920            if (SparseArray.IsCreated)
 1921                SparseArray.Dispose();
 1922            SparseArray = default;
 1923            if (DenseArray.IsCreated)
 1924                DenseArray.Dispose();
 1925            DenseArray = default;
 1926            Count = 0;
 1927            FreeIndex = 0;
 928
 1929        }
 930    }
 931}

Methods/Properties

NativeArraySparseSet(System.Int32, Unity.Collections.Allocator)
NativeArraySparseSet(System.Int32, Unity.Collections.Allocator, Unity.Collections.NativeArray`1[[System.UInt64, mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089]]&)
AddWithExpandCheck(System.Int32, System.Int32&, System.Int32&, Unity.Collections.Allocator)
AddWithExpandCheck(System.Int32, System.Int32&, System.Int32&, Unity.Collections.Allocator, Unity.Collections.NativeArray`1[[System.UInt64, mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089]]&)
AddUnchecked(System.Int32&, System.Int32&)
AddUnchecked(System.Int32&, System.Int32&, Unity.Collections.NativeArray[UInt64], System.UInt64&)
GetDenseIndexUnchecked(System.Int32)
GetDenseIndexWithBoundsCheck(System.Int32)
GetDenseIndexWithVersionCheck(System.Int32, System.UInt64, Unity.Collections.NativeArray[UInt64])
GetDenseIndexWithBoundsAndVersionCheck(System.Int32, System.UInt64, Unity.Collections.NativeArray[UInt64])
RemoveWithBoundsCheck(System.Int32&, System.Int32&, System.Int32&)
RemoveWithBoundsAndVersionChecks(System.Int32&, System.UInt64, Unity.Collections.NativeArray[UInt64], System.Int32&, System.Int32&)
RemoveUnchecked(System.Int32)
RemoveUnchecked(System.Int32, Unity.Collections.NativeArray[UInt64])
RemoveUnchecked(System.Int32, System.Int32&, System.Int32&)
RemoveUnchecked(System.Int32, Unity.Collections.NativeArray[UInt64], System.Int32&, System.Int32&)
RemoveUncheckedFromDenseIndex(System.Int32)
RemoveUncheckedFromDenseIndex(System.Int32, Unity.Collections.NativeArray[UInt64])
RemoveUncheckedFromDenseIndex(System.Int32, System.Int32&)
RemoveUncheckedFromDenseIndex(System.Int32, Unity.Collections.NativeArray[UInt64], System.Int32&)
RemoveWithVersionCheck(System.Int32, System.UInt64, Unity.Collections.NativeArray[UInt64], System.Int32&, System.Int32&)
Clear()
Clear(Unity.Collections.NativeArray[UInt64])
ClearWithVersionArrayReset(Unity.Collections.NativeArray[UInt64])
Expand(System.Int32, Unity.Collections.Allocator)
Expand(System.Int32, Unity.Collections.Allocator, Unity.Collections.NativeArray`1[[System.UInt64, mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089]]&)
Reserve(System.Int32, Unity.Collections.Allocator)
Reserve(System.Int32, Unity.Collections.Allocator, Unity.Collections.NativeArray`1[[System.UInt64, mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089]]&)
Dispose()