ref return and NativeList resize

Unity Engine
,
1

So, I have a job that recurses down a hierarchy expanding and collapsing nodes as it goes. All nodes are stored in a NativeList, contain an id, which is their index into the array, and reference each other via index. Unused nodes are marked by storing their index in a NativeHashSet. Essentially, the crux of the traversal code looks like so:

for (int i = 0; i < 6; ++i)
{
    ref Node n = ref mNodes.ElementAt(i);
    if (NeedsSubdivide(ref n))
    {
        Subdivide(ref n); // makes 4 more sub nodes, recurses down..
    }
    else if (NeedsCollapse(ref n))
    {
         Collapse(ref n); // recurses and removes all subn odes below this
    }
}

This works great, but there’s one issue- if the NativeList is not allocated large enough for the entire list, then when a new node is created, the internal array is copied to a new, larger array, and the references to those elements are no longer valid.

void AddNode(ref Node parent)
{
   mNodes.Add(new Node());
   // At this point, the array may be invalidated, making parent point to the old memory of where the array was
   ref Node newNode = ref mNodes.ElementAt(mNodes.Length-1);
   newNode.id = mNodes.Length -1;
   parent.child[0] = newNode.id;
}

So basically I’m wondering if there’s a better way. Essentially what I want to pass, in C++ terms, is not a reference to an object, but a pointer to a pointer of the object, such that the AddNode function could re-get the parent node via it’s id, and the calling function would point to the new node instead of the old one.

Is such a construct available? I can easily just work with ID’s through all of these functions, requiring every function get a reference to the array element, but it also means they have to do this after calling any function which might grow the array. This seems like a potential for lots of bugs, since it may not always be obvious that calling a function might trigger the creation of a new node as a system gets more complex. Being able to pass a *& or ** would effectively limit the knowledge of this to only the areas which actually expand the array - they would simply change the passed in memory address to the potentially new one after adding to the array. Though this wouldn’t protect any references the calling function may have had to other structures… Ugh…
.

2

I think this should be fairly easy to solve with some additional indirection.

Split node so you have NodeData and Node.

So you have a NativeList.

Node is now just a wrapper with a reference to that list and also stores it’s index into it, and you can just pass it by value.

It’s the same type of indirection collections themselves use so you can pass them around by value.

1 Like