< 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

Method	Branch coverage	Crap Score	Cyclomatic complexity	NPath complexity	Sequence coverage
UnsafeSparseSet(...)	0%	4	4	0	100%
UnsafeSparseSet(...)	0%	4	4	0	100%
AddWithExpandCheck(...)	0%	6	6	0	100%
AddWithExpandCheck(...)	0%	7	7	0	100%
AddUnchecked(...)	0%	1	1	0	100%
AddUnchecked(...)	0%	1	1	0	100%
GetDenseIndexUnchecked(...)	0%	1	1	0	100%
GetDenseIndexWithBoundsCheck(...)	0%	6.01	6	0	92.86%
GetDenseIndexWithVersionCheck(...)	0%	2	2	0	100%
GetDenseIndexWithBoundsAndVersionCheck(...)	0%	7.01	7	0	93.33%
RemoveWithBoundsCheck(...)	0%	7	7	0	100%
RemoveWithBoundsAndVersionChecks(...)	0%	8	8	0	100%
RemoveUnchecked(...)	0%	1	1	0	100%
RemoveUnchecked(...)	0%	1	1	0	100%
RemoveUnchecked(...)	0%	1	1	0	100%
RemoveUnchecked(...)	0%	1	1	0	100%
RemoveUncheckedFromDenseIndex(...)	0%	1	1	0	100%
RemoveUncheckedFromDenseIndex(...)	0%	1	1	0	100%
RemoveUncheckedFromDenseIndex(...)	0%	1	1	0	100%
RemoveUncheckedFromDenseIndex(...)	0%	1	1	0	100%
RemoveWithVersionCheck(...)	0%	2	2	0	100%
Clear()	0%	2	2	0	100%
Clear(...)	0%	2	2	0	100%
ClearWithVersionArrayReset(...)	0%	2	2	0	100%
Expand(...)	0%	5	5	0	100%
Expand(...)	0%	6	6	0	100%
Reserve(...)	0%	6	6	0	100%
Reserve(...)	0%	7	7	0	100%
Dispose()	0%	2	2	0	100%
Dispose(...)	0%	6	2	0	0%
Dispose(...)	0%	6	2	0	0%
DisposeVersionArray(...)	0%	1	1	0	100%
DisposeVersionArray(...)	0%	6	2	0	0%

File(s)

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

	#	Line		Line 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
		6		using System.Runtime.CompilerServices;
		7		using Unity.Collections;
		8		using Unity.Collections.LowLevel.Unsafe;
		9		using Unity.Jobs;
		10		using Unity.Jobs.LowLevel.Unsafe;
		11		using System.Diagnostics;
		12		using System.Runtime.InteropServices;
		13		using Unity.Burst;
		14
		15		namespace 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)]
	398	37		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)]
	460	49		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>
	0	73		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>
	0	79		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)
	14	87		{
	14	88		initialCapacity = initialCapacity > MinimumCapacity ? initialCapacity : MinimumCapacity;
	14	89		--initialCapacity;
	14	90		initialCapacity |= initialCapacity >> 1;
	14	91		initialCapacity |= initialCapacity >> 2;
	14	92		initialCapacity |= initialCapacity >> 4;
	14	93		initialCapacity |= initialCapacity >> 8;
	14	94		initialCapacity |= initialCapacity >> 16;
	14	95		++initialCapacity;
		96
	14	97		Data = allocator.Allocate(sizeof(int), JobsUtility.CacheLineSize, initialCapacity * 2);
	14	98		Count = 0;
	14	99		FreeIndex = 0;
	14	100		Length = initialCapacity;
	14	101		Allocator = allocator;
		102
	252	103		for (int i = 0; i < initialCapacity; i++)
	112	104		{
	112	105		DenseArray[i] = -1;
	112	106		SparseArray[i] = i + 1;
	112	107		}
	14	108		}
		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)
	16	117		{
	16	118		initialCapacity = initialCapacity > MinimumCapacity ? initialCapacity : MinimumCapacity;
	16	119		--initialCapacity;
	16	120		initialCapacity |= initialCapacity >> 1;
	16	121		initialCapacity |= initialCapacity >> 2;
	16	122		initialCapacity |= initialCapacity >> 4;
	16	123		initialCapacity |= initialCapacity >> 8;
	16	124		initialCapacity |= initialCapacity >> 16;
	16	125		++initialCapacity;
		126
	16	127		Data = allocator.Allocate(sizeof(int), JobsUtility.CacheLineSize, initialCapacity * 2);
	16	128		Count = 0;
	16	129		FreeIndex = 0;
	16	130		Length = initialCapacity;
	16	131		Allocator = allocator;
	16	132		versionArray = (ulong*)allocator.Allocate(sizeof(ulong), JobsUtility.CacheLineSize, initialCapacity);
		133
	288	134		for (int i = 0; i < initialCapacity; i++)
	128	135		{
	128	136		DenseArray[i] = -1;
	128	137		SparseArray[i] = i + 1;
	128	138		versionArray[i] = 1;
	128	139		}
	16	140		}
		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)
	18	150		{
	18	151		int indexToClaim = FreeIndex;
	18	152		int currentCapacity = Length;
	18	153		bool needsExpansion = false;
		154
	18	155		if (indexToClaim >= currentCapacity)
	2	156		{
		157		// We're out of space, the last free index points to nothing. Allocate more indices.
	2	158		needsExpansion = true;
		159
	2	160		int newCapacity = currentCapacity + expandBy;
		161
	2	162		newCapacity = newCapacity > MinimumCapacity ? newCapacity : MinimumCapacity;
	2	163		--newCapacity;
	2	164		newCapacity |= newCapacity >> 1;
	2	165		newCapacity |= newCapacity >> 2;
	2	166		newCapacity |= newCapacity >> 4;
	2	167		newCapacity |= newCapacity >> 8;
	2	168		newCapacity |= newCapacity >> 16;
	2	169		++newCapacity;
		170
	2	171		void* newData = Allocator.Allocate(sizeof(int), JobsUtility.CacheLineSize, newCapacity * 2);
		172
	2	173		UnsafeUtility.MemCpy(newData, Data, sizeof(int) * currentCapacity);
	2	174		int* newSparseArray = (int*)newData;
	36	175		for (int i = currentCapacity; i < newCapacity; i++)
	16	176		{
	16	177		newSparseArray[i] = i + 1;
	16	178		}
		179
	2	180		int* newDenseArray = newSparseArray + newCapacity;
	2	181		UnsafeUtility.MemCpy(newDenseArray, DenseArray, sizeof(int) * currentCapacity);
	36	182		for (int i = currentCapacity; i < newCapacity; i++)
	16	183		{
	16	184		newDenseArray[i] = -1;
	16	185		}
		186
	2	187		Allocator.Free(Data, sizeof(int), JobsUtility.CacheLineSize, currentCapacity * 2);
		188
	2	189		Data = newData;
	2	190		Length = newCapacity;
	2	191		}
		192
	18	193		int nextFreeIndex = SparseArray[indexToClaim];
	18	194		DenseArray[Count] = indexToClaim; // Point the next dense id at our newly claimed sparse index.
	18	195		SparseArray[indexToClaim] = Count; // Point our newly claimed sparse index at the dense index.
	18	196		denseIndex = Count;
		197
	18	198		++Count;
	18	199		FreeIndex = nextFreeIndex; // Set the free list head for next time.
		200
	18	201		sparseIndex = indexToClaim;
	18	202		return needsExpansion;
	18	203		}
		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)
	9	214		{
	9	215		int indexToClaim = FreeIndex;
	9	216		int currentCapacity = Length;
	9	217		bool needsExpansion = false;
		218
	9	219		if (indexToClaim >= currentCapacity)
	1	220		{
		221		// We're out of space, the last free index points to nothing. Allocate more indices.
	1	222		needsExpansion = true;
		223
	1	224		int newCapacity = currentCapacity + expandBy;
		225
	1	226		newCapacity = newCapacity > MinimumCapacity ? newCapacity : MinimumCapacity;
	1	227		--newCapacity;
	1	228		newCapacity |= newCapacity >> 1;
	1	229		newCapacity |= newCapacity >> 2;
	1	230		newCapacity |= newCapacity >> 4;
	1	231		newCapacity |= newCapacity >> 8;
	1	232		newCapacity |= newCapacity >> 16;
	1	233		++newCapacity;
		234
	1	235		void* newData = Allocator.Allocate(sizeof(int), JobsUtility.CacheLineSize, newCapacity * 2);
		236
	1	237		UnsafeUtility.MemCpy(newData, Data, sizeof(int) * currentCapacity);
	1	238		int* newSparseArray = (int*)newData;
	18	239		for (int i = currentCapacity; i < newCapacity; i++)
	8	240		{
	8	241		newSparseArray[i] = i + 1;
	8	242		}
		243
	1	244		int* newDenseArray = newSparseArray + newCapacity;
	1	245		UnsafeUtility.MemCpy(newDenseArray, DenseArray, sizeof(int) * currentCapacity);
	18	246		for (int i = currentCapacity; i < newCapacity; i++)
	8	247		{
	8	248		newDenseArray[i] = -1;
	8	249		}
		250
	1	251		ulong* newVersionArray =
		252
	1	253		UnsafeUtility.MemCpy(newVersionArray, versionArray, sizeof(ulong) * currentCapacity);
	18	254		for (int i = currentCapacity; i < newCapacity; i++)
	8	255		{
	8	256		newVersionArray[i] = 1;
	8	257		}
		258
	1	259		Allocator.Free(Data, sizeof(int), JobsUtility.CacheLineSize, currentCapacity * 2);
	1	260		Allocator.Free(versionArray, sizeof(ulong), JobsUtility.CacheLineSize, currentCapacity);
	1	261		versionArray = newVersionArray;
		262
	1	263		Data = newData;
	1	264		Length = newCapacity;
	1	265		}
		266
	9	267		int nextFreeIndex = SparseArray[indexToClaim];
	9	268		DenseArray[Count] = indexToClaim; // Point the next dense id at our newly claimed sparse index.
	9	269		SparseArray[indexToClaim] = Count; // Point our newly claimed sparse index at the dense index.
	9	270		denseIndex = Count;
		271
	9	272		++Count;
	9	273		FreeIndex = nextFreeIndex; // Set the free list head for next time.
		274
	9	275		sparseIndex = indexToClaim;
	9	276		return needsExpansion;
	9	277		}
		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)
	18	286		{
	18	287		int indexToClaim = FreeIndex;
	18	288		int nextFreeIndex = SparseArray[indexToClaim];
	18	289		DenseArray[Count] = indexToClaim; // Point the next dense id at our newly claimed sparse index.
	18	290		SparseArray[indexToClaim] = Count; // Point our newly claimed sparse index at the dense index.
		291
	18	292		sparseIndex = indexToClaim;
	18	293		denseIndex = Count;
	18	294		++Count;
	18	295		FreeIndex = nextFreeIndex; // Set the free list head for next time.
	18	296		}
		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)
	22	307		{
	22	308		int indexToClaim = FreeIndex;
	22	309		int nextFreeIndex = SparseArray[indexToClaim];
	22	310		DenseArray[Count] = indexToClaim; // Point the next dense id at our newly claimed sparse index.
	22	311		SparseArray[indexToClaim] = Count; // Point our newly claimed sparse index at the dense index.
		312
	22	313		version = versionArray[indexToClaim];
	22	314		sparseIndex = indexToClaim;
	22	315		denseIndex = Count;
		316
	22	317		++Count;
	22	318		FreeIndex = nextFreeIndex; // Set the free list head for next time.
	22	319		}
		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)
	1	328		{
	1	329		return SparseArray[sparseIndex];
	1	330		}
		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)
	4	339		{
	4	340		if (sparseIndex >= 0 && sparseIndex < Length)
	3	341		{
	3	342		int denseIndex = SparseArray[sparseIndex];
		343
	3	344		if (denseIndex < Count && denseIndex >= 0)
	1	345		{
	1	346		int sparseIndexAtDenseIndex = DenseArray[denseIndex];
		347
	1	348		if (sparseIndex == sparseIndexAtDenseIndex)
	1	349		{
	1	350		return denseIndex;
		351		}
	0	352		}
	2	353		}
		354
	3	355		return -1;
	4	356		}
		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)
	4	367		{
	4	368		int denseIndex = SparseArray[sparseIndex];
	4	369		ulong versionAtSparseIndex = versionArray[sparseIndex];
		370
	4	371		if (version == versionAtSparseIndex)
	2	372		{
	2	373		return denseIndex;
		374		}
		375
	2	376		return -1;
	4	377		}
		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)
	7	388		{
	7	389		if (sparseIndex >= 0 && sparseIndex < Length)
	5	390		{
	5	391		int denseIndex = SparseArray[sparseIndex];
	5	392		ulong versionAtSparseIndex = versionArray[sparseIndex];
		393
	5	394		if (versionAtSparseIndex == version && denseIndex < Count && denseIndex >= 0)
	2	395		{
	2	396		int sparseIndexAtDenseIndex = DenseArray[denseIndex];
		397
	2	398		if (sparseIndex == sparseIndexAtDenseIndex)
	2	399		{
	2	400		return denseIndex;
		401		}
	0	402		}
	3	403		}
		404
	5	405		return -1;
	7	406		}
		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
	4	419		{
	4	420		dataIndexToSwapFrom = -1;
	4	421		dataIndexToSwapTo = -1;
	4	422		bool didRemove = false;
	4	423		if (sparseIndexToRemove >= 0 && sparseIndexToRemove < Length)
	2	424		{
	2	425		int denseIndexToRemove = SparseArray[sparseIndexToRemove];
		426
	2	427		if (denseIndexToRemove >= 0 && denseIndexToRemove < Count)
	1	428		{
	1	429		int sparseIndexAtDenseIndex = DenseArray[denseIndexToRemove];
	1	430		int newLength = Count - 1;
	1	431		int sparseIndexBeingSwapped = DenseArray[newLength];
		432
	1	433		if (denseIndexToRemove < Count && sparseIndexAtDenseIndex == sparseIndexToRemove)
	1	434		{
	1	435		didRemove = true;
		436		// Swap the entry being removed with the last entry.
	1	437		SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
	1	438		DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
		439
	1	440		dataIndexToSwapFrom = newLength;
	1	441		dataIndexToSwapTo = denseIndexToRemove;
		442
		443		// Clear the dense index, for debugging purposes
	1	444		DenseArray[newLength] = -1;
		445
		446		// Add the sparse index to the free list.
	1	447		SparseArray[sparseIndexToRemove] = FreeIndex;
	1	448		FreeIndex = sparseIndexToRemove;
		449
	1	450		Count = newLength;
	1	451		}
	1	452		}
	2	453		}
		454
	4	455		sparseIndexToRemove = -1;
		456
	4	457		return didRemove;
	4	458		}
		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
	6	477		{
	6	478		indexToSwapFrom = -1;
	6	479		indexToSwapTo = -1;
	6	480		bool didRemove = false;
	6	481		if (sparseIndexToRemove >= 0 && sparseIndexToRemove < Length)
	3	482		{
	3	483		ulong sparseIndexVersion = versionArray[sparseIndexToRemove];
	3	484		int denseIndexToRemove = SparseArray[sparseIndexToRemove];
		485
	3	486		if (sparseIndexVersion == version && denseIndexToRemove >= 0 && denseIndexToRemove < Count)
	2	487		{
	2	488		int sparseIndexAtDenseIndex = DenseArray[denseIndexToRemove];
	2	489		int newLength = Count - 1;
	2	490		int sparseIndexBeingSwapped = DenseArray[newLength];
		491
	2	492		if (denseIndexToRemove < Count && sparseIndexAtDenseIndex == sparseIndexToRemove)
	2	493		{
	2	494		didRemove = true;
	2	495		versionArray[sparseIndexToRemove] = sparseIndexVersion + 1;
		496		// Swap the entry being removed with the last entry.
	2	497		SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
	2	498		DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
		499
	2	500		indexToSwapFrom = newLength;
	2	501		indexToSwapTo = denseIndexToRemove;
		502
		503		// Clear the dense index, for debugging purposes
	2	504		DenseArray[newLength] = -1;
		505
		506		// Add the sparse index to the free list.
	2	507		SparseArray[sparseIndexToRemove] = FreeIndex;
	2	508		FreeIndex = sparseIndexToRemove;
		509
	2	510		Count = newLength;
	2	511		}
	2	512		}
	3	513		}
		514
	6	515		sparseIndexToRemove = -1;
		516
	6	517		return didRemove;
	6	518		}
		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)
	1	526		{
	1	527		int denseIndexToRemove = SparseArray[sparseIndexToRemove];
	1	528		int newLength = Count - 1;
	1	529		int sparseIndexBeingSwapped = DenseArray[newLength];
		530
		531		// Swap the entry being removed with the last entry.
	1	532		SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
	1	533		DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
		534
		535		// Clear the dense  index, for debugging purposes
	1	536		DenseArray[newLength] = -1;
		537
		538		// Add the sparse index to the free list.
	1	539		SparseArray[sparseIndexToRemove] = FreeIndex;
	1	540		FreeIndex = sparseIndexToRemove;
		541
	1	542		Count = newLength;
	1	543		}
		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)
	1	552		{
	1	553		int denseIndexToRemove = SparseArray[sparseIndexToRemove];
	1	554		int newLength = Count - 1;
	1	555		int sparseIndexBeingSwapped = DenseArray[newLength];
		556
		557		// Swap the entry being removed with the last entry.
	1	558		SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
	1	559		DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
		560
		561		// Clear the dense  index, for debugging purposes
	1	562		DenseArray[newLength] = -1;
		563
		564		// Add the sparse index to the free list.
	1	565		SparseArray[sparseIndexToRemove] = FreeIndex;
	1	566		versionArray[sparseIndexToRemove] += 1;
	1	567		FreeIndex = sparseIndexToRemove;
		568
	1	569		Count = newLength;
	1	570		}
		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)
	1	584		{
	1	585		int denseIndexToRemove = SparseArray[sparseIndexToRemove];
	1	586		int newLength = Count - 1;
	1	587		int sparseIndexBeingSwapped = DenseArray[newLength];
		588
		589		// Swap the entry being removed with the last entry.
	1	590		SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
	1	591		DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
		592
		593		// Clear the dense  index, for debugging purposes
	1	594		DenseArray[newLength] = -1;
		595
		596		// Add the sparse index to the free list.
	1	597		SparseArray[sparseIndexToRemove] = FreeIndex;
	1	598		FreeIndex = sparseIndexToRemove;
		599
	1	600		Count = newLength;
		601
	1	602		indexToSwapTo = denseIndexToRemove;
	1	603		indexToSwapFrom = newLength;
	1	604		}
		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
	2	619		{
	2	620		int denseIndexToRemove = SparseArray[sparseIndexToRemove];
	2	621		int newLength = Count - 1;
	2	622		int sparseIndexBeingSwapped = DenseArray[newLength];
		623
		624		// Swap the entry being removed with the last entry.
	2	625		SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
	2	626		DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
		627
		628		// Clear the dense  index, for debugging purposes
	2	629		DenseArray[newLength] = -1;
		630
		631		// Add the sparse index to the free list.
	2	632		SparseArray[sparseIndexToRemove] = FreeIndex;
	2	633		versionArray[sparseIndexToRemove] += 1;
	2	634		FreeIndex = sparseIndexToRemove;
		635
	2	636		Count = newLength;
		637
	2	638		indexToSwapTo = denseIndexToRemove;
	2	639		indexToSwapFrom = newLength;
	2	640		}
		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)
	1	647		{
	1	648		int sparseIndexToRemove = DenseArray[denseIndexToRemove];
	1	649		int newLength = Count - 1;
	1	650		int sparseIndexBeingSwapped = DenseArray[newLength];
		651
		652		// Swap the entry being removed with the last entry.
	1	653		SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
	1	654		DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
		655
		656		// Clear the dense  index, for debugging purposes
	1	657		DenseArray[newLength] = -1;
		658
		659		// Add the sparse index to the free list.
	1	660		SparseArray[sparseIndexToRemove] = FreeIndex;
	1	661		FreeIndex = sparseIndexToRemove;
		662
	1	663		Count = newLength;
	1	664		}
		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)
	1	672		{
	1	673		int sparseIndexToRemove = DenseArray[denseIndexToRemove];
	1	674		int newLength = Count - 1;
	1	675		int sparseIndexBeingSwapped = DenseArray[newLength];
		676
		677		// Swap the entry being removed with the last entry.
	1	678		SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
	1	679		DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
		680
		681		// Clear the dense  index, for debugging purposes
	1	682		DenseArray[newLength] = -1;
		683
		684		// Add the sparse index to the free list.
	1	685		SparseArray[sparseIndexToRemove] = FreeIndex;
	1	686		versionArray[sparseIndexToRemove] += 1;
	1	687		FreeIndex = sparseIndexToRemove;
		688
	1	689		Count = newLength;
	1	690		}
		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)
	1	702		{
	1	703		int sparseIndexToRemove = DenseArray[denseIndexToRemove];
	1	704		int newLength = Count - 1;
	1	705		int sparseIndexBeingSwapped = DenseArray[newLength];
		706
		707		// Swap the entry being removed with the last entry.
	1	708		SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
	1	709		DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
		710
		711		// Clear the dense  index, for debugging purposes
	1	712		DenseArray[newLength] = -1;
		713
		714		// Add the sparse index to the free list.
	1	715		SparseArray[sparseIndexToRemove] = FreeIndex;
	1	716		FreeIndex = sparseIndexToRemove;
		717
	1	718		Count = newLength;
		719
	1	720		indexToSwapFrom = newLength;
	1	721		}
		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)
	1	734		{
	1	735		int sparseIndexToRemove = DenseArray[denseIndexToRemove];
	1	736		int newLength = Count - 1;
	1	737		int sparseIndexBeingSwapped = DenseArray[newLength];
		738
		739		// Swap the entry being removed with the last entry.
	1	740		SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
	1	741		DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
		742
		743		// Clear the dense  index, for debugging purposes
	1	744		DenseArray[newLength] = -1;
		745
		746		// Add the sparse index to the free list.
	1	747		SparseArray[sparseIndexToRemove] = FreeIndex;
	1	748		versionArray[sparseIndexToRemove] += 1;
	1	749		FreeIndex = sparseIndexToRemove;
		750
	1	751		Count = newLength;
		752
	1	753		indexToSwapFrom = newLength;
	1	754		}
		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
	2	773		{
	2	774		int denseIndexToRemove = SparseArray[sparseIndexToRemove];
	2	775		ulong versionAtSparseIndex = versionArray[sparseIndexToRemove];
		776
	2	777		indexToSwapFrom = -1;
	2	778		indexToSwapTo = -1;
		779
	2	780		bool succeeded = versionAtSparseIndex == version;
		781
	2	782		if (succeeded)
	1	783		{
	1	784		int newLength = Count - 1;
	1	785		int sparseIndexBeingSwapped = DenseArray[newLength];
		786
		787		// Swap the entry being removed with the last entry.
	1	788		SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
	1	789		DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
		790
		791		// Clear the dense  index, for debugging purposes
	1	792		DenseArray[newLength] = -1;
		793
		794		// Add the sparse index to the free list.
	1	795		SparseArray[sparseIndexToRemove] = FreeIndex;
	1	796		versionArray[sparseIndexToRemove] += 1;
	1	797		FreeIndex = sparseIndexToRemove;
		798
	1	799		Count = newLength;
		800
	1	801		indexToSwapTo = denseIndexToRemove;
	1	802		indexToSwapFrom = newLength;
	1	803		}
		804
	2	805		return succeeded;
	2	806		}
		807
		808		/// <summary>
		809		///     Clear the dense and sparse arrays.
		810		/// </summary>
		811		public void Clear()
	1	812		{
	1	813		int capacity = Length;
	18	814		for (int i = 0; i < capacity; i++)
	8	815		{
	8	816		DenseArray[i] = -1;
	8	817		SparseArray[i] = i + 1;
	8	818		}
		819
	1	820		FreeIndex = 0;
	1	821		Count = 0;
	1	822		}
		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)
	1	829		{
	1	830		int capacity = Length;
	18	831		for (int i = 0; i < capacity; i++)
	8	832		{
	8	833		DenseArray[i] = -1;
	8	834		SparseArray[i] = i + 1;
	8	835		versionArray[i] += 1;
	8	836		}
		837
	1	838		FreeIndex = 0;
	1	839		Count = 0;
	1	840		}
		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)
	1	849		{
	1	850		int capacity = Length;
	18	851		for (int i = 0; i < capacity; i++)
	8	852		{
	8	853		DenseArray[i] = -1;
	8	854		SparseArray[i] = i + 1;
	8	855		versionArray[i] = 1;
	8	856		}
		857
	1	858		FreeIndex = 0;
	1	859		Count = 0;
	1	860		}
		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)
	1	867		{
	1	868		int currentCapacity = Length;
	1	869		int newCapacity = currentCapacity + extraCapacity;
		870
	1	871		newCapacity = newCapacity > MinimumCapacity ? newCapacity : MinimumCapacity;
	1	872		--newCapacity;
	1	873		newCapacity |= newCapacity >> 1;
	1	874		newCapacity |= newCapacity >> 2;
	1	875		newCapacity |= newCapacity >> 4;
	1	876		newCapacity |= newCapacity >> 8;
	1	877		newCapacity |= newCapacity >> 16;
	1	878		++newCapacity;
		879
	1	880		void* newData = Allocator.Allocate(sizeof(int), JobsUtility.CacheLineSize, newCapacity * 2);
		881
	1	882		UnsafeUtility.MemCpy(newData, Data, sizeof(int) * currentCapacity);
	1	883		int* newSparseArray = (int*)newData;
	18	884		for (int i = currentCapacity; i < newCapacity; i++)
	8	885		{
	8	886		newSparseArray[i] = i + 1;
	8	887		}
		888
	1	889		int* newDenseArray = newSparseArray + newCapacity;
	1	890		UnsafeUtility.MemCpy(newDenseArray, DenseArray, sizeof(int) * currentCapacity);
	18	891		for (int i = currentCapacity; i < newCapacity; i++)
	8	892		{
	8	893		newDenseArray[i] = -1;
	8	894		}
		895
	1	896		Allocator.Free(Data, sizeof(int), JobsUtility.CacheLineSize, currentCapacity * 2);
		897
	1	898		Data = newData;
	1	899		Length = newCapacity;
	1	900		}
		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)
	1	908		{
	1	909		int currentCapacity = Length;
	1	910		int newCapacity = currentCapacity + extraCapacity;
		911
	1	912		newCapacity = newCapacity > MinimumCapacity ? newCapacity : MinimumCapacity;
	1	913		--newCapacity;
	1	914		newCapacity |= newCapacity >> 1;
	1	915		newCapacity |= newCapacity >> 2;
	1	916		newCapacity |= newCapacity >> 4;
	1	917		newCapacity |= newCapacity >> 8;
	1	918		newCapacity |= newCapacity >> 16;
	1	919		++newCapacity;
		920
	1	921		void* newData = Allocator.Allocate(sizeof(int), JobsUtility.CacheLineSize, newCapacity * 2);
		922
	1	923		UnsafeUtility.MemCpy(newData, Data, sizeof(int) * currentCapacity);
	1	924		int* newSparseArray = (int*)newData;
	18	925		for (int i = currentCapacity; i < newCapacity; i++)
	8	926		{
	8	927		newSparseArray[i] = i + 1;
	8	928		}
		929
	1	930		int* newDenseArray = newSparseArray + newCapacity;
	1	931		UnsafeUtility.MemCpy(newDenseArray, DenseArray, sizeof(int) * currentCapacity);
	18	932		for (int i = currentCapacity; i < newCapacity; i++)
	8	933		{
	8	934		newDenseArray[i] = -1;
	8	935		}
		936
	1	937		ulong* newVersionArray =
		938
	1	939		UnsafeUtility.MemCpy(newVersionArray, versionArray, sizeof(ulong) * currentCapacity);
	18	940		for (int i = currentCapacity; i < newCapacity; i++)
	8	941		{
	8	942		newVersionArray[i] = 1;
	8	943		}
		944
	1	945		Allocator.Free(Data, sizeof(int), JobsUtility.CacheLineSize, currentCapacity * 2);
	1	946		Allocator.Free(versionArray, sizeof(ulong), JobsUtility.CacheLineSize, currentCapacity);
	1	947		versionArray = newVersionArray;
		948
	1	949		Data = newData;
	1	950		Length = newCapacity;
	1	951		}
		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)
	1	958		{
	1	959		int currentCapacity = Length;
	1	960		int currentCount = Count;
	1	961		int newCapacity = currentCount + numberToReserve;
		962
	1	963		if (newCapacity > currentCapacity)
	1	964		{
	1	965		newCapacity = newCapacity > MinimumCapacity ? newCapacity : MinimumCapacity;
	1	966		--newCapacity;
	1	967		newCapacity |= newCapacity >> 1;
	1	968		newCapacity |= newCapacity >> 2;
	1	969		newCapacity |= newCapacity >> 4;
	1	970		newCapacity |= newCapacity >> 8;
	1	971		newCapacity |= newCapacity >> 16;
	1	972		++newCapacity;
		973
	1	974		void* newData = Allocator.Allocate(sizeof(int), JobsUtility.CacheLineSize, newCapacity * 2);
		975
	1	976		UnsafeUtility.MemCpy(newData, Data, sizeof(int) * currentCapacity);
	1	977		int* newSparseArray = (int*)newData;
	18	978		for (int i = currentCapacity; i < newCapacity; i++)
	8	979		{
	8	980		newSparseArray[i] = i + 1;
	8	981		}
		982
	1	983		int* newDenseArray = newSparseArray + newCapacity;
	1	984		UnsafeUtility.MemCpy(newDenseArray, DenseArray, sizeof(int) * currentCapacity);
	18	985		for (int i = currentCapacity; i < newCapacity; i++)
	8	986		{
	8	987		newDenseArray[i] = -1;
	8	988		}
		989
	1	990		Allocator.Free(Data, sizeof(int), JobsUtility.CacheLineSize, currentCapacity * 2);
		991
	1	992		Data = newData;
	1	993		Length = newCapacity;
	1	994		}
	1	995		}
		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)
	1	1003		{
	1	1004		int currentCapacity = Length;
	1	1005		int currentCount = Count;
	1	1006		int newCapacity = currentCount + numberToReserve;
		1007
	1	1008		if (newCapacity > currentCapacity)
	1	1009		{
	1	1010		newCapacity = newCapacity > MinimumCapacity ? newCapacity : MinimumCapacity;
	1	1011		--newCapacity;
	1	1012		newCapacity |= newCapacity >> 1;
	1	1013		newCapacity |= newCapacity >> 2;
	1	1014		newCapacity |= newCapacity >> 4;
	1	1015		newCapacity |= newCapacity >> 8;
	1	1016		newCapacity |= newCapacity >> 16;
	1	1017		++newCapacity;
		1018
	1	1019		void* newData = Allocator.Allocate(sizeof(int), JobsUtility.CacheLineSize, newCapacity * 2);
		1020
	1	1021		UnsafeUtility.MemCpy(newData, Data, sizeof(int) * currentCapacity);
	1	1022		int* newSparseArray = (int*)newData;
	18	1023		for (int i = currentCapacity; i < newCapacity; i++)
	8	1024		{
	8	1025		newSparseArray[i] = i + 1;
	8	1026		}
		1027
	1	1028		int* newDenseArray = newSparseArray + newCapacity;
	1	1029		UnsafeUtility.MemCpy(newDenseArray, DenseArray, sizeof(int) * currentCapacity);
	18	1030		for (int i = currentCapacity; i < newCapacity; i++)
	8	1031		{
	8	1032		newDenseArray[i] = -1;
	8	1033		}
		1034
	1	1035		ulong* newVersionArray =
		1036
	1	1037		UnsafeUtility.MemCpy(newVersionArray, versionArray, sizeof(ulong) * currentCapacity);
	18	1038		for (int i = currentCapacity; i < newCapacity; i++)
	8	1039		{
	8	1040		newVersionArray[i] = 1;
	8	1041		}
		1042
	1	1043		Allocator.Free(Data, sizeof(int), JobsUtility.CacheLineSize, currentCapacity * 2);
	1	1044		Allocator.Free(versionArray, sizeof(ulong), JobsUtility.CacheLineSize, currentCapacity);
	1	1045		versionArray = newVersionArray;
		1046
	1	1047		Data = newData;
	1	1048		Length = newCapacity;
	1	1049		}
	1	1050		}
		1051
		1052		/// <summary>
		1053		/// Disposes the memory of this Sparse Set.
		1054		/// </summary>
		1055		public void Dispose()
	1	1056		{
	1	1057		if (Data != null)
	1	1058		{
	1	1059		Allocator.Free(Data, sizeof(int), JobsUtility.CacheLineSize, Length * 2);
	1	1060		Data = null;
	1	1061		Length = 0;
	1	1062		Count = 0;
	1	1063		FreeIndex = 0;
	1	1064		Allocator = Unity.Collections.Allocator.Invalid;
	1	1065		}
	1	1066		}
		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)
	0	1075		{
	0	1076		if (CollectionHelper.ShouldDeallocate(Allocator))
	0	1077		{
	0	1078		var jobHandle = new DisposeUnsafeSparseSetJob { Ptr = Data, Capacity = Length, Allocator =
		1079
		1080
	0	1081		Data = null;
	0	1082		Length = 0;
	0	1083		Count = 0;
	0	1084		FreeIndex = 0;
	0	1085		Allocator = Unity.Collections.Allocator.Invalid;
		1086
	0	1087		return jobHandle;
		1088		}
		1089
	0	1090		Data = null;
	0	1091		Length = 0;
	0	1092		Count = 0;
	0	1093		FreeIndex = 0;
	0	1094		Allocator = Unity.Collections.Allocator.Invalid;
		1095
	0	1096		return inputDeps;
	0	1097		}
		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)
	0	1106		{
	0	1107		if (CollectionHelper.ShouldDeallocate(Allocator))
	0	1108		{
	0	1109		var jobHandle = new DisposeUnsafeSparseSetAndVersionArrayJob { Ptr = Data, VersionArrayPtr =
		1110
		1111
	0	1112		Data = null;
	0	1113		Length = 0;
	0	1114		Count = 0;
	0	1115		FreeIndex = 0;
	0	1116		Allocator = Unity.Collections.Allocator.Invalid;
	0	1117		versionArray = null;
		1118
	0	1119		return jobHandle;
		1120		}
		1121
	0	1122		Data = null;
	0	1123		Length = 0;
	0	1124		Count = 0;
	0	1125		FreeIndex = 0;
	0	1126		Allocator = Unity.Collections.Allocator.Invalid;
	0	1127		versionArray = null;
		1128
	0	1129		return inputDeps;
	0	1130		}
		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)
	1	1137		{
	1	1138		Allocator.Free(versionArray, sizeof(ulong), JobsUtility.CacheLineSize, Length);
	1	1139		versionArray = null;
	1	1140		}
		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)
	0	1149		{
	0	1150		if (CollectionHelper.ShouldDeallocate(Allocator))
	0	1151		{
	0	1152		var jobHandle = new DisposeUnsafeVersionArrayJob { Ptr = versionArray, Capacity = Length, Allocator =
		1153
		1154
	0	1155		versionArray = null;
		1156
	0	1157		return jobHandle;
		1158		}
		1159
	0	1160		versionArray = null;
		1161
	0	1162		return inputDeps;
	0	1163		}
		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