Warm tip: This article is reproduced from stackoverflow.com, please click
c++ gdb segmentation-fault valgrind

Segmentation Fault inserting in binary tree

发布于 2020-03-27 10:20:22

I'm repeating some assignement from my class about binary tree, and I encountered a problem that never showed up to me.

At first try running the code, I've got segmentation fault. I thought about a weird loop, but I am not able to find the problem. So I've tried with gdb and valgrind, obtaining a this: Starting program: /home/and/Documenti/Algoritmi/Esercizi/Esame 01-02-2018/esa2 < input0.txt

Starting program: /home/and/Documenti/Algoritmi/Esercizi/Esame 01-02-2018/esa2 < input0.txt

Program received signal SIGSEGV, Segmentation fault.
0x00007ffff7c65cbc in _int_malloc (av=av@entry=0x7ffff7db3c40 <main_arena>, bytes=bytes@entry=32) at malloc.c:3711
3711    malloc.c: File o directory non esistente.
(gdb) where
#0  0x00007ffff7c65cbc in _int_malloc (av=av@entry=0x7ffff7db3c40 <main_arena>, bytes=bytes@entry=32) at malloc.c:3711
#1  0x00007ffff7c67ad3 in __GI___libc_malloc (bytes=32) at malloc.c:3065
#2  0x00007ffff7e79a25 in operator new(unsigned long) () from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
#3  0x0000555555555240 in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6df90: 0x0) at esa_2.cpp:38
#4  0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6df60: 0x555555b6df80) at esa_2.cpp:44
#5  0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6df30: 0x555555b6df50) at esa_2.cpp:44
#6  0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6df00: 0x555555b6df20) at esa_2.cpp:44
#7  0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6ded0: 0x555555b6def0) at esa_2.cpp:44
#8  0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6dea0: 0x555555b6dec0) at esa_2.cpp:44
#9  0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6de70: 0x555555b6de90) at esa_2.cpp:44
#10 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6de40: 0x555555b6de60) at esa_2.cpp:44
#11 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6de10: 0x555555b6de30) at esa_2.cpp:44
#12 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6dde0: 0x555555b6de00) at esa_2.cpp:44
#13 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6ddb0: 0x555555b6ddd0) at esa_2.cpp:44
#14 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6dd80: 0x555555b6dda0) at esa_2.cpp:44
#15 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6dd50: 0x555555b6dd70) at esa_2.cpp:44
#16 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6dd20: 0x555555b6dd40) at esa_2.cpp:44
#17 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6dcf0: 0x555555b6dd10) at esa_2.cpp:44
#18 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6dcc0: 0x555555b6dce0) at esa_2.cpp:44
#19 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6dc90: 0x555555b6dcb0) at esa_2.cpp:44
#20 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6dc60: 0x555555b6dc80) at esa_2.cpp:44
#21 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6dc30: 0x555555b6dc50) at esa_2.cpp:44
#22 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6dc00: 0x555555b6dc20) at esa_2.cpp:44
#23 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6dbd0: 0x555555b6dbf0) at esa_2.cpp:44
#24 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6dba0: 0x555555b6dbc0) at esa_2.cpp:44
#25 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6db70: 0x555555b6db90) at esa_2.cpp:44
#26 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6db40: 0x555555b6db60) at esa_2.cpp:44
#27 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6db10: 0x555555b6db30) at esa_2.cpp:44
#28 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6dae0: 0x555555b6db00) at esa_2.cpp:44
#29 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6dab0: 0x555555b6dad0) at esa_2.cpp:44
#30 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6da80: 0x555555b6daa0) at esa_2.cpp:44
#31 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6da50: 0x555555b6da70) at esa_2.cpp:44
#32 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6da20: 0x555555b6da40) at esa_2.cpp:44
#33 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d9f0: 0x555555b6da10) at esa_2.cpp:44
#34 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d9c0: 0x555555b6d9e0) at esa_2.cpp:44
#35 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d990: 0x555555b6d9b0) at esa_2.cpp:44
#36 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d960: 0x555555b6d980) at esa_2.cpp:44
#37 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d930: 0x555555b6d950) at esa_2.cpp:44
#38 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d900: 0x555555b6d920) at esa_2.cpp:44
#39 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d8d0: 0x555555b6d8f0) at esa_2.cpp:44
#40 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d8a0: 0x555555b6d8c0) at esa_2.cpp:44
#41 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d870: 0x555555b6d890) at esa_2.cpp:44
#42 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d840: 0x555555b6d860) at esa_2.cpp:44
#43 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d810: 0x555555b6d830) at esa_2.cpp:44
#44 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d7e0: 0x555555b6d800) at esa_2.cpp:44
#45 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d7b0: 0x555555b6d7d0) at esa_2.cpp:44
#46 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d780: 0x555555b6d7a0) at esa_2.cpp:44
#47 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d750: 0x555555b6d770) at esa_2.cpp:44
#48 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d720: 0x555555b6d740) at esa_2.cpp:44
#49 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d6f0: 0x555555b6d710) at esa_2.cpp:44
#50 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d6c0: 0x555555b6d6e0) at esa_2.cpp:44
#51 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d690: 0x555555b6d6b0) at esa_2.cpp:44
#52 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d660: 0x555555b6d680) at esa_2.cpp:44
#53 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d630: 0x555555b6d650) at esa_2.cpp:44
#54 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d600: 0x555555b6d620) at esa_2.cpp:44

Then I've done some research and someone suggested Valgrind, so I give it a try. This is the result:

==5605== Memcheck, a memory error detector
==5605== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==5605== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==5605== Command: ./esa2
==5605== 
==5605== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==5605== 
==5605== Process terminating with default action of signal 11 (SIGSEGV)
==5605==  Access not within mapped region at address 0x1FFE801FE0
==5605== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==5605==    at 0x4A3546B: operator new(unsigned long) (vg_replace_malloc.c:344)
==5605==  If you believe this happened as a result of a stack
==5605==  overflow in your program's main thread (unlikely but
==5605==  possible), you can try to increase the size of the
==5605==  main thread stack using the --main-stacksize= flag.
==5605==  The main thread stack size used in this run was 8388608.
==5605== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==5605== 
==5605== Process terminating with default action of signal 11 (SIGSEGV)
==5605==  Access not within mapped region at address 0x1FFE801FC8
==5605== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==5605==    at 0x482D6E0: _vgnU_freeres (vg_preloaded.c:59)
==5605==  If you believe this happened as a result of a stack
==5605==  overflow in your program's main thread (unlikely but
==5605==  possible), you can try to increase the size of the
==5605==  main thread stack using the --main-stacksize= flag.
==5605==  The main thread stack size used in this run was 8388608.
==5605== 
==5605== HEAP SUMMARY:
==5605==     in use at exit: 4,266,272 bytes in 130,923 blocks
==5605==   total heap usage: 130,923 allocs, 0 frees, 4,266,272 bytes allocated
==5605== 
==5605== LEAK SUMMARY:
==5605==    definitely lost: 0 bytes in 0 blocks
==5605==    indirectly lost: 0 bytes in 0 blocks
==5605==      possibly lost: 0 bytes in 0 blocks
==5605==    still reachable: 4,266,272 bytes in 130,923 blocks
==5605==         suppressed: 0 bytes in 0 blocks
==5605== Reachable blocks (those to which a pointer was found) are not shown.
==5605== To see them, rerun with: --leak-check=full --show-leak-kinds=all
==5605== 
==5605== For lists of detected and suppressed errors, rerun with: -s
==5605== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Here is the code:

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

class BinTree{
    struct node{
        int label;
        bool concordant;
        int nConcordant;
        node *left;
        node *right;
        node(int info){
            label = info;
            nConcordant = 0;
            left = right = NULL;
        }
    };

    node *root;
    vector<int> values;

    void insert(int, node*&);
    bool isLeaf(node*); 
    void setConcordant(node*);
    int countConcordant(node*);
    void setValues(node*, vector<int>&);
    void printValues(vector<int>);
  public:
    BinTree(){root = NULL;};
    void insertTree(int);
    void output();
};

void BinTree::insert(int info, node *&tree){
    if(!tree){
        tree = new node(info);
        tree->left = tree->right = NULL;
    }
    if(tree->label < info)
        insert(info, tree->right);
    else
        insert(info, tree->left);
};

bool BinTree::isLeaf(node* tree){
    if(!tree)
        return false;
    if(!(tree->left) && !(tree->right))
        return true;
    return false;
};

void BinTree::setConcordant(node *tree){
    if(!tree)
        return;
    if(isLeaf(tree))
        return;
    if(tree->left){
        if(tree->label % 2 == (tree->left)->label % 2)
            (tree->left)->concordant = true;
        else
            (tree->left)->concordant = false;
    }
    if(tree->right){
        if(tree->label % 2 == (tree->right)->label % 2)
            (tree->right)->concordant = true;
        else
            (tree->right)->concordant = false;
    }
    setConcordant(tree->left);
    setConcordant(tree->right);
};

int BinTree::countConcordant(node* tree){
    if(!tree)
        return 0;
    if(isLeaf(tree)){
        if(tree->concordant)
            return 1;
        else
            return -1;
    }
    tree->nConcordant += countConcordant(tree->left) + countConcordant(tree->right);
    return tree->nConcordant;
};

void BinTree::setValues(node* tree, vector<int>& values){
    if(!tree)
        return;
    if(tree->nConcordant >= 0)
        values.push_back(tree->label);
    setValues(tree->left, values);
    setValues(tree->right, values);
};

void BinTree::printValues(vector<int> values){
    sort(values.begin(), values.end());
    for(int i=0; i<values.size(); i++)
        cout<<values[i]<<endl;
};
void BinTree::insertTree(int info){
    insert(info, root);
};

void BinTree::output(){
    setConcordant(root);
    countConcordant(root);
    setValues(root, values);
    printValues(values);
};

int main(){
    int dim;
    cin >> dim;
    BinTree tree;
    for(int i=0; i<dim; i++){
        int info;
        cin >> info;
        tree.insertTree(info);
    }
    tree.output();
    return 0;
}

The problem seems to be in the insert function but I don't know what to do to fix it

Questioner
Liamen
Viewed
120
分享
SolidMercury 2019-07-03 22:29

Your insert function gets executed recursively. There is no breaking condition with which it can return without calling insert further. This will cause the stack memory to get filled up and finally an overflow occurs which is a segmentation fault.

john 2019-07-03 22:46:36

I guessing all that is wrong is a missing else. Should be if ... else if ... else ...

SolidMercury 2019-07-03 22:53:00

@john The first if block is for inserting at the end of the tree. It should return after executing the statements in the first if block of insert function.

Liamen 2019-07-03 23:07:13

@SolidMercury Adding the return at the end of first if block works, but I always wrote the insert in this way and I don't understand why before worked

john 2019-07-03 23:23:07

@Liamen if ... else if ... else ... is better style than using return. And (a guess) I would say it worked before because you did write if ... else if ... else ... before.

Liamen 2019-07-03 23:49:12

The problem was the last else, in the other tries, i used if..if..if, but in this case I use if, if .. else, so the last if was never called, but with else it recurses endlessly. Thank you

Related issues

1
Receiving Segmentation fault when trying to execute injected code inside ELF binary
2
Segmentation fault for all elements except the first
3
Unable to concatenate two strings and return it from a function
4
C exercise bool type segmentation fault
5
How to solve the segmentation fault issue when I use Python ctypes to call rs232.c?
6
C struct Segmentation fault
7
terminate called without an active exception when calling pthread_exit in segmentation fault handler
8
Expected or unexpected Segmentation errors?
9
getting SEGFAULT when reading an array from shared memory
10
Accessing MultiDim Array gives Seg Fault C++