內存泄漏在後綴樹中C++

Question

我使用了來自source的streed2006.cpp庫。該代碼在刪除邊緣時存在內存泄漏。我清除使用下面的代碼從哈希表中的邊數：

//throwing away the edges from hashtable 
for(int t=0;t<HASH_TABLE_SIZE;t++) 
{ 
    Edges[t].Remove(); 
    Edges[t].start_node == -1 

} 

Valgrind的輸出：

3,920 bytes in 245 blocks are definitely lost in loss record 9 of 12 
==6301== at 0x4029F34: operator new(unsigned int) (in /usr/lib/valgrind /vgpreload_memcheck-x86-linux.so) 
==6301== by 0x804A683: Edge::SplitEdge(Suffix&) (suffix_tree.cpp:555) 
==6301== by 0x804B02F: AddPrefix(Suffix&, int) (suffix_tree.cpp:753) 

請指導我如何刪除邊緣。

能夠消除內存泄漏。以下是該解決方案：

void AddPrefix(Suffix &active, int last_char_index) 
{ 
int parent_node; 
int last_parent_node = -1; 

for (; ;) { 
    Edge edge; 
    parent_node = active.origin_node; 
    if (active.Explicit()) { 
     edge = Edge::Find(active.origin_node, T[ last_char_index ]); 
     if (edge.start_node != -1) 
      break; 
    } else { //implicit node, a little more complicated 
     edge = Edge::Find(active.origin_node, T[ active.first_char_index ]); 
     int span = active.last_char_index - active.first_char_index; 
     if (T[ edge.first_char_index + span + 1 ] == T[ last_char_index ]) 
      break; 
     parent_node = edge.SplitEdge(active); 
    } 

    Edge *new_edge = new Edge(last_char_index, T.N, parent_node); 
    new_edge->Insert(); 
    //cout << "Created edge to new leaf: " << *new_edge << "\n"; 
    AddSuffixLink(last_parent_node, parent_node); 
    if (active.origin_node == 0) { 
     //cout << "Can't follow suffix link, I'm at the root\n"; 
     active.first_char_index++; 
    } else { 
    /* 
     cout << "Following suffix link from node " 
      << active.origin_node 
      << " to node " 
      << Suffix_Nodes[ active.origin_node ].suffix_node 
      << ".\n"; 
    */ 
     active.origin_node = Suffix_Nodes[ active.origin_node ].suffix_node; 
     //cout << "New prefix : " << active << "\n"; 
    } 
    active.Canonize(); 
delete(new_edge); 
new_edge = NULL; 
} 
AddSuffixLink(last_parent_node, parent_node); 
active.last_char_index++; //Now the endpoint is the next active point 
active.Canonize(); 
}; 

和

int Edge::SplitEdge(Suffix &s) 
{ 
//cout << "Splitting edge: " << *this << "\n"; 
Remove(); 
Edge *new_edge = 
    new Edge(first_char_index, 
      first_char_index + s.last_char_index - s.first_char_index, 
      s.origin_node); 
new_edge->Insert(); 
Suffix_Nodes[ new_edge->end_node ].suffix_node = s.origin_node; 
first_char_index += s.last_char_index - s.first_char_index + 1; 
start_node = new_edge->end_node; 
Insert(); 
//cout << "New edge: " << *new_edge << "\n"; 
//cout << "Old edge: " << *this << "\n"; 
delete(new_edge); 
//return new_edge->end_node; 
return(start_node); 
} 

Answer 1

void AddPrefix(Suffix &active, int last_char_index) 
{ 
int parent_node; 
int last_parent_node = -1; 

for (; ;) { 
    Edge edge; 
    parent_node = active.origin_node; 
    if (active.Explicit()) { 
     edge = Edge::Find(active.origin_node, T[ last_char_index ]); 
     if (edge.start_node != -1) 
      break; 
    } else { //implicit node, a little more complicated 
     edge = Edge::Find(active.origin_node, T[ active.first_char_index ]); 
     int span = active.last_char_index - active.first_char_index; 
     if (T[ edge.first_char_index + span + 1 ] == T[ last_char_index ]) 
      break; 
     parent_node = edge.SplitEdge(active); 
    } 

    Edge *new_edge = new Edge(last_char_index, T.N, parent_node); 
    new_edge->Insert(); 
    //cout << "Created edge to new leaf: " << *new_edge << "\n"; 
    AddSuffixLink(last_parent_node, parent_node); 
    if (active.origin_node == 0) { 
     //cout << "Can't follow suffix link, I'm at the root\n"; 
     active.first_char_index++; 
    } else { 
    /* 
     cout << "Following suffix link from node " 
      << active.origin_node 
      << " to node " 
      << Suffix_Nodes[ active.origin_node ].suffix_node 
      << ".\n"; 
    */ 
     active.origin_node = Suffix_Nodes[ active.origin_node ].suffix_node; 
     //cout << "New prefix : " << active << "\n"; 
    } 
    active.Canonize(); 
//ADDED THIS DELETE HERE 
delete(new_edge); 
new_edge = NULL; 
} 
AddSuffixLink(last_parent_node, parent_node); 
active.last_char_index++; //Now the endpoint is the next active point 
active.Canonize(); 
}; 

和

int Edge::SplitEdge(Suffix &s) 
{ 
//cout << "Splitting edge: " << *this << "\n"; 
Remove(); 
Edge *new_edge = 
    new Edge(first_char_index, 
      first_char_index + s.last_char_index - s.first_char_index, 
      s.origin_node); 
new_edge->Insert(); 
Suffix_Nodes[ new_edge->end_node ].suffix_node = s.origin_node; 
first_char_index += s.last_char_index - s.first_char_index + 1; 
start_node = new_edge->end_node; 
Insert(); 
//cout << "New edge: " << *new_edge << "\n"; 
//cout << "Old edge: " << *this << "\n"; 
//ADDED THIS DELETE HERE 
delete(new_edge); 
//return new_edge->end_node; 
return(start_node); 
}