Segmentation Fault (core dumped) during Red-Black tree "correction" - C

Question

Code is as follows:

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

typedef struct node
{
    unsigned long int val;
    bool black;
    struct node* parent;
    struct node* lchild;
    struct node* rchild;
}mynode;

mynode* createNode(unsigned long int ival, mynode* father);
mynode* createLeaf(unsigned long int ival, mynode* father);
mynode* search (unsigned long int ival, mynode *root);
void insert ( unsigned long int ival, mynode *root);
mynode * getFather (mynode* child);
mynode * getUncle (mynode* child);
void doubleRotate (mynode* myptr);
void rotate(mynode* myptr);
void myRotate(mynode* myptr);
void changeRed(mynode* myptr);
void changeBlack(mynode* myptr);
void colorFlip( mynode* myptr);
void subtreeRepair (mynode* myptr);
bool isRoot(mynode* myptr);
void rootRepair (mynode* myptr);
void repair (mynode* myptr);
bool isRed (mynode* myptr);
void smallRotate(mynode* myptr);


int main()
{
    mynode myroot;
    mynode *myrootptr;
    mynode *myleafptr;
    FILE *fp;
    int ch;
    unsigned long long lines=0, i=0;
    unsigned long *myArr;
    unsigned long int ival;

   fp = fopen("integers.txt","r");
   if(fp == NULL)
   {
      printf("Error in opening file.");
      return(-1);
   }

    while(!feof(fp))
    {
    ch = fgetc(fp);
    if(ch == '\n')
    {
        lines++;
    }
    }
    lines++;
    printf("lines = %lu", lines);
    myArr = (unsigned long*)calloc(lines, sizeof(unsigned long));

    fseek(fp, 0, SEEK_SET);
    while(!feof(fp))
    {
          fscanf(fp, "%lu,", &myArr[i] ); // des ta pos k giati tou input.
          i++;
    }
    fclose(fp);

    myroot.val = myArr[0];
    myroot.parent = NULL;
    myroot.lchild = NULL;
    myroot.rchild = NULL;
    myroot.black = true;
    myrootptr = &myroot;
    myleafptr = createLeaf(myrootptr->val, myrootptr);
    myrootptr->lchild = myleafptr;
    myleafptr = createLeaf(myrootptr->val, myrootptr);
    myrootptr->rchild = myleafptr;
    for(i=1; i<lines; i++)
    {
        ival = myArr[i];
        insert(ival, myrootptr);
    }

    return 0;
}

mynode* createNode(unsigned long int ival, mynode* father)
{
  mynode* nodeptr = (mynode* )malloc(sizeof(mynode));
  nodeptr->val = ival;
  nodeptr->lchild = NULL;
  nodeptr->rchild = NULL;
  nodeptr->parent = father;
  nodeptr->black = false;
  return nodeptr;
}

mynode* createLeaf(unsigned long int ival, mynode* father)
{
  mynode* leafptr = (mynode* )malloc(sizeof(mynode));
  leafptr->val = ival;
  leafptr->lchild = NULL;
  leafptr->rchild = NULL;
  leafptr->parent = father;
  leafptr->black = true;
  return leafptr;
}

mynode* search (unsigned long int ival, mynode *rootptr)
{
    mynode* myptr = (mynode* )malloc(sizeof(mynode));

    myptr = rootptr;

    while ( ( (myptr->lchild) != NULL) && ( (myptr->rchild) != NULL))
    {
        if ( ival < myptr->val)
        {
            myptr = myptr->lchild;
        }
        else
        {
            myptr = myptr->rchild;
        }
    }
    return myptr;
    }

void insert (unsigned long int ival, mynode *root)
{
    mynode * current = (mynode* )malloc(sizeof(mynode));
    mynode * insertleafptr = (mynode* )malloc(sizeof(mynode));
    mynode * father = (mynode* )malloc(sizeof(mynode));
    unsigned long int max, min;
    unsigned long int num;

    current = search(ival, root);
    num = current->val;
    if((current->val) == ival)
    {
        return ;
    }
    else
    {
        if(ival>(current->val))
        {
            max = ival;
            min = current->val;
        }
        else
        {
            max = current->val;
            min = ival;
        }
        father = current->parent;
        current = createNode(min, father);
        if(num == (father->lchild)->val)
        {
            father->lchild = current;
        }
        else
        {
            father->rchild = current;
        }
        insertleafptr = createLeaf(min, current);
        current->lchild = insertleafptr;
        insertleafptr = createLeaf(max, current);
        current->rchild = insertleafptr;
        repair(current);
       return ;
    }
}

mynode * getFather (mynode* child)
{
    return child->parent;
}

mynode * getUncle (mynode* child)
{
    mynode * randNode1 = (mynode* )malloc(sizeof(mynode));
    mynode * randNode2 = (mynode* )malloc(sizeof(mynode));
    randNode1 = getFather(child);
    randNode2 = getFather(randNode1);
    if((randNode1->val) == ((randNode2->lchild)->val))
    {
        return randNode2->rchild;
    }
    else
    {
        return randNode2->lchild;
    }
    free(randNode1);
}

bool isRed (mynode* myptr)
{
    if ((myptr->black) != true)
    {
        return true;
    }
    else
    {
        return false;
    }
}

void changeColor (mynode* myptr)
{
        if ((myptr->black) == true)
        {
            myptr->black = false;
        }
        else
        {
            myptr->black = true;
        }
}

bool sameType(mynode* myptr)
{
    int counter = 0;
    unsigned long int val;
    mynode* father;
    father = myptr->parent;
    val = myptr->val;
    if ( val == (father->lchild)->val)
    {
        counter++;
    }
    else
    {
        counter--;
    }
    val = father->val;
    father = father->parent;
        if ( val == (father->lchild)->val)
    {
        counter++;
    }
    else
    {
        counter--;
    }
    if( (counter == 2) || (counter == -2))
    {
        return true;
    }
    else
    {
        return false;
    }
}



void repair (mynode* myptr)
{
    rootRepair(myptr);
    subtreeRepair(myptr);
    return ;
}

void rootRepair (mynode* myptr)
{
    if(isRoot(myptr))
    {
        myptr->black = true;
    }
    return ;
}

bool isRoot(mynode* myptr)
{
    if ((myptr->parent) == NULL)
    {
        return true;
    }
    return false;
}

void subtreeRepair (mynode* myptr)
{
    mynode* father = (mynode* )malloc(sizeof(mynode));
    mynode* uncle = (mynode* )malloc(sizeof(mynode));
    father = getFather(myptr);
    uncle = getUncle(myptr);

    if( (isRed(father)) || (isRoot(myptr) == false))
    {
        if( isRed(uncle))
        {
            colorFlip(myptr);
        }
        else
        {
            myRotate(myptr);
        }

    }
    return ;
}


void colorFlip( mynode* myptr)
{
    mynode* cfather = (mynode* )malloc(sizeof(mynode));
    mynode* cuncle = (mynode* )malloc(sizeof(mynode));
    mynode* cgrandpa = (mynode* )malloc(sizeof(mynode));
    cfather = getFather(myptr);
    cuncle = getUncle(myptr);
    cgrandpa = getFather(cfather);
    changeBlack(cfather);
    changeBlack(cuncle);
    changeRed(cgrandpa);
    repair(cgrandpa);
    return ;
}

void changeBlack(mynode* myptr)
{
    myptr->black = true;
    return ;
}

void changeRed(mynode* myptr)
{
    myptr->black = false;
    return ;
}

void myRotate(mynode* myptr)
{
    if( sameType(myptr))
    {
        rotate(myptr);
    }
    else
    {
        doubleRotate(myptr);
    }
    return ;
}

void rotate(mynode* myptr)
{
    mynode* rfather = (mynode* )malloc(sizeof(mynode));
    mynode* runcle = (mynode* )malloc(sizeof(mynode));
    mynode* rgrandpa = (mynode* )malloc(sizeof(mynode));
    mynode* current = (mynode* )malloc(sizeof(mynode));
    rfather = getFather(myptr);
    runcle = getUncle(myptr);
    rgrandpa = getFather(rfather);

    changeColor(rfather);
    changeColor(rgrandpa);

    if((rfather->lchild)->val == ((myptr)->val) )
    {
        current = rfather->rchild;
    }
    else
    {
        current = rfather->lchild;
    }

    if((rgrandpa->lchild)->val == (runcle->val))
    {
        rgrandpa->rchild = current;
    }
    else
    {
        rgrandpa->lchild = current;
    }

    rfather->parent = rgrandpa->parent;
    current = rgrandpa->parent;
    if((current->lchild)->val == (rgrandpa)->val)
    {
        current->lchild = rfather;
    }
    else
    {
        current->rchild = rfather;
    }

    if((rfather->rchild)->val == (myptr)->val)
    {
        rfather->lchild = rgrandpa;
    }
    else
    {
        rfather->rchild = rgrandpa;
    }

    free(current);
    return ;
}

void doubleRotate (mynode* myptr)
{
    mynode* current = (mynode* )malloc(sizeof(mynode));
    current = myptr->parent;
    smallRotate(myptr);
    rotate(current);
    return ;
}


void smallRotate(mynode* myptr)
{
    mynode* srfather = (mynode* )malloc(sizeof(mynode));
    mynode* srgrandpa = (mynode* )malloc(sizeof(mynode));
    mynode* srcurrent = (mynode* )malloc(sizeof(mynode));
    int flag = 0;
    srfather = getFather(myptr);
    srgrandpa = getFather(srfather);

    if( (srgrandpa->lchild)->val == (srfather->val))
    {
        srgrandpa->lchild = myptr;
    }
    else
    {
        srgrandpa->rchild = myptr;
        flag = 1;
    }

    if(flag = 0)
    {
        srcurrent = myptr->lchild;
        myptr->lchild = srfather;
        srfather->rchild = srcurrent;
    }
    else
    {
        srcurrent = myptr->rchild;
        myptr->rchild = srfather;
        srfather->lchild = srcurrent;
    }

    return ;
}

Program up until "insert" function ran without problems. Segmentation fault occured when I added repair function (in insert function) and all the functions which implement Red-black tree properties to my data structure.

R&B correction ( or balancing if your prefer )algorithm is mostly from here

important EDIT:

Using the debugger led me to getUncle functions and I think segmentation fault led occured there. My prediction is that it cannot return an "uncle" because it is near the root. So when information at the beginning of the array is stored in the tree or balancing reached so high up the tree, I have a problem... Any ideas?

Answer 1

You have the following line:

if(flag = 0)

which should most likely be:

if(flag == 0)

Note that = is assignment, == is comparison.

Note also that if you had enabled compiler warnings (e.g. gcc -Wall ...), this would have been flagged at compile-time, along with other helpful warnings about questionable code:

rbtree.c:64:31: warning: format specifies type 'unsigned long' but the argument has type 'unsigned long long' [-Wformat]
        printf("lines = %lu", lines);
                        ~~~   ^~~~~
                        %llu
rbtree.c:436:17: warning: using the result of an assignment as a condition without parentheses [-Wparentheses]
        if(flag = 0)
           ~~~~~^~~
rbtree.c:436:17: note: place parentheses around the assignment to silence this warning
        if(flag = 0)
                ^
           (       )
rbtree.c:436:17: note: use '==' to turn this assignment into an equality comparison
        if(flag = 0)
                ^
                ==
2 warnings generated.