fork download
copy 
  1. #include <iostream>
  2. #include <thread>
  3. #include <vector>
  4. #include <memory>
  5. #include <atomic>
  6.  
  7. /* wrapping-structure for using vector which element is std::atomic<T> */
  8. /* because vector's element must be copy-constructible and copy-assignable but atomic<T> is not. */
  9. /* https://stackoverflow.com/questions/13193484/how-to-declare-a-vector-of-atomic-in-c */
  10.  
  11. template <typename T>
  12. struct atomicwrapper {
  13.   std::atomic<T> _a;
  14.   atomicwrapper() : _a() {}
  15.   atomicwrapper(const std::atomic<T> &a) : _a(a.load()) {}
  16.   atomicwrapper(const atomicwrapper &obj) : _a(obj._a.load()) {}
  17.   atomicwrapper &operator=(const atomicwrapper &obj) { _a.store(obj._a.load()); }
  18. };
  19.  
  20. void divmod(int64_t a, int64_t b, int64_t &q, int64_t &r) { q = a / b; r = a % b; }
  21.  
  22. using T = int;
  23. class MyVectorBool {
  24.  
  25. private:
  26.   static constexpr T width = sizeof(T) * 8;
  27.   static constexpr T bits = width - 1;
  28.   static constexpr T mask_dirty = 1 << bits;
  29.  
  30.   std::vector<atomicwrapper<T>> _myVectorBool;
  31.   int64_t _size;
  32.  
  33. public:
  34.   MyVectorBool() = delete;
  35.   MyVectorBool(int64_t size) {
  36.     _size = size;
  37.     _myVectorBool = std::vector<atomicwrapper<T>>((_size - 1) / bits + 1);
  38.     for (auto &c : _myVectorBool)
  39.       c._a.store(0);
  40.   }
  41.  
  42.   bool test(int64_t index) {
  43.     if (index >= _size) throw 1;
  44.     int64_t q, r;
  45.     divmod(index, bits, q, r);
  46.     T elements;
  47.     for (;;) {
  48.       elements = _myVectorBool[q]._a.load();
  49.       if (!(elements & mask_dirty)) break;
  50.     }
  51.     return ((elements & (1 << r)) != 0);
  52.   }
  53.  
  54. #define MACRO_CAS(V) \
  55.     for (;;) { \
  56.       T before_cas; \
  57.       V = before_cas = _myVectorBool[q]._a.load(); /* preliminary data-loading */ \
  58.       if (V & mask_dirty) continue; /* if elment's dirty bit is on, spin lock */ \
  59.     CAS_START: \
  60.       if (_myVectorBool[q]._a.compare_exchange_weak(/*ref*/V, V | mask_dirty)) { \
  61.         /* when exchange-able, status is not dirty, nothing to do */ \
  62.       } else if (/*returned */ V != before_cas) { \
  63.         /* when not-change-able and atomic-value is actually change, spin lock */ \
  64.         continue; \
  65.       } else { \
  66.         /* when not-change-able and yet atomic-value is same befor and after CAS (it's called weak-CAS's Spurious Failure), do CAS again */ \
  67.         goto CAS_START; \
  68.       } \
  69.       break; \
  70.     }
  71. /* end of macro */
  72.  
  73.   void set(int64_t index) {
  74.     if (index >= _size) return;
  75.     int64_t q, r;
  76.     divmod(index, bits, q, r);
  77.     T elements;
  78.  
  79.     MACRO_CAS(elements)
  80.  
  81.     elements |= 1 << r;
  82.     _myVectorBool[q]._a.store(elements);
  83.   }
  84.  
  85.   void reset(int64_t index) {
  86.     if (index >= _size) return;
  87.     int64_t q, r;
  88.     divmod(index, bits, q, r);
  89.     T elements;
  90.  
  91.     MACRO_CAS(elements)
  92.  
  93.     T mask = 1 << r;
  94.     elements &= ~mask;
  95.     _myVectorBool[q]._a.store(elements);
  96.   }
  97. };
  98. /*------------------------------------------------*/
  99.  
  100. int const A = 60; /* test A */
  101. int const B = 15; /* test B */
  102.  
  103. MyVectorBool vb1(A);
  104. MyVectorBool vb2(B);
  105.  
  106. void worker(int i) {
  107.   vb2.set(i);
  108. }
  109.  
  110. int main() {
  111.   /* test A */
  112.   for (int i = 0; i < A; i++) {
  113.     std::cout << "set: i = " << i << " : ";
  114.     vb1.set(i);
  115.     if (vb1.test(i)) std::cout << "OK" << std::endl;
  116.     else { std::cout << "NG" << std::endl; return 0; }
  117.   }
  118.   for (int i = 0; i < A; i++) {
  119.     std::cout << "reset: i = " << i << " : ";
  120.     vb1.reset(i);
  121.     if (!vb1.test(i)) std::cout << "OK" << std::endl;
  122.     else { std::cout << "NG" << std::endl; return 0; }
  123.   }
  124.  
  125.   /* test B */
  126.   std::cout << "core.n = " << std::thread::hardware_concurrency() << std::endl;
  127.  
  128.   for (int i = 0; i < B; i++)
  129.     std::cout << (vb2.test(i) ? "1" : "0");
  130.   std::cout << std::endl;
  131.  
  132.   std::vector<std::shared_ptr<std::thread>> threads(B);
  133.   int i = 0;
  134.   for (std::shared_ptr<std::thread> &t : threads)
  135.     t = std::make_shared<std::thread>(worker, i++);
  136.  
  137.   for (std::shared_ptr<std::thread> t : threads)
  138.     t->join();
  139.  
  140.   for (int i = 0; i < B; i++)
  141.     std::cout << (vb2.test(i) ? "1" : "0");
  142.   std::cout << std::endl;
  143.  
  144.   return 0;
  145. }
  146. /* end */
  147.  
Success #stdin #stdout 0s 46024KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
set: i = 0 : OK
set: i = 1 : OK
set: i = 2 : OK
set: i = 3 : OK
set: i = 4 : OK
set: i = 5 : OK
set: i = 6 : OK
set: i = 7 : OK
set: i = 8 : OK
set: i = 9 : OK
set: i = 10 : OK
set: i = 11 : OK
set: i = 12 : OK
set: i = 13 : OK
set: i = 14 : OK
set: i = 15 : OK
set: i = 16 : OK
set: i = 17 : OK
set: i = 18 : OK
set: i = 19 : OK
set: i = 20 : OK
set: i = 21 : OK
set: i = 22 : OK
set: i = 23 : OK
set: i = 24 : OK
set: i = 25 : OK
set: i = 26 : OK
set: i = 27 : OK
set: i = 28 : OK
set: i = 29 : OK
set: i = 30 : OK
set: i = 31 : OK
set: i = 32 : OK
set: i = 33 : OK
set: i = 34 : OK
set: i = 35 : OK
set: i = 36 : OK
set: i = 37 : OK
set: i = 38 : OK
set: i = 39 : OK
set: i = 40 : OK
set: i = 41 : OK
set: i = 42 : OK
set: i = 43 : OK
set: i = 44 : OK
set: i = 45 : OK
set: i = 46 : OK
set: i = 47 : OK
set: i = 48 : OK
set: i = 49 : OK
set: i = 50 : OK
set: i = 51 : OK
set: i = 52 : OK
set: i = 53 : OK
set: i = 54 : OK
set: i = 55 : OK
set: i = 56 : OK
set: i = 57 : OK
set: i = 58 : OK
set: i = 59 : OK
reset: i = 0 : OK
reset: i = 1 : OK
reset: i = 2 : OK
reset: i = 3 : OK
reset: i = 4 : OK
reset: i = 5 : OK
reset: i = 6 : OK
reset: i = 7 : OK
reset: i = 8 : OK
reset: i = 9 : OK
reset: i = 10 : OK
reset: i = 11 : OK
reset: i = 12 : OK
reset: i = 13 : OK
reset: i = 14 : OK
reset: i = 15 : OK
reset: i = 16 : OK
reset: i = 17 : OK
reset: i = 18 : OK
reset: i = 19 : OK
reset: i = 20 : OK
reset: i = 21 : OK
reset: i = 22 : OK
reset: i = 23 : OK
reset: i = 24 : OK
reset: i = 25 : OK
reset: i = 26 : OK
reset: i = 27 : OK
reset: i = 28 : OK
reset: i = 29 : OK
reset: i = 30 : OK
reset: i = 31 : OK
reset: i = 32 : OK
reset: i = 33 : OK
reset: i = 34 : OK
reset: i = 35 : OK
reset: i = 36 : OK
reset: i = 37 : OK
reset: i = 38 : OK
reset: i = 39 : OK
reset: i = 40 : OK
reset: i = 41 : OK
reset: i = 42 : OK
reset: i = 43 : OK
reset: i = 44 : OK
reset: i = 45 : OK
reset: i = 46 : OK
reset: i = 47 : OK
reset: i = 48 : OK
reset: i = 49 : OK
reset: i = 50 : OK
reset: i = 51 : OK
reset: i = 52 : OK
reset: i = 53 : OK
reset: i = 54 : OK
reset: i = 55 : OK
reset: i = 56 : OK
reset: i = 57 : OK
reset: i = 58 : OK
reset: i = 59 : OK
core.n = 8
000000000000000
111111111111111
https://ideone.com/nwcmzq
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!