diff options
Diffstat (limited to 'third_party/immer/immer/detail/hamts/bits.hpp')
-rw-r--r-- | third_party/immer/immer/detail/hamts/bits.hpp | 108 |
1 files changed, 0 insertions, 108 deletions
diff --git a/third_party/immer/immer/detail/hamts/bits.hpp b/third_party/immer/immer/detail/hamts/bits.hpp deleted file mode 100644 index b02caf770666..000000000000 --- a/third_party/immer/immer/detail/hamts/bits.hpp +++ /dev/null @@ -1,108 +0,0 @@ -// -// immer: immutable data structures for C++ -// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente -// -// This software is distributed under the Boost Software License, Version 1.0. -// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt -// - -#pragma once - -#include <cstdint> - -#if defined(_MSC_VER) -#include <intrin.h> // __popcnt -#endif - -namespace immer { -namespace detail { -namespace hamts { - -using size_t = std::size_t; -using hash_t = std::size_t; -using bits_t = std::uint32_t; -using count_t = std::uint32_t; -using shift_t = std::uint32_t; - -template <bits_t B> -struct get_bitmap_type -{ - static_assert(B < 6u, "B > 6 is not supported."); - - using type = std::uint32_t; -}; - -template <> -struct get_bitmap_type<6u> -{ - using type = std::uint64_t; -}; - -template <bits_t B, typename T = count_t> -constexpr T branches = T{1u} << B; - -template <bits_t B, typename T = size_t> -constexpr T mask = branches<B, T> - 1u; - -template <bits_t B, typename T = count_t> -constexpr T max_depth = (sizeof(hash_t) * 8u + B - 1u) / B; - -template <bits_t B, typename T = count_t> -constexpr T max_shift = max_depth<B, count_t>* B; - -#define IMMER_HAS_BUILTIN_POPCOUNT 1 - -inline auto popcount_fallback(std::uint32_t x) -{ - // More alternatives: - // https://en.wikipedia.org/wiki/Hamming_weight - // http://wm.ite.pl/articles/sse-popcount.html - // http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel - x = x - ((x >> 1) & 0x55555555u); - x = (x & 0x33333333u) + ((x >> 2) & 0x33333333u); - return (((x + (x >> 4u)) & 0xF0F0F0Fu) * 0x1010101u) >> 24u; -} - -inline auto popcount_fallback(std::uint64_t x) -{ - x = x - ((x >> 1) & 0x5555555555555555u); - x = (x & 0x3333333333333333u) + ((x >> 2u) & 0x3333333333333333u); - return (((x + (x >> 4)) & 0x0F0F0F0F0F0F0F0Fu) * 0x0101010101010101u) >> - 56u; -} - -inline count_t popcount(std::uint32_t x) -{ -#if IMMER_HAS_BUILTIN_POPCOUNT -#if defined(_MSC_VER) - return __popcnt(x); -#else - return __builtin_popcount(x); -#endif -#else - return popcount_fallback(x); -#endif -} - -inline count_t popcount(std::uint64_t x) -{ -#if IMMER_HAS_BUILTIN_POPCOUNT -#if defined(_MSC_VER) -#if defined(_WIN64) - return __popcnt64(x); -#else - // TODO: benchmark against popcount_fallback(std::uint64_t x) - return popcount(static_cast<std::uint32_t>(x >> 32)) + - popcount(static_cast<std::uint32_t>(x)); -#endif -#else - return __builtin_popcountll(x); -#endif -#else - return popcount_fallback(x); -#endif -} - -} // namespace hamts -} // namespace detail -} // namespace immer |