#include <stdatomic.h>
+#include <atomic>
#define release memory_order_release
#define acquire memory_order_acquire
+#define acq_rel memory_order_acq_rel
#define relaxed memory_order_relaxed
-#define MAX_NODES 0xf
-
-typedef unsigned long long pointer;
-typedef atomic_ullong pointer_t;
-
-#define MAKE_POINTER(ptr, count) ((((pointer)count) << 32) | ptr)
-#define PTR_MASK 0xffffffffLL
-#define COUNT_MASK (0xffffffffLL << 32)
-
-static inline void set_count(pointer *p, unsigned int val) { *p = (*p & ~COUNT_MASK) | ((pointer)val << 32); }
-static inline void set_ptr(pointer *p, unsigned int val) { *p = (*p & ~PTR_MASK) | val; }
-static inline unsigned int get_count(pointer p) { return (p & COUNT_MASK) >> 32; }
-static inline unsigned int get_ptr(pointer p) { return p & PTR_MASK; }
-
-typedef struct node {
+struct node {
unsigned int value;
- pointer_t next;
-
-} node_t;
-
-typedef struct {
- pointer_t top;
- node_t nodes[MAX_NODES + 1];
-} stack_t;
+ node *next;
+
+ node(unsigned int v) {
+ value = v;
+ next = NULL;
+ }
+};
+
+struct stack {
+ atomic<node*> top;
+
+ stack() {
+ atomic_init(&top, NULL);
+ }
+
+ void push(unsigned int val) {
+ node *n = new node(val);
+ node *old = top.load(acquire);
+ do {
+ n->next = old;
+ } while (!top.compare_exchange_strong(old, n, acq_rel, relaxed));
+ }
+
+ unsigned int pop() {
+ node *old = top.load(acquire);
+ node *n;
+ do {
+ if (!old)
+ return 0;
+ n = old->next;
+ } while (!top.compare_exchange_strong(old, n, acq_rel, acquire));
+ return old->value;
+ }
+};
-void init_stack(stack_t *s, int num_threads);
-void push(stack_t *s, unsigned int val);
-unsigned int pop(stack_t *s);
-int get_thread_num();