Simple Dynamic threadsafe bitset

threadsafe_bitset.hpp

// vim: ts=2 sw=2 et

#include <cmath>
#include <cstdint>
#include <cstdlib>
#include <atomic>
#include <vector>

namespace bits {
  template <typename Storage, bool Atomic>
  struct TypeChooser;

  template <typename Storage>
  struct TypeChooser<Storage, true> {
    using type = std::atomic<Storage>;
  };

  template <typename Storage>
  struct TypeChooser<Storage, false> {
    using type = Storage;
  };
} // ns bits


template <typename Storage=std::uint8_t, bool Atomic=true>
class DynamicBitset {

  using type = typename bits::TypeChooser<Storage, Atomic>::type;
  static constexpr std::size_t size = sizeof(Storage);

public:
  explicit DynamicBitset(std::size_t size)
    : data(ComputeVectorSize(size))
  {
    for (auto& elem: data)
      elem = 0;
  }

  bool
  Get(std::size_t index) const
  {
    std::size_t quot;
    std::size_t rem;
    DivMod(index, quot, rem);

    return data[quot] & (1 << rem);
  }

  void
  Set(std::size_t index)
  {
    std::size_t quot;
    std::size_t rem;
    DivMod(index, quot, rem);

    data[quot] |= (1 << rem);
  }

private:
  std::vector<type> data;

  static void
  DivMod(std::size_t index, std::size_t& quot, std::size_t& rem)
  {
    quot = std::floor(index / size);
    rem = index - (quot * size);
  }

  static std::size_t
  ComputeVectorSize(std::size_t elementCount)
  {
    std::size_t quot;
    std::size_t rem;

    DivMod(elementCount, quot, rem);
    if (rem != 0)
      ++quot;

    return (quot * size);
  }
};

#if PROFILING_TEST
#include <ctime>

static constexpr std::size_t BitSetSize = 4096;
static constexpr std::size_t Iterations = 10000;

template <typename Bitset>
float
TimeIt()
{
  clock_t start = clock();
  Bitset bitset(BitSetSize);

  for (size_t i = 0; i < BitSetSize; i += 2) {
    bitset.Set(i);
  }

  for (size_t k = 0; k < Iterations; ++k) {
    volatile std::size_t S = 0;
    for (size_t i = 0; i < BitSetSize; ++i) {
      S += (bitset.Get(i) ? 1 : 0);
    }

    if (S != BitSetSize / 2)
      return -1;
  }

  return float(clock() - start) / CLOCKS_PER_SEC;
}

#include <bitset>

float
TimeIt2()
{
  clock_t start = clock();
  std::bitset<BitSetSize> bitset;

  for (size_t i = 0; i < BitSetSize; i += 2) {
    bitset.set(i);
  }

  for (size_t k = 0; k < Iterations; ++k) {
    volatile std::size_t S = 0;
    for (size_t i = 0; i < BitSetSize; ++i) {
      S += (bitset.test(i) ? 1 : 0);
    }

    if (S != BitSetSize / 2)
      return -1;
  }

  return float(clock() - start) / CLOCKS_PER_SEC;
}

#include <iostream>
#include <iomanip>

int
main()
{
  std::cerr
    << "-------------------------------------" << std::endl
    << TimeIt<DynamicBitset<uint8_t, true> >() << std::endl
    << TimeIt<DynamicBitset<uint8_t, false>>() << std::endl
    << "-------------------------------------" << std::endl
    << TimeIt<DynamicBitset<uint16_t,true> >() << std::endl
    << TimeIt<DynamicBitset<uint16_t,false>>() << std::endl
    << "-------------------------------------" << std::endl
    << TimeIt<DynamicBitset<uint32_t,true> >() << std::endl
    << TimeIt<DynamicBitset<uint32_t,false>>() << std::endl
    << "-------------------------------------" << std::endl
    << TimeIt<DynamicBitset<uint64_t,true> >() << std::endl
    << TimeIt<DynamicBitset<uint64_t,false>>() << std::endl
    << "-------------------------------------" << std::endl
    << TimeIt2() << std::endl
    << std::endl;

  //DynamicBitset<> bitset(1024);

  //bitset.Set(1);

  //std::cerr << std::boolalpha
  //          << bitset.Get(0) << "\n"
  //          << bitset.Get(1) << "\n"
  //          << std::endl;
}
#endif