Chris M Thomasson

#include <relacy/relacy_std.hpp>
#include <cstdio>
#include <climits>




#if ! defined (NDEBUG)
#   define DBG_PRINTF(mp_exp) std::printf mp_exp
#else
#   define DBG_PRINTF(mp_exp) ((void)0)
#endif




#define POWER 2U
#define SIZE (1U << POWER)
#define MASK (~(0xFFFFFFFFU << POWER))


// By: Amine Moulay Ramadane
// Translated to Relacy By: Chris M. Thomasson
// Relacy By: Dmitriy Vyukov
template<typename T>
class spmcq {
  rl::atomic<T> m_tab[SIZE];
  rl::atomic<unsigned> m_head;
  rl::atomic<unsigned> m_tail;


  unsigned get_length() {
    unsigned head = m_head($).load();
    unsigned tail = m_tail($).load();
    if (tail < head) {
      return UINT_MAX - head + 1 + tail;
    } else {
      return tail - head;
    }
  }


public:
  spmcq() {
    m_head($).store(0, rl::memory_order_relaxed);
    m_tail($).store(0, rl::memory_order_relaxed);
    for (unsigned i = 0; i < SIZE; ++i) {
      m_tab[i]($).store(T(), rl::memory_order_relaxed);
    }
  }


public:
  bool push(T& state) {
    if (get_length() >= SIZE) {
      return false;
    }
    unsigned tail = m_tail($).load();
    m_tab[tail & MASK]($).store(state);
    m_tail($).store(tail + 1);
    return true;
  }


  bool pop(T& state) {
    unsigned last_head = m_head($).load();
    do {
      if (m_tail($).load() == last_head) {
        return false;
      }
      state = m_tab[last_head & MASK]($).load();
    } while (! m_head($).compare_exchange_weak(last_head, last_head + 1));
    return true;
  }
};



#define THREADS 4
#define ITERS 10


struct spmcq_test : rl::test_suite<spmcq_test, THREADS> {
  spmcq<unsigned> m_queue[THREADS];

  bool steal(unsigned tidx, unsigned& x) {
    unsigned i = tidx + 1;
    for (; i < THREADS; ++i) {
      if (m_queue[i].pop(x)) return true;
    }
    for (i = 0; i < tidx; ++i) {
      if (m_queue[i].pop(x)) return true;
    }
    return false;
  }

  void thread(unsigned tidx) {
    unsigned i = 0, x;
    for (; i < ITERS; ++i) {
      if (m_queue[tidx].push(i)) {
        DBG_PRINTF(("Thread(%u) pushed (%u)\n", tidx, i));
      }
    }
    for (i = 1; i < ITERS + 1; ++i) {
      if (! (i % 2)) {
        if (m_queue[tidx].pop(x)) {
          DBG_PRINTF(("Thread(%u) popped (%u)\n", tidx, x));
        }
      } else if (steal(tidx, x)) {
        DBG_PRINTF(("Thread(%u) has stolen (%u)\n", tidx, x));
      }
    }
  }
};



int main() {
  rl::test_params params;
  params.iteration_count = 9999999;
  rl::simulate<spmcq_test>(params);
  std::puts("\n\n\n_____________________________\nCompleted!");
  std::getchar();
  return 0;
}