Sehr obskurer bug mit pointern auf heap
-
Hallo alle.
(Nicht ganz so) Kurze Vorgeschichte was ich so programmiere:
Ich habe eine Klasse, die mir Konturlinien aus einem array von Daten extrahiert und diese dann in einer linked list speichert. So weit so gut. Für eine weitere Anwendung brauche ich die inneren Punkte einer Konturlinie, bisschen trickreicher, geht aber auch noch. Ein Problem gibt es bei der Behandlung von Sonderfällen, wie zum Beispiel daß die Kontur am Rand des Feldes offen ist, also z.B.X0000000000000 0XXXX000000000 00000X00000000 0000X000000000 00XX0000000000 XX000000000000wobei offensichtlich ist, welches der "eingeschlossene" Teil ist, wollte jetzt nur nicht riesig ASCII art einfügen. Um solche Fälle in den Griff zu kriegen habe ich eine Routine, die die Randpunkte der Kontur findet und zählt, in diesem Fall zwei. Diese beiden Punkte werden dann entlang des Randes miteinander verbunden, und man kann prima die inneren Punkte finden.
Es gibt natürlich noch mehr Sonderfälle, die ich als "falsche" Randpunkte bezeichne, zum Beispiel
X0000000000000 0XXXX000000000 00000X00000000 0000X000000000 00XX0000000000 XX000000000000 [b]X[/b]0000000000000 [b]X[/b]0000000000000 [b]X[/b]0000000000000Die fetten Punkte sind doppelte Randpunkte. Um Fehler zu vermeiden, entferne ich die in einer Subroutine, so daß das Bild dann wie oben aussieht.
Die Randpunkte sind ursprünglich in einem array gespeichert, das pointer auf die Punkte (= elemente der linked list) enthält. Wenn ich die Randpunkte entferne, werden die Einträge in dem array auf nullpointer gesetzt, um anzuzeigen, daß dieser Punkt schon entfernt wurde. Nachdem ich alle falschen Punkte entfernt habe (klappt auch so weit), möchte ich die Einträge in ein kürzeres array speichern, daß nur noch "echte" Randpunkte enthält, so daß ich nicht dauernd auf nullpointer prüfen muss.
Eigentliches Problem/Bug:
Ich habe eine Schleife, die das ursprüngliche array durchläuft und alle nicht-null Pointer in ein neues array der richtigen Länge kopiert (habe vorher mitgezählt). Bei genau diesem Prozess verändern sich scheinbar Membervariablen eines Punktes (der auf dem heap liegt und über einen Pointer zugänglich ist), wie kann das sein?if(verbose)cerr << "extrablatt: " << rPP[3] << endl; if(verbose)cerr << "extrablatt: " << rPP[3]->getX() << "," << rPP[3]->getY() << endl;produziert mir noch den richtigen output
extrablatt: 0xa898b28 extrablatt: 0, 235aber bei der unmittelbar darauf folgenden Schleife
us j=0; for(us i=0; i<numberRimPoints; i++){ if(verbose){cerr << "checking rPP["<<i<<"]"; if(rPP[i] != 0){cerr << ": it's the point " << rPP[i]->getX() << ", " << rPP[i]->getY() << endl; } } if(rPP[i] != 0){ trueRPP[j] = rPP[i]; j++; } }ist der output dann auf einmal
checking rPP[0]: (...korrekte Werte...) ... checking rPP[3]: it's the point 35584, 2679obwohl die Speicheradresse die in rPP[3] abgelegt ist (z.B. 0xa898b28) exakt gleich bleibt (habe ich nachgeprüft). Die getX() und getY() sind einfache getter, ändern gar nichts.
Irgendjemand ne Idee?
-
ich schätze hier müssen wir erheblich mehr code sehen, um das beurteilen zu können. insbesondere auch die definition aller variablen und deren typen.
-
Entschuldige, daß ich die deklarationen nicht reinkopiert habe:
const point ** rPP = new const point * [numberRimPoints];
const point ** trueRPP = new const point * [trueNumberRP];Die einzigen relevanten typedefs sind hier real -> float und us -> unsigned short.
Was weiteren code angeht, ich möchte nicht alles alles posten, einfach weil das massig viel Zeug ist. Ich poste mal die subroutine, die falsche Randpunkte entfernt (die ganzen "if(verbose)" Geschichten benutze ich zum debuggen):
void contour::closeContour(us lenX, us lenY, short verbose){ //If it is necessary, this routine connects rim points, so that the inner points of a contour //touching the border of the picture can be properly recognized. //- neighbouring rim points don't need to be closed, and removing one will not change the resulting inner points //- if there is an odd number of rim points, remove the one that is furthest away from the rest // (although there can be cases where this leads to a wrong pixel being removed, it should not prevent // detection of true phase singularities) //After surplus rim points have been removed, the remaining ones are connected using a greed strategy: //test all couples, connect the shortest distance possible, remove the used points and test the rest again if(verbose){ cerr << "entered closeContour (enter)" << endl; } us numberRimPoints = countRimPoints(lenX, lenY); if(verbose){cerr << "numberRimPoints " << numberRimPoints << endl; cin.get();} if(verbose == -1 && numberRimPoints>=4)verbose = 1; if(verbose == -1 && numberRimPoints<4)verbose = 0; if(numberRimPoints >=2){ //if(verbose){cerr << "Interesting contour being closed: number of rim points is " << numberRimPoints << endl;cin.get();} const point ** rPP = new const point * [numberRimPoints]; us rimcounter = 0; const point * p = start; while(rimcounter < numberRimPoints && p){ if(p->getX() == 0 || p->getX()== lenX-1 || p->getY() == 0 || p->getY()== lenY-1){ rPP[rimcounter] = p; rimcounter++; } p = p->getNext(); } if(verbose){ cerr << numberRimPoints << " entering: " << endl; for(short s=0; s<numberRimPoints; s++){ if(rPP[s]){ cerr << "[" << s << "]: "<< rPP[s] <<" :("<< rPP[s]->getX() << "," << rPP[s]->getY() << ")" << ", "; }else{ cerr << "[" << s << "]: " << rPP[s] << " (null)" << endl; } }cerr << endl; cin.get(); } //got all raw rim points in array now us trueNumberRP=0; us tempNumberRimPoints = numberRimPoints; //cerr << "removing double rims" << endl; //remove double rim points for(us i=0; i<numberRimPoints; i++){ if(rPP[i]==0){continue;} for(us j=i+1; j<numberRimPoints; j++){ if(rPP[j] == 0 || rPP[i] == 0){continue;} if(rPP[i]->getDistanceTo(rPP[j]) < real(1.3)){ //found neighbouring rim points //check which one has the shorter connection to a different rim point //erase the other if(verbose){cerr << "searching for double rimpoint to erase" << endl; cin.get();} real minDistanceI = real(lenX+lenY); for(us k=0; k<numberRimPoints; k++){ if(rPP[k]==0 || k == i || k == j)continue; if(rPP[i]->getDistanceTo(rPP[k]) < minDistanceI){ minDistanceI = rPP[i]->getDistanceTo(rPP[k]); } } real minDistanceJ = real(lenX+lenY); for(us k=0; k<numberRimPoints; k++){ if(rPP[k]==0 || k == i || k == j)continue; if(rPP[j]->getDistanceTo(rPP[k]) < minDistanceJ){ minDistanceJ = rPP[j]->getDistanceTo(rPP[k]); } } //exclude the case with only 2 points //(no other point is nearer than the default minDistance) if(!(minDistanceI == real(lenX+lenY))){ if(minDistanceJ < minDistanceI){ if(verbose)cerr << "removing double rim at coords " << rPP[i]->getX() << ", " << rPP[i]->getY() << endl; removePoint(rPP[i]->getX(), rPP[i]->getY()); rPP[i] = 0; tempNumberRimPoints--; }else{ if(verbose)cerr << "removing double rim at coords " << rPP[j]->getX() << ", " << rPP[j]->getY() << endl; removePoint(rPP[i]->getX(), rPP[i]->getY()); rPP[j] = 0; tempNumberRimPoints--; } } } } } //cerr << "removing furthest odd" << endl; //uneven number of remaining rim points: remove the one furthest away from any other rim point if(tempNumberRimPoints%2 == 1){ real currentNearestDistance; real globalFarthestNearest = 0; us loser; for(us i=0; i<numberRimPoints; i++){ if(rPP[i]==0)continue; currentNearestDistance = real(lenX+lenY); for(us j=0; j<numberRimPoints; j++){ if(rPP[j]==0 || i==j) continue; if(rPP[i]->getDistanceTo(rPP[j]) < currentNearestDistance){ currentNearestDistance = rPP[i]->getDistanceTo(rPP[j]); } } if(currentNearestDistance > globalFarthestNearest){ globalFarthestNearest = currentNearestDistance; loser = i; } } if(verbose)cerr << "removing odd rim at coords " << rPP[loser]->getX() << ", " << rPP[loser]->getY() << endl; removePoint(rPP[loser]->getX(), rPP[loser]->getY()); rPP[loser]=0; tempNumberRimPoints--; } //count remaining rim points and transfer them to new array for(us i=0; i<numberRimPoints; i++){ if(rPP[i]){trueNumberRP++;} } const point ** trueRPP = new const point * [trueNumberRP]; if(trueRPP) if(verbose){ cerr << numberRimPoints << " pre transcription: " << endl; for(short s=0; s<numberRimPoints; s++){ if(rPP[s]){ cerr << "[" << s << "]: "<< rPP[s] <<" :("<< rPP[s]->getX() << "," << rPP[s]->getY() << ")" << ", "; }else{ cerr << "[" << s << "]: " << rPP[s] << " (null)" << endl; } }cerr << endl; cin.get(); } if(verbose)cerr << "extrablatt: " << rPP[3] << endl; if(verbose)cerr << "extrablatt: " << rPP[3]->getX() << "," << rPP[3]->getY() << endl; us j=0; for(us i=0; i<numberRimPoints; i++){ if(verbose){cerr << "checking rPP["<<i<<"]"; if(rPP[i] != 0){ cerr << ": it's the point " << rPP[i]->getX() << ", " << rPP[i]->getY() << endl; } } if(rPP[i] != 0){trueRPP[j] = rPP[i]; j++;} } if(verbose){ cerr << numberRimPoints << " post transcription: " << endl; for(short s=0; s<numberRimPoints; s++){ if(rPP[s])cerr << "[" << s << "]: ("<< rPP[s]->getX() << "," << rPP[s]->getY() << ")" << ", "; }cerr << endl; cin.get(); } numberRimPoints = trueNumberRP; delete [] rPP; rPP = trueRPP; (...code zum schließen der kontur...) }
-
das ist ein wenig zu kompliziert, um das hier bereits zu übersehen. wenn du willst, kannst du mir kompilierbaren code per email schicken, und ich schaue es mir dann an.
-
Vielen Dank für das Angebot, aber das wird problematisch... um das Programm laufen zu lassen braucht man die ganzen Rohdaten, über denen diese Konturerkennung läuft und das sind 100MB+ (die ich noch dazu nicht weitergeben sollte
).Ich hatte in der Hauptsache auf allgemeine Antworten gehofft, wie "ach ja, das könnte xyz-overflow sein, das passiert wenn man abc macht". Naja, ich wende mich dann wohl erstmal wieder anderen Aspekten zu und komme irgendwann zu diesem Problem zurück. Vielleicht wird ein rewrite fällig, vielleicht komm ich aber auch noch drauf was es ist.
Vielen Dank für alle bisherigen Antworten, und falls jemand ne Idee hat was da passieren _könnte_, nur her damit.
-
die drei ??? schrieb:
Ich hatte in der Hauptsache auf allgemeine Antworten gehofft, wie "ach ja, das könnte xyz-overflow sein, das passiert wenn man abc macht".
das kann im prinzip schon sein. das problem ist einfach das, dass das ganze ein massives refactoring gebrauchen könnte. in monsterfunktionen voll mit low-level code liest man sich eben nicht gerne hinein
-
Hi nochmal.
Die Geschichte hat sich erledigt, es war wohl irgendeine Art heap overflow. Ich habe die heap-Variablen durch stack-Variable ersetzt (sind klein genug) -> funktioniert. Auf zum nächsten Bug!