Implementing a thread safe generic stack

[Ankur Arora]

Hi All,

In a recent interview, I was asked to implement a thread safe generic
(i.e.template based) stack in C++, on linux machine.
I quickly came up with the following (It may have compilation errors).
I got through. The interviewer probably liked something in this
implementation. Maybe the design part
Here are a few problems that this implementation may have:-
1. Correct implementation to indicate overflow/underflow. There is no
overflow handling since I'm using STL vector as the underlying data
structure. Should there be any such handling? Also, underflow (in Pop
()) yields false as return value. Should it be done by throwing of an
exception?
2. Implementation of PopElem routine. Is the below implementation
correct?
3. Better timing between start of writer and reader thread.

Please make any comments/suggestions/improvements.
Thanks.

//Implementing a thread safe generic stack.

#include<pthread.h>
#include<iostream>
#include<vector>

using namespace std;

template<typename T>
class MyStack
{
public:
//interface
bool Push(T elem);
bool Pop(T& elem);
bool IsEmpty();

//constructor
MyStack() {
pthread_mutex_init(&lock);
top = 0;
}

//destructor
~MyStack() {
pthread_mutex_destroy(&lock);
}

private:
pthread_mutex_t lock;
int top;
vector<T> stack;

bool MyStack:ush(T elem);
bool MyStack:opElem(T& elem);
}; //end of MyStack

template<typename T>
bool MyStack<T>:ush(T elem)
{
pthread_mutex_lock(&lock);
PushElem(elem);
pthread_mutex_unlock(&lock);
}

template<typename T>
bool MyStack<T>:op(T& elem)
{
pthread_mutex_lock(&lock);
PopElem(elem);
pthread_mutex_unlock(&lock);
}

template<typename T>
bool MyStack<T>:ushElem(T elem)
{
stack.push_back(elem);
top = stack.size();
}

template<typename T>
bool MyStack<T>:opElem(T& elem)
{
if(this.IsEmpty())
{
return false;
}

elem = stack.back(); //tricky, returns a reference to the last
element
stack.pop_back(); // is elem valid after this ??
top = stack.size();
return true;
}


template<typename T>
bool MyStack<T>::IsEmpty()
{
return stack.empty();
}


class MyStackTest
{
public:
void Initialize() {
pthread_init(&readerT);
pthread_init(&writerT);
}

void Run() {
pthread_create(writerT,0,writer,0);
pthread_create(readerT,0,reader,0);
pthread_join(&writerT);
pthread_join(&readerT);
}

private:
pthread_t readerT;
pthread_t writerT;
MyStack<int> stack;

void reader(void);
void writer(void);
};

void MyStackTest::writer() {
for(int i=0;i<20;i++) {
stack.Push(i);
cout<<"\n\t Pushed element: "<<i;
} //end for
}

void MyStackTest::reader() {
int elem;
while(stack.Pop(elem))
{
cout<<"\n\t Popped: "<<elem;
}
}

int main()
{
MyStackTest Test;

Test.Run();
}

 

[Michael Doubez]

Hi All,

In a recent interview, I was asked to implement a thread safe generic
(i.e.template based) stack in C++, on linux machine.
I quickly came up with the following (It may have compilation errors).
I got through. The interviewer probably liked something in this
implementation. Maybe the design part
Here are a few problems that this implementation may have:-
1. Correct implementation to indicate overflow/underflow. There is no
overflow handling since I'm using STL vector as the underlying data
structure. Should there be any such handling?

Yes, in multithreaded environment, you cannot require a pre-condition
of !empty().

Also, underflow (in Pop
()) yields false as return value. Should it be done by throwing of an
exception?

No. Underflow is not an exceptional case.

2. Implementation of PopElem routine. Is the below implementation
correct?

Yes but pop() doesn't return the value.

3. Better timing between start of writer and reader thread.

Please make any comments/suggestions/improvements.

Your code is not exception-safe: if the push_back() or a copy of your
type throws, the mutex will stay locked. Use RAII or intercept all
exception.

pthread_create() cannot take a member function in parameter, you must
use a (in theory extern "C") free function.

Your top member is useless.

//Implementing a thread safe generic stack.

#include<pthread.h>
#include<iostream>
#include<vector>

using namespace std;

template<typename T>
class MyStack
{
public:
//interface
bool Push(T elem);
bool Pop(T& elem);
bool IsEmpty();

//constructor
MyStack() {
pthread_mutex_init(&lock);
top = 0;

}

//destructor
~MyStack() {
pthread_mutex_destroy(&lock);

}

private:
pthread_mutex_t lock;
int top;
vector<T> stack;

bool MyStack:ush(T elem);
bool MyStack:opElem(T& elem);

}; //end of MyStack

template<typename T>
bool MyStack<T>:ush(T elem)
{
    pthread_mutex_lock(&lock);
    PushElem(elem);
    pthread_mutex_unlock(&lock);

}

template<typename T>
bool MyStack<T>:op(T& elem)
{
    pthread_mutex_lock(&lock);
    PopElem(elem);
    pthread_mutex_unlock(&lock);

}

template<typename T>
bool MyStack<T>:ushElem(T elem)
{
    stack.push_back(elem);
     top = stack.size();

}

template<typename T>
bool MyStack<T>:opElem(T& elem)
{
   if(this.IsEmpty())
   {
        return false;
   }

   elem = stack.back(); //tricky, returns a reference to the last
element
   stack.pop_back(); // is elem valid after this ??

Yes, it has been copied.