unordered_tuple.hpp

Go to the documentation of this file.

#ifndef LIBJMMCG_CORE_UNORDERED_TUPLE_HPP
#define LIBJMMCG_CORE_UNORDERED_TUPLE_HPP
 
/******************************************************************************
** Copyright © 2017 by J.M.McGuiness, libjmmcg@hussar.me.uk
**
** This library is free software; you can redistribute it and/or
** modify it under the terms of the GNU Lesser General Public
** License as published by the Free Software Foundation; either
** version 2.1 of the License, or (at your option) any later version.
**
** This library is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
** Lesser General Public License for more details.
**
** You should have received a copy of the GNU Lesser General Public
** License along with this library; if not, write to the Free Software
** Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
 
#include "blatant_old_msvc_compiler_hacks.hpp"
#include "max_min.hpp"
#include "non_allocatable.hpp"
 
#include "frozen/unordered_map.h"
 
#include <algorithm>
#include <cstdint>
 
namespace jmmcg { namespace LIBJMMCG_VER_NAMESPACE {
 
/// A unordered container for a disparate list of types for which the keys form a perfect hash, computable at compile-time.
/**
   This class performs zero memory allocations. All of the data is maintained on the stack at the cost of some additional space. There is padding added between each instance of a MappedType to ensure that those instances avoid false sharing in any cache level.
*/
template<
   class KeyType, ///< The type of the keys used to identify the particular instance of a MappedType.
   class MappedType, ///< A base-class common to all of the MappedTypes.
   class Hasher,  ///< The hash functor to be applied to the keys.
   template<class> class ExtractHash,  ///< A template-algorithm to extract the particular key to be hashed from the MappedType, that will be hashed using the Hasher. Must have a static, constexpr member called value that should contain the key extracted from the type.
   class... MappedTypes ///< The disparate list of types to be contained, which will be used to generate a hash with ExtractHash and Hasher.
>
class unordered_tuple final : private non_newable {
public:
   enum : std::size_t {
      size=sizeof...(MappedTypes)
   };
   BOOST_MPL_ASSERT_RELATION(size, >, 0);
 
private:
   using mapped_buffer_element=std::uint8_t;
   enum : std::size_t {
      tmp_max_size=varadic_max(sizeof(MappedTypes)...),
      mapped_elem_stride=((tmp_max_size+sizeof(std::uint64_t))/sizeof(std::uint64_t))*sizeof(std::uint64_t), ///< False sharing size.
   };
   /**
      As we do not know the alignment of each of the objects to be constructed, be very conservative and 64-bit align all of them. This might waste memory, but that is life... At least they'll be better aligned to avoid false sharing.
   */
   BOOST_MPL_ASSERT_RELATION(mapped_elem_stride%sizeof(std::uint64_t), ==, 0);
 
public:
   enum : std::size_t {
      max_size=mapped_elem_stride*size
   };
 
private:
   /// Map the keys to an index into the mapped_cont_t, at compile-time.
   using mapped_index_colln=frozen::unordered_map<
      KeyType,
      unsigned,
      size,
      Hasher
   >;
   template<class>
   class idx_for_mapped_index_colln;
   template<std::size_t... Indices>
   class idx_for_mapped_index_colln<std::index_sequence<Indices...>> final {
   public:
      static constexpr typename mapped_index_colln::const_iterator
      find(typename mapped_index_colln::key_type key) noexcept(true) {
         typename mapped_index_colln::const_iterator const iter=mapped_indices.find(key);
         assert(iter!=mapped_indices.end());
         return iter;
      }
 
   private:
      /// The compile-time map of hashes to indices into the mapped_cont_t.
      ALIGN_TO_L1_CACHE static inline constexpr const mapped_index_colln mapped_indices={
         {ExtractHash<MappedTypes>::value, Indices*mapped_elem_stride}...
      };
   };
   using mapped_index_colln_t=idx_for_mapped_index_colln<std::make_index_sequence<size>>;
 
   /// The type of the underlying buffer that will contain the instances of mapped_types.
   using mapped_cont_t=std::array<mapped_buffer_element, mapped_elem_stride*size>;
   enum : std::size_t {
      objs_size=(0+...+sizeof(MappedTypes))
   };
   BOOST_MPL_ASSERT_RELATION(static_cast<std::size_t>(objs_size), <=, static_cast<std::size_t>(max_size));
 
   /**
       Avoid false sharing...
    */
   ALIGN_TO_L1_CACHE mapped_cont_t mapped_cont{};
 
   /// Recursively construct, in turn & in-place, each instance of a mapped_type, immediately stopping if an exception is thrown.
   template<class MappedType1, class... MappedTypes1>
   struct ctors_t final {
      template<class MappedCtorArg, class... MappedCtorArgs>
      static void
      result(typename mapped_cont_t::pointer ptr, MappedCtorArg &&arg, MappedCtorArgs &&...args) noexcept(
         noexcept(MappedType1(std::forward<MappedCtorArg>(arg)))
         ||
         noexcept(ctors_t<MappedTypes1...>::result(ptr+mapped_elem_stride, std::forward<MappedCtorArgs>(args)...))
      ) {
         BOOST_MPL_ASSERT((std::is_base_of<mapped_type, MappedType1>));
         new (ptr) MappedType1(std::forward<MappedCtorArg>(arg));
         ctors_t<MappedTypes1...>::result(ptr+mapped_elem_stride, std::forward<MappedCtorArgs>(args)...);
      }
   };
   template<class MappedType1>
   struct ctors_t<MappedType1> final {
      template<class MappedCtorArg>
      static void result(typename mapped_cont_t::pointer ptr, MappedCtorArg &&arg) noexcept(noexcept(MappedType1(std::forward<MappedCtorArg>(arg)))) {
         BOOST_MPL_ASSERT((std::is_base_of<mapped_type, MappedType1>));
         new (ptr) MappedType1(std::forward<MappedCtorArg>(arg));
      }
   };
   /// Recursively construct, in turn & in-place, each instance of a mapped_type, immediately stopping if an exception is thrown.
   template<class MappedType1, class... MappedTypes1>
   struct default_ctors_t final {
      static void
      result(typename mapped_cont_t::pointer ptr) noexcept(
         noexcept(MappedType1())
         || noexcept(default_ctors_t<MappedTypes1...>::result(ptr+mapped_elem_stride))
      ) {
         BOOST_MPL_ASSERT((std::is_base_of<mapped_type, MappedType1>));
         new (ptr) MappedType1();
         default_ctors_t<MappedTypes1...>::result(ptr+mapped_elem_stride);
      }
   };
   template<class MappedType1>
   struct default_ctors_t<MappedType1> final {
      static void
      result(typename mapped_cont_t::pointer ptr) noexcept(noexcept(MappedType1())) {
         BOOST_MPL_ASSERT((std::is_base_of<mapped_type, MappedType1>));
         new (ptr) MappedType1();
      }
   };
 
public:
   using key_type=typename mapped_index_colln::key_type;
   using mapped_type=MappedType;
 
   // TODO consider noexcept(true) ctors, so no need for try-catch so constexpr ctors possible...
   unordered_tuple() noexcept(noexcept(default_ctors_t<MappedTypes...>::result(mapped_cont.data())));
   /**
      If the construction of any instance of a mapped_type fails, then any already constructed instance of a mapped_type will be correctly deleted, and that failing exception re-thrown.
      Each of the MappedTypes is either default constructed or constructed with exactly, successively, one of the {arg, args...} parameters passed to this ctor. Thus there must be the same number of MappedTypes as the number of ctor arguments passed in. i.e. sizeof...(MappedTypes)==sizeof...(args)+1.
   */
   template<
      class MappedCtorArg,
      class... MappedCtorArgs,
      class =typename std::enable_if<!std::is_convertible<MappedCtorArg, unordered_tuple>::value>::type
   >
   unordered_tuple(MappedCtorArg &&arg, MappedCtorArgs &&... args) noexcept(noexcept(ctors_t<MappedTypes...>::result(mapped_cont.data(), std::forward<MappedCtorArg>(arg), std::forward<MappedCtorArgs>(args)...)));
   ~unordered_tuple() noexcept(true);
 
   /// Find the instance of mapped_type associated with the instance of key_type.
   /**
      Algorithmic complexity: O(1)
      Note that great effort has been made to ensure that this is as fast as possible.
 
      \param key  The instance of key_type associated with a mapped_type.
      \return  A reference to the associated instance of mapped_type.
    */
   constexpr mapped_type const &operator[](const key_type key) const noexcept(true);
   /// Find the instance of mapped_type associated with the instance of key_type.
   /**
      Algorithmic complexity: O(1)
      Note that great effort has been made to ensure that this is as fast as possible.
 
      \param key  The instance of key_type associated with a mapped_type.
      \return  A reference to the associated instance of mapped_type.
    */
   constexpr mapped_type &operator[](const key_type key) noexcept(true);
 
private:
   /// Recursively delete, in turn, all instanced of mapped_types that have been successfully constructed.
   template<class MappedType1, class... MappedTypes1>
   struct dtors final {
      static void result(typename mapped_cont_t::pointer ptr) noexcept(true) {
         MappedType1 * obj_ctord=reinterpret_cast<MappedType1 *>(ptr);
         if (obj_ctord) {
            obj_ctord->~MappedType1();
            obj_ctord=nullptr;
         }
         dtors<MappedTypes1...>::result(ptr+mapped_elem_stride);
      }
   };
   template<class MappedType1>
   struct dtors<MappedType1> final {
      static void result(typename mapped_cont_t::pointer ptr) noexcept(true) {
         MappedType1 * obj_ctord=reinterpret_cast<MappedType1 *>(ptr);
         if (obj_ctord) {
            obj_ctord->~MappedType1();
            obj_ctord=nullptr;
         }
      }
   };
};
 
} }
 
#include "unordered_tuple_impl.hpp"
 
#endif