Line data    Source code

       1             : //
       2             : // immer: immutable data structures for C++
       3             : // Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
       4             : //
       5             : // This software is distributed under the Boost Software License, Version 1.0.
       6             : // See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
       7             : //
       8             : 
       9             : #pragma once
      10             : 
      11             : #include <cstddef>
      12             : #include <cstdint>
      13             : 
      14             : #if defined(_MSC_VER)
      15             : #include <intrin.h> // __popcnt
      16             : #endif
      17             : 
      18             : namespace immer {
      19             : namespace detail {
      20             : namespace hamts {
      21             : 
      22             : using size_t  = std::size_t;
      23             : using hash_t  = std::size_t;
      24             : using bits_t  = std::uint32_t;
      25             : using count_t = std::uint32_t;
      26             : using shift_t = std::uint32_t;
      27             : 
      28             : template <bits_t B>
      29             : struct get_bitmap_type
      30             : {
      31             :     static_assert(B < 6u, "B > 6 is not supported.");
      32             :     using type = std::uint8_t;
      33             : };
      34             : 
      35             : template <>
      36             : struct get_bitmap_type<6u>
      37             : {
      38             :     using type = std::uint64_t;
      39             : };
      40             : 
      41             : template <>
      42             : struct get_bitmap_type<5u>
      43             : {
      44             :     using type = std::uint32_t;
      45             : };
      46             : 
      47             : template <>
      48             : struct get_bitmap_type<4u>
      49             : {
      50             :     using type = std::uint16_t;
      51             : };
      52             : 
      53             : template <bits_t B, typename T = count_t>
      54             : constexpr T branches = T{1u} << B;
      55             : 
      56             : template <bits_t B, typename T = size_t>
      57             : constexpr T mask = branches<B, T> - 1u;
      58             : 
      59             : template <bits_t B, typename T = count_t>
      60             : constexpr T max_depth = (sizeof(hash_t) * 8u + B - 1u) / B;
      61             : 
      62             : template <bits_t B, typename T = count_t>
      63             : constexpr T max_shift = max_depth<B, count_t>* B;
      64             : 
      65             : #define IMMER_HAS_BUILTIN_POPCOUNT 1
      66             : 
      67             : inline auto popcount_fallback(std::uint32_t x)
      68             : {
      69             :     // More alternatives:
      70             :     // https://en.wikipedia.org/wiki/Hamming_weight
      71             :     // http://wm.ite.pl/articles/sse-popcount.html
      72             :     // http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
      73             :     x = x - ((x >> 1) & 0x55555555u);
      74             :     x = (x & 0x33333333u) + ((x >> 2) & 0x33333333u);
      75             :     return (((x + (x >> 4u)) & 0xF0F0F0Fu) * 0x1010101u) >> 24u;
      76             : }
      77             : 
      78             : inline auto popcount_fallback(std::uint64_t x)
      79             : {
      80             :     x = x - ((x >> 1) & 0x5555555555555555u);
      81             :     x = (x & 0x3333333333333333u) + ((x >> 2u) & 0x3333333333333333u);
      82             :     return (((x + (x >> 4)) & 0x0F0F0F0F0F0F0F0Fu) * 0x0101010101010101u) >>
      83             :            56u;
      84             : }
      85             : 
      86      620089 : inline count_t popcount(std::uint32_t x)
      87             : {
      88             : #if IMMER_HAS_BUILTIN_POPCOUNT
      89             : #if defined(_MSC_VER)
      90             :     return __popcnt(x);
      91             : #else
      92      596384 :     return __builtin_popcount(x);
      93             : #endif
      94             : #else
      95             :     return popcount_fallback(x);
      96             : #endif
      97             : }
      98             : 
      99             : inline count_t popcount(std::uint64_t x)
     100             : {
     101             : #if IMMER_HAS_BUILTIN_POPCOUNT
     102             : #if defined(_MSC_VER)
     103             : #if defined(_WIN64)
     104             :     return static_cast<count_t>(__popcnt64(x));
     105             : #else
     106             :     // TODO: benchmark against popcount_fallback(std::uint64_t x)
     107             :     return popcount(static_cast<std::uint32_t>(x >> 32)) +
     108             :            popcount(static_cast<std::uint32_t>(x));
     109             : #endif
     110             : #else
     111             :     return __builtin_popcountll(x);
     112             : #endif
     113             : #else
     114             :     return popcount_fallback(x);
     115             : #endif
     116             : }
     117             : 
     118             : inline count_t popcount(std::uint16_t x)
     119             : {
     120             :     return popcount(static_cast<std::uint32_t>(x));
     121             : }
     122             : 
     123             : inline count_t popcount(std::uint8_t x)
     124             : {
     125             :     return popcount(static_cast<std::uint32_t>(x));
     126             : }
     127             : 
     128             : } // namespace hamts
     129             : } // namespace detail
     130             : } // namespace immer