Remember to clear the memory hold in Boost recursive intrusive

While I'm studying on making an intrusive container right inside an object which which is also an intrusive container. Some sort of nested intrusive container I might think of. Well, I never thought Boost really made one for us, this feature is called recursive intrusive container.

There is some issue with this container. It happens only on Windows, no problem in Linux at all. When removing an object from an intrusive container, make sure the nested intrusive container is clear off before the object is removed. I have run some test case about it.

Here is the declaration of the object for the test case, the sibling member is the recursive intrusive container:

class FileNode : public boost::intrusive::list_base_hook<link_mode<auto_unlink> >
{
public:
    boost::intrusive::list<FileNode, base_hook<list_base_hook<link_mode<auto_unlink> > >, constant_time_size<false> > sibling;

...
...
};

This is the intrusive list declaration:

typedef boost::intrusive::list<FileNode, base_hook<list_base_hook<link_mode<auto_unlink> > >, constant_time_size<false> > FileNodeListType;

class FileBot
{
public:
    FileNodeListType fileList;
 

First, an object was pumped into the intrusive container, fileList in this case. Then allocate another object into recursive list, sibling. I loop through every object in the fileList and put in another object into the recursive list.

void FileBot::addFileNode()
{
    FileNode *f1 = new FileNode();
    f1->setName("ASD");
    fileList.push_back(*f1);
}

void FileBot::addSubFileNode()
{
    FileNode *f2 = NULL;

    for(FileNode &T : fileList)
    {
        f2 = new FileNode();
        f2->setName("QWE");
        T.sibling.push_back(*f2);
    }
}

Now I want to clear everything in the fileList, without knowing is there any object saved into the container yet. Basically I just doesn't care at all, I just want to clear the container. Thus I implemented the following code:

void FileBot::clearMemory()
{
   fileList.erase_and_dispose(fileList.begin(), fileList.end(), DisposeFileNode());
}

When I call this method, memory leak is detected. This happens only on Windows. This is my mistake. I overlook on the addSubFileNode() on how I extract the object, T from the fileList. Each object has its sibling, and each sibling has another FileNode object in it, which consume memory as well. For my case, the object inside sibling memory is not removed but the object in fileList memory has already removed. Put in other words, it just like the parent object contain the child object, when releasing the memory, the child's object must release first then only release the parent's object. And what I did here is I go straight to the release the parent object, thus the child object is now complaining about the memory leak.

So in order to play safe in this game, I'll do this:

void FileBot::clearMemory()
{
    for(FileNode &T : fileList) {
        T.sibling.erase_and_dispose(T.sibling.begin(), T.sibling.end(), DisposeFileNode());
    }

    fileList.erase_and_dispose(fileList.begin(), fileList.end(), DisposeFileNode());
}

Clean off the memory in the recursive intrusive container before cleaning the memory in the parent intrusive container. This should be the strategy for this game.

Removing an item from the Boost Intrusive list

Over the pass few weeks, I was reading the a lot of articles about the intrusive list, its benefits of using it, and its use case example on game development. This brings me a strong message that there are so many peoples on Earth promoting this container. What was so special about this container? Due to the limitation on the container provided by STL and intrusive container's low memory footprint which could benefit to the application's performance.

Does Boost provide this container. Yes! During this great moment with a sudden impulse, I begin my journey to develop a demo program using the Boost Intrusive container. Tadaa~

So far the journey was up and down, a lot of road pump, and feel tired to continue. When trying to remove an item from the list using following method will not work. Before that, let's presume I have the following declaration in the header file:

typedef boost::intrusive::list<FileNode, base_hook<list_base_hook<link_mode<auto_unlink> > >, constant_time_size<false> > FileNodeListType;

class FileBot
{
private:
    FileNodeListType fileList;

    ...
    ...
};

Then I begin to insert something into the list, assume the object type is a FileNode, do take note that I do this purely in one method:

void FileBot::addFileNode()
{
    FileNode *f1 = new FileNode();
    f1->setName("ASD");
    fileList.push_back(*f1);

    cout << "addFileNode(): memory address of insert object: " << f1 << endl;
}

Then I have another method to remove an object from the list:

void FileBot::clearMemoryByName(string filename)
{
    cout << "before delete: " << fileList.size() << endl;

    FileNode *p = new FileNode();
    p->setName("ASD");

    fileList.erase(FileNodeListType::s_iterator_to(*p));
    delete p;

    cout << "clearMemoryByName(): memory address of remove object: " << p << endl;

    cout << "after delete: " << fileList.size() << endl;
}

But somehow this method will cause a memory leak due to the following assertion failed in boost/intrusive/list.hpp, line 1270:

Assertion failed: !node_algorithms::inited(value_traits::to_node_ptr(value)), file D:\tool\boost_1_61_0\msvc\boost/intrusive/list.hpp, line 1270
Detected memory leaks!
Dumping objects ->
...
...
...
Object dump complete.
Press <return> to close this window...

A million hours were spent on studying the weak spot of this creature has finally found a solution. The clue was lying on the memory address of the object. The memory address of the object inserted into the list in addFileNode() was different from the memory object created in the clearMemoryByName().

...

addFileNode(): memory address of insert object: 001180C8
clearMemoryByName(): memory address of remove object: 00111DE0

...

In the revise's version, the object was retrieved from the list and then perform some filtering (e.g. match the property field's value), then only perform the deletion.

void FileBot::clearMemoryByName(string filename)
{
    FileNode *p = NULL;
    FileNodeListType::iterator it(fileList.begin());

    for(; it != fileList.end(); it++)
    {
        cout << &*it << endl;

        // look for particular node
        string curName = (*it).getName().c_str();
        if( filename == curName) {
            p = &*it;
            break;
        }
    }

    cout << "claerMemoryByName(): memory address of remove object: " << p << endl;

    fileList.erase(FileNodeListType::s_iterator_to(*p));
    delete p;

The result was stunning! The object was removed from the list. And here is the output of the memory address:

...

addFileNode(): memory address of insert object: 00E2DAF0
claerMemoryByName(): memory address of remove object: 00E2DAF0

...

To conclude this, in order to remove an object from the list, O(n) algorithm is the only way to filter the object, then only come to deletion.

Convert Windows file separator into Linux format

I wrote a function to extract the parent path for a given path. An interesting thing happens here; Windows's file system was used (\) backslash as file separator, whereas Linux's using (/) slash as file separator. Thus, this will end up I have following code produce:

void FileBot::constructParentPath()
{
   ...

   string sep = string(1, boost::filesystem::path::preferred_separator);
   if( sep == "/" )
      boost::replace_last(filePath, "/", "|");
   else
      boost::replace_last(filePath, "\", "|");

   ...
}

When handling file separator with Boost library, the library will able to convert the Windows's file separator into Linux format. Therefore, my code will reduce into one line from the previous version:

void FileBot::constructParentPath()
{
   ...

   string filePath = fileNode.getName().generic_string();
   boost::replace_last(filePath, "/", "|");

   ...
}