bitfield_map.hpp

Go to the documentation of this file.

#ifndef LIBJMMCG_CORE_BITFIELD_MAP_HPP
#define LIBJMMCG_CORE_BITFIELD_MAP_HPP
/******************************************************************************
** Copyright © 2014 by J.M.McGuiness, coder@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 "bit_fiddling.hpp"
#include "count_setbits.hpp"
#include "memops.hpp"
#include "sizeof_void.hpp"
 
#include <boost/mpl/accumulate.hpp>
#include <boost/mpl/assert.hpp>
#include <boost/mpl/at.hpp>
#include <boost/mpl/begin.hpp>
#include <boost/mpl/deref.hpp>
#include <boost/mpl/empty.hpp>
#include <boost/mpl/find_if.hpp>
#include <boost/mpl/int.hpp>
#include <boost/mpl/next.hpp>
#include <boost/mpl/not.hpp>
#include <boost/mpl/placeholders.hpp>
#include <boost/mpl/plus.hpp>
#include <boost/mpl/size.hpp>
#include <boost/mpl/sizeof.hpp>
#include <boost/mpl/transform_view.hpp>
 
#include <cassert>
#include <limits>
#include <cstdint>
#include <sstream>
#include <stdexcept>
#include <type_traits>
 
namespace jmmcg { namespace LIBJMMCG_VER_NAMESPACE {
 
/// This container is an associative collection of types. The domain is a bit-map of the mapped_types that are selected in the range.
/**
   This container packs a selection of objects of the types that are given in mapped_types into an internal buffer of contiguous memory. If few types are selected, then the size() returns much less than the size of the object (which must be large enough to holds all of the mapped_types). It could be useful for passing assorted large mapped_types along a slow network link, when, usually, not all are needed.
   Note that the types placed in mapped_types must be able to support arbitrary alignment - no guarantee of correct alignment is made by this class. These types are packed into the internal buffer such that there is no padding used, hence no guarantee of correct alignment. This restriction implies that only PODs are likely to be supported, in general.
*/
template<
   class BFSM,
   std::size_t BFSz=sizeof(typename std::underlying_type<typename boost::mpl::deref<typename boost::mpl::begin<BFSM>::type>::type::first::value_type>::type)
>
class bitfield_map {
public:
   using key_type=uint64_t;
   using size_type=std::size_t;
   using mapped_types=BFSM;   ///< The range of mapped-types that may be selected by the domain. This range is a collection that is indexed by the unique enum-tag of the range.
   using bitfields_tags_type=typename boost::mpl::deref<typename boost::mpl::begin<mapped_types>::type>::type::first::value_type;   ///< The range of enum-tags used to indicate the requested element in the mapped_types range.
   using underlying_key_type=typename std::underlying_type<bitfields_tags_type>::type; ///< The underlying type of the domain enum.
 
   /**
      Make sure the funky mpl actually finds something that is POD-like so could be an enumeration...
   */
   BOOST_MPL_ASSERT((std::is_pod<bitfields_tags_type>));
   /**
      Make sure the funky mpl actually finds something that is integral so could be an enumeration...
   */
   BOOST_MPL_ASSERT((std::is_integral<typename std::underlying_type<bitfields_tags_type>::type>));
 
   enum : std::size_t {
      range_mapped_types_size=boost::mpl::accumulate<
         boost::mpl::transform_view<mapped_types, boost::mpl::sizeof_<boost::mpl::second<boost::mpl::_1>>>,
         boost::mpl::int_<0u>::type,
         boost::mpl::plus<boost::mpl::_1, boost::mpl::_2>
      >::type::value,   ///< The sum of the sizes of the types in mapped_types.
      bitfields_size=BFSz, ///< The number of 8-bit bytes that the range of enum-tags should occupy. By default this is the sizeof(underlying_key_type). Note that enums require the underlying type to be an integral type, so this option allows for non-integral "underlying types". Also note that if this option is used it is the responsibility of the user to ensure that the number of bits in the underlying type can accommodate the number of enum-tags in the range.
      mapped_types_size=boost::mpl::size<mapped_types>::value
   };
 
   using raw_mapped_data_t=std::array<uint8_t, range_mapped_types_size>;
 
private:
   using raw_key_type_t=std::array<uint8_t, bitfields_size>;
 
public:
   enum : bool {
      all_pod=std::is_same<
         typename boost::mpl::find_if<
            mapped_types,
            boost::mpl::not_<std::is_pod<boost::mpl::second<boost::mpl::_1>>>
         >::type,
         typename boost::mpl::end<mapped_types>::type
      >::type::value ///< True if all of the range mapped_types in the container are PODs otherwise false.
   };
 
   BOOST_MPL_ASSERT_RELATION(sizeof(bitfields_tags_type), <=, sizeof(key_type));
   BOOST_MPL_ASSERT_RELATION(sizeof(underlying_key_type), ==, sizeof(bitfields_tags_type));
   BOOST_MPL_ASSERT_RELATION(range_mapped_types_size, >, 0);
   BOOST_MPL_ASSERT_RELATION(boost::mpl::empty<mapped_types>::value, !=, true);
 
   /// Default-construct an empty container.
   /**
      Algorithmic complexity: O(1)
      Post-condition: empty()==true.
   */
   constexpr bitfield_map() noexcept(true) FORCE_INLINE;
   /// Bit-wise copy the contents of the argument into the constructed container, out of the argument.
   /**
      Algorithmic complexity: O(sizeof(range of mapped_types))
      Post-condition: bm.empty()==true.
   */
   constexpr bitfield_map(bitfield_map const &) noexcept(true) FORCE_INLINE;
   /**
      Algorithmic complexity: O(sizeof(range of mapped_types))
      Post-condition: bm.empty()==true.
   */
   constexpr bitfield_map(bitfield_map &&) noexcept(true) FORCE_INLINE;
   /**
      Algorithmic complexity: POD: O(1) otherwise O(sizeof(key_type)^2)
 
      \see clear()
   */
   ~bitfield_map() noexcept(true) FORCE_INLINE;
 
   /// Bit-wise swap the contents of the container with that of the argument.
   /**
      Algorithmic complexity: O(sizeof(range of mapped_types))
 
      \see swap()
   */
   constexpr bitfield_map &operator=(bitfield_map &&) noexcept(true) FORCE_INLINE;
 
   /// Indicate if there are any elements selected in the mapped_types.
   /**
      Algorithmic complexity: O(1)
      Invariant: emply() iff size()==0
 
      \return  true if no types have been selected in the mapped_types, otherwise false.
   */
   constexpr bool empty() const noexcept(true) FORCE_INLINE;
 
   /// Indicate the total size of any elements selected in the mapped_types, including the size of the domain bitfield.
   /**
      Algorithmic complexity: O(sizeof(key_type))
      Invariant: size()<=max_size()
 
      \return  The size, in bytes, of the types have been selected in the mapped_types, otherwise 0, always less than or equal to the sum of the sizes of the types in mapped_types, range_mapped_types_size.
 
      \see max_size()
   */
   constexpr size_type size() const noexcept(true) FORCE_INLINE;
 
   /// Indicate the maximum size of all elements that can be selected in the mapped_types, including the size of the domain bitfield.
   /**
      Algorithmic complexity: O(1)
      Invariant: size()<=max_size()
 
      \return  At least the size, in bytes, of all of the types have can be selected in the mapped_types.
 
      \see size()
   */
   static constexpr size_type max_size() noexcept(true) FORCE_INLINE;
 
   /// Erase each enabled mapped_types selected in the key_type.
   /**
      Algorithmic complexity: POD: O(1) otherwise O(sizeof(key_type)^2)
      Post-condition: empty()==true.
   */
   void constexpr clear() noexcept(true) FORCE_INLINE;
 
   /// Perform a range-checked selection of the requested element.
   /**
      Algorithmic complexity: O(sizeof(key_type))
      Pre-condition: empty()==false.
 
      \return  Return a reference to the enabled SelectedField in the mapped_types, otherwise throw a std::range_error exception..
   */
   template<
      bitfields_tags_type SelectedField,
      class AsType=typename std::integral_constant<bitfields_tags_type, SelectedField>::type,
      class Ret=typename boost::mpl::at<mapped_types, AsType>::type
   >
   constexpr const Ret &at() const noexcept(false) FORCE_INLINE;
   /// Perform a range-checked selection of the requested element.
   /**
      Algorithmic complexity: O(sizeof(key_type))
      Pre-condition: empty()==false.
 
      \return  Return a reference to the enabled SelectedField in the mapped_types, otherwise throw a std::range_error exception..
   */
   template<
      bitfields_tags_type SelectedField,
      class AsType=typename std::integral_constant<bitfields_tags_type, SelectedField>::type,
      class Ret=typename boost::mpl::at<mapped_types, AsType>::type
   >
   constexpr Ret &at() noexcept(false) FORCE_INLINE;
 
   /// Remove and delete the SelectedField element, if enabled, from the mapped_types range.
   /**
      Note: this is not a generic erase, items should only be erased from the end of the collection, otherwise undefined behaviour will result. This should really be considered a pop_back() operation, where the end iterator is manually specified. Not ideal. No compaction of the mapped_types is performed after an erase, so if holes were left, this would cause the at() operations to behave incorrectly.
      Algorithmic complexity: POD: O(1) otherwise O(sizeof(key_type))
      Pre-condition: SelectedField is the last enabled bit in the key_type.
 
      \see push_back()
   */
   template<
      bitfields_tags_type SelectedField,
      class AsType=typename std::integral_constant<bitfields_tags_type, SelectedField>::type,
      class Ret=typename boost::mpl::at<mapped_types, AsType>::type
   >
   void erase() noexcept(true) FORCE_INLINE;
 
   /// Find if the SelectedField is enabled in the key_type,
   /**
      Algorithmic complexity: O(1)
 
      \return  True if the SelectedField is enabled in the key_type, otherwise false.
   */
   template<bitfields_tags_type SelectedField>
   bool find() const noexcept(true) FORCE_INLINE;
 
   /// Enable the SelectedField in the key_type, and initialise the appropriate element in the mapped_types, if necessary,
   /**
      Note: This only works going from smaller to larger tags in the key_type, one must not insert in the middle, otherwise this may result in undefined behaviour. This is because of the internally-computed offsets into the range of mapped_types. Hence one must not insert randomly: it is likely that existing contents will be incorrectly overwritten, also leading to undefined behaviour.
      Algorithmic complexity: O(sizeof(key_type))
      Post-condition: empty()==false.
 
      \return  A reference to the initialised element in the mapped_types.
   */
   template<
      bitfields_tags_type SelectedField,
      class AsType=typename std::integral_constant<bitfields_tags_type, SelectedField>::type,
      class Arg=typename boost::mpl::at<mapped_types, AsType>::type
   >
   void push_back(Arg const &) noexcept(false) FORCE_INLINE;
 
   /// Bit-wise swap the contents of the container with that of the argument.
   /**
      Algorithmic complexity: O(sizeof(range of mapped_types))
   */
   void constexpr swap(bitfield_map &) noexcept(true) FORCE_INLINE;
 
private:
   /**
      A hack to convert non-integral underlying types to integral types to allow the bit-wise operators to work.
   */
   union converter {
      key_type conv_bfs;
      raw_key_type_t bfs;  ///< Here's hoping this is LSB-justified in the word, otherwise we are b'gg'r'd...
   };
   key_type constexpr convert_to_biggest_integral_type() const noexcept(true);
 
   raw_key_type_t bfs;
   raw_mapped_data_t raw_mapped_data;
}__attribute__((packed));
 
} }
 
#include "bitfield_map_impl.hpp"
 
#endif