[C] Segmentation Fault

[Osyriis_]

Salve! Spero di aver aperto la discussione in modo giusto. Ho bisogno di aiuto.
Dunque sto implementando un Binary Search Tree con inserimento e ricerca, e fin qui tutto bene, dopo di che mi è stato chiesto di implementare anche una versione modificata della ricerca che dovrebbe stampare a video tutti i numeri presenti nell'albero compresi fra k1 e k2(valori forniti dall'utente in input). Ora il problema è proprio qui, a un certo punto va in segmentation fault ma non riesco a capire quale sia il problema in quanto il codice è identico allo pseudocodice fornito. Vi metto qui di seguito il pezzo di codice in questione(chiedo scusa nel caso fosse molto ma continua a sbucarmi il segmentation sempre in un punto diverso).

void withinRange(BST **root, int k1, int k2){
    BST *x = (BST*)malloc(sizeof(BST));
    BST *y = (BST*)malloc(sizeof(BST));
    if(k1 == k2){
        printf("%d\n", k1);
        return;
    }
    *x = BSTsearch(&root, k1);
    *y = BSTsearch(&root, k2);
    printf("%d\n", x->data);
    while(!found){
        inOrderTreeWalkWithCheck(&root, x->right, y);
        *x = treeSuccessorAsAncestor(&root, x);
        if ( x == y ){
            found = 1;
        }
        if ((x != NULL) && (!found)){
            printf("%d\n", x->data);
        }
    }
    printf("%d\n", y->data);
    found = 0;
}

void inOrderTreeWalkWithCheck(BST **root, BST *x, BST *y){
    if (x != NULL){
        if(x == y){
            inOrderTreeWalk(y);
            found = 1;
            return;
        }
    }else{
        inOrderTreeWalkWithCheck(&root, x->left, y);
        if(!found){
            printf("%d\n", x->data);
            inOrderTreeWalkWithCheck(&root, x->right, y);
        }
    }
}

void inOrderTreeWalk(BST *y){
    if(y != NULL){
        inOrderTreeWalk(y->left);
        printf("%d\n", y->data);
        inOrderTreeWalk(y->right);
    }
}

BST treeSuccessorAsAncestor(BST **root, BST *x){
    BST *y = (BST*)malloc(sizeof(BST));
    y = x->parent;
    while ((y != NULL) && (x == y->right)){
        x = y;
        y = y->parent;
    }
    return *y;
}

attualmente si blocca al while della funzione treeSuccessorAsAncestor, ho provato a modificare le condizioni ma nulla.

[wingman87]

Scusa ma non ho avuto tempo di analizzare fino in fondo tutto il codice, ti scrivo quello che ho notato.

Nel metodo inOrderTreeWalkWithCheck accedi agli attributi di x nel ramo else in cui x è sicuramente NULL.

Note a parte non legate al segmentation fault:
* Ci sono dei malloc ma non ci sono free, quindi si creano dei memory leak.
* Ci sono delle variabili globali (found), e questo rende difficile seguire il flusso.

[Kaya]

Un altro consiglio: COMMENTA.
Metti i commenti al codice che per quanto possa sembrare banale torna sempre utile quando poi ci metti mano..

[Osyriis_]

Originariamente inviato da wingman87

Scusa ma non ho avuto tempo di analizzare fino in fondo tutto il codice, ti scrivo quello che ho notato.

Nel metodo inOrderTreeWalkWithCheck accedi agli attributi di x nel ramo else in cui x è sicuramente NULL.

Note a parte non legate al segmentation fault:
* Ci sono dei malloc ma non ci sono free, quindi si creano dei memory leak.
* Ci sono delle variabili globali (found), e questo rende difficile seguire il flusso.

Ho corretto l'else in inOrderTreeWalkWithCheck che chiaramente andava con if (x == y), ora mi da segmentation fault su x->left della prima chiamata ricorsiva all'interno dell'else.

Per quanto riguarda i malloc aggiungo immediatamente i free che ho completamente scordato.
Found mi è stata richiesta come una variabile globale settata a 0, che comunque viene usata per la prima volta all'interno di withinrange

[wingman87]

BST come è definito? Puoi riportare tutto il codice aggiornato?

[Osyriis_]

Originariamente inviato da wingman87

BST come è definito? Puoi riportare tutto il codice aggiornato?

E' un po' lungo, spero non sia un problema.
Ho anche scoperto che se inserisco k1 e k2 uguali il programma va senza problemi, va in segmentation sono quando sono diversi.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>

#define NUMOP 500

int found = 0;

typedef struct BST{
	int data;
	struct BST* parent;
	struct BST* left;
	struct BST* right;
} BST;

BST* root = NULL;

BST newNode(int value);
BST BSTinsert(BST **root, int value);
BST BSTsearch(BST *x, int value);
void withinRange(BST **root, int k1, int k2);
void inOrderTreeWalkWithCheck(BST **root, BST *x, BST *y);
void inOrderTreeWalk(BST *y);
BST treeSuccessorAsAncestor(BST **root, BST *x);

int main(){
    clock_t start, end;
    int iterazione, k1, k2, i;
    double BST=0, BSTS=0, BSTW=0;
    double mediaBST;
    FILE * risultatiBST;

    srand(1);

    risultatiBST=fopen("risultatiBST.txt","w");
	if (risultatiBST==NULL)
	{
        printf ("ERRORE nell'apertura del file");
        return(1);
	}

    printf ("Inserisci k1: ");
    scanf ("%d", &k1);
    printf("Inserisci k2:");
    scanf("%d", &k2);
    printf ("BST\n");

    int inserimento, ricerca, withinrange;
    for(i = 1; i<=NUMOP; i++){
        inserimento=(70*NUMOP)/100;
        start = clock();
        for (iterazione = 1; iterazione <= inserimento; iterazione++){
            int value = rand();
            BSTinsert(&root, value);
            //end = clock();
        }

        ricerca = (15*NUMOP)/100;
        for(iterazione = 1; iterazione<=ricerca; iterazione++){
            //start = clock();
            int value = rand();
            BSTsearch(&root, value);
            //end = clock();
            //BSTS = BSTS + (double) (end-start)/CLOCKS_PER_SEC;
        }

        withinrange = (15*NUMOP)/100;
        for(iterazione = 1; iterazione <= withinrange; iterazione++){
            //start = clock();
            withinRange(&root, k1, k2);
            //BSTW = BSTW + (double) (end-start)/CLOCKS_PER_SEC;
        }
        end = clock();
        BST = BSTW + (double) (end-start)/CLOCKS_PER_SEC;

        mediaBST=BST/NUMOP;
        printf ("%d\t %f\n",i, mediaBST);
        fprintf(risultatiBST,"%d\t %f\n", i, mediaBST);
    }

    fclose(risultatiBST);

}

BST newNode(int value){
    BST *temp = (BST*)malloc(sizeof(BST));

    temp->data = value;

    temp->left = NULL;
    temp->right = NULL;
    free(temp);
    return *temp;
}

// A utility function to insert a new
// Node with given key in BST
BST BSTinsert(BST **root, int value)
{
    // Create a new Node containing
    // the new element
    BST *newnode = (BST*)malloc(sizeof(BST));
    *newnode = newNode(value);

    // Pointer to start traversing from root and
    // traverses downward path to search
    // where the new node to be inserted
    BST *x = root;

    // Pointer y maintains the trailing
    // pointer of x
    BST *y = NULL;

    while (x != NULL) {
        y = x;
        if (value < x->data)
            x = x->left;
        else
            x = x->right;
    }

    // If the root is NULL i.e the tree is empty
    // The new node is the root node
    if (y == NULL)
        y = newnode;

    // If the new key is less then the leaf node key
    // Assign the new node to be its left child
    else if (value < y->data)
        y->left = newnode;

    // else assign the new node its right child
    else
        y->right = newnode;

    // Returns the pointer where the
    // new node is inserted
    return *y;
}

BST BSTsearch(BST *x, int value){
	if ((x == NULL) || (x->data = value)){
        return *x;
	}
	if(value<x->data){
        return BSTsearch(x->left, value);
    }else{
        return BSTsearch(x->right, value);
    }
}


//withinRange
void withinRange(BST **root, int k1, int k2){
    BST *x = (BST*)malloc(sizeof(BST));
    BST *y = (BST*)malloc(sizeof(BST));
    if(k1 == k2){
        printf("%d\n", k1);
        return;
    }
    *x = BSTsearch(&root, k1);
    *y = BSTsearch(&root, k2);
    printf("%d\n", x->data);
    while(!found){
        inOrderTreeWalkWithCheck(&root, x->right, y);
        *x = treeSuccessorAsAncestor(&root, x);
        if ( x == y ){
            found = 1;
        }
        if ((x != NULL) && (!found)){
            printf("%d\n", x->data);
        }
    }
    printf("%d\n", y->data);
    found = 0;
    free(x);
    free(y);
}

void inOrderTreeWalkWithCheck(BST **root, BST *x, BST *y){
    if (x != NULL){
        if(x == y){
            inOrderTreeWalk(y);
            found = 1;
            return;
        }else{
            inOrderTreeWalkWithCheck(&root, x->left, y);
            if(!found){
                printf("%d\n", x->data);
                inOrderTreeWalkWithCheck(&root, x->right, y);
            }
        }
    }
}

void inOrderTreeWalk(BST *y){
    if(y != NULL){
        inOrderTreeWalk(y->left);
        printf("%d\n", y->data);
        inOrderTreeWalk(y->right);
    }
}

BST treeSuccessorAsAncestor(BST **root, BST *x){
    BST *y = (BST*)malloc(sizeof(BST));
    y = x->parent;
    while ((y != NULL) && (x == y->right)){
        printf("ciao");
        x = y;
        y = y->parent;
    }
    free(y);
    return *y;
}

[Lampo89]

Originariamente inviato da Osyriis_

E' un po' lungo, spero non sia un problema.
Ho anche scoperto che se inserisco k1 e k2 uguali il programma va senza problemi, va in segmentation sono quando sono diversi.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>

#define NUMOP 500

int found = 0;

typedef struct BST{
	int data;
	struct BST* parent;
	struct BST* left;
	struct BST* right;
} BST;

BST* root = NULL;

BST newNode(int value);
BST BSTinsert(BST **root, int value);
BST BSTsearch(BST *x, int value);
void withinRange(BST **root, int k1, int k2);
void inOrderTreeWalkWithCheck(BST **root, BST *x, BST *y);
void inOrderTreeWalk(BST *y);
BST treeSuccessorAsAncestor(BST **root, BST *x);

int main(){
    clock_t start, end;
    int iterazione, k1, k2, i;
    double BST=0, BSTS=0, BSTW=0;
    double mediaBST;
    FILE * risultatiBST;

    srand(1);

    risultatiBST=fopen("risultatiBST.txt","w");
	if (risultatiBST==NULL)
	{
        printf ("ERRORE nell'apertura del file");
        return(1);
	}

    printf ("Inserisci k1: ");
    scanf ("%d", &k1);
    printf("Inserisci k2:");
    scanf("%d", &k2);
    printf ("BST\n");

    int inserimento, ricerca, withinrange;
    for(i = 1; i<=NUMOP; i++){
        inserimento=(70*NUMOP)/100;
        start = clock();
        for (iterazione = 1; iterazione <= inserimento; iterazione++){
            int value = rand();
            BSTinsert(&root, value);
            //end = clock();
        }

        ricerca = (15*NUMOP)/100;
        for(iterazione = 1; iterazione<=ricerca; iterazione++){
            //start = clock();
            int value = rand();
            BSTsearch(&root, value);
            //end = clock();
            //BSTS = BSTS + (double) (end-start)/CLOCKS_PER_SEC;
        }

        withinrange = (15*NUMOP)/100;
        for(iterazione = 1; iterazione <= withinrange; iterazione++){
            //start = clock();
            withinRange(&root, k1, k2);
            //BSTW = BSTW + (double) (end-start)/CLOCKS_PER_SEC;
        }
        end = clock();
        BST = BSTW + (double) (end-start)/CLOCKS_PER_SEC;

        mediaBST=BST/NUMOP;
        printf ("%d\t %f\n",i, mediaBST);
        fprintf(risultatiBST,"%d\t %f\n", i, mediaBST);
    }

    fclose(risultatiBST);

}

BST newNode(int value){
    BST *temp = (BST*)malloc(sizeof(BST));

    temp->data = value;

    temp->left = NULL;
    temp->right = NULL;
    free(temp);
    return *temp;
}

// A utility function to insert a new
// Node with given key in BST
BST BSTinsert(BST **root, int value)
{
    // Create a new Node containing
    // the new element
    BST *newnode = (BST*)malloc(sizeof(BST));
    *newnode = newNode(value);

    // Pointer to start traversing from root and
    // traverses downward path to search
    // where the new node to be inserted
    BST *x = root;

    // Pointer y maintains the trailing
    // pointer of x
    BST *y = NULL;

    while (x != NULL) {
        y = x;
        if (value < x->data)
            x = x->left;
        else
            x = x->right;
    }

    // If the root is NULL i.e the tree is empty
    // The new node is the root node
    if (y == NULL)
        y = newnode;

    // If the new key is less then the leaf node key
    // Assign the new node to be its left child
    else if (value < y->data)
        y->left = newnode;

    // else assign the new node its right child
    else
        y->right = newnode;

    // Returns the pointer where the
    // new node is inserted
    return *y;
}

BST BSTsearch(BST *x, int value){
	if ((x == NULL) || (x->data = value)){
        return *x;
	}
	if(value<x->data){
        return BSTsearch(x->left, value);
    }else{
        return BSTsearch(x->right, value);
    }
}


//withinRange
void withinRange(BST **root, int k1, int k2){
    BST *x = (BST*)malloc(sizeof(BST));
    BST *y = (BST*)malloc(sizeof(BST));
    if(k1 == k2){
        printf("%d\n", k1);
        return;
    }
    *x = BSTsearch(&root, k1);
    *y = BSTsearch(&root, k2);
    printf("%d\n", x->data);
    while(!found){
        inOrderTreeWalkWithCheck(&root, x->right, y);
        *x = treeSuccessorAsAncestor(&root, x);
        if ( x == y ){
            found = 1;
        }
        if ((x != NULL) && (!found)){
            printf("%d\n", x->data);
        }
    }
    printf("%d\n", y->data);
    found = 0;
    free(x);
    free(y);
}

void inOrderTreeWalkWithCheck(BST **root, BST *x, BST *y){
    if (x != NULL){
        if(x == y){
            inOrderTreeWalk(y);
            found = 1;
            return;
        }else{
            inOrderTreeWalkWithCheck(&root, x->left, y);
            if(!found){
                printf("%d\n", x->data);
                inOrderTreeWalkWithCheck(&root, x->right, y);
            }
        }
    }
}

void inOrderTreeWalk(BST *y){
    if(y != NULL){
        inOrderTreeWalk(y->left);
        printf("%d\n", y->data);
        inOrderTreeWalk(y->right);
    }
}

BST treeSuccessorAsAncestor(BST **root, BST *x){
    BST *y = (BST*)malloc(sizeof(BST));
    y = x->parent;
    while ((y != NULL) && (x == y->right)){
        printf("ciao");
        x = y;
        y = y->parent;
    }
    free(y);
    return *y;
}

A prima vista nella funzione newNode c'è un use-after-free: allochi un nuovo nodo nella heap, inizializzi tutto e poi deallochi la memoria, ma ritorni by value una copia della nodo che hai appena deallocato.

Direi che ci sono già qui potenziali problemi di accesso alla memoria nella costruzione dell'albero.

Ps: Sinceramente, ad un primo sguardo a qualche implementazione e alle interfacce, temo che ci siano inoltre altri leaks di memoria e problemi in genere. Purtroppo è risaputo che il linguaggio C richiede molta attenzione da questo punto di vista.
Secondo me conviene che se studi una implementazione di un binary search tree già fatta da altri (ad es. https://github.com/fbuihuu/libtree) per avere una buona base di partenza, prendendo spunti per riscriverla e estenderla per risolvere il tuo problema.

[wingman87]

Aggiungo:
1) alla riga 144, nella funzione BSTsearch: non puoi restituire *x se x == NULL
devi prendere in considerazione il fatto che BSTsearch potrebbe non trovare il valore cercato e quindi deve poter restituire NULL. Per farlo il tipo restituito non può essere BST ma deve essere BST* (con tutte le modifiche che questo implica)

2) nella funzione treeSuccessorAsAncestor c'è lo stesso problema indicato da Lampo89 per la funzione newNode (use-after-free)