Safe Stack

The C program stack$-$ptr$.$c $($provided$)$ contains an implementation of a stack using a linked list.

An example of its use is as follows:

StackNode $*$top $=$ NULL;

$...$

push$(5,$ &top$)$;

push $(10,$ &top$)$;

push $(15,$ &top$)$;

$...$

int value $=$ pop$($&top$)$;

value $=$ pop$($&top$)$;

value $=$ pop$($&top$)$;

$...$

This program currently has a race condition and is not appropriate for a concurrent environment. Using

Pthreads mutex locks $($section $7\mathrm{.}3\mathrm{.}1),$ fix the race conditions. Test your now$-$thread$-$safe stack by

creating $200$ concurrent threads in main$()$ that intermix pushing and popping values.

Use a loop in main$()$ to create all those threads. Apply all the things you've learned about creating

and joining threads from previous chapters.

$$ Write one testStack function, and use it as the entry point for each thread.

$$ The testStack function should intermix $3$ push operations with $3$ pop operations in a loop that

executes $500$ times.

$$ All threads use the same stack.

gcc $-$pthread stack$-$ptr$.$c $-$o stack$-$ptr is an example command to compile and link

your program

If you're up for it$,$ you may rewrite the provided C program into well$-$formed C$++$ code using proper

Object Oriented Design concepts, but you must maintain the dynamically allocated linked list

concept, and you must still use the Pthreads mutex locks.

$/*$

$*$ Stack containing race conditions

$*/$

#include

#include

#include

$//$ Linked list node

typedef int value$\_$t;

typedef struct Node

$\{$

value$\_$t data;

struct Node $*$next;

$\}$ StackNode;

$//$ Stack function declarations

void push $($value$\_$t v$,$ StackNode $**$top$)$;

value$\_$t pop $($ StackNode $**$top$)$;

int is$\_$empty$($ StackNode $*$top$)$;

int main$($void$)$

$\{$

StackNode $*$top $=$ NULL;

push$(5,$ &top$)$;

push$(10,$&top$)$;

pop $($ &top$)$;

push$(15,$&top$)$;

pop $($ &top$)$;

pop $($ &top$)$;

push$(20,$&top$)$;

push$(-5,$ &top$)$;

pop $($ &top$)$;

push$(-10,$&top$)$;

pop $($ &top$)$;

pop $($ &top$)$;

push$(-15,$&top$)$;

pop $($ &top$)$;

push$(-20,$&top$)$;

return $0$;

$\}$

$//$ Stack function definitions

void push$($value$\_$t v$,$ StackNode $**$top$)$

$\{$

StackNode $*$ new$\_$node $=$ malloc$($sizeof$($StackNode$))$;

new$\_$node$->$data $=$ v;

new$\_$node$->$next $=*$top;

$*$top $=$ new$\_$node;

$\}$

value$\_$t pop$($StackNode $**$top$)$

$\{$

if $($is$\_$empty$(*$top$))$ return $($value$\_$t$)0$;

value$\_$t data $=(*$top$)->$data;

StackNode $*$ temp $=*$top;

$*$top $=(*$top$)->$next;

free$($temp$)$;

return data;

$\}$

int is$\_$empty$($StackNode $*$top$)\{$

if $($top $==$ NULL$)$ return $1$;

else return $0$;

$\}$