Segmentation fault in deque array implementation

Question

I am trying DeQue implementation in C++. I am getting Segmentation fault on calling insertFront function. I am not getting what is wrong in the code. Please help me to identify the cause. Here is the code:

#include <iostream>

using namespace std;

#define MAX 100

class DeQueue {
    int arr[MAX];
    int front;
    int rear;
    int size;
    
public:
    DeQueue(int size){
        front = -1;
        rear = -1;
        this->size = size;
    }
    
    void insertFront(int n);
    void insertRear(int n);
    int deleteFront();
    int deleteRear();
    bool isEmpty();
    bool isFull();
    int getFront();
    int getRear();
};

bool DeQueue::isEmpty(){
    return (((front - 1) % size == rear) || (front == -1 && rear == -1));
}

bool DeQueue::isFull(){
    return ((front - 2) % size == rear);
}

void DeQueue::insertFront(int n){
    if(isFull()){
        cout << "Stack overflow!" << endl;
        return;
    }

    if(front == -1 && rear == -1)
        front = rear = size - 1;
    else
        front = (front - 1) % size;
    
    arr[front] = n;
}

void DeQueue::insertRear(int n){
    if(isFull()){
        cout << "Stack overflow!" << endl;
        return;
    }

    if(front == -1 && rear == -1)
        front = rear = 0;
    else
        rear = (rear + 1) % size;

    arr[rear] = n;
}

int DeQueue::deleteFront(){
    if(isEmpty()){
        cout << "Stack underflow!" << endl;
        return 0;
    }
    
    int temp = arr[front];
    front = (front + 1) % size;
    return temp;
}

int DeQueue::deleteRear(){
    if(isEmpty()){
        cout << "Stack underflow!" << endl;
        return 0;
    }

    int temp = arr[rear];
    rear = (rear - 1) % size;
    return temp;
}

int DeQueue::getFront(){
    if(isEmpty()){
        cout << "Stack underflow!" << endl;
        return 0;
    }

    return arr[front];
}

int DeQueue::getRear(){
    if(isEmpty()){
        cout << "Stack underflow!" << endl;
        return 0;
    }

    return arr[rear];
}

int main() {
    
    DeQueue dq(5); 
    cout << "Insert element at rear end  : 5 \n"; 
    dq.insertRear(5); 
  
    cout << "insert element at rear end : 10 \n"; 
    dq.insertRear(10); 
  
    cout << "get rear element " << " " << dq.getRear() << endl; 
  
    dq.deleteRear(); 
    cout << "After delete rear element new rear" << " become " << dq.getRear() << endl;
  
    cout << "inserting element at front end \n"; 
    dq.insertFront(15); 
  
    cout << "get front element " << " " << dq.getFront() << endl; 
  
    dq.deleteFront(); 
  
    cout << "After delete front element new " << "front become " << dq.getFront() << endl; 
    return 0;
}

Output:

Insert element at rear end  : 5 
insert element at rear end : 10 
get rear element  10
After delete rear element new rear become 5
/usr/bin/timeout: the monitored command dumped core
sh: line 1: 17584 Segmentation fault      /usr/bin/timeout 10s main

In general, `negative_value % positive_value == negative_value`, so your calculations of indices with modulus are incorrect. — Yksisarvinen, Aug 28 '20 at 09:30

StPiere · Answer 1 · 2020-08-28T10:13:40.093

1

You have some serious implementation problems. One of them:

void DeQueue::insertFront(int n){
    if(isFull()){
        cout << "Stack overflow!" << endl;
        return;
    }

    if(front == -1 && rear == -1)    // <- This is definitely problem if rear != -1, as in your case 
        front = rear = size - 1;            
    else
        front = (front - 1) % size; // this is where you get on first insertFront() by rear != -1
    
    arr[front] = n;  // front < 0!! in your case because rear != -1
}

Also be aware of differences in % operator in C++ and its mathematical definition of mod: in C++ % can provide negative values if divisor and divident have different signs.

edited Aug 28 '20 at 10:13

answered Aug 28 '20 at 09:23

StPiere

4,113
15
24

This will never happen as I am setting front = 0 inside `insertRear` – Avadh Vashisth Aug 28 '20 at 09:28
in your example this will happen. try to debug and you'll see – StPiere Aug 28 '20 at 10:05
yes it will happen. Actually, in most of the high level language % return only positive value and wrap-around the array. But in c++ modulo returns negative value also which was causing this issue. – Avadh Vashisth Aug 28 '20 at 10:14

score 0 · Answer 2 · answered Aug 28 '20 at 09:29

$ g++ -o stackoverflowasan stackoverflowasan.C -Wall -g -fsanitize=address
$ gdb ./stackoverflowasan
(gdb) catch syscall exit_group
(gdb) run
...
Insert element at rear end  : 5 
insert element at rear end : 10 
get rear element  10
After delete rear element new rear become 5
inserting element at front end 
=================================================================
==319319==ERROR: AddressSanitizer: stack-buffer-underflow on address 0x7fffffffcc8c at pc 0x00000040169a bp 0x7fffffffcc40 sp 0x7fffffffcc30
WRITE of size 4 at 0x7fffffffcc8c thread T0
    #0 0x401699 in DeQueue::insertFront(int) /home/jkratoch/t/stackoverflowasan.C:49
    #1 0x401ec7 in main /home/jkratoch/t/stackoverflowasan.C:121
    #2 0x7ffff70c6041 in __libc_start_main ../csu/libc-start.c:308
    #3 0x40115d in _start (/quad/home/jkratoch/t/stackoverflowasan+0x40115d)

Address 0x7fffffffcc8c is located in stack of thread T0 at offset 28 in frame
    #0 0x401d34 in main /home/jkratoch/t/stackoverflowasan.C:106
...

(gdb) frame 5
#5  0x000000000040169a in DeQueue::insertFront (this=0x7fffffffcc90, n=15) at stackoverflowasan.C:49
49      arr[front] = n;
(gdb) p front
$1 = -1
(gdb) p rear
$2 = 0

Segmentation fault in deque array implementation

2 Answers2