density_common.h

Go to the documentation of this file.

//   Copyright Giuseppe Campana (giu.campana@gmail.com) 2016-2018.
// Distributed under the Boost Software License, Version 1.0.
//    (See accompanying file LICENSE_1_0.txt or copy at
//          http://www.boost.org/LICENSE_1_0.txt)

#pragma once
#include <atomic> // for std::memory_order
#include <cstddef>
#include <limits>
#include <new>
#include <type_traits>
#include <utility>

#include <density/density_config.h>

#define DENSITY_VERSION 0x00020000

// detect 'Relaxed constraints on constexpr functions / constexpr member functions and implicit const'
// see http://en.cppreference.com/w/User:D41D8CD98F/feature_testing_macros#C.2B.2B14
#if __cpp_constexpr >= 201304
#define DENSITY_CPP14_CONSTEXPR constexpr
#else
#define DENSITY_CPP14_CONSTEXPR
#endif

#if __cpp_noexcept_function_type >= 201510
#define DENSITY_CPP17_NOEXCEPT noexcept
#else
#define DENSITY_CPP17_NOEXCEPT
#endif

// DENSITY_NODISCARD
#if defined(__has_cpp_attribute)
#if __has_cpp_attribute(nodiscard) >= 201603
// clang-format off
#define DENSITY_NODISCARD [[nodiscard]]
// clang-format on
#endif
#endif
#ifndef DENSITY_NODISCARD
#define DENSITY_NODISCARD
#endif

namespace density
{
    constexpr char version[] = "2.0.0";

    enum concurrency_cardinality
    {
        concurrency_single, 
        concurrency_multiple, 
    };

    enum consistency_model
    {
        consistency_relaxed, 
        consistency_sequential, 
    };

    enum progress_guarantee
    {
        progress_blocking, 
        progress_obstruction_free, 
        progress_lock_free, 
        progress_wait_free 
    };

    enum function_type_erasure
    {
        function_standard_erasure, 
        function_manual_clear 
    };

    // address functions

    constexpr bool is_power_of_2(size_t i_number) noexcept
    {
        //DENSITY_ASSERT(i_number > 0);
        return (i_number & (i_number - 1)) == 0;
    }

    inline bool address_is_aligned(const void * i_address, size_t i_alignment) noexcept
    {
        DENSITY_ASSERT(is_power_of_2(i_alignment));
        DENSITY_ASSUME(i_alignment > 0);
        return (reinterpret_cast<uintptr_t>(i_address) & (i_alignment - 1)) == 0;
    }

    template <typename UINT> inline bool uint_is_aligned(UINT i_uint, UINT i_alignment) noexcept
    {
        static_assert(
          std::numeric_limits<UINT>::is_integer && !std::numeric_limits<UINT>::is_signed,
          "UINT mus be an unsigned integer");
        DENSITY_ASSERT(is_power_of_2(i_alignment));
        DENSITY_ASSUME(i_alignment > 0);
        return (i_uint & (i_alignment - 1)) == 0;
    }

    inline void * address_add(void * i_address, size_t i_offset) noexcept
    {
        const uintptr_t uint_pointer = reinterpret_cast<uintptr_t>(i_address);
        return reinterpret_cast<void *>(uint_pointer + i_offset);
    }

    inline const void * address_add(const void * i_address, size_t i_offset) noexcept
    {
        const uintptr_t uint_pointer = reinterpret_cast<uintptr_t>(i_address);
        return reinterpret_cast<const void *>(uint_pointer + i_offset);
    }

    inline void * address_sub(void * i_address, size_t i_offset) noexcept
    {
        const uintptr_t uint_pointer = reinterpret_cast<uintptr_t>(i_address);
        DENSITY_ASSUME(uint_pointer >= i_offset);
        return reinterpret_cast<void *>(uint_pointer - i_offset);
    }

    inline const void * address_sub(const void * i_address, size_t i_offset) noexcept
    {
        const uintptr_t uint_pointer = reinterpret_cast<uintptr_t>(i_address);
        DENSITY_ASSUME(uint_pointer >= i_offset);
        return reinterpret_cast<const void *>(uint_pointer - i_offset);
    }

    inline uintptr_t address_diff(const void * i_end_address, const void * i_start_address) noexcept
    {
        DENSITY_ASSUME(i_end_address >= i_start_address);

        const uintptr_t end_uint_pointer   = reinterpret_cast<uintptr_t>(i_end_address);
        const uintptr_t start_uint_pointer = reinterpret_cast<uintptr_t>(i_start_address);

        return end_uint_pointer - start_uint_pointer;
    }

    inline void * address_lower_align(void * i_address, size_t i_alignment) noexcept
    {
        DENSITY_ASSERT(is_power_of_2(i_alignment));
        DENSITY_ASSUME(i_alignment > 0);

        const uintptr_t uint_pointer = reinterpret_cast<uintptr_t>(i_address);

        const size_t mask = i_alignment - 1;

        return reinterpret_cast<void *>(uint_pointer & ~mask);
    }

    inline const void * address_lower_align(const void * i_address, size_t i_alignment) noexcept
    {
        DENSITY_ASSERT(is_power_of_2(i_alignment));
        DENSITY_ASSUME(i_alignment > 0);

        const uintptr_t uint_pointer = reinterpret_cast<uintptr_t>(i_address);

        const size_t mask = i_alignment - 1;

        return reinterpret_cast<void *>(uint_pointer & ~mask);
    }

    inline void *
      address_lower_align(void * i_address, size_t i_alignment, size_t i_alignment_offset) noexcept
    {
        void * address = address_add(i_address, i_alignment_offset);

        address = address_lower_align(address, i_alignment);

        address = address_sub(address, i_alignment_offset);

        return address;
    }

    inline const void * address_lower_align(
      const void * i_address, size_t i_alignment, size_t i_alignment_offset) noexcept
    {
        const void * address = address_add(i_address, i_alignment_offset);

        address = address_lower_align(address, i_alignment);

        address = address_sub(address, i_alignment_offset);

        return address;
    }

    inline void * address_upper_align(void * i_address, size_t i_alignment) noexcept
    {
        DENSITY_ASSERT(is_power_of_2(i_alignment));
        DENSITY_ASSUME(i_alignment > 0);

        const uintptr_t uint_pointer = reinterpret_cast<uintptr_t>(i_address);

        const size_t mask = i_alignment - 1;

        return reinterpret_cast<void *>((uint_pointer + mask) & ~mask);
    }

    inline const void * address_upper_align(const void * i_address, size_t i_alignment) noexcept
    {
        DENSITY_ASSERT(is_power_of_2(i_alignment));
        DENSITY_ASSUME(i_alignment > 0);

        const uintptr_t uint_pointer = reinterpret_cast<uintptr_t>(i_address);

        const size_t mask = i_alignment - 1;

        return reinterpret_cast<void *>((uint_pointer + mask) & ~mask);
    }

    template <typename UINT>
    constexpr UINT uint_upper_align(UINT i_uint, size_t i_alignment) noexcept
    {
        static_assert(
          std::numeric_limits<UINT>::is_integer && !std::numeric_limits<UINT>::is_signed,
          "UINT must be an unsigned integer");
        return (i_uint + (i_alignment - 1)) & ~(i_alignment - 1);
    }


    template <typename UINT>
    constexpr UINT uint_lower_align(UINT i_uint, size_t i_alignment) noexcept
    {
        static_assert(
          std::numeric_limits<UINT>::is_integer && !std::numeric_limits<UINT>::is_signed,
          "UINT must be an unsigned integer");
        return i_uint & ~(i_alignment - 1);
    }

    inline void *
      address_upper_align(void * i_address, size_t i_alignment, size_t i_alignment_offset) noexcept
    {
        void * address = address_add(i_address, i_alignment_offset);

        address = address_upper_align(address, i_alignment);

        address = address_sub(address, i_alignment_offset);

        return address;
    }

    inline const void * address_upper_align(
      const void * i_address, size_t i_alignment, size_t i_alignment_offset) noexcept
    {
        const void * address = address_add(i_address, i_alignment_offset);

        address = address_upper_align(address, i_alignment);

        address = address_sub(address, i_alignment_offset);

        return address;
    }

    namespace detail
    {
        // size_min: avoid including <algorithm> just to use std::min<size_t>
        constexpr inline size_t size_min(size_t i_first, size_t i_second) noexcept
        {
            return i_first < i_second ? i_first : i_second;
        }

        // size_max: avoid including <algorithm> just to use std::max<size_t>
        constexpr inline size_t size_max(size_t i_first, size_t i_second) noexcept
        {
            return i_first > i_second ? i_first : i_second;
        }
        constexpr inline size_t size_max(size_t i_first, size_t i_second, size_t i_third) noexcept
        {
            return size_max(size_max(i_first, i_second), i_third);
        }
        constexpr inline size_t
          size_max(size_t i_first, size_t i_second, size_t i_third, size_t i_fourth) noexcept
        {
            return size_max(size_max(i_first, i_second), size_max(i_third, i_fourth));
        }

        struct AlignmentHeader
        {
            void * m_block;
        };

        constexpr auto mem_relaxed =
          !enable_relaxed_atomics ? std::memory_order_seq_cst : std::memory_order_relaxed;
        constexpr auto mem_acquire =
          !enable_relaxed_atomics ? std::memory_order_seq_cst : std::memory_order_acquire;
        constexpr auto mem_release =
          !enable_relaxed_atomics ? std::memory_order_seq_cst : std::memory_order_release;
        constexpr auto mem_acq_rel =
          !enable_relaxed_atomics ? std::memory_order_seq_cst : std::memory_order_acq_rel;
        constexpr auto mem_seq_cst =
          !enable_relaxed_atomics ? std::memory_order_seq_cst : std::memory_order_seq_cst;

        constexpr size_t size_log2(size_t i_size) noexcept
        {
            return i_size <= 1 ? 0 : size_log2(i_size / 2) + 1;
        }

        inline bool ConstConditional(bool i_value) noexcept { return i_value; }

        struct ExternalBlock
        {
            void * m_block;
            size_t m_size, m_alignment;
        };

        template <typename TYPE> struct size_of
        {
            static constexpr size_t value = std::is_empty<TYPE>::value ? 0 : sizeof(TYPE);
        };

        // old versions of libstdc++ define max_align_t only outside std::
#if defined(__GLIBCXX__)
        constexpr size_t MaxAlignment = alignof(max_align_t);
#else
        constexpr size_t MaxAlignment = alignof(std::max_align_t);
#endif

#ifdef _MSC_VER
#define DENSITY_INTERNAL_RETHROW_FROM_NOEXCEPT                                                     \
    __pragma(warning(push)) __pragma(warning(disable : 4297)) throw;                               \
    __pragma(warning(pop))
#elif defined(__GNUG__) && __GNUG__ >= 6 && !defined(__clang__)
#define DENSITY_INTERNAL_RETHROW_FROM_NOEXCEPT                                                     \
    _Pragma("GCC diagnostic push") _Pragma("GCC diagnostic ignored \"-Wterminate\"") throw;        \
    _Pragma("GCC diagnostic pop")
#else
#define DENSITY_INTERNAL_RETHROW_FROM_NOEXCEPT throw;
#endif
    } // namespace detail

    inline void * aligned_allocate(size_t i_size, size_t i_alignment, size_t i_alignment_offset = 0)
    {
        DENSITY_ASSERT(is_power_of_2(i_alignment));
        DENSITY_ASSUME(i_alignment > 0);
        DENSITY_ASSUME(i_alignment_offset <= i_size);

        void * user_block;
        if (i_alignment <= detail::MaxAlignment && i_alignment_offset == 0)
        {
            user_block = operator new(i_size);
        }
        else
        {
            // reserve an additional space in the block equal to the max(i_alignment, sizeof(AlignmentHeader) - sizeof(void*) )
            size_t const extra_size =
              detail::size_max(i_alignment, sizeof(detail::AlignmentHeader));
            size_t const actual_size  = i_size + extra_size;
            auto const complete_block = operator new(actual_size);
            user_block                = address_lower_align(
              address_add(complete_block, extra_size), i_alignment, i_alignment_offset);
            detail::AlignmentHeader & header =
              *(static_cast<detail::AlignmentHeader *>(user_block) - 1);
            header.m_block = complete_block;
            DENSITY_ASSERT_INTERNAL(
              user_block >= complete_block &&
              address_add(user_block, i_size) <= address_add(complete_block, actual_size));
        }
        return user_block;
    }

    inline void * try_aligned_allocate(
      size_t i_size, size_t i_alignment, size_t i_alignment_offset = 0) noexcept
    {
        DENSITY_ASSERT(is_power_of_2(i_alignment));
        DENSITY_ASSUME(i_alignment > 0);
        DENSITY_ASSUME(i_alignment_offset <= i_size);

        void * user_block;
        if (i_alignment <= detail::MaxAlignment && i_alignment_offset == 0)
        {
            user_block = operator new(i_size, std::nothrow);
        }
        else
        {
            // reserve an additional space in the block equal to the max(i_alignment, sizeof(AlignmentHeader) - sizeof(void*) )
            size_t const extra_size =
              detail::size_max(i_alignment, sizeof(detail::AlignmentHeader));
            size_t const actual_size  = i_size + extra_size;
            auto const complete_block = operator new(actual_size, std::nothrow);
            if (complete_block != nullptr)
            {
                user_block = address_lower_align(
                  address_add(complete_block, extra_size), i_alignment, i_alignment_offset);
                detail::AlignmentHeader & header =
                  *(static_cast<detail::AlignmentHeader *>(user_block) - 1);
                header.m_block = complete_block;
                DENSITY_ASSERT_INTERNAL(
                  user_block >= complete_block &&
                  address_add(user_block, i_size) <= address_add(complete_block, actual_size));
            }
            else
            {
                user_block = nullptr;
            }
        }
        return user_block;
    }

    inline void aligned_deallocate(
      void * i_block, size_t i_size, size_t i_alignment, size_t i_alignment_offset = 0) noexcept
    {
        DENSITY_ASSERT(is_power_of_2(i_alignment));
        DENSITY_ASSUME(i_alignment > 0);

        if (i_alignment <= detail::MaxAlignment && i_alignment_offset == 0)
        {
#if __cpp_sized_deallocation >= 201309
            operator delete(i_block, i_size); // since C++14
#else
            (void)i_size;
            operator delete(i_block);
#endif
        }
        else
        {
            if (i_block != nullptr)
            {
                const auto & header = *(static_cast<detail::AlignmentHeader *>(i_block) - 1);
#if __cpp_sized_deallocation >= 201309 // since C++14
                size_t const extra_size =
                  detail::size_max(i_alignment, sizeof(detail::AlignmentHeader));
                size_t const actual_size = i_size + extra_size;
                             operator delete(header.m_block, actual_size);
#else
                (void)i_size;
                operator delete(header.m_block);
#endif
            }
        }
    }

    // clang-format off
    // clang-format on
} // namespace density