Pointer set to NULL but not in debugger

Question

So I am working o AVL tree, however I cant seem to either get the delete function working nor freeing the tree right. The delete function segfaults everytime, but the free function segfaults when in the debugger. Here is gdb's stack trace:

#0  0x00007fffd935a87a in msvcrt!_memicmp_l () from C:\WINDOWS\System32\msvcrt.dll
#1  0x0000000000402811 in isPresentRecurs (root=0xb756d0, searchedValue=0xb795b0 "aaa", found=0x61fcec) at ../.source/binTree.c:206
#2  0x00000000004027d6 in isPresent (root=0xb756d0, searchKey=0xb795b0 "aaa") at ../.source/binTree.c:200
#3  0x0000000000401c3d in main () at test.c:110

In my tests I check if the root has been set to NULL, which running it normally does finish however running it inside the debugger does not and instead goes into the else statement: Minimal Example (test.c):

#include "binTree.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define TRACE 0
#define MAX_SEARCH_ITEMS 20

void fillTree(binTree **tree);
void fillSearchValues( char **valArray);

void fillTree(binTree** tree){
    printf( "Constructing tree\n\n" );
    char key[200] ="";
    for(int j=1 ;j<4;j++ ){
        memset(&key,0,199);
        for(int i=0; i<26; i++){
            for(int k = 0;k<j;k++) key[k]= i+'a';
            Var value;
            value.data = malloc(sizeof(varData));
            value.data->iData = j;
            value.type =INTEGER;
            (*tree)->root= insert((*tree)->root,key,value);
           if(TRACE) printf("key: %s, value: %d\n",(*tree)->root->key,(*tree)->root->value.data->iData);
        }
    }
    (*tree)->nodeCount = getSizeBinaryTree((*tree)->root);
    printf( "\n\nTree constructed\n\n" );
}

void fillSearchValues( char **valArray){
    char key[200]="";
    for(int j=1 ;j<4;j++ ){
        memset(&key,0,199);
        for(int i=0; i<26; i++){
            if(i*j>MAX_SEARCH_ITEMS) break;
            for(int k = 0;k<j;k++) key[k]= i+'a';
            *(valArray+i*j) = strdup(key);
        if (TRACE)printf ("%s read; %s inserted\n", key, valArray[i*j] );
        }
    }
}

int main(){
    binTree *tree = createNewTree();
    fillTree(&tree);
    printTree(tree->root);

/*   //Fails at delete
    for(int i=0;i<26;i++){
        char string = i+'a';
        tree->root = Delete(tree->root,&string);
    }*/


    printf("\nFreeing Tree: \n=================================\n");
    freeTree(tree->root);

    if(tree->root==NULL) printf("Tree has been freed successfully\n");
    else printf("Failed to free tree \n");

     // searching after freeing 
    int found =0; int lost =0;
    char *values[MAX_SEARCH_ITEMS];
    fillSearchValues(values);

    for(int i=0;i<MAX_SEARCH_ITEMS;i++){
        if(isPresent(tree->root,values[i])){
            if (TRACE)printf("found search value %s\n",values[i]);
            found++;
        }else{
            lost++;
            if(TRACE)printf("didnot find search value %s\n",values[i]);
        }
    }
    printf("found %d of %d while cleared %d\n", found,MAX_SEARCH_ITEMS,lost);
    free(tree);
    return 0;
}

binTree.h:

#ifndef BINTREE_H
#define BINTREE_H

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

#define COUNT 10

typedef enum TYPE {INTEGER, FLOAT, CHARACTER} TYPE;

typedef union {
    float fData;
    int iData;
    char cData;
} varData;

typedef struct Var{
    varData * data;
    TYPE type;
} Var;

typedef struct Node{
    char* key;
    Var value;

    int height;
    struct Node *left;
    struct Node *right;
}Node;

typedef struct binTree{
    Node *root;
    unsigned int nodeCount;
}binTree;

int max(int a,int b);
binTree *createNewTree();
Node *newNode(char *key,Var value);
void freeTree(Node *node);
void freeNode(Node *node);
Node *insert(Node *node,char *key,Var value);
Node *rightRotate(Node *n);
Node *leftRotate(Node *n);
int height(Node *node);
int getBalance(Node *N);
void printTree(Node *root);
void printTreeS(Node *root,int space);
int isPresent(Node *root,char *searchKey);
void isPresentRecurs(Node *root,char *searchedValue,int *found);
Node *minValueNode(Node *node);
Node *search(Node *node,char *key);
Node *Delete(Node *root,char *key);
int getSizeBinaryTree(Node* root);


#endif

binTree.c

#include "binTree.h"

int max(int a, int b){
    return (a > b)? a : b;
}

binTree* createNewTree(){
    binTree *t = (binTree *) malloc(sizeof(binTree));
    if(!t){
          printf("Failed at allocationg tree\n");
          exit(-1);
    }
    t->root = NULL;
    return t;
}
Node* newNode(char * key,Var value){
    Node *p =  (Node*)malloc(sizeof(Node));
    if(!p){
         printf("Failed at allocationg node\n");
         exit(-1);
    }
    p->key = strdup(key);
    p->value = value;

    p->left=p->right=NULL;
    p->height = 1;
    return p;
}
void freeTree(Node* node){
    if (node==NULL) return;
    freeTree(node->left);
    freeTree(node->right);
    freeNode(node);
    node=NULL;
}
void freeNode(Node *node){
    free(node->value.data);
    node->value.data = NULL;
    free(node->key);
    node->key = NULL;
    free(node);
    node = NULL;
}

Node* insert(Node *node, char *key,Var value){
    if (node == NULL) return newNode(key,value);
    if ( strcasecmp(key ,node->key)<0) node->left = insert(node->left, key,value);
    else if (strcasecmp(key ,node->key)>0) node->right = insert(node->right, key,value);
    else if(strcasecmp(key,node->key)==0){
        if(memcmp(&value.data,&node->value,sizeof(Var))!=0){
            memcpy(&node->value,&value,sizeof(Var));
        }
        return node;
    };

    node->height = max(height(node->left),height(node->right))+1;

    int balance = getBalance(node);

    // Left Left Case
    if (balance > 1 && strcasecmp(key, node->left->key)<0)
        return rightRotate(node);

    // Right Right Case
    if (balance < -1 && strcasecmp(key, node->right->key)>0)
        return leftRotate(node);

    // Left Right Case
    if (balance > 1 && strcasecmp(key, node->left->key)>0){
        node->left =  leftRotate(node->left);
        return rightRotate(node);
    }

    // Right Left Case
    if (balance < -1 && strcasecmp(key,node->right->key)<0){
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node;
}

Node *rightRotate(Node *n){
    Node *leftNode =n->left;
    if(!leftNode) return n;
    Node *rightOfLeft =leftNode->right;

    leftNode->right = n;
    n->left = rightOfLeft;

    n->height = max(height(n->left), height(n->right)) + 1;
    leftNode->height = max(height(leftNode->left), height(leftNode->right)) + 1;

    return leftNode;
}

Node *leftRotate(Node *n){
     Node *rightNode = n->right;
     if(!rightNode) return n;
     Node *leftOfright = rightNode->left;

    rightNode->left = n;
    n->right = leftOfright;

    n->height = max(height(n->left), height(n->right)) + 1;
    rightNode->height = max(height(rightNode->left), height(rightNode->right)) + 1;

    return rightNode;
}

int height(Node *node){
    if (!node) return 0;
    return node->height;
}

int getBalance(Node *N){
    if (N == NULL) return 0;
    return height(N->left) - height(N->right);
}

void printTree(Node *root){
    printTreeS(root, 0);
}

void printTreeS( Node *root, int space){
    if (root == NULL)
        return;
    space += COUNT;
    printTreeS(root->right, space);
    printf("\n");
    for (int i = COUNT; i < space; i++) printf(" ");
    if (root->value.type == CHARACTER)printf("type:  CHAR key: %s value: %s\n", root->key, root->value.data->cData);
    if (root->value.type == INTEGER)printf("type: INT key: %s value: %d\n", root->key, root->value.data->iData);
    if (root->value.type == FLOAT)printf("type: FLOAT  key: %s value: %f\n", root->key, root->value.data->fData);
    printTreeS(root->left, space);
}

int isPresent(Node* root, char* searchKey){
        int found = 0;
        isPresentRecurs( root, searchKey, &found );
        return found;
}

void isPresentRecurs( Node *root,char *searchedValue,int* found ){
    if (root) {
        if (strcasecmp(root->key,searchedValue)==0)
            *found = 1;
        else {
            isPresentRecurs(root->left, searchedValue, found);
            if (!(*found))
                isPresentRecurs( root->right, searchedValue, found);
        }
    }
}

Node * minValueNode(Node* node){
    if(!node) return NULL;
    if(node->left )return minValueNode(node->left);
    return node;
}

Node *search(Node *node, char *key){
    if (node == NULL || strcmp(node->key, key)==0)return node;
    if (strcmp(node->key, key)<0) return search(node->right, key);
    return search(node->left, key);
}

int getSizeBinaryTree(Node* root){
    if (root) return 1 +getSizeBinaryTree( root->left ) + getSizeBinaryTree( root->right );
    else return 0;
}

Node* Delete(Node* root,char *key) {
    if (root==NULL) return root;
    else if (strcasecmp(key ,root->key)>0)      root->left =Delete(root->left,key);
    else if (strcasecmp(key ,root->key)<0)      root->right = Delete(root->right,key);
    else {
        if(root->right==NULL && root->left==NULL) {
            free(root);
            root = NULL;
        }
        else if(root->left!=NULL && root->right==NULL) {
            Node* temp = root->left;
            root = root->left;
            freeNode(temp);
        }
        else if(root->right!=NULL && root->left==NULL) {
            Node* temp = root->right;
            root = root->right;
            freeNode(temp);
        }
        else {
            Node* temp = minValueNode(root->right);
            root->key= temp->key;
            root->value = temp->value;
            root->right = Delete(root->right,temp->key);
        }
    }
    if(root==NULL) return root;

    root->height = 1 + max(height(root->left),height(root->right));
    int balance = getBalance(root);

    //Left Left Case
    if(balance > 1 && getBalance(root->left) >=0)   return rightRotate(root);

    // Right Right Case
    if(balance < -1 && getBalance(root->right) <=0) return leftRotate(root);

    // Left Right Case
    if(balance > 1 && getBalance(root->left) < 0)   {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }

    //Right Left Case
    if(balance < -1 && getBalance(root->right) > 0) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }
    return root;
}

You really need to convert it to minimal reproducible example — Eugene Sh.
– Eugene Sh., Commented Jun 4, 2020 at 21:56
please try to avoid redundant casts such as Node *rightNode =(Node*) n->right; . If there is a diagnostic message without the cast then that indicates some problem you need to fix , not silence . — M.M
– M.M, Commented Jun 4, 2020 at 21:59
@M.M there were no diagnostic messages, but to make sure I put casts. Will try a minimal example dunno how to compress it further, AVL code is usually long. — AM429
– AM429, Commented Jun 4, 2020 at 22:03
I would comment-out all the "Var" handling, and debug the underlying tree code. The code is not handling allocation failures. You'll lose marks for this. — Kingsley
– Kingsley, Commented Jun 4, 2020 at 22:10

M.M · Accepted Answer · 2020-06-04 23:05:31Z

1

This is a mistake:

freeTree(tree->root);

if(tree->root==NULL) printf("Tree has been freed successfully\n");
else printf("Failed to free tree \n");

C uses pass-by-value, so it is not possible for freeTree to set tree->root to NULL.

The line node = NULL; inside the freeTree function sets the function parameter (which is a copy of the argument), it does not modify the argument in the calling context.

The function does free the pointed-to memory, which renders all pointers to that memory indeterminate, so the test tree->root == NULL actually causes undefined behaviour by using an indeterminate value.

Your compiler should warn about a dead-store for node=NULL; , if you do not see a warning then try turning up the warning and/or optimization level in your compiler, or running a static analyzer such as clang-tidy. freeNode has a similar issue.

To fix the problem, either change the calling code, e.g. freeTree(tree->root); tree->root = NULL;, or you will have to use pass-by-pointer, i.e. pass the address of the node you want to free.

answered Jun 4, 2020 at 23:05

M.M

143k26 gold badges223 silver badges400 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

AM429 Over a year ago

void freeTree(Node** node){     if (node==NULL) return;     freeTree(&(*node)->left);     freeTree(&(*node)->right);     freeNode(node);     *node=NULL; } void freeNode(Node **node){     free((*node)->value.data);     (*node)->value.data = NULL;     free((*node)->key);     (*node)->key = NULL;     free(*node); }

changing the free code to this segfaults as well

M.M Over a year ago

@AM429 you want if (*node == NULL) return; too

Collectives™ on Stack Overflow

Pointer set to NULL but not in debugger

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related