source/modules/ysfx/sources/utility/sync_bitset.hpp

   1 // Copyright 2021 Jean Pierre Cimalando
   2 //
   3 // Licensed under the Apache License, Version 2.0 (the "License");
   4 // you may not use this file except in compliance with the License.
   5 // You may obtain a copy of the License at
   6 //
   7 //     http://www.apache.org/licenses/LICENSE-2.0
   8 //
   9 // Unless required by applicable law or agreed to in writing, software
  10 // distributed under the License is distributed on an "AS IS" BASIS,
  11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12 // See the License for the specific language governing permissions and
  13 // limitations under the License.
  14 //
  15 // SPDX-License-Identifier: Apache-2.0
  16 //
  17
  18 #pragma once
  19 #include <type_traits>
  20 #include <atomic>
  21 #include <cstdint>
  22
  23 namespace ysfx {
  24
  25 //------------------------------------------------------------------------------
  26 // sync_bitset64: A lock-free synchronized bitset of size 64
  27 //
  28 // This is implemented by a single qword on 64-bit machine, otherwise a pair of
  29 // dwords on 32-bit machine, which is to ensure lock-freedom.
  30 //
  31 // This bitset is synchronized but not atomic; a thread might see a
  32 // partially updated set after a modification. Conceptually, it can be seen as
  33 // atomic on individual bit flips (that is, masking operations do not race).
  34
  35 class sync_bitset64_single;
  36 class sync_bitset64_dual;
  37
  38 // could use std::atomic::is_always_lock_free on C++17 and up
  39 using sync_bitset64 = std::conditional<
  40     sizeof(intptr_t) <= 4, sync_bitset64_dual, sync_bitset64_single>::type;
  41
  42 //------------------------------------------------------------------------------
  43 class sync_bitset64_single {
  44 public:
  45     uint64_t load() const
  46     {
  47         return bits_.load(std::memory_order_relaxed);
  48     }
  49
  50     void store(uint64_t value)
  51     {
  52         bits_.store(value, std::memory_order_relaxed);
  53     }
  54
  55     uint64_t exchange(uint64_t value)
  56     {
  57         return bits_.exchange(value, std::memory_order_relaxed);
  58     }
  59
  60     uint64_t fetch_or(uint64_t value)
  61     {
  62         return bits_.fetch_or(value, std::memory_order_relaxed);
  63     }
  64
  65     uint64_t fetch_and(uint64_t value)
  66     {
  67         return bits_.fetch_and(value, std::memory_order_relaxed);
  68     }
  69
  70     uint64_t fetch_xor(uint64_t value)
  71     {
  72         return bits_.fetch_xor(value, std::memory_order_relaxed);
  73     }
  74
  75     void operator|=(uint64_t value)
  76     {
  77         fetch_or(value);
  78     }
  79
  80     void operator&=(uint64_t value)
  81     {
  82         fetch_and(value);
  83     }
  84
  85     void operator^=(uint64_t value)
  86     {
  87         fetch_xor(value);
  88     }
  89
  90 private:
  91     std::atomic<uint64_t> bits_{0};
  92 };
  93
  94 //------------------------------------------------------------------------------
  95 class sync_bitset64_dual {
  96 public:
  97     uint64_t load() const
  98     {
  99         return join(lobits_.load(std::memory_order_relaxed),
 100                     hibits_.load(std::memory_order_relaxed));
 101     }
 102
 103     void store(uint64_t value)
 104     {
 105         lobits_.store(lo(value), std::memory_order_relaxed);
 106         hibits_.store(hi(value), std::memory_order_relaxed);
 107     }
 108
 109     uint64_t exchange(uint64_t value)
 110     {
 111         return join(lobits_.exchange(lo(value), std::memory_order_relaxed),
 112                     hibits_.exchange(hi(value), std::memory_order_relaxed));
 113     }
 114
 115     uint64_t fetch_or(uint64_t value)
 116     {
 117         return join(lobits_.fetch_or(lo(value), std::memory_order_relaxed),
 118                     hibits_.fetch_or(hi(value), std::memory_order_relaxed));
 119     }
 120
 121     uint64_t fetch_and(uint64_t value)
 122     {
 123         return join(lobits_.fetch_and(lo(value), std::memory_order_relaxed),
 124                     hibits_.fetch_and(hi(value), std::memory_order_relaxed));
 125     }
 126
 127     uint64_t fetch_xor(uint64_t value)
 128     {
 129         return join(lobits_.fetch_xor(lo(value), std::memory_order_relaxed),
 130                     hibits_.fetch_xor(hi(value), std::memory_order_relaxed));
 131     }
 132
 133     void operator|=(uint64_t value)
 134     {
 135         fetch_or(value);
 136     }
 137
 138     void operator&=(uint64_t value)
 139     {
 140         fetch_and(value);
 141     }
 142
 143     void operator^=(uint64_t value)
 144     {
 145         fetch_xor(value);
 146     }
 147
 148 private:
 149     static constexpr uint64_t join(uint32_t lo, uint32_t hi)
 150     {
 151         return (uint64_t)lo | ((uint64_t)hi << 32);
 152     }
 153
 154     static constexpr uint32_t lo(uint64_t value)
 155     {
 156         return (uint32_t)(value & 0xFFFFFFFFu);
 157     }
 158
 159     static constexpr uint32_t hi(uint64_t value)
 160     {
 161         return (uint32_t)(value >> 32);
 162     }
 163
 164 private:
 165     std::atomic<uint32_t> lobits_{0};
 166     std::atomic<uint32_t> hibits_{0};
 167 };
 168
 169 } // namespace ysfx