Getting segmentation fault while pushing in stack

Question

I am trying to write a simple code for DFS using stack template available in C++.

It is giving segmentation fault with core dump while running.

Snippets of my code as below:

#define XPIX 400
#define YPIX 600

This the definition of node class:

class node{
public:
    int x;
    int y;
    node(int x,int y);
};

node::node(int x, int y){
    this->x = x;
    this->y = y;
}

Main class is as below:

class grafixMask {
public:
    vector <int> sortedAreas(vector <string> rectangles);
private:
    bool bitmap[XPIX][YPIX];
    stack <node> st;
    vector <int> parseInput(vector <string> Input);
    void init(int xLeft, int yLeft, int xRight, int yRight);
    int depth_first_search(int x,int y);
};

Below is the function of DFS:

int grafixMask::depth_first_search(int x, int y){
int result = 0;

this->st.push(node(x,y));

while(this->st.empty() == false){
    node topEle = this->st.top();
    this->st.pop();

    if(topEle.x < 0 || topEle.x > XPIX) continue;
    if(topEle.y < 0 || topEle.y > YPIX) continue;
    if(this->bitmap[topEle.x][topEle.y] == true) continue;
    this->bitmap[topEle.x][topEle.y] = true;
    result++;
    this->st.push(node(topEle.x - 1,topEle.y));
    this->st.push(node(topEle.x,topEle.y + 1));
    this->st.push(node(topEle.x + 1,topEle.y));
    this->st.push(node(topEle.x,topEle.y - 1));
}

return result;
}

I analysed the core dump and it says:

#1 0x0000000000403b47 in std::allocator<node>::~allocator ( this=0x7fffea214780, __in_chrg=<optimized out>) at /usr/include/c++/4.7/bits/allocator.h:112 
#2 0x0000000000402d1b in std::_Deque_base<node, std::allocator<node> >::~_Deque_base (this=0x6dd3c0, __in_chrg=<optimized out>) at /usr/include/c++/4.7/bits/stl_deque.h:568 
#3 0x000000000040216e in std::vector<std::string, std::allocator<std::string> >::push_back (this=0x7fffea24f340, __x=...) at /usr/include/c++/4.7/bits/stl_vector.h:887    
#4 0x00000000004016f6 in grafixMask::depth_first_search ( this=0x7fffea2149c0, x=0, y=0) at B.cpp:137 
#5 0x00000000004012c7 in grafixMask::sortedAreas (this=0x7fffea2149c0, rectangles=...) at B.cpp:87 #6 0x0000000000401965 in main () at B.cpp:154

debugging shows that issue is with line number 134:

(gdb) print topEle.y
$5 = 51
(gdb) next
132         this->bitmap[topEle.x][topEle.y] = true;
(gdb) next
133         result++;
(gdb) next
134         this->st.push(node(topEle.x - 1,topEle.y));
(gdb) next

Program received signal SIGSEGV, Segmentation fault.
0x00000000004038b9 in __gnu_cxx::new_allocator<node>::construct (
    this=0x7fffffffde50, __p=0x160d698, __val=...)
    at /usr/include/c++/4.7/ext/new_allocator.h:120
120       { ::new((void *)__p) _Tp(__val); }

According to source code these statements are in between line no 134 to 137.

    this->st.push(node(topEle.x - 1,topEle.y));
    this->st.push(node(topEle.x,topEle.y + 1));
    this->st.push(node(topEle.x + 1,topEle.y));
    this->st.push(node(topEle.x,topEle.y - 1));

Please suggest why it is failing in pushing node element in stack.

Wojtek Surowka · Accepted Answer · 2014-08-05 14:48:49Z

1

It looks like you have a problem in the line

if(topEle.x < 0 || topEle.x > XPIX) continue;

You have declared your array as bool bitmap[XPIX][YPIX];, which means that indices in the range 0...XPIX-1 are allowed. Replace topEle.x > XPIX with topEle.x >= XPIX.

answered Aug 5, 2014 at 14:48

Wojtek Surowka

21.1k4 gold badges48 silver badges53 bronze badges

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

Comments

Matt · Accepted Answer · 2014-08-05 14:49:05Z

1

You declare an array:

bool bitmap[XPIX][YPIX];

while in your code:

if(topEle.x < 0 || topEle.x > XPIX) continue;
if(topEle.y < 0 || topEle.y > YPIX) continue;
if(this->bitmap[topEle.x][topEle.y] == true) continue;
this->bitmap[topEle.x][topEle.y] = true;

if topEle.x == XPIX or topEle.y == YPIX the code this->bitmap[topEle.x][topEle.y] does corrupt the memory, and in the next memory allocation or deallocation, the error will surface.

answered Aug 5, 2014 at 14:49

Matt

6,06027 silver badges37 bronze badges

Collectives™ on Stack Overflow

Getting segmentation fault while pushing in stack

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related