jacksondunstan/nativecollections

Native Collection Types for Unity

nativecollections's Issues

NativeLinkedList SortingNodeMemoryAddresses() does not sort properly after inserting an intermediate node.

Hi there,

I have been trying very hard to figure out what I was doing wrong with the NativeLinkedList but I think I found a bug.

I duplicated the test SortNodeMemoryAddressesPreservesOrderButSortsMemory and create a new one like this:

[Test]
public void SortNodeMemoryAddressesPreservesOrderButSortsMemoryRemoveAndInsertIntermediateNode()
{
	using (var list = new NativeLinkedList<int>(7, Allocator.Temp))
	{
		var e00 = list.InsertAfter(list.Tail, 0);
		var e10 = list.InsertAfter(list.Tail, 10);
		var e20 = list.InsertAfter(list.Tail, 20);
		var e30 = list.InsertAfter(list.Tail, 30);
		var e40 = list.InsertAfter(list.Tail, 40);
		var e50 = list.InsertAfter(list.Tail, 50);
		var e60 = list.InsertAfter(list.Tail, 60);
		// values = [ h-0, 10, 20, 30, 40, 50, 60-t ]

		list.Remove(e30);
		// values = [ h-0, 10, 20, 60-t, 40, 50, _ ]

		list.SortNodeMemoryAddresses();
		// values = [ h-0, 10, 20, 40, 50, 60-t, _ ]

		// Same as removing e20 but the enumerator is invalid at this point.
		list.Remove(list.GetEnumeratorAtIndex(2));
		// values = [ h-0, 10, 60-t, 40, 50, _, _ ]

		list.SortNodeMemoryAddresses();
		// values = [ h-0, 10, 40, 50, 60-t, _, _ ]

		Assert.That(list[0], Is.EqualTo(0));
		Assert.That(list[1], Is.EqualTo(10));
		Assert.That(list[2], Is.EqualTo(40));
		Assert.That(list[3], Is.EqualTo(50));
		Assert.That(list[4], Is.EqualTo(60));
		Assert.That(list.GetEnumeratorAtIndex(0).Current, Is.EqualTo(0));
		Assert.That(list.GetEnumeratorAtIndex(1).Current, Is.EqualTo(10));
		Assert.That(list.GetEnumeratorAtIndex(2).Current, Is.EqualTo(40));
		Assert.That(list.GetEnumeratorAtIndex(3).Current, Is.EqualTo(50));
		Assert.That(list.GetEnumeratorAtIndex(4).Current, Is.EqualTo(60));
		AssertListValues(list, 0, 10, 40, 50, 60);

		var e15 = list.InsertAfter(list.GetEnumeratorAtIndex(1), 15);
		// values = [ h-0, 10, 40, 50, 60-t, 15, _ ]

		Assert.That(list[0], Is.EqualTo(0));
		Assert.That(list[1], Is.EqualTo(10));
		Assert.That(list[2], Is.EqualTo(40));
		Assert.That(list[3], Is.EqualTo(50));
		Assert.That(list[4], Is.EqualTo(60));
		Assert.That(list[5], Is.EqualTo(15));
		Assert.That(list.GetEnumeratorAtIndex(0).Current, Is.EqualTo(0));
		Assert.That(list.GetEnumeratorAtIndex(1).Current, Is.EqualTo(10));
		Assert.That(list.GetEnumeratorAtIndex(2).Current, Is.EqualTo(40));
		Assert.That(list.GetEnumeratorAtIndex(3).Current, Is.EqualTo(50));
		Assert.That(list.GetEnumeratorAtIndex(4).Current, Is.EqualTo(60));
		Assert.That(list.GetEnumeratorAtIndex(5).Current, Is.EqualTo(15));
		AssertListValues(list, 0, 10, 15, 40, 50, 60);

		list.SortNodeMemoryAddresses();
		// values = [ h-0, 10, 15, 40, 50, 60-t, _ ]

		Assert.That(list[0], Is.EqualTo(0));
		Assert.That(list[1], Is.EqualTo(10));
		Assert.That(list[2], Is.EqualTo(15));
		Assert.That(list[3], Is.EqualTo(40)); // ERROR HERE -> 50
		Assert.That(list[4], Is.EqualTo(50)); // ERROR HERE -> 60
		Assert.That(list[5], Is.EqualTo(60)); // ERROR HERE -> 40
		Assert.That(list.GetEnumeratorAtIndex(0).Current, Is.EqualTo(0));
		Assert.That(list.GetEnumeratorAtIndex(1).Current, Is.EqualTo(10));
		Assert.That(list.GetEnumeratorAtIndex(2).Current, Is.EqualTo(15));
		Assert.That(list.GetEnumeratorAtIndex(3).Current, Is.EqualTo(40)); // ERROR HERE -> 50
		Assert.That(list.GetEnumeratorAtIndex(4).Current, Is.EqualTo(50)); // ERROR HERE -> 60
		Assert.That(list.GetEnumeratorAtIndex(5).Current, Is.EqualTo(60)); // ERROR HERE -> 40
		AssertListValues(list, 0, 10, 15, 40, 50, 60);

		AssertGeneralInvariants(list);
	}
}

Everything works fine until the very end where you can see the ERROR HERE followed by the value I'm getting.
As you can see it appears that the addresses after the one that was inserted have circled around, as if they all went up by one index, and the one at the first index became last.

I was able to fix that issue by modifying the for loop in SortNodeMemoryAddresses with the following:

using (var temporaryBuffer = new NativeArray<T>(m_State -> m_Length, Allocator.Temp, NativeArrayOptions.UninitializedMemory))
{
	UnsafeUtility.MemCpy(temporaryBuffer.GetUnsafePtr(), m_State -> m_Values, (long) (m_State -> m_Length * UnsafeUtility.SizeOf<T>()));

	for (int nodeIndex = m_State -> m_HeadIndex, sequentialIndex = 0; nodeIndex >= 0; nodeIndex = m_State -> m_NextIndexes[nodeIndex], sequentialIndex++)
		UnsafeUtility.WriteArrayElement(m_State -> m_Values, sequentialIndex, temporaryBuffer[nodeIndex]);
}

Where I create a copy of all the values as they are in the memory and they rewrite them in sequential order, which works, but it allocates a native array every time the method is called.

Did I miss something and I am not using the linked list the right way? or is there indeed a problem when the sequential value is written at the node index?

Thank you very much in advance.

NativeChunkedList<T> memory overwrite when it grows Capacity

NativeChunkedList.cs 1267 line
sizeof(NativeChunkedListChunk) => sizeof(NativeChunkedListChunk*)
miss a * for the pointers

// Copy the old chunk pointers to the new chunk pointers UnsafeUtility.MemCpy( chunks, m_State->m_Chunks, sizeof(NativeChunkedListChunk) * numOldChunks);

NativeHashSet.ParallelWriter error with Unity 2019.2

I have two problems, however the first one may be a current limitation of Unity (that's why I am not opening another issue)

1. I can't use [DeallocateOnJobCompletion] on NativeHashSet so I am forced to use a persistent one

2. Using the parallel writer I get this error:

InvalidOperationException: ListTriggerEventEntitiesJob.UserJobData.TriggerdContactsWriter uses the [NativeContainer] but has no AtomicSafetyHandle embedded, this is an internal error in the container type.

NativeLinkedList.GetEnumerator .MoveNext returns true for empty Lists

I have an empty list and try to do it like the usual Native API

var list = new NativeLinkedList<int>(capacity: 10, Allocator.Temp);
var e = list.getEnumerator();
while(e.MoveNext()) {
// do something
}

Workaround:

while(e.MoveNext() && e.IsValid()){
...
}

NativeArray2D: Multi-dimensional vs Jagged Arrays Performance

I am wondering whether your approach on implementing a 2d nativeArray could have performance implications, specially when used in the job system. Unity also advised that iterating over multidimensional arrays are less efficient than jagged and one dimensional arrays.

Wouldn't it be more efficient to flatten the multidimensional/jagged arrays into one dimensional native arrays (with modified indices) and then use that for jobs?

Versioning with tags for UPM

It would be immensely helpful if you could do semantic versioning with git tags, so that we could pull a specific version via UPM instead of the head of the repo.

Feature request: NativePriorityQueue<T>

A native priority queue/min heap (a simple binary heap would suffice, I suppose) would be extremely useful. I completely understand if that's outside of the scope of the project, however. Just an idea :).

Error

First, love your blog so many great articles well written and informative.

Second, I just tried importing NativeCollections into a new empty project and I get this error message:

Assets\JacksonDunstanNativeCollections\NativeLinkedList.cs(1128,20): error CS7036: There is no argument given that corresponds to the required formal parameter 'allocator' of 'DisposeSentinel.Create(out AtomicSafetyHandle, out DisposeSentinel, int, Allocator)'

Is says in the readme that Jobs or Burst aren't necessary. Is there something else that I need?

Using Unity 2018.3.0f2.

[Feature Request] Add a NativeArray3D container

Pretty straightforward, just need to duplicate the NativeArray2D class and extend it