gdb - bad_alloc from libc.so.6 C++ -
i'm running c++ program under gdb debian 7 64bit machine 4gb ram , encountered bad_alloc problem. try running under gdb backtrace
program received signal sigabrt, aborted. 0x00007ffff72e5475 in raise () /lib/x86_64-linux-gnu/libc.so.6 (gdb) bt #0 0x00007ffff72e5475 in raise () /lib/x86_64-linux-gnu/libc.so.6 #1 0x00007ffff72e86f0 in abort () /lib/x86_64-linux-gnu/libc.so.6 #2 0x00007ffff7b3b89d in __gnu_cxx::__verbose_terminate_handler() () /usr/lib/x86_64-linux-gnu/libstdc++.so.6 #3 0x00007ffff7b39996 in ?? () /usr/lib/x86_64-linux-gnu/libstdc++.so.6 #4 0x00007ffff7b399c3 in std::terminate() () /usr/lib/x86_64-linux-gnu/libstdc++.so.6 #5 0x00007ffff7b39bee in __cxa_throw () /usr/lib/x86_64-linux-gnu/libstdc++.so.6 #6 0x00007ffff7b3a0dd in operator new(unsigned long) () /usr/lib/x86_64-linux-gnu/libstdc++.so.6 #7 0x000000000040bfdb in allocate (__n=67108864, this=) @ /usr/include/c++/4.7/ext/new_allocator.h:94 #8 _m_allocate (__n=, this=) @ /usr/include/c++/4.7/bits/stl_vector.h:169 #9 std::vector >::_m_insert_aux ( this=this@entry=0x1f50c68, __position=..., __position@entry=..., __x=...) @ /usr/include/c++/4.7/bits/vector.tcc:343 #10 0x00000000004201eb in push_back (__x=..., this=0x1f50c68) @ /usr/include/c++/4.7/bits/stl_vector.h:893 #11 rdfcftree::closedextensionexplore (this=this@entry=0x21349950, frequency=..., outfile=..., database=..., occlist=..., frequent2tree=..., headindex=..., threshold=@0x7fffffffd818: 6, checked=..., closed=..., maximal=...) @ rdfcftree.cpp:1280 #12 0x000000000041ffd0 in rdfcftree::closedextensionexplore ( this=this@entry=0x1284a10, frequency=..., outfile=..., database=..., occlist=..., frequent2tree=..., headindex=..., threshold=@0x7fffffffd818: 6, checked=..., closed=..., maximal=...) @ rdfcftree.cpp:1302 #13 0x000000000041ffd0 in rdfcftree::closedextensionexplore ( this=this@entry=0x737a20, frequency=..., outfile=..., database=..., occlist=..., frequent2tree=..., headindex=..., threshold=@0x7fffffffd818: 6, checked=..., closed=..., maximal=...) @ rdfcftree.cpp:1302 #14 0x000000000041ffd0 in rdfcftree::closedextensionexplore ( this=this@entry=0x67bbd0, frequency=..., outfile=..., database=..., occlist=..., frequent2tree=..., headindex=..., threshold=@0x7fffffffd818: 6, checked=..., closed=..., maximal=...) @ rdfcftree.cpp:1302 #15 0x000000000041ffd0 in rdfcftree::closedextensionexplore (this=0x6f0ac0, frequency=..., outfile=..., database=..., occlist=..., frequent2tree=..., headindex=..., threshold=@0x7fffffffd818: 6, checked=..., closed=..., maximal=...) @ rdfcftree.cpp:1302 #16 0x0000000000405252 in rfrequenttreelist::extensionexplorelist4 ( this=0x7fffffffd8c0, database=..., outfile=..., frequency=..., threshold=@0x7fffffffd818: 6, checked=..., closed=..., maximal=...) @ rfrequenttreelist.cpp:248 #17 0x0000000000401fd0 in main (argc=, argv=) @ cmtreeminer.cpp:112 this constructor of rdfcftree:
rdfcftree::rdfcftree(const rdfcftree& parent, short newedgelabel, short newvertexlabel, short position) { /****************************************************************** idea: copy tree structure of parent, plus 1 new leg note: use deep copy , preserve original order of link list @ end, recompute dfcs , automorphisms ******************************************************************/ vcount = parent.vcount + 1; tid = parent.tid; adj.resize(vcount + 1); tnodelink t1, t2, t3; ( short = 1; <= vcount - 1; i++ ) //copy parent part here { t1 = parent.adj[i]; if ( t1 == 0 ) //unlike happen tree { adj[i] = 0; continue; } else { t2 = new tnode(*t1); adj[i] = t2; while ( t1->next != 0 ) { t1 = t1->next; t3 = new tnode(*t1); t2->next = t3; t2 = t3; } } } vertexlabel = parent.vertexlabel; vertexlabel.push_back(newvertexlabel); degree = parent.degree; degree.push_back(0); level = parent.level; level.push_back(level[position]+1); insertedge(edge(position,vcount,newedgelabel)); automorphism.resize(vcount+1); computedfcs(); computeautomorphism(); } this closedextensionexplore function:
void rdfcftree::closedextensionexplore( vector<long>&frequency, ostream & outfile, const vector<ptrrfreetree>& database, const vector<occurrence> & occlist, const vector< vector<short> > & frequent2tree, const vector<long> & headindex, const long & threshold, vector<long> & checked, vector<long> & closed, vector<long> & maximal) { /****************************************************************** step0: output tree ******************************************************************/ checked[vcount]++; tnodelink t; /****************************************************************** step1: using occurrence-match pruning ******************************************************************/ /****************************************************************** step1.1: initialize parent first occurrence ******************************************************************/ short parentvertex, parentedge; bool sameparent = true; if ( occlist[0].nodeindex[0] == 1 ) //if first occurrence's root //is root of transaction sameparent = false; else { t = database[occlist[0].tid]->adj[occlist[0].nodeindex[0]]; while ( t->next != 0 ) t = t->next; parentedge = t->elabel; parentvertex = database[occlist[0].tid]->vertexlabel[t->v]; } /****************************************************************** step1.2: use other occurrences compute intersections of parents ******************************************************************/ ( long s = 1; s < occlist.size(); s++ ) { short tempedge, tempvertex; if ( occlist[s].nodeindex[0] == 1 ) //if occurrence's root //is root of transaction sameparent = false; else { t = database[occlist[s].tid]->adj[occlist[s].nodeindex[0]]; while ( t->next != 0 ) t = t->next; tempedge = t->elabel; tempvertex = database[occlist[s].tid]->vertexlabel[t->v]; if ( tempedge != parentedge || tempvertex != parentvertex ) sameparent = false; } if ( sameparent == false ) break; } //parent-pruning if ( sameparent == true ) return; /****************************************************************** step1.3: find locations new leg can grow ******************************************************************/ vector<short> positiontoexplore; if ( vcount != 1 ) //be careful! single-vertex tree, adj[j] = empty { short j = 1; while ( level[j] == 1 || degree[j] > 1 ) { positiontoexplore.push_back(j); j = adj[j]->v; } positiontoexplore.push_back(j); } else positiontoexplore.push_back(1); /****************************************************************** step1.4: compute range of labels each vertex ******************************************************************/ vector<short> vertexrange(vcount + 1, max_vertex + 1); vector<short> edgerange(vcount + 1, max_edge + 1); ( short j = 0; j < positiontoexplore.size(); j++ ) { short = positiontoexplore[j]; possiblelegs(i, edgerange[i], vertexrange[i]); } /****************************************************************** step1.5: initialize list of legs first occurrence ******************************************************************/ vector<short> legtriple(3); //vertex index, leg edge label, leg vertex label vector<vector<short> > commonlegs; set<short> neighbors; // set<short>::iterator pos; ( short = 1; <= vcount; i++ ) { neighbors.clear(); t = adj[i]; while ( t != 0 ) //insert index of neighbors of position { neighbors.insert(occlist[0].nodeindex[t->v - 1]);//inconsistency on index t = t->next; } t = database[occlist[0].tid]->adj[occlist[0].nodeindex[i-1]]; while ( t != 0 ) { if ( occlist[0].nodeindex[i-1] < t->v ) { pos = neighbors.find( t->v ); if ( pos == neighbors.end() ) //if vertex hasn't been used { legtriple[0] = i; legtriple[1] = t->elabel; legtriple[2] = database[occlist[0].tid]->vertexlabel[t->v]; commonlegs.push_back(legtriple); } } t = t->next; }//end of while ( t != 0 ) } /****************************************************************** step1.6: use other occurrences compute intersections of legs ******************************************************************/ ( long s = 1; s < occlist.size(); s++ ) { vector<bool> isfetched(vcount + 1, false); vector<vector<short> > tuplelegs(0); vector<short> legevpair(2); vector<vector<short> >::iterator pos1; ( pos1 = commonlegs.begin(); pos1 != commonlegs.end(); ) { vector<short> thistriple = *pos1; //get next commonleg //debug //cout << commonlegs.size() << endl; //cout << thistriple[0] << ' ' << thistriple[1] << ' ' << thistriple[2] << endl; short = thistriple[0]; //the index of vertex //assuming indices in commonlegs non-decreasing if ( !isfetched[i] ) //fetch neighbors of vertex in //corresponding database transaction { neighbors.clear(); tuplelegs.resize(0); t = adj[i]; while ( t != 0 ) //insert index of neighbors of position { neighbors.insert(occlist[s].nodeindex[t->v - 1]);//inconsistency on index t = t->next; } t = database[occlist[s].tid]->adj[occlist[s].nodeindex[i-1]]; while ( t != 0 ) { if ( occlist[s].nodeindex[i-1] < t->v ) { pos = neighbors.find( t->v ); if ( pos == neighbors.end() ) //if vertex hasn't been used { legevpair[0] = t->elabel; legevpair[1] = database[occlist[s].tid]->vertexlabel[t->v]; tuplelegs.push_back(legevpair); } } t = t->next; } isfetched[i] = true; } bool isfound = false; ( short k = 0; k < tuplelegs.size(); k++ ) { if ( thistriple[1] == tuplelegs[k][0] && thistriple[2] == tuplelegs[k][1] ) { isfound = true; break; } } if ( !isfound ) { pos1 = commonlegs.erase(pos1); } else { ++pos1; } } if ( commonlegs.size() == 0 ) break; } if ( commonlegs.size() != 0 ) { set<short> positionset; ( short = 0; < positiontoexplore.size(); i++ ) positionset.insert(positiontoexplore[i]); ( short = 0; < commonlegs.size(); i++ ) { pos = positionset.find(commonlegs[i][0]); if ( pos == positionset.end() ) //not on rightmost path { return; } else { short j = commonlegs[i][0]; if ( (commonlegs[i][1] < edgerange[j]) || ((commonlegs[i][1] == edgerange[j]) && (commonlegs[i][2] < vertexrange[j])) ) return; } } } bool isclosed = true; bool ismaximal = true; /****************************************************************** step2: check if tree closed ******************************************************************/ while ( true ) { /****************************************************************** step2.1: if previous step, there common legs, not closed ******************************************************************/ if ( commonlegs.size() != 0 ) { isclosed = false; ismaximal = false; break; } /****************************************************************** step2.2: list of parents of first tid ******************************************************************/ vector< vector<short> > candidateparent; vector<short> parentpair(2,0); //parentedge, parentvertex sameparent = true; long m = 0; long n = 0; long temptid = occlist[0].tid; while ( m < occlist.size() && occlist[m].tid == temptid ) { if ( occlist[m].nodeindex[0] != 1 ) //if first occurrence's root //is not root of transaction { t = database[occlist[m].tid]->adj[occlist[m].nodeindex[0]]; while ( t->next != 0 ) t = t->next; parentpair[0] = t->elabel; parentpair[1] = database[occlist[m].tid]->vertexlabel[t->v]; candidateparent.push_back(parentpair); } m++; } //now candidateparent holds possible parents /****************************************************************** step2.3: use other transactions compute intersections of parents ******************************************************************/ if ( candidateparent.size() == 0 ) { sameparent = false; } else { while ( m < occlist.size() && candidateparent.size() != 0 ) { n = m; short tempedge, tempvertex; while ( n < occlist.size() && occlist[n].tid == occlist[m].tid ) n++; n--; vector < vector<short> >::iterator pos1; ( pos1 = candidateparent.begin(); pos1 != candidateparent.end(); ) { bool tempflag = false; ( long s = m; s <= n; s++ ) { if ( occlist[s].nodeindex[0] != 1 ) { t = database[occlist[s].tid]->adj[occlist[s].nodeindex[0]]; while ( t->next != 0 ) t = t->next; tempedge = t->elabel; tempvertex = database[occlist[s].tid]->vertexlabel[t->v]; if ( tempedge == (*pos1)[0] && tempvertex == (*pos1)[1] ) { tempflag = true; break; //break loop: ( s = m; ... ) } } } if ( tempflag == true ) ++pos1; else pos1 = candidateparent.erase(pos1); } m = n+1; }//end of while ( m < ... ) } //parent-closed-checking if ( candidateparent.size() == 0 ) sameparent = false; if ( sameparent == true ) { isclosed = false; ismaximal = false; break; } /****************************************************************** step2.4: list of legs of first tid ******************************************************************/ commonlegs.clear(); m = 0; n = 0; temptid = occlist[0].tid; while ( n < occlist.size() && occlist[n].tid == temptid ) n++; n--; ( short = 1; <= vcount; i++ ) { ( long s = m; s <= n; s++ ) { neighbors.clear(); t = adj[i]; while ( t != 0 ) //insert index of neighbors of position { neighbors.insert(occlist[s].nodeindex[t->v - 1]);//inconsistency on index t = t->next; } t = database[occlist[s].tid]->adj[occlist[s].nodeindex[i-1]]; while ( t != 0 ) { if ( occlist[s].nodeindex[i-1] < t->v ) { pos = neighbors.find( t->v ); if ( pos == neighbors.end() ) //if vertex hasn't been used { legtriple[0] = i; legtriple[1] = t->elabel; legtriple[2] = database[occlist[s].tid]->vertexlabel[t->v]; commonlegs.push_back(legtriple); } } t = t->next; }//end of while ( t != 0 ) }//end of ( long s = m; ... ) } //now commonlegs stores possible new legs /****************************************************************** step2.5: using other transactions prune commonlegs ******************************************************************/ m = n+1; //next tid while ( m < occlist.size() && commonlegs.size() != 0 ) { n = m+1; while ( n < occlist.size() && occlist[n].tid == occlist[m].tid ) n++; n--; //now m n occurrences sharing same tid vector<bool> isfetched(vcount + 1, false); vector<vector<short> > tuplelegs(0); vector<short> legevpair(2); vector<vector<short> >::iterator pos1; ( pos1 = commonlegs.begin(); pos1 != commonlegs.end(); ) { vector<short> thistriple = *pos1; //get next commonleg short = thistriple[0]; //the index of vertex //assuming indices in commonlegs non-decreasing if ( !isfetched[i] ) //fetch neighbors of vertex in //corresponding database transaction { tuplelegs.resize(0); ( long s = m; s <= n; s++ ) { neighbors.clear(); t = adj[i]; while ( t != 0 ) //insert index of neighbors of position { neighbors.insert(occlist[s].nodeindex[t->v - 1]);//inconsistency on index t = t->next; } t = database[occlist[s].tid]->adj[occlist[s].nodeindex[i-1]]; while ( t != 0 ) { if ( occlist[s].nodeindex[i-1] < t->v ) { pos = neighbors.find( t->v ); if ( pos == neighbors.end() ) //if vertex hasn't been used { legevpair[0] = t->elabel; legevpair[1] = database[occlist[s].tid]->vertexlabel[t->v]; tuplelegs.push_back(legevpair); } } t = t->next; } }//end of ( long s = m; ... ) isfetched[i] = true; } bool isfound = false; ( short k = 0; k < tuplelegs.size(); k++ ) { if ( thistriple[1] == tuplelegs[k][0] && thistriple[2] == tuplelegs[k][1] ) { isfound = true; break; } } if ( !isfound ) { pos1 = commonlegs.erase(pos1); } else { ++pos1; } } if ( commonlegs.size() == 0 ) break; m = n+1; }//end of while ( m < ... ) if ( commonlegs.size() != 0 ) { isclosed = false; ismaximal = false; break; } break; }//end of while @ beginning of step2 if ( isclosed == true ) closed[vcount]++; /****************************************************************** step3: main loop, each position, explore ******************************************************************/ ( short j = 0; j < positiontoexplore.size(); j++ ) { short = positiontoexplore[j]; //step3_1: range of valid legs short minedge = edgerange[i]; short minvertex = vertexrange[i]; //if there no possible leg @ position if ( minedge > max_edge ) continue; //continue loop //if there no frequent 2-tree starting vertex label if ( headindex[vertexlabel[i] - min_vertex] == 0 ) continue; //step3_2: possible frequent legs vector<bool> isfrequent( (max_edge - min_edge + 1) *(max_vertex - min_vertex + 1), false); (short j = headindex[vertexlabel[i] - min_vertex]; (j < frequent2tree.size() && frequent2tree[j][0] == vertexlabel[i]); j++ ) isfrequent[( frequent2tree[j][1] - min_edge ) * ( max_vertex - min_vertex + 1 ) + ( frequent2tree[j][2] - min_vertex )] = true; //step2_3: explore each potential leg occurrence tempocc; vector<supportnode> potential((max_edge - min_edge + 1) *(max_vertex - min_vertex + 1)); ( long s = 0; s < occlist.size(); s++ ) { neighbors.clear(); t = adj[i]; while ( t != 0 ) //insert index of neighbors of position { neighbors.insert(occlist[s].nodeindex[t->v - 1]);//inconsistency on index t = t->next; } t = database[occlist[s].tid]->adj[occlist[s].nodeindex[i-1]]; while ( t != 0 ) { if ( occlist[s].nodeindex[i-1] < t->v ) { pos = neighbors.find( t->v ); if ( pos == neighbors.end() ) //if vertex hasn't been used { short tempe = t->elabel; short tempv = database[occlist[s].tid]->vertexlabel[t->v]; short location = ( tempe - min_edge ) * ( max_vertex - min_vertex + 1 ) + ( tempv - min_vertex ); if ( ((tempe > minedge) || (tempe == minedge && tempv >= minvertex)) && isfrequent[location] ) //if leg potentially frequent { tempocc = occlist[s]; tempocc.nodeindex.push_back(t->v); **potential[location].occlist.push_back(tempocc);** if ( tempocc.tid != potential[location].lasttid ) { potential[location].lasttid = tempocc.tid; potential[location].support++; } } } } t = t->next; }//end of while ( t != 0 ) }//end of ( s = 0; ...) ( long s = 0; s < potential.size(); s++ ) { if ( potential[s].support >= threshold ) { ismaximal = false; //this tree cannot maximal short tempe = min_edge + (short)(floor(s/(max_vertex - min_vertex + 1))); short tempv = min_vertex + (s % (max_vertex - min_vertex + 1)); rdfcftree *pbfcf = new rdfcftree(*this,tempe,tempv,i); pbfcf->closedextensionexplore(frequency, outfile, database,potential[s].occlist, frequent2tree,headindex,threshold, checked, closed, maximal); delete pbfcf; } } ////test //cout << "leg position is: " << << " vertex label is: " << vertexlabel[i] << endl; //cout << "min edge , min vertex are: " << minedge << ' ' << minvertex << endl; //for ( j = 0; j < isfrequent.size(); j++ ) // cout << isfrequent[j] << ' '; //cout << endl; //cout << endl; }//end of for(short j = ...) /****************************************************************** step4: check if tree maximal ******************************************************************/ /****************************************************************** step4.1: if determined previous step not maximal ******************************************************************/ if ( isclosed == false || ismaximal == false) return; /****************************************************************** step4.2: check frequent parents ******************************************************************/ vector<long> tempvector(max_vertex-min_vertex+1,0); vector < vector <long> > countingmatrix(max_edge-min_edge+1,tempvector); long m = 0; long n = 0; while ( m < occlist.size() ) { n = m+1; while ( n < occlist.size() && occlist[n].tid == occlist[m].tid ) n++; n--; set<pair<short,short> > parentevpairs; short tempedge, tempvertex; ( long s = m; s <= n; s++ ) { if ( occlist[s].nodeindex[0] != 1 ) //if first occurrence's root //is not root of transaction { t = database[occlist[s].tid]->adj[occlist[s].nodeindex[0]]; while ( t->next != 0 ) t = t->next; tempedge = t->elabel; tempvertex = database[occlist[s].tid]->vertexlabel[t->v]; parentevpairs.insert(make_pair(tempedge,tempvertex)); } } set<pair<short,short> >::iterator pos2; ( pos2 = parentevpairs.begin(); pos2 != parentevpairs.end(); ++pos2 ) countingmatrix[pos2->first - min_edge][pos2->second - min_vertex]++; m = n+1; }//end of while ( m < ... ) bool tempflag = false; ( short = 0; < max_edge-min_edge+1; i++ ) { if ( tempflag == false ) { ( short j = 0; j < max_vertex - min_vertex+1; j++ ) { if ( countingmatrix[i][j] >= threshold ) { tempflag = true; break; } } } else break; } if ( tempflag == true ) //not maximal { ismaximal = false; return; } /****************************************************************** step4.3: check frequent new legs, @ place ******************************************************************/ ( short = 1; <= vcount; i++ ) { vector<long> tempvector2(max_vertex-min_vertex+1,0); vector < vector <long> > countingmatrix2(max_edge-min_edge+1,tempvector2); long m = 0; long n = 0; while ( m < occlist.size() ) { n = m+1; while ( n < occlist.size() && occlist[n].tid == occlist[m].tid ) n++; n--; set<pair<short,short> > legevpairs; short tempedge2, tempvertex2; ( long s = m; s <= n; s++ ) { neighbors.clear(); t = adj[i]; while ( t != 0 ) //insert index of neighbors of position { neighbors.insert(occlist[s].nodeindex[t->v - 1]);//inconsistency on index t = t->next; } t = database[occlist[s].tid]->adj[occlist[s].nodeindex[i-1]]; while ( t != 0 ) { if ( occlist[s].nodeindex[i-1] < t->v ) { pos = neighbors.find( t->v ); if ( pos == neighbors.end() ) //if vertex hasn't been used { tempedge2 = t->elabel; tempvertex2 = database[occlist[s].tid]->vertexlabel[t->v]; legevpairs.insert(make_pair(tempedge2,tempvertex2)); } } t = t->next; } }//end of ( long s = m; ... ) set<pair<short,short> >::iterator pos2; ( pos2 = legevpairs.begin(); pos2 != legevpairs.end(); ++pos2 ) countingmatrix2[pos2->first - min_edge][pos2->second - min_vertex]++; m = n+1; }//end of while ( m < ... ) bool tempflag2 = false; ( short k = 0; k < max_edge-min_edge+1; k++ ) { if ( tempflag2 == false ) { ( short j = 0; j < max_vertex - min_vertex+1; j++ ) { if ( countingmatrix2[k][j] >= threshold ) { tempflag2 = true; break; } } } else break; } if ( tempflag2 == true ) //not maximal { ismaximal = false; return; } }//end of ( short ... ) if ( ismaximal == true ) maximal[vcount]++; //cout << *this; //cout << "support is: " << occlist.size() << endl << endl; /* } how can understand causes problem? variable? thank much
you appear trying create vector 67,108,864 elements. fails because resulting allocation request unreasonably large.
i'll try increasing stack/heap limit "ulimit -s unlimited"
that unlikely (it not make allocation request smaller).
are expecting vector large? if not, need bug in algorithm.
update:
how see length of vector?
you can see in gdb output:
#7 0x000000000040bfdb in allocate (__n=67108864, this=) yes possible array becomes large because it's mining algorithm. can do?
i can't tell type of vector push_backing (you appear have screwed cut/paste, or edited gdb backtrace, and didn't tell line line 1280). chances are, element size quite large. may have store pointers elements in vector, instead of elements themselves.
Comments
Post a Comment