Delete on a very deep tree

Question

I am creating the trie suffix (unfortunately, there is no time to correctly inject the suffix tree) for a 10-character set. The lines I want to parse will be quite long (up to 1 M characters). The tree is designed without any problems, however, I encounter some when I try to free memory after it ends.

In particular, if I configured my constructor and destructor as such (where CNode.child is a pointer to an array of 10 pointers to other CNodes, and count is a simple unsigned int):

CNode::CNode(){ count = 0; child = new CNode* [10]; memset(child, 0, sizeof(CNode*) * 10); } CNode::~CNode(){ for (int i=0; i<10; i++) delete child[i]; } 

When I try to remove the root of the node, I get a stack overflow. Maybe I'm wrong, but I'm sure this is due to too many calls to destructors (each destructor calls up to 10 other destructors). I know that this is suboptimal and spatial, and temporary, but it should be a quick and dirty solution to the problem with a repeating substring.

tl; dr : how could one free the memory occupied by a very deep tree?

Thank you for your time.

Answer 1

One option is to allocate from a large buffer, and then release this buffer immediately.

For example (untested):

 class CNodeBuffer { private: std::vector<CNode *> nodes; public: ~CNodeBuffer() { empty(); } CNode *get(...) { CNode *node = new CNode(...); nodes.push_back(node); return node; } void empty() { for(std::vector<CNode *>::iterator *i = nodes.begin(); i != nodes.end(); ++i) { delete *i; } nodes = std::vector<CNode *>(); } }; 

If pointers to std::vector elements are stable, you can make things a little simpler and just use std::vector<CNode> . This requires testing.

Answer 2

Do you initialize the memory for the nodes themselves? From what I see, your code only allocates memory to pointers, not to actual nodes.

As for your question, try iterating over the tree iteratively, not recursively. Recursion is bad, it is good only when it is on paper, not in code, unfortunately.

Answer 3

Have you only considered an increase in stack size?

In visual studio, you do this with / FNUMBER, where NUMBER is the stack size in bytes. You may also need to specify / STACK: reserve [, commit].

Answer 4

You are about to make a few deletions. This will take a lot of time because you will gain access to memory in a very random way. However, at this point, you no longer need a tree structure. Therefore, I would do two passes. In the first pass, create std::vector<CNode*> and reserve() enough space for all nodes in your tree. Now go back to the tree and copy all the CNode * into your vector. At the second stage, sort them (!). Then, in the third step, delete all of them. The second step is technically optional, but probably makes the third step much faster. If not, try sorting in the reverse order.

Answer 5

I think that in this case, help in the first half can help by putting all the tracking information back in deque, and not on the stack provided by the OS. It still will not be nice to solve the problem, to do it in the destructor.

pseudo code:

 void CNode::cleanup() { std::deque<CNode*> nodes; nodes.push_back(this); while(!nodes.empty()) { // Get and remove front node from deque. // From that node, put all non-null children at end of deque. // Delete front node. } }