CODEWITHSUNDEEP
c++segmentation-faultboolean
Mattia Paterna
Mattia Paterna

Reputation: 1356

segfault when setting bool possible?

I have a binary tree, whose nodes are defined as

typedef unsigned long ul;
struct Fibonacci_node{
    ul number;                              
    int n;                                 
    bool isLeaf;                            
    Fibonacci_node * left;
    Fibonacci_node * right;
  };

I'd like to set isLeaf each insertion, so that I could easily get the total number of leafs eventually. The insertion method is made up of a public method, insert, that calls the private recursive method insertR.

#include <iostream>
using namespace std;

class Fibonacci_tree{
    private:
        struct Fibonacci_node{
        ul number;                              // store the n-th fibonacci number
        int n;                                  // fibonacci number to compute
        bool isLeaf;                            // true if the node is leaf
        Fibonacci_node * left;
        Fibonacci_node * right;
      };



        /* definition of the root of the binary tree */
        Fibonacci_node * root;

        /* class private methods (recursively defined) */
        ul fibonacci(int n){
        /* BASE CASE */
        if (n == 0) { return 1; }
        if (n == 1) { return 1; }

        /* call the function recursively */
        return fibonacci(n - 1) + fibonacci(n - 2);
      };

      Fibonacci_node * insertR(int n, Fibonacci_node * node){
        if (!node) {
        /* if pointer is null create a new node */

        Fibonacci_node * tmp = new Fibonacci_node;
        tmp->n = n;
        tmp->number = fibonacci(tmp->n);
        tmp->left = tmp->right = 0;
        tmp->isLeaf = 0;

        /* update the pointer and return it */
        node = tmp;

        /* BASE CASE */
        if (n == 0) {
          node->isLeaf = 1;
          return node;
        }
        if (n == 1) {
          node->isLeaf = 1;
          return node;
        }
      }

      /* call the function recursively */
      node->left = insertR(n - 1, node->left);
      node->right = insertR(n - 2, node->right);

      return node;
    };

  public:
    Fibonacci_tree(){
      root = 0;
    }
    ~Fibonacci_tree(){}

    /* class public methods (they include private methods recursively defined)*/
    void insert(int n){

      /* first, create initial node and compute fibonacci for the root */
      Fibonacci_node * tmp = new Fibonacci_node;
      tmp->n = n;
      tmp->number = fibonacci(n);
      tmp->isLeaf = false;
      //getNo(tmp);

      /* make root point to the first element of the tree */
      root = tmp;

      /* then call the recursive function */
      root = insertR(n, root);
    };
};
/* END OF CLASS DECLARATION */


/* main program to check the class */
int main(void) {
  int n = 3;

  /* instantiate a Fibonacci tree */
  Fibonacci_tree fib_series;
  /* fill the tree */
  fib_series.insert(n);

  return 0;
}

When I run my executable, I get

Segmentation fault: 11

I printed several comments and I noted that the error seems appear immediately after before I assign "false" to the boolean. So, I'm assuming that the assignment gets wrong but it's the first time I get segmentation fault in such a situation.

I also think that because so far I haven't had any problem but this, and it started when I introduced this variable in the class definition.

Could it be possible to get segmentation fault because of this, or I may have a problem elsewhere that I haven't noted yet?

I'd like to completely debug it by myself, but my debugging skills still sucks a bit. Any feedback is therefore really appreciated.

Upvotes: 0

Views: 2224

Answers (2)

Jabberwocky
Jabberwocky

Reputation: 50775

The actual problem is here:

 /* call the function recursively */
    node->left = insertR(n - 1, node->left);

at that point node->left is not yet initialized, you pass that non inizialized value recursively to insertR, where you check if it's NULL, as it is non inizialized it is most likely non null, and then you dereference it again here: node->left = insertR(n - 1, node->left);. Dereferencing a non initialized pointer is undefined behaviour.

Actually you simply forgot to initialize leftand right to 0 here:

/* first, create initial node and compute fibonacci for the root */
Fibonacci_node * tmp = new Fibonacci_node;
tmp->n = n;
tmp->number = fibonacci(n);
tmp->isLeaf = false;
tmp->left = tmp->right = 0;    // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< you forgot this.
//getNo(tmp);

As you are writing in C++ why don't you write a constructor for Fibonacci_node where all the initialisation could be done in one place ?

tmp->isLeaf = false; causing a segfault on your computer is just a consequence of undefined behaviour.

Upvotes: 3

Muzer
Muzer

Reputation: 774

If tmp is not a valid pointer (NULL, something that has been freed, something that has gone out of scope, or something that has not been allocated properly in the first place), this is likely the cause.

Upvotes: 1

Related Questions