Fehler bei Rückgabe einer Liste

[Ratlos (Gast)]

Hallo zusammen,

ich habe einen Fehler in einem Programm den ich einfach nicht finde. 
Vereinfacht gesagt ist die Aufgabe, aus einer Anzahl von gegebenen 
Werten eine Liste mit bestimmter Reihenfolge zu erstellen. Die Funktion 
besteht im Wesentlichen aus folgendem Code:

int16_t* generateList(int16_t *list_cnt){

    /* ****************************************************
    INITIALIZE VARIABLES
    **************************************************** */
    int16_t *list = NULL;
    *list_cnt = 0;

    int16_t *queue = NULL;
    int16_t queue_cnt = 0;
    int16_t queue_size = global_cnt.final + 1; /* Anzahl d. gegebenen Werte + 1 */

    int16_t previous[5]   = {0};
    int16_t previous_cnt  = 0;

    int16_t n = 0;
    int8_t considered = 0;
    int16_t currentEntry = 0;

    /* ****************************************************
    COPY THE FIRST ENTRIES QUEUE AND LIST
    **************************************************** */
    queue = calloc(queue_size, sizeof(int16_t));
    queue_cnt = global_cnt.final;
    for(n=0; n<global_cnt.final; n++){
        queue[n] = global.final[n]; /* Array mit gegebenen Werte */
    }

    *list_cnt = global_cnt.final;
    list = malloc((*list_cnt) * sizeof(int16_t));
    for(n=0; n < *list_cnt; n++){
        list[n] = global.final[n];
    }

    /* ****************************************************
    PROCESS THE DATA IN QUEUE
    **************************************************** */
    while(*list_cnt != global_cnt.states){

        considered = 0;
        currentEntry = queue[0];
        getPrevious(currentEntry, previous, &previous_cnt);

        if(previous_cnt != 0){
            /* check whether the entry was already mentioned */
            for(n=0; n<*list_cnt; n++){
                if(list[n] == previous[0]){
                    considered = 1;
                }
            } /* END: iterate over the list */

            /* Append new entry to list and queue */
            if(0 == considered){
                queue[queue_cnt] = previous[0];
                queue_cnt++;

                (*list_cnt)++;
                list = realloc(list, *list_cnt * sizeof(int16_t));
                list[*list_cnt - 1] = previous[0];

            } /* END: Entry is not considered yet */

        } /* END: There is a previous entry */


        /* ****************************************************
        REMOVE THE FIRST ENTRY IN QUEUE
        **************************************************** */
        if(queue_cnt > 1){
            for(n=1; n<queue_cnt; n++){
                queue[n-1] = queue[n];
            }
            queue[queue_cnt] = 0;
            queue_cnt--;
        }

puts("Ende While-Schleife");
free(queue);
/* return the generated list */
return list;
}

Aufgerufen wird das Ganze so:

    int16_t *list= NULL;
    int16_t list_cnt = 0;

    list= generateList(&list_cnt);
    puts("Back!");

Problem: die Liste wird richtig erstellt und die while Schleife 
verlassen (erkennbar an puts-Ausgabe). Danach stürzt das Programm ab. 
Die aufrufende Funktion wird nicht wieder erreicht.

Sieht jemand den Fehler?

Gruß

[Robert L. (lrlr)]

(ich kann nicht C)
aber

 list[n] =

ist "bin ich mir sicher" falsch..??

[Ratlos (Gast)]

Robert L. schrieb:
> (ich kann nicht C)
> aber
>
>  list[n] =
>
> ist "bin ich mir sicher" falsch..??

Wie bitte!?

[Peter II (Gast)]

es wird wohl ein überschreiber vom Speicher sein. Da wir aber die 
Variablen (z.b. global_cnt) nicht kennen, wird hier keiner helfen 
können.

[NurEinGast (Gast)]

um es besser nachvollziehen zu können,

was steht denn in global_cnt ?

[Ratlos (Gast)]

global_cnt ist eine Struktur der Form:

typedef struct {
    int16_t ...;
    int16_t ...;
    int16_t final;
    int16_t ...;
    int16_t ...;
} global_cnt_t;

Also nichts weltbewegendes..

[Peter II (Gast)]

Ratlos schrieb:
> Also nichts weltbewegendes..

und welche Werte stehen da drin

[Ratlos (Gast)]

In global_cnt.final steht '1' und In global.final[..] steht '13'. Das 
bedeutet global_cnt.x enthält die Anzahl der Einträge in global.x.

[Rufus Τ. F. (rufus)]

Ratlos schrieb:
> Problem: die Liste wird richtig erstellt und die while Schleife
> verlassen (erkennbar an puts-Ausgabe). Danach stürzt das Programm ab.
> Die aufrufende Funktion wird nicht wieder erreicht.

Und, hast Du das ganze mal im Debugger laufenlassen?

Wozu gibt es Debugger?

[Peter II (Gast)]

das sieht mir merkwürdig aus

queue[queue_cnt]

ich denke hier überschreibst du dir den stack.

[Karl H. (kbuchegg)]

Puh.
Der Code sieht mir reichlich kompliziert aus.
Auch wenn ich nicht so ganz raus habe, was das ganze soll, bin ich mir 
recht sicher, dass man das auch einfacher schreiben kann.

Zb. ist mir überhaupt nicht klar, wozu du da die queue brauchst.
So wie das aussieht, willst du von einer global verfügbaren Liste
  global.final / global_cnt.final;
alle Einträge holen, wobei du Duplikate eliminierst.

Was allerdings
getPrevious
in diesem Zusammenhang soll, ist nicht wirklich ersichtlich.

Ich denke, mit deinen vielen Variablen und ebensovielen counts hast du 
dir selbst ein Eigentor geschossen und dir irgendwo den Speicher 
zerschossen.
Das hier

            if(0 == considered){
                queue[queue_cnt] = previous[0];
                queue_cnt++;

ist mir zb suspekt. Leider ist nicht einfach nachvollziehbar, welche 
Werte queue_cnt im Laufe der Zeit annimmt. Wenn du aber über die 
allokierte Länge drüber kommst, dann ....

[Karl H. (kbuchegg)]

Das hier

    int16_t previous[5]   = {0};
    int16_t previous_cnt  = 0;

...
        getPrevious(currentEntry, previous, &previous_cnt);

ist zb auch gefährlich.

[Ratlos (Gast)]

@Karl Heinz:
Die Anwendung IST leider sehr komplex! getPrevious sucht aus einer 
Baumstruktur den Vorgänger des aktuellen Eintrags. Die Funktion habe ich 
getestet und für gut befunden... :-)

@Peter II:
Der Absturz kommt aber erst nach der while-Schleife und dem richtigen 
Erstellen der Liste!

@Rufus:
Nein, habe ich noch nicht. Was mich eben wundert ist, dass der Absturz 
bei der Rückgabe zu passieren scheint. Dementsprechend habe ich gehofft, 
das würde die Fehlersuche eingrenzen. Und richtig: ich kann (noch) nicht 
wirklich mit dem Debugger umgehen.

[Peter II (Gast)]

Ratlos schrieb:
> @Peter II:
> Der Absturz kommt aber erst nach der while-Schleife und dem richtigen
> Erstellen der Liste!

der Abstuzt erfolgt ja auch nicht beim überschreiben vom Speicher, 
sonder beim zugriff auf die fehlerhaften Daten.

Karl Heinz Buchegger  hat den gleichen code gefunden, er wird das 
Problem sein. Mache doch einfach mal die queue ein element größer und 
schau was dann passiert.

[Karl H. (kbuchegg)]

Ratlos schrieb:
> @Karl Heinz:
> Die Anwendung IST leider sehr komplex!

Das ist kein Grund, dass man sich nicht Teilsysteme schreiben kann, die 
sich um einen bestimmten Aspekt kümmern, anstatt alles in eine Funktion 
zu pappen.

ZB. ist es kein Problem sich ein Queue Modul zu schreiben, welches

struct queue
{
  int  cnt;
  int* values;
}

void Init( struct queue* object );
void Enqueue( struct queue* object, int newValue );
int  Dequeue( struct queue* object );
}

sich ausschlieeslich um die Belange einer queue, samt 
Speicherallokierung kümmert.
Damit hat man dann diese dynamisch Speicherverwaltung aus der Funktion 
schon mal weg und hat gleichtzeitig dann auch noch eine Codestelle, an 
der man Überprüfungen in die Debug Version einbauen kann.

[Ratlos (Gast)]

Ist diese Zeile richtig angewendet:

queue = calloc(queue_size, sizeof(int16_t));

Ich habe die Variable "queue_size" mal vergrößert. Es kommt zum selben 
Absturz. :-/

[Peter II (Gast)]

Ratlos schrieb:
> Ist diese Zeile richtig angewendet:queue = calloc(queue_size,
> sizeof(int16_t));

die zeile ist erstmal richtig, es fehlt aber überll die 
Fehlerbehandlung. Was ist wenn du keinen speicher mehr bekommst?

> Ich habe die Variable "queue_size" mal vergrößert. Es kommt zum selben
> Absturz. :-/
dann musst du dich doch mal mit dem Debugger vertraut machen, das blickt 
hier sonst keiner. Und uns ein vollständiges Testprogramm geben.

[Karl H. (kbuchegg)]

Ratlos schrieb:
> Ist diese Zeile richtig angewendet:
>

queue = calloc(queue_size, sizeof(int16_t));

Das ist grundsätzlich schon ok.
Die Frage ist, ob die allokierte Speichergröße reicht.
Das kann hier aber keiner sagen, weil die ja wiederrum von

    int16_t queue_size = global_cnt.final + 1; /* Anzahl d. gegebenen Werte + 1 */

abhängt.
Zudem ändert sich queue_cnt dann ja auch in Abhängigkeit der Daten

    queue_cnt = global_cnt.final;

und dann weiter wird queoe_cnt erniedrigt und erhöht, so dass ohne die 
Kentniss der Daten das auf dieser Seite des Bildschirms nicht 
nachvollziehbar ist, was passiert.

> Ich habe die Variable "queue_size" mal vergrößert.

Du betreibst Software-Entwicklung nach dem Prinzip der 'Hoffnung'.
Gerade bei dynamischen Datenstrukturen ist das keine gute Idee.

Wenn du schon deinen Code nicht aufräumst, dann spicke ihn wenigstens 
mit Ausgaben, so dass du am Papier nachvollziehen kannst, was passiert.

[Ratlos (Gast)]

Karl Heinz Buchegger schrieb:
> Wenn du schon deinen Code nicht aufräumst, dann spicke ihn wenigstens
> mit Ausgaben, so dass du am Papier nachvollziehen kannst, was passiert.

Schon geschehen, daher weiß ich ja, dass die Liste an sich richtig 
generiert wird. Ich die Ausgaben nur der Übersichtlichkeit halber hier 
rausgelöscht.

Okay, ich befürchte das Problem ist aus der Ferne nicht lösbar. Danke 
trotzdem.

[Karl H. (kbuchegg)]

Das hier wäre mir zb suspekt

    queue = calloc(queue_size, sizeof(int16_t));
    queue_cnt = global_cnt.final;


...


            /* Append new entry to list and queue */
            if(0 == considered){
                queue[queue_cnt] = previous[0];
                queue_cnt++;
....


        if(queue_cnt > 1){
            for(n=1; n<queue_cnt; n++){
                queue[n-1] = queue[n];
            }
            queue[queue_cnt] = 0;
            queue_cnt--;
        }

Du greifst da recht munter auf den Speicher zu, ohne dich darum zu 
kümmern, dass queue_cnt nicht größer/gleich als queue_size werden darf.
Wozu das 0-setzen in

            queue[queue_cnt] = 0;

bei korrektem Programm brauchst du es nicht, denn queue_cnt sagt wir 
sowieso immer, wieviele Einträge gültig sind. Alles was du tust ist, du 
läufst Gefahr auf ein nicht existentes queue Element zuzugreifen, wenn 
die Queue erst mal verlängert wurde, ehe das erste Element rausgenommen 
wurde.


Mein Tip:
Kapsle die Queue Funktionalität in eigene Funktionen. Das IST machbar! 
Und dort vergrößerst/verkleinerst du den Speicher für die Queue nach 
Bedarf, anstatt auf einer Default-Initialisierung zu bestehen, die je 
nach Datenlage dich in enorme Probleme bringen kann.

[DirkZ (Gast)]

Ratlos schrieb:
> Problem: die Liste wird richtig erstellt und die while Schleife
> verlassen (erkennbar an puts-Ausgabe). Danach stürzt das Programm ab.

Falsche Schlußfolgerung (die Liste wird richtig erstellt). Du weißt nur, 
dass Funktion bis zum Schluß durchläuft (puts-Ausgabe), dann das 
Programm abstürtzt.

Wenn

return list;

 auf einen ungültigen Speicherbereich verweist -> Absturz.

[Peter II (Gast)]

DirkZ schrieb:
> Wennreturn list; auf einen ungültigen Speicherbereich verweist ->
> Absturz.

nein, denn wohin ist zeigt ist absolut egal.

Das Problem ist das return, dabei wird er stack aufgeräumt. Und wenn der 
stack dabei übeschrieben wurde, dann stützt das Programm halt ab.

[Ratlos (Gast)]

Um das Thema noch mal kurz aufzuwärmen. Ich habe den Original-Code auf 
einem anderen System kompiliert und da geht es.

Fehlerhaft: Windows 7 64 Bit mit 32 Bit-MinGW
Fehlerfrei: Xubuntu 64 Bit   mit gcc

Kann man mit den Informationen den Fehler eingrenzen?

Gruß

[Peter II (Gast)]

Ratlos schrieb:
> Kann man mit den Informationen den Fehler eingrenzen?

nein.

Ich würde weiter den fehler suchen. Es muss einer drin sein. kannst du 
nicht eine lauffähiges Quellcode bereitstellenm, wo wir es eventuell 
nachvollziehen können.