fork download
copy 
  1. #include <atomic>
  2. #include <cassert>
  3. #include <thread>
  4. #include <type_traits>
  5. #include <utility>
  6.  
  7. // Make a bitfield class that has a private BaseT bitfield.
  8. // Then, for each bitfield member, make a method that returns a bitfield_member
  9. // for that.
  10. //
  11. // Ex:
  12. // class MyBitfield {
  13. //    unsigned long long bits;
  14. //    using A_type = bitfield_member<unsigned long long, bool, 0, 1>;
  15. //    using A_const = bitfield_member<unsigned long long, const bool, 0, 1>;
  16. //    using B_type = bitfield_member<unsigned long long, unsigned short, 1, 16>
  17. // public:
  18. //    A_type A() {return {bits};}
  19. //    A_const A() const {return {bits};}
  20. //    B_type B() {return {bits};}
  21. //    B_const B() const {return {bits};}
  22. // };
  23. //
  24. template<class BaseT, class FieldT, unsigned bitcount, unsigned offset>
  25. class bitfield_member {
  26.     static_assert(bitcount>0);
  27.     static_assert(bitcount<sizeof(BaseT)*8);
  28.     static_assert(offset<sizeof(BaseT)*8-bitcount);
  29.  
  30.     static const BaseT lomask = static_cast<BaseT>((1ull<<bitcount)-1ull);
  31.     BaseT* bits;
  32. public:
  33.     constexpr explicit bitfield_member(BaseT& bits_) :bits(&bits_) {}
  34.     constexpr operator FieldT() const {return get();}
  35.     constexpr FieldT get() const {return static_cast<FieldT>((*bits>>offset)&lomask);}
  36.     constexpr void set(FieldT value) {
  37.     	assert((value&mask)==value);
  38.     	*bits = (*bits&~(lomask<<offset))|(static_cast<BaseT>(value)<<offset); 
  39.     }
  40.     constexpr bitfield_member& operator=(FieldT value) {set(value); return *this;}
  41.     constexpr bitfield_member& operator++() {set(get()++); return *this;}
  42.     constexpr FieldT operator++(int) {FieldT t=get(); set(get()++); return t;}
  43.     constexpr bitfield_member& operator--() {set(get()--); return *this;}
  44.     constexpr FieldT operator--(int) {FieldT t=get(); set(get()--); return t;}
  45.     constexpr FieldT operator+() const {return get();}
  46.     constexpr FieldT operator-() const {return -get();}
  47.     constexpr FieldT operator!() const {return !get();}
  48.     constexpr FieldT operator~() const {return ~get();}
  49.     constexpr FieldT operator*(FieldT value) const {return get()*value;}
  50.     constexpr bitfield_member& operator*=(FieldT value) {set(get()*value); return *this;}
  51.     constexpr FieldT operator/(FieldT value) const {return get()/value;}
  52.     constexpr bitfield_member& operator/=(FieldT value) {set(get()/value); return *this;}
  53.     constexpr FieldT operator%(FieldT value) const {return get()%value;}
  54.     constexpr bitfield_member& operator%=(FieldT value) {set(get()%value); return *this;}
  55.     constexpr FieldT operator+(FieldT value) const {return get()+value;}
  56.     constexpr bitfield_member& operator+=(FieldT value) {set(get()+value); return *this;}
  57.     constexpr FieldT operator-(FieldT value) const {return get()-value;}
  58.     constexpr bitfield_member& operator-=(FieldT value) {set(get()-value); return *this;}
  59.     constexpr FieldT operator<<(FieldT value) const {return get()<<value;}
  60.     constexpr bitfield_member& operator<<=(FieldT value) {set(get()<<=value); return *this;}
  61.     constexpr FieldT operator>>(FieldT value) const {return get()>>value;}
  62.     constexpr bitfield_member& operator>>=(FieldT value) {set(get()>>=value); return *this;}
  63.     constexpr bool operator<(FieldT value) const {return get()<value;}
  64.     constexpr bool operator<=(FieldT value) const {return get()<=value;}
  65.     constexpr bool operator>(FieldT value) const {return get()>value;}
  66.     constexpr bool operator>=(FieldT value) const {return get()>=value;}
  67.     constexpr bool operator==(FieldT value) const {return get()==value;}
  68.     constexpr bool operator!=(FieldT value) const {return get()!=value;}
  69.     constexpr FieldT operator&(FieldT value) const {return get()&value;}
  70.     constexpr bitfield_member& operator&=(FieldT value) {set(get()&value); return *this;}
  71.     constexpr FieldT operator^(FieldT value) const {return get()^value;}
  72.     constexpr bitfield_member& operator^=(FieldT value) {set(get()^value); return *this;}
  73.     constexpr FieldT operator|(FieldT value) const {return get()|value;}
  74.     constexpr bitfield_member& operator|=(FieldT value) {set(get()|value); return *this;}
  75. };
  76.  
  77. enum class atomic_bitfield_mutate_step {store, abort, yield_and_retry};
  78. template<class T, class F>
  79. std::pair<bool,T> atomic_bitfield_mutate(std::atomic<T>& atomic, F mutation) {
  80. #if __cpp_lib_is_invocable
  81.     static_assert(std::is_invocable_r_v<atomic_bitfield_mutate_step, F, T&>);
  82. #endif
  83.     T old_value = atomic.load(std::memory_order_consume);
  84.     T store_value;
  85.     do {
  86.         store_value = old_value;
  87.         auto step = mutation(store_value);
  88.         if (step == atomic_bitfield_mutate_step::abort) {return {false, old_value};}
  89.         if (step == atomic_bitfield_mutate_step::yield_and_retry) {std::this_thread::yield(); old_value = atomic.load(std::memory_order_consume); continue;}
  90.     } while(!atomic.compare_exchange_weak(old_value, store_value));
  91.     return {true, store_value};
  92. }
  93.  
  94. template<class T, class F, class...Args>
  95. T atomic_bitfield_busy_wait_until(std::atomic<T>& atomic, Args&&...params, F is_done_waiting) {
  96. #if __cpp_lib_is_invocable
  97.     static_assert(std::is_invocable_r_v<bool, F, T&, Args...>);
  98. #endif
  99.     T old_value;
  100.     bool is_done;
  101.     do {
  102.         old_value = atomic.load(std::memory_order_consume);
  103.         is_done = is_done_waiting(old_value, std::forward<Args>(params)...);
  104.     } while(!is_done && (std::this_thread::yield(),true));
  105.     return old_value;
  106. }
  107.  
  108.  
  109.  
  110.  
  111.  
  112. //USAGE:
  113. class SingleProducerConsumer 
  114. {
  115. 	struct bitfield {
  116.         using read_idx_t = bitfield_member<unsigned, unsigned, 8, 0>;
  117.         using write_idx_t = bitfield_member<unsigned, unsigned, 8, 8>;
  118.         using end_idx_t = bitfield_member<unsigned, unsigned, 8, 16>;
  119.         using is_end_found_t = bitfield_member<unsigned, bool, 1, 24>;
  120.         using should_abort_t = bitfield_member<unsigned, bool, 1, 25>;
  121.  
  122.         unsigned value;
  123.  
  124.         read_idx_t read_idx() {return read_idx_t{value};} 
  125.         write_idx_t write_idx() {return write_idx_t{value};}
  126.         end_idx_t end_idx() {return end_idx_t{value};}
  127.         is_end_found_t is_end_found() {return is_end_found_t{value};}
  128.         should_abort_t should_abort() {return should_abort_t{value};}
  129. 	};
  130.  
  131. 	std::atomic<bitfield> async_flags;
  132.  
  133.     int values[32];
  134.  
  135.     void produce(int value) {
  136.     	unsigned write_idx = async_flags.load(std::memory_order_consume).write_idx();
  137.     	values[write_idx] = value;
  138.     	unsigned next_idx = (write_idx+1)%32;
  139.         std::pair<bool,bitfield> did_advance = atomic_bitfield_mutate(async_flags, [=](bitfield& flags) {
  140.             if (flags.should_abort()) return atomic_bitfield_mutate_step::abort;
  141.             if (next_idx == flags.read_idx()) return atomic_bitfield_mutate_step::yield_and_retry;
  142.             flags.write_idx() = next_idx;
  143.             return atomic_bitfield_mutate_step::store;
  144.         });
  145.     }
  146.     void producer_mark_end() {
  147.     	unsigned idx = async_flags.load(std::memory_order_consume).write_idx();
  148.         unsigned next_idx = (idx + 1) % 32;
  149.         atomic_bitfield_mutate(async_flags, [=](bitfield& flags) {
  150.             if (flags.should_abort()) return atomic_bitfield_mutate_step::abort;
  151.             if (next_idx == flags.read_idx()) return atomic_bitfield_mutate_step::yield_and_retry;
  152.             flags.write_idx() = next_idx;
  153.             flags.end_idx() = idx;
  154.             flags.is_end_found() = true;
  155.             return atomic_bitfield_mutate_step::store;
  156.         });
  157.     }
  158.     bool consumer_at_end() const {
  159.         bitfield flags = async_flags.load(std::memory_order_consume);
  160.         return flags.is_end_found() && flags.read_idx()==flags.end_idx();
  161.     }
  162.     int consumer_read() {
  163.         bitfield flags = atomic_bitfield_busy_wait_until(async_flags, [](bitfield& flags) {
  164.             return flags.read_idx() != flags.write_idx();
  165.         });
  166.         unsigned idx = flags.read_idx();
  167.         return values[idx];
  168.     }
  169.     void consumer_advance() {
  170.         std::pair<bool,bitfield> r = atomic_bitfield_mutate(async_flags, [](bitfield& flags) {
  171.             unsigned old_idx = flags.read_idx();
  172.             if (old_idx == flags.write_idx()) return atomic_bitfield_mutate_step::yield_and_retry;
  173.             flags.read_idx() = (old_idx+1) % 32;
  174.             return atomic_bitfield_mutate_step::store;
  175.         });
  176.     }
  177. };
  178.  
  179. #include <iostream>
  180. int main() {
  181. 	SingleProducerConsumer t;
  182. }
Success #stdin #stdout 0s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/QK6NSG
language:
C++14 (gcc 8.3)
created:
35 days ago
visibility:
secret

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!