A thread-safe stack data structure

So far, we have discussed how to launch and manage a thread, and how to synchronize the operations between concurrent threads. But, when it comes to actual systems, the data is represented in the form of data structures, which must be chosen appropriately for the situation to guarantee the performance of the program. In this section, we are going to discuss how to design a concurrent stack using conditional variables and mutexes. The following program is a wrapper to std::stack, which is declared under the library header <stack>, and the stack wrapper will be available with different overloads for pop and push functionalities (this has been done to keep the listing small, and this also demonstrates how we can adapt a sequential data structure to work in a concurrent context):

template <typename T> 
class Stack 
{ 
private: 
    std::stack<T> myData; 
    mutable std::mutex myMutex; 
    std::condition_variable myCond; 
     
public: 
    Stack() = default; 
    ~Stack() = default; 
    Stack& operator=(const Stack&) = delete; 
     
    Stack(const Stack& that) 
    { 
        std::lock_guard<std::mutex> lock(that.myMutex); 
        myData = that.myData; 
    }

The Stack class contains an object to the template class std::stack, along with member variables for std::mutex and std::condition_variable. The constructor and destructor of the class are marked as default, letting the compiler generate a default implementation for those, and the copy assignment operator is marked as delete to prevent the invocation of the assignment operator of this class at compile time itself. The copy constructor is defined, which copies the std::stack member object myData, by invoking its own copy assignment operator, which is protected by the right-hand side object's mutex:

      void push(T new_value) 
      { 
          std::lock_guard<std::mutex> local_lock(myMutex); 
          myData.push(new_value); 
          myCond.notify_one(); 
      } 

The member function push() is wrapping the push function of std::stack container. As you can see, the mutex member variable, myMutex, is locked by an std::lock_guard object to safeguard the push operation that follows in the next line. Followed by that, the notify_one() function is invoked using the member std::condition_variable object to raise an event to notify the waiting threads over this same condition variable. There are two overloads of the pop operation that you will see in the following code listings, which wait over this condition variable to get signaled:

    bool try_pop(T& return_value) 
    { 
        std::lock_guard<std::mutex> local_lock(myMutex); 
        if (myData.empty()) return false; 
        return_value = myData.top(); 
        myData.pop(); 
        return true; 
    }

The try_pop() function takes a template argument as a reference. Since the implementation never waits for the stack to fill at least one element, this uses the std::lock_guard object to protect the thread. The function returns false if the stack is empty, otherwise it returns true. Here, the output is assigned to input a reference argument by invoking the top() function of std::stack, which returns the topmost element in the stack, followed by the pop() function to clear the topmost element from the stack. All overloads for the pop function invoke the top() function followed by a call to the pop() function of std::stack:

    std::shared_ptr<T> try_pop() 
    { 
        std::lock_guard<std::mutex> local_lock(myMutex); 
        if (myData.empty()) return std::shared_ptr<T>(); 
         
        std::shared_ptr<T> return_value(std::make_shared<T>(myData.top())); 
        myData.pop(); 
         
        return return_value;
    } 

This is another overload of the try_pop() function, which returns an instance of std::shared_ptr (smart pointer) of the template type. As you have already seen, the try_pop function overloads, and never waits for a stack to fill at least one element; therefore, this implementation uses std::lock_guard. If the internal stack is empty, the function returns an instance of std::shared_ptr and holds no element of the stack. Otherwise, a std::shared_ptr instance that holds the top element of the stack is returned:

    void wait_n_pop(T& return_value) 
    { 
        std::unique_lock<std::mutex> local_lock(myMutex); 
        myCond.wait(local_lock, [this]{ return !myData.empty(); }); 
        return_value = myData.top(); 
        myData.pop(); 
    }      
    std::shared_ptr<T> wait_n_pop() 
    { 
        std::unique_lock<std::mutex> local_lock(myMutex); 
        myCond.wait(local_lock, [this]{ return !myData.empty(); }); 
        std::shared_ptr<T> return_value(std::make_shared<T>(myData.top())); 
        return return_value; 
    }   
}; 

So far, the overloads of the pop function are not waiting for the stack to fill at least one element if it is empty. To achieve that, two more overloads of the pop function are added, which uses the wait function associated with std::condition_variable. The first implementation returns the template value as an output argument, and the second one returns an std::shared_ptr instance. Both functions use std::unique_lock to control the mutex in order to supply the wait() function of std::condition_variable. In the wait function, the predicate function is checking whether the stack is empty or not. If the stack is empty, then the wait() function unlocks the mutex and continues to wait until a notification is received from the push() function. As soon as the push is called, the predicate will return true, and wait_n_pop continues its execution. The function overload takes the template reference and assigns the top element into the input argument, and the latter implementation returns an std::shared_ptr instance, holding the top element.