< Summary

Class:	GDX.Collections.NativeArraySparseSet
Assembly:	GDX
File(s):	./Packages/com.dotbunny.gdx/GDX/Collections/NativeArraySparseSet.cs
Covered lines:	477
Uncovered lines:	2
Coverable lines:	479
Total lines:	965
Line coverage:	99.5% (477 of 479)
Covered branches:	0
Total branches:	0
Covered methods:	29
Total methods:	29
Method coverage:	100% (29 of 29)

Coverage History

Metrics

Method	Branch coverage	Crap Score	Cyclomatic complexity	NPath complexity	Sequence coverage
NativeArraySparseSet(...)	0%	2	2	0	100%
NativeArraySparseSet(...)	0%	2	2	0	100%
AddWithExpandCheck(...)	0%	3	3	0	100%
AddWithExpandCheck(...)	0%	3	3	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%	2	2	0	100%
Expand(...)	0%	2	2	0	100%
Reserve(...)	0%	3	3	0	100%
Reserve(...)	0%	3	3	0	100%
Dispose()	0%	3	3	0	100%

File(s)

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

	#	Line		Line coverage
		1		// Copyright (c) 2020-2024 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
		5		using System;
		6		using System.Runtime.CompilerServices;
		7		using Unity.Collections;
		8
		9		namespace GDX.Collections
		10		{
		11		/// <summary>
		12		///     An adapter collection for external data arrays that allows constant-time insertion, deletion, and lookup by
		13		///     handle, as well as array-like iteration.
		14		/// </summary>
		15		public struct NativeArraySparseSet : IDisposable
		16		{
		17		/// <summary>
		18		///     Holds references to the sparse array for swapping indices.
		19		/// </summary>
		20		public NativeArray<int> DenseArray;
		21
		22		/// <summary>
		23		///     Holds references to dense array indices.
		24		/// </summary>
		25		/// <remarks>
		26		///     Its own indices are claimed and freed via a free-list.
		27		/// </remarks>
		28		public NativeArray<int> SparseArray;
		29
		30		/// <summary>
		31		///     How many indices are being used currently?
		32		/// </summary>
		33		public int Count;
		34
		35		/// <summary>
		36		///     The first free (currently unused) index in the sparse array.
		37		/// </summary>
		38		public int FreeIndex;
		39
		40		/// <summary>
		41		///     Create a <see cref="NativeArraySparseSet" /> with an <paramref name="initialCapacity" />.
		42		/// </summary>
		43		/// <param name="initialCapacity">The initial capacity of the sparse and dense int arrays.</param>
		44		/// <param name="allocator">The <see cref="Unity.Collections.Allocator" /> type to use.</param>
		45		public NativeArraySparseSet(int initialCapacity, Allocator allocator)
	14	46		{
	14	47		DenseArray = new NativeArray<int>(initialCapacity, allocator, NativeArrayOptions.UninitializedMemory);
	14	48		SparseArray = new NativeArray<int>(initialCapacity, allocator, NativeArrayOptions.UninitializedMemory);
	14	49		Count = 0;
	14	50		FreeIndex = 0;
		51
	100	52		for (int i = 0; i < initialCapacity; i++)
	36	53		{
	36	54		DenseArray[i] = -1;
	36	55		SparseArray[i] = i + 1;
	36	56		}
	14	57		}
		58
		59		/// <summary>
		60		///     Create a <see cref="NativeArraySparseSet" /> with an <paramref name="initialCapacity" />.
		61		/// </summary>
		62		/// <param name="initialCapacity">The initial capacity of the sparse and dense int arrays.</param>
		63		/// <param name="allocator">The <see cref="Unity.Collections.Allocator" /> type to use.</param>
		64		/// <param name="versionArray">Enables detection of use-after-free errors when using sparse indices as reference
		65		public NativeArraySparseSet(int initialCapacity, Allocator allocator, out NativeArray<ulong> versionArray)
	17	66		{
	17	67		DenseArray = new NativeArray<int>(initialCapacity, allocator, NativeArrayOptions.UninitializedMemory);
	17	68		SparseArray = new NativeArray<int>(initialCapacity, allocator, NativeArrayOptions.UninitializedMemory);
	17	69		versionArray = new NativeArray<ulong>(initialCapacity, allocator, NativeArrayOptions.UninitializedMemory);
	17	70		Count = 0;
	17	71		FreeIndex = 0;
		72
	124	73		for (int i = 0; i < initialCapacity; i++)
	45	74		{
	45	75		DenseArray[i] = -1;
	45	76		SparseArray[i] = i + 1;
	45	77		versionArray[i] = 1;
	45	78		}
	17	79		}
		80
		81		/// <summary>
		82		///     Adds a sparse/dense index pair to the set and expands the arrays if necessary.
		83		/// </summary>
		84		/// <param name="expandBy">How many indices to expand by.</param>
		85		/// <param name="sparseIndex">The sparse index allocated.</param>
		86		/// <param name="denseIndex">The dense index allocated.</param>
		87		/// <param name="allocator">The <see cref="Unity.Collections.Allocator" /> type to use.</param>
		88		/// <returns>True if the index pool expanded.</returns>
		89		public bool AddWithExpandCheck(int expandBy, out int sparseIndex, out int denseIndex, Allocator allocator)
	4	90		{
	4	91		int indexToClaim = FreeIndex;
	4	92		int currentCapacity = SparseArray.Length;
	4	93		bool needsExpansion = false;
		94
	4	95		if (indexToClaim >= currentCapacity)
	2	96		{
		97		// We're out of space, the last free index points to nothing. Allocate more indices.
	2	98		needsExpansion = true;
		99
	2	100		int newCapacity = currentCapacity + expandBy;
		101
	2	102		NativeArray<int> newSparseArray =
		103		new NativeArray<int>(newCapacity, allocator, NativeArrayOptions.UninitializedMemory);
	2	104		NativeSlice<int> newSparseArraySlice = new NativeSlice<int>(newSparseArray, 0, currentCapacity);
	2	105		newSparseArraySlice.CopyFrom(SparseArray);
	2	106		SparseArray.Dispose();
	2	107		SparseArray = newSparseArray;
		108
	2	109		NativeArray<int> newDenseArray =
		110		new NativeArray<int>(newCapacity, allocator, NativeArrayOptions.UninitializedMemory);
	2	111		NativeSlice<int> newDenseArraySlice = new NativeSlice<int>(newDenseArray, 0, currentCapacity);
	2	112		newDenseArraySlice.CopyFrom(DenseArray);
	2	113		DenseArray.Dispose();
	2	114		DenseArray = newDenseArray;
		115
	24	116		for (int i = currentCapacity; i < newCapacity; i++)
	10	117		{
	10	118		SparseArray[i] = i + 1; // Build the free list chain.
	10	119		DenseArray[i] = -1; // Set new dense indices as unclaimed.
	10	120		}
	2	121		}
		122
	4	123		int nextFreeIndex = SparseArray[indexToClaim];
	4	124		DenseArray[Count] = indexToClaim; // Point the next dense id at our newly claimed sparse index.
	4	125		SparseArray[indexToClaim] = Count; // Point our newly claimed sparse index at the dense index.
	4	126		denseIndex = Count;
		127
	4	128		++Count;
	4	129		FreeIndex = nextFreeIndex; // Set the free list head for next time.
		130
	4	131		sparseIndex = indexToClaim;
	4	132		return needsExpansion;
	4	133		}
		134
		135		/// <summary>
		136		///     Adds a sparse/dense index pair to the set and expands the arrays if necessary.
		137		/// </summary>
		138		/// <param name="expandBy">How many indices to expand by.</param>
		139		/// <param name="sparseIndex">The sparse index allocated.</param>
		140		/// <param name="denseIndex">The dense index allocated.</param>
		141		/// <param name="allocator">The <see cref="Unity.Collections.Allocator" /> type to use.</param>
		142		/// <param name="versionArray">Enables detection of use-after-free errors when using sparse indices as reference
		143		/// <returns>True if the index pool expanded.</returns>
		144		public bool AddWithExpandCheck(int expandBy, out int sparseIndex, out int denseIndex, Allocator allocator,
		145		ref NativeArray<ulong> versionArray)
	2	146		{
	2	147		int indexToClaim = FreeIndex;
	2	148		int currentCapacity = SparseArray.Length;
	2	149		bool needsExpansion = false;
		150
	2	151		if (indexToClaim >= currentCapacity)
	1	152		{
		153		// We're out of space, the last free index points to nothing. Allocate more indices.
	1	154		needsExpansion = true;
		155
	1	156		int newCapacity = currentCapacity + expandBy;
		157
	1	158		NativeArray<int> newSparseArray =
		159		new NativeArray<int>(newCapacity, allocator, NativeArrayOptions.UninitializedMemory);
	1	160		NativeSlice<int> newSparseArraySlice = new NativeSlice<int>(newSparseArray, 0, currentCapacity);
	1	161		newSparseArraySlice.CopyFrom(SparseArray);
	1	162		SparseArray.Dispose();
	1	163		SparseArray = newSparseArray;
		164
	1	165		NativeArray<int> newDenseArray =
		166		new NativeArray<int>(newCapacity, allocator, NativeArrayOptions.UninitializedMemory);
	1	167		NativeSlice<int> newDenseArraySlice = new NativeSlice<int>(newDenseArray, 0, currentCapacity);
	1	168		newDenseArraySlice.CopyFrom(DenseArray);
	1	169		DenseArray.Dispose();
	1	170		DenseArray = newDenseArray;
		171
	1	172		NativeArray<ulong> newVersionArray =
		173		new NativeArray<ulong>(newCapacity, allocator, NativeArrayOptions.UninitializedMemory);
	1	174		NativeSlice<ulong> newVersionArraySlice = new NativeSlice<ulong>(newVersionArray, 0, currentCapacity);
	1	175		newVersionArraySlice.CopyFrom(versionArray);
	1	176		versionArray.Dispose();
	1	177		versionArray = newVersionArray;
		178
	12	179		for (int i = currentCapacity; i < newCapacity; i++)
	5	180		{
	5	181		SparseArray[i] = i + 1; // Build the free list chain.
	5	182		DenseArray[i] = -1; // Set new dense indices as unclaimed.
	5	183		versionArray[i] = 1;
	5	184		}
	1	185		}
		186
	2	187		int nextFreeIndex = SparseArray[indexToClaim];
	2	188		DenseArray[Count] = indexToClaim; // Point the next dense id at our newly claimed sparse index.
	2	189		SparseArray[indexToClaim] = Count; // Point our newly claimed sparse index at the dense index.
	2	190		denseIndex = Count;
		191
	2	192		++Count;
	2	193		FreeIndex = nextFreeIndex; // Set the free list head for next time.
		194
	2	195		sparseIndex = indexToClaim;
	2	196		return needsExpansion;
	2	197		}
		198
		199		/// <summary>
		200		///     Adds a sparse/dense index pair to the set without checking if the set needs to expand.
		201		/// </summary>
		202		/// <param name="sparseIndex">The sparse index allocated.</param>
		203		/// <param name="denseIndex">The dense index allocated.</param>
		204		[MethodImpl(MethodImplOptions.AggressiveInlining)]
		205		public void AddUnchecked(out int sparseIndex, out int denseIndex)
	20	206		{
	20	207		int indexToClaim = FreeIndex;
	20	208		int nextFreeIndex = SparseArray[indexToClaim];
	19	209		DenseArray[Count] = indexToClaim; // Point the next dense id at our newly claimed sparse index.
	19	210		SparseArray[indexToClaim] = Count; // Point our newly claimed sparse index at the dense index.
		211
	19	212		sparseIndex = indexToClaim;
	19	213		denseIndex = Count;
	19	214		++Count;
	19	215		FreeIndex = nextFreeIndex; // Set the free list head for next time.
	19	216		}
		217
		218		/// <summary>
		219		///     Adds a sparse/dense index pair to the set without checking if the set needs to expand.
		220		/// </summary>
		221		/// <param name="sparseIndex">The sparse index allocated.</param>
		222		/// <param name="denseIndex">The dense index allocated.</param>
		223		/// <param name="versionArray">The array containing the version number to check against.</param>
		224		/// <param name="version">Enables detection of use-after-free errors when using the sparse index as a reference.
		225		[MethodImpl(MethodImplOptions.AggressiveInlining)]
		226		public void AddUnchecked(out int sparseIndex, out int denseIndex, NativeArray<ulong> versionArray,
		227		out ulong version)
	24	228		{
	24	229		int indexToClaim = FreeIndex;
	24	230		int nextFreeIndex = SparseArray[indexToClaim];
	23	231		DenseArray[Count] = indexToClaim; // Point the next dense id at our newly claimed sparse index.
	23	232		SparseArray[indexToClaim] = Count; // Point our newly claimed sparse index at the dense index.
		233
	23	234		version = versionArray[indexToClaim];
	23	235		sparseIndex = indexToClaim;
	23	236		denseIndex = Count;
		237
	23	238		++Count;
	23	239		FreeIndex = nextFreeIndex; // Set the free list head for next time.
	23	240		}
		241
		242		/// <summary>
		243		///     Gets the value of the sparse array at the given index without any data validation.
		244		/// </summary>
		245		/// <param name="sparseIndex">The index to check in the sparse array.</param>
		246		/// <returns>The dense index at the given sparse index.</returns>
		247		[MethodImpl(MethodImplOptions.AggressiveInlining)]
		248		public int GetDenseIndexUnchecked(int sparseIndex)
	1	249		{
	1	250		return SparseArray[sparseIndex];
	1	251		}
		252
		253		/// <summary>
		254		///     Gets the value of the sparse array at the given index,
		255		///     or -1 if the dense and sparse indices don't point to each other or if the dense index is outside the den
		256		/// </summary>
		257		/// <param name="sparseIndex">The index in the sparse array to check against.</param>
		258		/// <returns>The dense index pointed to by the current sparse index, or -1 if invalid.</returns>
		259		public int GetDenseIndexWithBoundsCheck(int sparseIndex)
	4	260		{
	4	261		if (sparseIndex >= 0 && sparseIndex < SparseArray.Length)
	2	262		{
	2	263		int denseIndex = SparseArray[sparseIndex];
		264
	2	265		if (denseIndex < Count && denseIndex >= 0)
	1	266		{
	1	267		int sparseIndexAtDenseIndex = DenseArray[denseIndex];
		268
	1	269		if (sparseIndex == sparseIndexAtDenseIndex)
	1	270		{
	1	271		return denseIndex;
		272		}
	0	273		}
	1	274		}
		275
	3	276		return -1;
	4	277		}
		278
		279		/// <summary>
		280		///     Gets the value of the sparse array at the given index,
		281		///     or -1 if the version number does not match.
		282		/// </summary>
		283		/// <param name="sparseIndex">The index in the sparse array to check against.</param>
		284		/// <param name="version">The version number associated with the sparse index.</param>
		285		/// <param name="versionArray">The array containing the version number to check against.</param>
		286		/// <returns>The dense index pointed to by the current sparse index, or -1 if invalid.</returns>
		287		public int GetDenseIndexWithVersionCheck(int sparseIndex, ulong version, NativeArray<ulong> versionArray)
	4	288		{
	4	289		int denseIndex = SparseArray[sparseIndex];
	4	290		ulong versionAtSparseIndex = versionArray[sparseIndex];
		291
	4	292		if (version == versionAtSparseIndex)
	2	293		{
	2	294		return denseIndex;
		295		}
		296
	2	297		return -1;
	4	298		}
		299
		300		/// <summary>
		301		///     Gets the value of the sparse array at the given index,
		302		///     or -1 if the given sparse index is invalid..
		303		/// </summary>
		304		/// <param name="sparseIndex">The index in the sparse array to check against.</param>
		305		/// <param name="version">The version number associated with the sparse index.</param>
		306		/// <param name="versionArray">The array containing the version number to check against.</param>
		307		/// <returns>The dense index pointed to by the current sparse index, or -1 if invalid.</returns>
		308		public int GetDenseIndexWithBoundsAndVersionCheck(int sparseIndex, ulong version,
		309		NativeArray<ulong> versionArray)
	7	310		{
	7	311		if (sparseIndex >= 0 && sparseIndex < SparseArray.Length)
	5	312		{
	5	313		int denseIndex = SparseArray[sparseIndex];
	5	314		ulong versionAtSparseIndex = versionArray[sparseIndex];
		315
	5	316		if (versionAtSparseIndex == version && denseIndex < Count && denseIndex >= 0)
	2	317		{
	2	318		int sparseIndexAtDenseIndex = DenseArray[denseIndex];
		319
	2	320		if (sparseIndex == sparseIndexAtDenseIndex)
	2	321		{
	2	322		return denseIndex;
		323		}
	0	324		}
	3	325		}
		326
	5	327		return -1;
	7	328		}
		329
		330		/// <summary>
		331		///     Removes the entry corresponding to the sparse index if the entry is within bounds and currently in use.
		332		/// </summary>
		333		/// <param name="sparseIndexToRemove">
		334		///     The sparse index corresponding to the entry to remove. Cleared to -1 in this
		335		///     operation.
		336		/// </param>
		337		/// <param name="dataIndexToSwapFrom">
		338		///     Set the data array value at this index to default after swapping with the data array
		339		///     value at indexToSwapTo.
		340		/// </param>
		341		/// <param name="dataIndexToSwapTo">
		342		///     Replace the data array value at this index with the data array value at
		343		///     indexToSwapFrom.
		344		/// </param>
		345		/// <returns>True if the index reference was valid, and thus removed.</returns>
		346		public bool RemoveWithBoundsCheck(ref int sparseIndexToRemove, out int dataIndexToSwapFrom,
		347		out int dataIndexToSwapTo)
	4	348		{
	4	349		dataIndexToSwapFrom = -1;
	4	350		dataIndexToSwapTo = -1;
	4	351		bool didRemove = false;
	4	352		if (sparseIndexToRemove >= 0 && sparseIndexToRemove < SparseArray.Length)
	2	353		{
	2	354		int denseIndexToRemove = SparseArray[sparseIndexToRemove];
		355
	2	356		if (denseIndexToRemove >= 0 && denseIndexToRemove < Count)
	1	357		{
	1	358		int sparseIndexAtDenseIndex = DenseArray[denseIndexToRemove];
	1	359		int newLength = Count - 1;
	1	360		int sparseIndexBeingSwapped = DenseArray[newLength];
		361
	1	362		if (denseIndexToRemove < Count && sparseIndexAtDenseIndex == sparseIndexToRemove)
	1	363		{
	1	364		didRemove = true;
		365		// Swap the entry being removed with the last entry.
	1	366		SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
	1	367		DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
		368
	1	369		dataIndexToSwapFrom = newLength;
	1	370		dataIndexToSwapTo = denseIndexToRemove;
		371
		372		// Clear the dense index, for debugging purposes
	1	373		DenseArray[newLength] = -1;
		374
		375		// Add the sparse index to the free list.
	1	376		SparseArray[sparseIndexToRemove] = FreeIndex;
	1	377		FreeIndex = sparseIndexToRemove;
		378
	1	379		Count = newLength;
	1	380		}
	1	381		}
	2	382		}
		383
	4	384		sparseIndexToRemove = -1;
		385
	4	386		return didRemove;
	4	387		}
		388
		389		/// <summary>
		390		///     Removes the associated sparse/dense index pair from active use.
		391		///     calls.
		392		/// </summary>
		393		/// <param name="sparseIndexToRemove">The sparse index to remove.</param>
		394		/// <param name="version">
		395		///     The version number of the int used to access the sparse index. Used to guard against accessing
		396		///     indices that have been removed and reused.
		397		/// </param>
		398		/// <param name="versionArray">The array containing the version number to check against.</param>
		399		/// <param name="indexToSwapFrom">
		400		///     Set the data array value at this index to default after swapping with the data array
		401		///     value at indexToSwapTo.
		402		/// </param>
		403		/// <param name="indexToSwapTo">Replace the data array value at this index with the data array value at indexToS
		404		/// <returns>True if the element was successfully removed.</returns>
		405		public bool RemoveWithBoundsAndVersionChecks(ref int sparseIndexToRemove, ulong version,
		406		NativeArray<ulong> versionArray, out int indexToSwapFrom, out int indexToSwapTo)
	6	407		{
	6	408		indexToSwapFrom = -1;
	6	409		indexToSwapTo = -1;
	6	410		bool didRemove = false;
	6	411		if (sparseIndexToRemove >= 0 && sparseIndexToRemove < SparseArray.Length)
	3	412		{
	3	413		ulong sparseIndexVersion = versionArray[sparseIndexToRemove];
	3	414		int denseIndexToRemove = SparseArray[sparseIndexToRemove];
		415
	3	416		if (sparseIndexVersion == version && denseIndexToRemove >= 0 && denseIndexToRemove < Count)
	2	417		{
	2	418		int sparseIndexAtDenseIndex = DenseArray[denseIndexToRemove];
	2	419		int newLength = Count - 1;
	2	420		int sparseIndexBeingSwapped = DenseArray[newLength];
		421
	2	422		if (denseIndexToRemove < Count && sparseIndexAtDenseIndex == sparseIndexToRemove)
	2	423		{
	2	424		didRemove = true;
	2	425		versionArray[sparseIndexToRemove] = sparseIndexVersion + 1;
		426		// Swap the entry being removed with the last entry.
	2	427		SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
	2	428		DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
		429
	2	430		indexToSwapFrom = newLength;
	2	431		indexToSwapTo = denseIndexToRemove;
		432
		433		// Clear the dense index, for debugging purposes
	2	434		DenseArray[newLength] = -1;
		435
		436		// Add the sparse index to the free list.
	2	437		SparseArray[sparseIndexToRemove] = FreeIndex;
	2	438		FreeIndex = sparseIndexToRemove;
		439
	2	440		Count = newLength;
	2	441		}
	2	442		}
	3	443		}
		444
	6	445		sparseIndexToRemove = -1;
		446
	6	447		return didRemove;
	6	448		}
		449
		450		/// <summary>
		451		///     Removes the associated sparse/dense index pair from active use.
		452		/// </summary>
		453		/// <param name="sparseIndexToRemove">The sparse index to remove.</param>
		454		[MethodImpl(MethodImplOptions.AggressiveInlining)]
		455		public void RemoveUnchecked(int sparseIndexToRemove)
	1	456		{
	1	457		int denseIndexToRemove = SparseArray[sparseIndexToRemove];
	1	458		int newLength = Count - 1;
	1	459		int sparseIndexBeingSwapped = DenseArray[newLength];
		460
		461		// Swap the entry being removed with the last entry.
	1	462		SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
	1	463		DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
		464
		465		// Clear the dense  index, for debugging purposes
	1	466		DenseArray[newLength] = -1;
		467
		468		// Add the sparse index to the free list.
	1	469		SparseArray[sparseIndexToRemove] = FreeIndex;
	1	470		FreeIndex = sparseIndexToRemove;
		471
	1	472		Count = newLength;
	1	473		}
		474
		475		/// <summary>
		476		///     Removes the associated sparse/dense index pair from active use and increments the version.
		477		/// </summary>
		478		/// <param name="sparseIndexToRemove">The sparse index to remove.</param>
		479		/// <param name="versionArray">Enables detection of use-after-free errors when using sparse indices as reference
		480		[MethodImpl(MethodImplOptions.AggressiveInlining)]
		481		public void RemoveUnchecked(int sparseIndexToRemove, NativeArray<ulong> versionArray)
	1	482		{
	1	483		int denseIndexToRemove = SparseArray[sparseIndexToRemove];
	1	484		int newLength = Count - 1;
	1	485		int sparseIndexBeingSwapped = DenseArray[newLength];
		486
		487		// Swap the entry being removed with the last entry.
	1	488		SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
	1	489		DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
		490
		491		// Clear the dense  index, for debugging purposes
	1	492		DenseArray[newLength] = -1;
		493
		494		// Add the sparse index to the free list.
	1	495		SparseArray[sparseIndexToRemove] = FreeIndex;
	1	496		versionArray[sparseIndexToRemove] += 1;
	1	497		FreeIndex = sparseIndexToRemove;
		498
	1	499		Count = newLength;
	1	500		}
		501
		502		/// <summary>
		503		///     Removes the associated sparse/dense index pair from active use.
		504		///     Out parameters used to manage parallel data arrays.
		505		/// </summary>
		506		/// <param name="sparseIndexToRemove">The sparse index to remove.</param>
		507		/// <param name="indexToSwapTo">Replace the data array value at this index with the data array value at indexToS
		508		/// <param name="indexToSwapFrom">
		509		///     Set the data array value at this index to default after swapping with the data array
		510		///     value at indexToSwapTo.
		511		/// </param>
		512		[MethodImpl(MethodImplOptions.AggressiveInlining)]
		513		public void RemoveUnchecked(int sparseIndexToRemove, out int indexToSwapFrom, out int indexToSwapTo)
	1	514		{
	1	515		int denseIndexToRemove = SparseArray[sparseIndexToRemove];
	1	516		int newLength = Count - 1;
	1	517		int sparseIndexBeingSwapped = DenseArray[newLength];
		518
		519		// Swap the entry being removed with the last entry.
	1	520		SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
	1	521		DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
		522
		523		// Clear the dense  index, for debugging purposes
	1	524		DenseArray[newLength] = -1;
		525
		526		// Add the sparse index to the free list.
	1	527		SparseArray[sparseIndexToRemove] = FreeIndex;
	1	528		FreeIndex = sparseIndexToRemove;
		529
	1	530		Count = newLength;
		531
	1	532		indexToSwapTo = denseIndexToRemove;
	1	533		indexToSwapFrom = newLength;
	1	534		}
		535
		536		/// <summary>
		537		///     Removes the associated sparse/dense index pair from active use and increments the version.
		538		///     Out parameters used to manage parallel data arrays.
		539		/// </summary>
		540		/// <param name="sparseIndexToRemove">The sparse index to remove.</param>
		541		/// <param name="versionArray">Enables detection of use-after-free errors when using sparse indices as reference
		542		/// <param name="indexToSwapTo">Replace the data array value at this index with the data array value at indexToS
		543		/// <param name="indexToSwapFrom">
		544		///     Set the data array value at this index to default after swapping with the data array
		545		///     value at indexToSwapTo.
		546		/// </param>
		547		[MethodImpl(MethodImplOptions.AggressiveInlining)]
		548		public void RemoveUnchecked(int sparseIndexToRemove, NativeArray<ulong> versionArray, out int indexToSwapFrom,
		549		out int indexToSwapTo)
	2	550		{
	2	551		int denseIndexToRemove = SparseArray[sparseIndexToRemove];
	2	552		int newLength = Count - 1;
	2	553		int sparseIndexBeingSwapped = DenseArray[newLength];
		554
		555		// Swap the entry being removed with the last entry.
	2	556		SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
	2	557		DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
		558
		559		// Clear the dense  index, for debugging purposes
	2	560		DenseArray[newLength] = -1;
		561
		562		// Add the sparse index to the free list.
	2	563		SparseArray[sparseIndexToRemove] = FreeIndex;
	2	564		versionArray[sparseIndexToRemove] += 1;
	2	565		FreeIndex = sparseIndexToRemove;
		566
	2	567		Count = newLength;
		568
	2	569		indexToSwapTo = denseIndexToRemove;
	2	570		indexToSwapFrom = newLength;
	2	571		}
		572
		573		/// <summary>
		574		///     Removes the associated sparse/dense index pair from active use.
		575		/// </summary>
		576		/// <param name="denseIndexToRemove">The dense index associated with the sparse index to remove.</param>
		577		public void RemoveUncheckedFromDenseIndex(int denseIndexToRemove)
	1	578		{
	1	579		int sparseIndexToRemove = DenseArray[denseIndexToRemove];
	1	580		int newLength = Count - 1;
	1	581		int sparseIndexBeingSwapped = DenseArray[newLength];
		582
		583		// Swap the entry being removed with the last entry.
	1	584		SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
	1	585		DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
		586
		587		// Clear the dense  index, for debugging purposes
	1	588		DenseArray[newLength] = -1;
		589
		590		// Add the sparse index to the free list.
	1	591		SparseArray[sparseIndexToRemove] = FreeIndex;
	1	592		FreeIndex = sparseIndexToRemove;
		593
	1	594		Count = newLength;
	1	595		}
		596
		597		/// <summary>
		598		///     Removes the associated sparse/dense index pair from active use.
		599		/// </summary>
		600		/// <param name="denseIndexToRemove">The dense index associated with the sparse index to remove.</param>
		601		/// <param name="versionArray">Enables detection of use-after-free errors when using sparse indices as reference
		602		public void RemoveUncheckedFromDenseIndex(int denseIndexToRemove, NativeArray<ulong> versionArray)
	1	603		{
	1	604		int sparseIndexToRemove = DenseArray[denseIndexToRemove];
	1	605		int newLength = Count - 1;
	1	606		int sparseIndexBeingSwapped = DenseArray[newLength];
		607
		608		// Swap the entry being removed with the last entry.
	1	609		SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
	1	610		DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
		611
		612		// Clear the dense  index, for debugging purposes
	1	613		DenseArray[newLength] = -1;
		614
		615		// Add the sparse index to the free list.
	1	616		SparseArray[sparseIndexToRemove] = FreeIndex;
	1	617		versionArray[sparseIndexToRemove] += 1;
	1	618		FreeIndex = sparseIndexToRemove;
		619
	1	620		Count = newLength;
	1	621		}
		622
		623		/// <summary>
		624		///     Removes the associated sparse/dense index pair from active use.
		625		///     Out parameter used to manage parallel data arrays.
		626		/// </summary>
		627		/// <param name="denseIndexToRemove">The sparse index to remove.</param>
		628		/// <param name="indexToSwapFrom">
		629		///     Set the data array value at this index to default after swapping with the data array
		630		///     value at denseIndexToRemove.
		631		/// </param>
		632		public void RemoveUncheckedFromDenseIndex(int denseIndexToRemove, out int indexToSwapFrom)
	1	633		{
	1	634		int sparseIndexToRemove = DenseArray[denseIndexToRemove];
	1	635		int newLength = Count - 1;
	1	636		int sparseIndexBeingSwapped = DenseArray[newLength];
		637
		638		// Swap the entry being removed with the last entry.
	1	639		SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
	1	640		DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
		641
		642		// Clear the dense  index, for debugging purposes
	1	643		DenseArray[newLength] = -1;
		644
		645		// Add the sparse index to the free list.
	1	646		SparseArray[sparseIndexToRemove] = FreeIndex;
	1	647		FreeIndex = sparseIndexToRemove;
		648
	1	649		Count = newLength;
		650
	1	651		indexToSwapFrom = newLength;
	1	652		}
		653
		654		/// <summary>
		655		///     Removes the associated sparse/dense index pair from active use.
		656		///     Out parameter used to manage parallel data arrays.
		657		/// </summary>
		658		/// <param name="denseIndexToRemove">The sparse index to remove.</param>
		659		/// <param name="versionArray">Enables detection of use-after-free errors when using sparse indices as reference
		660		/// <param name="indexToSwapFrom">
		661		///     Set the data array value at this index to default after swapping with the data array
		662		///     value at denseIndexToRemove.
		663		/// </param>
		664		public void RemoveUncheckedFromDenseIndex(int denseIndexToRemove, NativeArray<ulong> versionArray,
		665		out int indexToSwapFrom)
	1	666		{
	1	667		int sparseIndexToRemove = DenseArray[denseIndexToRemove];
	1	668		int newLength = Count - 1;
	1	669		int sparseIndexBeingSwapped = DenseArray[newLength];
		670
		671		// Swap the entry being removed with the last entry.
	1	672		SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
	1	673		DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
		674
		675		// Clear the dense  index, for debugging purposes
	1	676		DenseArray[newLength] = -1;
		677
		678		// Add the sparse index to the free list.
	1	679		SparseArray[sparseIndexToRemove] = FreeIndex;
	1	680		versionArray[sparseIndexToRemove] += 1;
	1	681		FreeIndex = sparseIndexToRemove;
		682
	1	683		Count = newLength;
		684
	1	685		indexToSwapFrom = newLength;
	1	686		}
		687
		688		/// <summary>
		689		///     Attempts to remove the associated sparse/dense index pair from active use and increments the version if
		690		///     Out parameters used to manage parallel data arrays.
		691		/// </summary>
		692		/// <param name="sparseIndexToRemove">The sparse index to remove.</param>
		693		/// <param name="version">
		694		///     The version number of the int used to access the sparse index. Used to guard against accessing
		695		///     indices that have been removed and reused.
		696		/// </param>
		697		/// <param name="versionArray">The array containing the version number to check against.</param>
		698		/// <param name="indexToSwapTo">Replace the data array value at this index with the data array value at indexToS
		699		/// <param name="indexToSwapFrom">
		700		///     Set the data array value at this index to default after swapping with the data array
		701		///     value at indexToSwapTo.
		702		/// </param>
		703		/// <returns>True if the entry was valid and thus removed.</returns>
		704		public bool RemoveWithVersionCheck(int sparseIndexToRemove, ulong version, NativeArray<ulong> versionArray,
		705		out int indexToSwapFrom, out int indexToSwapTo)
	2	706		{
	2	707		int denseIndexToRemove = SparseArray[sparseIndexToRemove];
	2	708		ulong versionAtSparseIndex = versionArray[sparseIndexToRemove];
		709
	2	710		indexToSwapFrom = -1;
	2	711		indexToSwapTo = -1;
		712
	2	713		bool succeeded = versionAtSparseIndex == version;
		714
	2	715		if (succeeded)
	1	716		{
	1	717		int newLength = Count - 1;
	1	718		int sparseIndexBeingSwapped = DenseArray[newLength];
		719
		720		// Swap the entry being removed with the last entry.
	1	721		SparseArray[sparseIndexBeingSwapped] = denseIndexToRemove;
	1	722		DenseArray[denseIndexToRemove] = sparseIndexBeingSwapped;
		723
		724		// Clear the dense  index, for debugging purposes
	1	725		DenseArray[newLength] = -1;
		726
		727		// Add the sparse index to the free list.
	1	728		SparseArray[sparseIndexToRemove] = FreeIndex;
	1	729		versionArray[sparseIndexToRemove] += 1;
	1	730		FreeIndex = sparseIndexToRemove;
		731
	1	732		Count = newLength;
		733
	1	734		indexToSwapTo = denseIndexToRemove;
	1	735		indexToSwapFrom = newLength;
	1	736		}
		737
	2	738		return succeeded;
	2	739		}
		740
		741		/// <summary>
		742		///     Clear the dense and sparse arrays.
		743		/// </summary>
		744		public void Clear()
	1	745		{
	1	746		int capacity = SparseArray.Length;
	8	747		for (int i = 0; i < capacity; i++)
	3	748		{
	3	749		DenseArray[i] = -1;
	3	750		SparseArray[i] = i + 1;
	3	751		}
		752
	1	753		FreeIndex = 0;
	1	754		Count = 0;
	1	755		}
		756
		757		/// <summary>
		758		///     Clear the dense and sparse arrays.
		759		/// </summary>
		760		/// <param name="versionArray">Enables detection of use-after-free errors when using sparse indices as reference
		761		public void Clear(NativeArray<ulong> versionArray)
	1	762		{
	1	763		int capacity = SparseArray.Length;
	8	764		for (int i = 0; i < capacity; i++)
	3	765		{
	3	766		DenseArray[i] = -1;
	3	767		SparseArray[i] = i + 1;
	3	768		versionArray[i] += 1;
	3	769		}
		770
	1	771		FreeIndex = 0;
	1	772		Count = 0;
	1	773		}
		774
		775		/// <summary>
		776		///     Clear the dense and sparse arrays and reset the version array.
		777		///     Note: Only clear the version array if you are sure there are no outstanding dependencies on version numb
		778		/// </summary>
		779		/// ///
		780		/// <param name="versionArray">Enables detection of use-after-free errors when using sparse indices as reference
		781		public void ClearWithVersionArrayReset(NativeArray<ulong> versionArray)
	1	782		{
	1	783		int capacity = SparseArray.Length;
	8	784		for (int i = 0; i < capacity; i++)
	3	785		{
	3	786		DenseArray[i] = -1;
	3	787		SparseArray[i] = i + 1;
	3	788		versionArray[i] = 1;
	3	789		}
		790
	1	791		FreeIndex = 0;
	1	792		Count = 0;
	1	793		}
		794
		795		/// <summary>
		796		///     Reallocate the dense and sparse arrays with additional capacity.
		797		/// </summary>
		798		/// <param name="extraCapacity">How many indices to expand the dense and sparse arrays by.</param>
		799		/// <param name="allocator">The <see cref="Unity.Collections.Allocator" /> type to use.</param>
		800		public void Expand(int extraCapacity, Allocator allocator)
	1	801		{
	1	802		int currentCapacity = SparseArray.Length;
	1	803		int newCapacity = currentCapacity + extraCapacity;
		804
	1	805		NativeArray<int> newSparseArray =
		806		new NativeArray<int>(newCapacity, allocator, NativeArrayOptions.UninitializedMemory);
	1	807		NativeSlice<int> newSparseArraySlice = new NativeSlice<int>(newSparseArray, 0, currentCapacity);
	1	808		newSparseArraySlice.CopyFrom(SparseArray);
	1	809		SparseArray.Dispose();
	1	810		SparseArray = newSparseArray;
		811
	1	812		NativeArray<int> newDenseArray =
		813		new NativeArray<int>(newCapacity, allocator, NativeArrayOptions.UninitializedMemory);
	1	814		NativeSlice<int> newDenseArraySlice = new NativeSlice<int>(newDenseArray, 0, currentCapacity);
	1	815		newDenseArraySlice.CopyFrom(DenseArray);
	1	816		DenseArray.Dispose();
	1	817		DenseArray = newDenseArray;
		818
	8	819		for (int i = currentCapacity; i < newCapacity; i++)
	3	820		{
	3	821		DenseArray[i] = -1; // Set new dense indices as unclaimed.
	3	822		SparseArray[i] = i + 1; // Build the free list chain.
	3	823		}
	1	824		}
		825
		826		/// <summary>
		827		///     Reallocate the dense and sparse arrays with additional capacity.
		828		/// </summary>
		829		/// <param name="extraCapacity">How many indices to expand the dense and sparse arrays by.</param>
		830		/// <param name="allocator">Which Unity memory allocator to use with the backing array.</param>
		831		/// <param name="versionArray">Enables detection of use-after-free errors when using sparse indices as reference
		832		public void Expand(int extraCapacity, Allocator allocator, ref NativeArray<ulong> versionArray)
	1	833		{
	1	834		int currentCapacity = SparseArray.Length;
	1	835		int newCapacity = currentCapacity + extraCapacity;
		836
	1	837		NativeArray<int> newSparseArray =
		838		new NativeArray<int>(newCapacity, allocator, NativeArrayOptions.UninitializedMemory);
	1	839		NativeSlice<int> newSparseArraySlice = new NativeSlice<int>(newSparseArray, 0, currentCapacity);
	1	840		newSparseArraySlice.CopyFrom(SparseArray);
	1	841		SparseArray.Dispose();
	1	842		SparseArray = newSparseArray;
		843
	1	844		NativeArray<int> newDenseArray =
		845		new NativeArray<int>(newCapacity, allocator, NativeArrayOptions.UninitializedMemory);
	1	846		NativeSlice<int> newDenseArraySlice = new NativeSlice<int>(newDenseArray, 0, currentCapacity);
	1	847		newDenseArraySlice.CopyFrom(DenseArray);
	1	848		DenseArray.Dispose();
	1	849		DenseArray = newDenseArray;
		850
	1	851		NativeArray<ulong> newVersionArray =
		852		new NativeArray<ulong>(newCapacity, allocator, NativeArrayOptions.UninitializedMemory);
	1	853		NativeSlice<ulong> newVersionArraySlice = new NativeSlice<ulong>(newVersionArray, 0, currentCapacity);
	1	854		newVersionArraySlice.CopyFrom(versionArray);
	1	855		versionArray.Dispose();
	1	856		versionArray = newVersionArray;
		857
	8	858		for (int i = currentCapacity; i < newCapacity; i++)
	3	859		{
	3	860		DenseArray[i] = -1; // Set new dense indices as unclaimed.
	3	861		SparseArray[i] = i + 1; // Build the free list chain.
	3	862		versionArray[i] = 1;
	3	863		}
	1	864		}
		865
		866		/// <summary>
		867		///     Reallocate the dense and sparse arrays with additional capacity if there are not at least
		868		///     <paramref name="numberToReserve" /> unused entries.
		869		/// </summary>
		870		/// <param name="numberToReserve">The number of unused entries to ensure capacity for.</param>
		871		/// <param name="allocator">The allocator to use on expansion.</param>
		872		public void Reserve(int numberToReserve, Allocator allocator)
	1	873		{
	1	874		int currentCapacity = SparseArray.Length;
	1	875		int currentCount = Count;
	1	876		int newCapacity = currentCount + numberToReserve;
		877
	1	878		if (newCapacity > currentCapacity)
	1	879		{
	1	880		NativeArray<int> newSparseArray =
		881		new NativeArray<int>(newCapacity, allocator, NativeArrayOptions.UninitializedMemory);
	1	882		NativeSlice<int> newSparseArraySlice = new NativeSlice<int>(newSparseArray, 0, currentCapacity);
	1	883		newSparseArraySlice.CopyFrom(SparseArray);
	1	884		SparseArray.Dispose();
	1	885		SparseArray = newSparseArray;
		886
	1	887		NativeArray<int> newDenseArray =
		888		new NativeArray<int>(newCapacity, allocator, NativeArrayOptions.UninitializedMemory);
	1	889		NativeSlice<int> newDenseArraySlice = new NativeSlice<int>(newDenseArray, 0, currentCapacity);
	1	890		newDenseArraySlice.CopyFrom(DenseArray);
	1	891		DenseArray.Dispose();
	1	892		DenseArray = newDenseArray;
		893
	4	894		for (int i = currentCapacity; i < newCapacity; i++)
	1	895		{
	1	896		DenseArray[i] = -1; // Set new dense indices as unclaimed.
	1	897		SparseArray[i] = i + 1; // Build the free list chain.
	1	898		}
	1	899		}
	1	900		}
		901
		902		/// <summary>
		903		///     Reallocate the dense and sparse arrays with additional capacity if there are not at least
		904		///     <paramref name="numberToReserve" /> unused entries.
		905		/// </summary>
		906		/// <param name="numberToReserve">The number of unused entries to ensure capacity for.</param>
		907		/// <param name="allocator">The allocator to use on expansion.</param>
		908		/// <param name="versionArray">Enables detection of use-after-free errors when using sparse indices as reference
		909		public void Reserve(int numberToReserve, Allocator allocator, ref NativeArray<ulong> versionArray)
	1	910		{
	1	911		int currentCapacity = SparseArray.Length;
	1	912		int currentCount = Count;
	1	913		int newCapacity = currentCount + numberToReserve;
		914
	1	915		if (newCapacity > currentCapacity)
	1	916		{
	1	917		NativeArray<int> newSparseArray =
		918		new NativeArray<int>(newCapacity, allocator, NativeArrayOptions.UninitializedMemory);
	1	919		NativeSlice<int> newSparseArraySlice = new NativeSlice<int>(newSparseArray, 0, currentCapacity);
	1	920		newSparseArraySlice.CopyFrom(SparseArray);
	1	921		SparseArray.Dispose();
	1	922		SparseArray = newSparseArray;
		923
	1	924		NativeArray<int> newDenseArray =
		925		new NativeArray<int>(newCapacity, allocator, NativeArrayOptions.UninitializedMemory);
	1	926		NativeSlice<int> newDenseArraySlice = new NativeSlice<int>(newDenseArray, 0, currentCapacity);
	1	927		newDenseArraySlice.CopyFrom(DenseArray);
	1	928		DenseArray.Dispose();
	1	929		DenseArray = newDenseArray;
		930
	1	931		NativeArray<ulong> newVersionArray =
		932		new NativeArray<ulong>(newCapacity, allocator, NativeArrayOptions.UninitializedMemory);
	1	933		NativeSlice<ulong> newVersionArraySlice = new NativeSlice<ulong>(newVersionArray, 0, currentCapacity);
	1	934		newVersionArraySlice.CopyFrom(versionArray);
	1	935		versionArray.Dispose();
	1	936		versionArray = newVersionArray;
		937
	4	938		for (int i = currentCapacity; i < newCapacity; i++)
	1	939		{
	1	940		DenseArray[i] = -1; // Set new dense indices as unclaimed.
	1	941		SparseArray[i] = i + 1; // Build the free list chain.
	1	942		versionArray[i] = 1;
	1	943		}
	1	944		}
	1	945		}
		946
		947		public void Dispose()
	1	948		{
	1	949		if (SparseArray.IsCreated)
	1	950		{
	1	951		SparseArray.Dispose();
	1	952		}
		953
	1	954		SparseArray = default;
	1	955		if (DenseArray.IsCreated)
	1	956		{
	1	957		DenseArray.Dispose();
	1	958		}
		959
	1	960		DenseArray = default;
	1	961		Count = 0;
	1	962		FreeIndex = 0;
	1	963		}
		964		}
		965		}