I noticed a lack of examples of TIntrusiveDoubleLinkedList and when I started using it I found an issue

Development Programming & Scripting
, ,
1

Intrusive containers are useful for a specific class of problem (LRU caches being one), but without going into lots of detail there are times you want to place an item in a map and also have that item in a list.

Quick explanation of “why?”
The map gives you O(1) look up, while the list gives you the ability to track a subset of the map items in one or more lists. Also worth mentioning the map gives you the ability to remove an item from the list without traversing the list searching for the item. So you get the benefits of both fast lookup, sortability without needing to resort to a sorted map which can be more costly for insertion/removal or simply updating the value we are sorting on, and instantaneous access to the beginning of the sorted data.

Bug
I found issues with the current implementation of TIntrusiveDoubleLinkedList when you are attempting to traverse it from a const function. It appears that the TIntrusiveDoubleLinkedListNode doesn’t specify a const version for a friend class, but even if you add it manually, there is an issue with the end(). I ended up giving up, but it would be great if someone at Epic could dig into it and get a fix out.

Secondly I want to give an example of usage, because I couldn’t find one.
Example which I hope works because I am taking my actual code and trying to change the types to remove any specific project details.

#include "Containers/IntrusiveDoubleLinkedList.h"
//...
	struct FExampleStructure : public TIntrusiveDoubleLinkedListNode<FExampleStructure>
{
	FGuid ExampleMapItemKey; // will be a copy of the key we use when inserting in the map so that we can get to the map item from the list for removal purposes
	float ExpirationInSeconds;
};

// Declare a map where the key is an FGuid, Value is an FExampleStructure which is also a node of an TIntrusiveDoubleLinkedListNode
using ExamplePair = TPair<FGuid, FExampleStructure>;
TMap<FGuid, FExampleStructure> ExampleMap;

// Declare a list that the values from the above map can be placed in 
using FExampleStructureIter = TIntrusiveDoubleLinkedList<FExampleStructure>::TIterator;
TIntrusiveDoubleLinkedList<FExampleStructure> ExampleIntrusiveList;

In the above we have a definition of a map where the value can be used in an intrusive list (doesn’t have to be in any list)

Adding items:

FGuid SomeValidId; // imagine this was a valid value we want to add
//..
if (ExampleMap.Find(SomeValidId) == nullptr)
{
	FExampleStructure& ExampleStructure = ExampleMap.Add(SomeValidId);
    ExampleStructure.ExampleMapItemKey = SomeValidId;
	ExampleStructure.ExpirationInSeconds =
		FApp::GetGameTime() + Example_Consts::CVarSomeTimeInSeconds.GetValueOnGameThread();
    // Now add to the list (you don't HAVE to add it to any list, but in this sample I am)
	ExampleIntrusiveList.AddTail(&ExampleStructure);

	// Nodes are set to point to themselves until they are added to a list
	ensure(ExampleIntrusiveList.IsInList() == true);

Removing items using the list from a tick call

void ExampleClass::Tick(float DeltaTime)
{
	if (!ExampleIntrusiveList.IsEmpty())
	{
		const double CurrentTime = FApp::GetGameTime();

		// Process the list and remove expired items
		while (ExampleIntrusiveList.GetHead()
			&& ExampleIntrusiveList.GetHead()->ExpirationInSeconds <= CurrentTime)
		{
			FExampleStructure* ExampleStructure = ExampleIntrusiveList.GetHead();

			ensure(ExampleIntrusiveList->IsInList() == true);

			// Remove expired items from the cache
			int32 CountRemoved = ExampleMap.Remove(ExampleStructure->ExampleMapItemKey);

			// One should be removed from map
			ensure(CountRemoved == 1);

			// Remove from the expiration list
			ExampleIntrusiveList.Remove(ExampleStructure);

			ensure(ExampleIntrusiveList->IsInList() == false);
		}
	}
}

Traversal of the list (this is where the const issues occur)

for (FExampleStructureIter AnIter = ExampleIntrusiveList.begin(); AnIter != ExampleIntrusiveList.end();
	 AnIter++)
{
	FExampleStructure* ExampleStructure = AnIter.GetNode();

	// Access fields here
}

The above traversal works so long as it’s not done from a const function which would attempt to use the const versions of begin() and end() and due to issues in the container as written the list cannot be traversed from inside a const function.

I hope this helps someone who is looking for an example of this usage, and I hope Epic can look into the const issue :slight_smile: