cache_line_bitmap.hpp

#pragma once

#include <cstdint>

#include <new>
#include <limits>

#include <intrin.h>

namespace cova::mem
{
	struct cache_line_bitmap final
	{
	private:
		static constexpr size_t bits_per_byte = 8;
	public:
		static constexpr size_t bytes_per_cache_line = std::hardware_constructive_interference_size;
		static constexpr size_t bits_per_cache_line = bytes_per_cache_line * bits_per_byte;
	private:
		template<typename T>
		struct bits_per final
		{
			static constexpr size_t result = sizeof(T) * bits_per_byte;
		};

		template<typename T>
		struct is_large_enough final
		{
			static constexpr bool result = bits_per_cache_line <= (std::numeric_limits<T>::max)();
		};

		template <size_t value>
		struct significant_bits {
			static constexpr size_t result = significant_bits<value / 2>::result + 1;
		};

		template <>
		struct significant_bits<0> {
			static constexpr size_t result = 0;
		};

	public:
		using block_type = uintmax_t;
		using bit_value_type = bool;
		using bit_index_type =
			std::conditional_t<is_large_enough<int8_t>::result, int8_t,
			std::conditional_t<is_large_enough<int16_t>::result, int16_t,
			std::conditional_t<is_large_enough<int16_t>::result, int32_t,
			int64_t>>>;

	private:
		static constexpr size_t blocks_per_cache_line = bytes_per_cache_line / sizeof(block_type);
		static constexpr size_t bits_per_block = sizeof(block_type) * bits_per_byte;
		static constexpr size_t bit_index_from_lsb_mask = bits_per_block - 1;
		static constexpr size_t block_index_mask = bits_per_cache_line - 1 & ~bit_index_from_lsb_mask;
		static constexpr size_t block_index_rshift = significant_bits<bit_index_from_lsb_mask>::result;

		block_type blocks[blocks_per_cache_line];

		static_assert(sizeof(block_type) <= bytes_per_cache_line);
		static_assert(bytes_per_cache_line % sizeof(block_type) == 0);
		static_assert(bits_per_cache_line <= (numeric_limits<bit_index_type>::max)());

		static size_t get_block_index(bit_index_type i)
		{
			return (i & block_index_mask) >> significant_bits<bit_index_from_lsb_mask>::result;
		}

		static size_t get_bit_index(bit_index_type i)
		{
			return i & bit_index_from_lsb_mask;
		}
	public:
		bit_value_type test(bit_index_type i) const
		{
			auto const block_index = get_block_index(i);
			auto const bit_index_from_lsb = get_bit_index(i);
			return (blocks[block_index] >> bit_index_from_lsb) & 1;
		}

		void set(bit_index_type i)
		{
			auto const block_index = get_block_index(i);
			auto const bit_index_from_lsb = get_bit_index(i);
			blocks[block_index] |= 1ull << bit_index_from_lsb;
		}

		void reset(bit_index_type i)
		{
			auto const block_index = get_block_index(i);
			auto const bit_index_from_lsb = get_bit_index(i);
			blocks[block_index] &= ~(1 << bit_index_from_lsb);
		}

		void set()
		{
			for (size_t i = 0; i != blocks_per_cache_line; ++i)
				blocks[i] = (std::numeric_limits<block_type>::max)();
		}

		void reset()
		{
			for (size_t i = 0; i != blocks_per_cache_line; ++i)
				blocks[i] = 0;
		}

		bit_index_type popcount() const
		{
			auto popcnt = 0;
			for (size_t i = 0; i != blocks_per_cache_line; ++i)
				popcnt += _mm_popcnt_u64(blocks[i]);
			return popcnt;
		}

		bit_index_type find_first_set_bit() const
		{
			for (size_t i = 0; i != blocks_per_cache_line; ++i)
			{
				DWORD first_set_bit_index;
				auto const bits_set = _BitScanForward64(&first_set_bit_index, blocks[i]);
				if (bits_set == 0)
					continue;
				return first_set_bit_index + (i * bits_per_block);
			}
			return -1;
		}

		// atomic

		bit_value_type atomic_test_and_set(bit_index_type i)
		{
			auto const block_index = get_block_index(i);
			auto const bit_index_from_lsb = get_bit_index(i);
			return _interlockedbittestandset64(reinterpret_cast<LONG64 *>(&blocks[block_index]), bit_index_from_lsb);
		}

		bit_value_type atomic_test_and_reset(bit_index_type i)
		{
			auto const block_index = get_block_index(i);
			auto const bit_index_from_lsb = get_bit_index(i);
			return _interlockedbittestandreset64(reinterpret_cast<LONG64 *>(&blocks[block_index]), bit_index_from_lsb);
		}
	};
}