1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
|
#include <set>
#include <list>
#include <iostream>
#include <string>
using namespace std;
class Node;
set<Node*> all_nodes;
Node *root;
class Node
{
public:
list<Node*> children;
string _name;
string *debug_name;
Node( string name ) : _name(name) {
cout << "Node " << _name << " created" << endl;
debug_name = new string(name);
}
virtual ~Node() {
cout << "Node " << _name << " deleted" << endl;
}
void remove( Node * node ) {
std::list<Node*>::iterator it_found = std::find(children.begin(), children.end(), node);
if( it_found != children.end() ) {
children.erase( it_found );
}
}
void *operator new( size_t size )
{
cout << "node allocated of size " << size << endl;
void* mem = malloc(size);
all_nodes.insert((Node*)mem);
return mem;
}
void operator delete( void *ptr )
{
cout << "node " << *(((Node*)ptr)->debug_name) << " deleted by the operator and freed" << endl;
// remove it from the total list
all_nodes.erase( (Node*)ptr );
free( ptr );
}
};
class NodeA : public Node
{
public:
int count;
NodeA( string name ) : Node( name ) {
cout << "NodeA " << _name << " created" << endl;
}
};
void gc_rec( Node *node, set<Node*> & set_to_delete ) {
set<Node*>::iterator it_found = std::find(set_to_delete.begin(), set_to_delete.end(), node);
if( it_found == set_to_delete.end() ) {
return;
}
set_to_delete.erase(node);
for( list<Node*>::iterator it=node->children.begin() ; it!= node->children.end() ; ++it) {
gc_rec( *it, set_to_delete );
}
}
void gc()
{
set<Node*> set_to_delete = all_nodes;
gc_rec( root, set_to_delete );
for( set<Node*>::iterator it = set_to_delete.begin(); it!= set_to_delete.end() ; ++it ) {
delete *it;
}
}
int main()
{
root = new Node("root");
Node *node1 = new Node("1");
Node *node2 = new Node("2");
Node *node3 = new Node("3");
Node *node4 = new Node("4");
Node *node5 = new Node("5");
Node *node6 = new Node("6");
root->children.push_back( node1 );
root->children.push_back( node2 );
node1->children.push_back( node3 );
node1->children.push_back( node4 );
node2->children.push_back( node4 );
node3->children.push_back( node5 );
node5->children.push_back( node3 );
node5->children.push_back( node6 );
node6->children.push_back( node6 );
node1->remove( node3 );
gc();
return 0;
} |
