What is the proper way of handling linked lists in wxWidgets?

Question

I wrote an application using wxWidgets that uses wxList. I am having some random crahses (segfault) in the destructors that collect the list data. I could not find a definite way of removing items from the list (Erase() VS DeleteNode()). Even iterating over the items has two flavours (list->GetFirst() VS list->begin()).

Below is a test class showing the approach I am using in my application. The test runs perfectly, no crash. It seems like some pointers are being used after they are freed, but I can not tell that by looking at the code. I suppose am doing something wrong around the Erase() and DeleteContents() calls.

P.S: in the application, the list contains about 15 thousand items, as opposed to only 9 in the test.

#include <wx/list.h>
#include <wx/log.h>

class TestItem
{
public:
    TestItem(int _x, int _y) { x = _x; y = _y; }
    int x;
    int y;
};

WX_DECLARE_LIST(TestItem, TestList);

#include <wx/listimpl.cpp>
WX_DEFINE_LIST(TestList);

class Test {

public:
    TestList *list;
    Test() {
        list = new TestList;
    }

    ~Test() {
        Clean();
        delete list;
    }


    void CreateAndAddToList(int x, int y) {
        TestItem *item = new TestItem(x, y);
        list->Append(item);
    }

    void PrintAll() {
        wxLogMessage(wxT("List size: %d"), list->GetCount());
        wxTestListNode *node = list->GetFirst();
        while (node) {
            TestItem *item = node->GetData();
            wxLogMessage(wxT("Item: %d, %d"), item->x, item->y);
            node = node->GetNext();
        }
    }

    void DeleteAllX(int x) {
        wxTestListNode *node = list->GetFirst();
        while (node) {
            TestItem *item = node->GetData();
            if (item->x != x) {
                node = node->GetNext();
                continue;
            }
            wxTestListNode *toDelete = node;
            node = node->GetNext();
            wxLogMessage(wxT("Deleting item: %d, %d"), item->x, item->y);
            list->Erase(toDelete);
            delete item;
        }
    }

    void Clean() {
        list->DeleteContents(true);
        list->Clear();
    }

    static void DoAllTests() {
        Test *t = new Test;
        t->CreateAndAddToList(1, 1);
        t->CreateAndAddToList(1, 2);
        t->CreateAndAddToList(1, 3);
        t->CreateAndAddToList(2, 1);
        t->CreateAndAddToList(2, 2);
        t->CreateAndAddToList(2, 3);
        t->CreateAndAddToList(3, 1);
        t->CreateAndAddToList(3, 2);
        t->CreateAndAddToList(3, 3);
        t->PrintAll();
        t->DeleteAllX(2);
        t->PrintAll();
        t->Clean();
        t->PrintAll();
        delete t;
    }
};

Answer 1

I never used wxWidgets but I think DeleteAllX will fail if you pass such a parameter which is not in the list. It will fail in the following line:

node = node->GetNext();

Make sure this doesn't happen in original app. Also you can put asserts into pointer accesses before you get something from the pointer:

TestItem *item = node->GetData();
assert(item);
if (item->x != x) {
    node = node->GetNext();
    assert(node);
    continue;
}

etc.

Answer 2

On the difference between list->GetFirst() and list->begin() in wxList API, it seems to be that list->GetFirst() returns NULL if list is empty and list->begin() returns the value of iterator to end list->end() as usual for other iterators. list->GetFirst() is the old API, list->begin() is the new one. The main benefit is that is allow you to use templates expecting an iterator with a wxList.

wxList is considered as deprecated and to be replaced by std::list, but that should not worry you too much as it is done internally with new versions of wx (wxList just become a thin wrapper over wxList).

The way you use it seems fine anyway and I see no obvious error in DeleteAllX(), even if it can be slightly simplified.

What I would suspect is that some previous memory allocation failed (can be very silent if it was done through malloc) and cause havoc in the list at a later time when you delete, or that the segfault occurs inside the destructor of your own objects when you call delete. As many programming errors can lead to that situation it looks more likely to me than some problem from wxList, including allocation problems. However that is easy enough to check, just track calls to your destructors and you knwo soon enough if segfaults came from there.