Got an iPhone or iPad? We have a brand new Pastebin App for both devices, and it's totally free! Click here to download the new Pastebin App for iOS.
Public Pastes
Guest

Chris M Thomasson

By: a guest on Jul 1st, 2009  |  syntax: C++  |  size: 2.63 KB  |  hits: 133  |  expires: Never
download  |  raw  |  embed  |  report abuse
This paste has a previous version, view the difference. Copied
  1. #include <relacy/relacy_std.hpp>
  2. #include <cstdio>
  3. #include <climits>
  4.  
  5.  
  6.  
  7.  
  8. #if ! defined (NDEBUG)
  9. #   define DBG_PRINTF(mp_exp) std::printf mp_exp
  10. #else
  11. #   define DBG_PRINTF(mp_exp) ((void)0)
  12. #endif
  13.  
  14.  
  15.  
  16.  
  17. #define POWER 2U
  18. #define SIZE (1U << POWER)
  19. #define MASK (~(0xFFFFFFFFU << POWER))
  20.  
  21.  
  22. // By: Amine Moulay Ramadane
  23. // Translated to Relacy By: Chris M. Thomasson
  24. // Relacy By: Dmitriy Vyukov
  25. template<typename T>
  26. class spmcq {
  27.   rl::atomic<T> m_tab[SIZE];
  28.   rl::atomic<unsigned> m_head;
  29.   rl::atomic<unsigned> m_tail;
  30.  
  31.  
  32.   unsigned get_length() {
  33.     unsigned head = m_head($).load();
  34.     unsigned tail = m_tail($).load();
  35.     if (tail < head) {
  36.       return UINT_MAX - head + 1 + tail;
  37.     } else {
  38.       return tail - head;
  39.     }
  40.   }
  41.  
  42.  
  43. public:
  44.   spmcq() {
  45.     m_head($).store(0, rl::memory_order_relaxed);
  46.     m_tail($).store(0, rl::memory_order_relaxed);
  47.     for (unsigned i = 0; i < SIZE; ++i) {
  48.       m_tab[i]($).store(T(), rl::memory_order_relaxed);
  49.     }
  50.   }
  51.  
  52.  
  53. public:
  54.   bool push(T& state) {
  55.     if (get_length() >= SIZE) {
  56.       return false;
  57.     }
  58.     unsigned tail = m_tail($).load();
  59.     m_tab[tail & MASK]($).store(state);
  60.     m_tail($).store(tail + 1);
  61.     return true;
  62.   }
  63.  
  64.  
  65.   bool pop(T& state) {
  66.     unsigned last_head = m_head($).load();
  67.     do {
  68.       if (m_tail($).load() == last_head) {
  69.         return false;
  70.       }
  71.       state = m_tab[last_head & MASK]($).load();
  72.     } while (! m_head($).compare_exchange_weak(last_head, last_head + 1));
  73.     return true;
  74.   }
  75. };
  76.  
  77.  
  78.  
  79. #define THREADS 4
  80. #define ITERS 10
  81.  
  82.  
  83. struct spmcq_test : rl::test_suite<spmcq_test, THREADS> {
  84.   spmcq<unsigned> m_queue[THREADS];
  85.  
  86.   bool steal(unsigned tidx, unsigned& x) {
  87.     unsigned i = tidx + 1;
  88.     for (; i < THREADS; ++i) {
  89.       if (m_queue[i].pop(x)) return true;
  90.     }
  91.     for (i = 0; i < tidx; ++i) {
  92.       if (m_queue[i].pop(x)) return true;
  93.     }
  94.     return false;
  95.   }
  96.  
  97.   void thread(unsigned tidx) {
  98.     unsigned i = 0, x;
  99.     for (; i < ITERS; ++i) {
  100.       if (m_queue[tidx].push(i)) {
  101.         DBG_PRINTF(("Thread(%u) pushed (%u)\n", tidx, i));
  102.       }
  103.     }
  104.     for (i = 1; i < ITERS + 1; ++i) {
  105.       if (! (i % 2)) {
  106.         if (m_queue[tidx].pop(x)) {
  107.           DBG_PRINTF(("Thread(%u) popped (%u)\n", tidx, x));
  108.         }
  109.       } else if (steal(tidx, x)) {
  110.         DBG_PRINTF(("Thread(%u) has stolen (%u)\n", tidx, x));
  111.       }
  112.     }
  113.   }
  114. };
  115.  
  116.  
  117.  
  118. int main() {
  119.   rl::test_params params;
  120.   params.iteration_count = 9999999;
  121.   rl::simulate<spmcq_test>(params);
  122.   std::puts("\n\n\n_____________________________\nCompleted!");
  123.   std::getchar();
  124.   return 0;
  125. }
create a new version of this paste RAW Paste Data