Chris@101: /* Copyright 2003-2014 Joaquin M Lopez Munoz.
Chris@16:  * Distributed under the Boost Software License, Version 1.0.
Chris@16:  * (See accompanying file LICENSE_1_0.txt or copy at
Chris@16:  * http://www.boost.org/LICENSE_1_0.txt)
Chris@16:  *
Chris@16:  * See http://www.boost.org/libs/multi_index for library home page.
Chris@16:  */
Chris@16: 
Chris@16: #ifndef BOOST_MULTI_INDEX_DETAIL_BUCKET_ARRAY_HPP
Chris@16: #define BOOST_MULTI_INDEX_DETAIL_BUCKET_ARRAY_HPP
Chris@16: 
Chris@101: #if defined(_MSC_VER)
Chris@16: #pragma once
Chris@16: #endif
Chris@16: 
Chris@16: #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
Chris@16: #include <algorithm>
Chris@16: #include <boost/multi_index/detail/auto_space.hpp>
Chris@16: #include <boost/multi_index/detail/hash_index_node.hpp>
Chris@16: #include <boost/noncopyable.hpp>
Chris@101: #include <boost/preprocessor/repetition/repeat.hpp>
Chris@101: #include <boost/preprocessor/seq/elem.hpp>
Chris@101: #include <boost/preprocessor/seq/enum.hpp>
Chris@101: #include <boost/preprocessor/seq/size.hpp>
Chris@16: #include <cstddef>
Chris@16: #include <limits.h>
Chris@16: 
Chris@16: #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
Chris@16: #include <boost/archive/archive_exception.hpp>
Chris@16: #include <boost/serialization/access.hpp>
Chris@16: #include <boost/throw_exception.hpp> 
Chris@16: #endif
Chris@16: 
Chris@16: namespace boost{
Chris@16: 
Chris@16: namespace multi_index{
Chris@16: 
Chris@16: namespace detail{
Chris@16: 
Chris@16: /* bucket structure for use by hashed indices */
Chris@16: 
Chris@101: #define BOOST_MULTI_INDEX_BA_SIZES_32BIT                                  \
Chris@101: (53ul)(97ul)(193ul)(389ul)(769ul)                                         \
Chris@101: (1543ul)(3079ul)(6151ul)(12289ul)(24593ul)                                \
Chris@101: (49157ul)(98317ul)(196613ul)(393241ul)(786433ul)                          \
Chris@101: (1572869ul)(3145739ul)(6291469ul)(12582917ul)(25165843ul)                 \
Chris@101: (50331653ul)(100663319ul)(201326611ul)(402653189ul)(805306457ul)          \
Chris@101: (1610612741ul)(3221225473ul)
Chris@101: 
Chris@101: #if ((((ULONG_MAX>>16)>>16)>>16)>>15)==0 /* unsigned long less than 64 bits */
Chris@101: #define BOOST_MULTI_INDEX_BA_SIZES                                         \
Chris@101: BOOST_MULTI_INDEX_BA_SIZES_32BIT                                           \
Chris@101: (4294967291ul)
Chris@101: #else
Chris@101:   /* obtained with aid from
Chris@101:    *   http://javaboutique.internet.com/prime_numb/
Chris@101:    *   http://www.rsok.com/~jrm/next_ten_primes.html
Chris@101:    * and verified with
Chris@101:    *   http://www.alpertron.com.ar/ECM.HTM
Chris@101:    */
Chris@101: 
Chris@101: #define BOOST_MULTI_INDEX_BA_SIZES                                         \
Chris@101: BOOST_MULTI_INDEX_BA_SIZES_32BIT                                           \
Chris@101: (6442450939ul)(12884901893ul)(25769803751ul)(51539607551ul)                \
Chris@101: (103079215111ul)(206158430209ul)(412316860441ul)(824633720831ul)           \
Chris@101: (1649267441651ul)(3298534883309ul)(6597069766657ul)(13194139533299ul)      \
Chris@101: (26388279066623ul)(52776558133303ul)(105553116266489ul)(211106232532969ul) \
Chris@101: (422212465066001ul)(844424930131963ul)(1688849860263953ul)                 \
Chris@101: (3377699720527861ul)(6755399441055731ul)(13510798882111483ul)              \
Chris@101: (27021597764222939ul)(54043195528445957ul)(108086391056891903ul)           \
Chris@101: (216172782113783843ul)(432345564227567621ul)(864691128455135207ul)         \
Chris@101: (1729382256910270481ul)(3458764513820540933ul)(6917529027641081903ul)      \
Chris@101: (13835058055282163729ul)(18446744073709551557ul)
Chris@101: #endif
Chris@101: 
Chris@101: template<bool _=true> /* templatized to have in-header static var defs */
Chris@16: class bucket_array_base:private noncopyable
Chris@16: {
Chris@16: protected:
Chris@101:   static const std::size_t sizes[];
Chris@101: 
Chris@101:   static std::size_t size_index(std::size_t n)
Chris@16:   {
Chris@101:     const std::size_t *bound=std::lower_bound(sizes,sizes+sizes_length,n);
Chris@101:     if(bound==sizes+sizes_length)--bound;
Chris@101:     return bound-sizes;
Chris@101:   }
Chris@16: 
Chris@101: #define BOOST_MULTI_INDEX_BA_POSITION_CASE(z,n,_)                    \
Chris@101:   case n:return hash%BOOST_PP_SEQ_ELEM(n,BOOST_MULTI_INDEX_BA_SIZES);
Chris@16: 
Chris@101:   static std::size_t position(std::size_t hash,std::size_t size_index_)
Chris@101:   {
Chris@101:     /* Accelerate hash%sizes[size_index_] by replacing with a switch on
Chris@101:      * hash%Ci expressions, each Ci a compile-time constant, which the
Chris@101:      * compiler can implement without using integer division.
Chris@101:      */
Chris@16: 
Chris@101:     switch(size_index_){
Chris@101:       default: /* never used */
Chris@101:       BOOST_PP_REPEAT(
Chris@101:         BOOST_PP_SEQ_SIZE(BOOST_MULTI_INDEX_BA_SIZES),
Chris@101:         BOOST_MULTI_INDEX_BA_POSITION_CASE,~)
Chris@101:     }
Chris@101:   }
Chris@16: 
Chris@101: private:
Chris@101:   static const std::size_t sizes_length;
Chris@16: };
Chris@16: 
Chris@101: template<bool _>
Chris@101: const std::size_t bucket_array_base<_>::sizes[]={
Chris@101:   BOOST_PP_SEQ_ENUM(BOOST_MULTI_INDEX_BA_SIZES)
Chris@101: };
Chris@101: 
Chris@101: template<bool _>
Chris@101: const std::size_t bucket_array_base<_>::sizes_length=
Chris@101:   sizeof(bucket_array_base<_>::sizes)/
Chris@101:   sizeof(bucket_array_base<_>::sizes[0]);
Chris@101: 
Chris@101: #undef BOOST_MULTI_INDEX_BA_POSITION_CASE
Chris@101: #undef BOOST_MULTI_INDEX_BA_SIZES
Chris@101: #undef BOOST_MULTI_INDEX_BA_SIZES_32BIT
Chris@101: 
Chris@16: template<typename Allocator>
Chris@101: class bucket_array:bucket_array_base<>
Chris@16: {
Chris@101:   typedef bucket_array_base<>                        super;
Chris@101:   typedef hashed_index_base_node_impl<
Chris@101:     typename boost::detail::allocator::rebind_to<
Chris@101:       Allocator,
Chris@101:       char
Chris@101:     >::type
Chris@101:   >                                                  base_node_impl_type;
Chris@16: 
Chris@16: public:
Chris@101:   typedef typename base_node_impl_type::base_pointer base_pointer;
Chris@101:   typedef typename base_node_impl_type::pointer      pointer;
Chris@16: 
Chris@101:   bucket_array(const Allocator& al,pointer end_,std::size_t size_):
Chris@101:     size_index_(super::size_index(size_)),
Chris@101:     spc(al,super::sizes[size_index_]+1)
Chris@16:   {
Chris@101:     clear(end_);
Chris@16:   }
Chris@16: 
Chris@16:   std::size_t size()const
Chris@16:   {
Chris@101:     return super::sizes[size_index_];
Chris@16:   }
Chris@16: 
Chris@16:   std::size_t position(std::size_t hash)const
Chris@16:   {
Chris@101:     return super::position(hash,size_index_);
Chris@16:   }
Chris@16: 
Chris@101:   base_pointer begin()const{return buckets();}
Chris@101:   base_pointer end()const{return buckets()+size();}
Chris@101:   base_pointer at(std::size_t n)const{return buckets()+n;}
Chris@16: 
Chris@101:   void clear(pointer end_)
Chris@16:   {
Chris@101:     for(base_pointer x=begin(),y=end();x!=y;++x)x->prior()=pointer(0);
Chris@101:     end()->prior()=end_->prior()=end_;
Chris@101:     end_->next()=end();
Chris@101:  }
Chris@16: 
Chris@16:   void swap(bucket_array& x)
Chris@16:   {
Chris@101:     std::swap(size_index_,x.size_index_);
Chris@16:     spc.swap(x.spc);
Chris@16:   }
Chris@16: 
Chris@16: private:
Chris@101:   std::size_t                               size_index_;
Chris@101:   auto_space<base_node_impl_type,Allocator> spc;
Chris@16: 
Chris@101:   base_pointer buckets()const
Chris@16:   {
Chris@16:     return spc.data();
Chris@16:   }
Chris@16: 
Chris@16: #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
Chris@16:   friend class boost::serialization::access;
Chris@16:   
Chris@16:   /* bucket_arrays do not emit any kind of serialization info. They are
Chris@16:    * fed to Boost.Serialization as hashed index iterators need to track
Chris@16:    * them during serialization.
Chris@16:    */
Chris@16: 
Chris@16:   template<class Archive>
Chris@16:   void serialize(Archive&,const unsigned int)
Chris@16:   {
Chris@16:   }
Chris@16: #endif
Chris@16: };
Chris@16: 
Chris@16: template<typename Allocator>
Chris@16: void swap(bucket_array<Allocator>& x,bucket_array<Allocator>& y)
Chris@16: {
Chris@16:   x.swap(y);
Chris@16: }
Chris@16: 
Chris@16: } /* namespace multi_index::detail */
Chris@16: 
Chris@16: } /* namespace multi_index */
Chris@16: 
Chris@16: #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
Chris@16: /* bucket_arrays never get constructed directly by Boost.Serialization,
Chris@16:  * as archives are always fed pointers to previously existent
Chris@16:  * arrays. So, if this is called it means we are dealing with a
Chris@16:  * somehow invalid archive.
Chris@16:  */
Chris@16: 
Chris@16: #if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
Chris@16: namespace serialization{
Chris@16: #else
Chris@16: namespace multi_index{
Chris@16: namespace detail{
Chris@16: #endif
Chris@16: 
Chris@16: template<class Archive,typename Allocator>
Chris@16: inline void load_construct_data(
Chris@16:   Archive&,boost::multi_index::detail::bucket_array<Allocator>*,
Chris@16:   const unsigned int)
Chris@16: {
Chris@16:   throw_exception(
Chris@16:     archive::archive_exception(archive::archive_exception::other_exception));
Chris@16: }
Chris@16: 
Chris@16: #if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
Chris@16: } /* namespace serialization */
Chris@16: #else
Chris@16: } /* namespace multi_index::detail */
Chris@16: } /* namespace multi_index */
Chris@16: #endif
Chris@16: 
Chris@16: #endif
Chris@16: 
Chris@16: } /* namespace boost */
Chris@16: 
Chris@16: #endif