Line data    Source code

       1             : /* Copyright 2003-2023 Joaquin M Lopez Munoz.
       2             :  * Distributed under the Boost Software License, Version 1.0.
       3             :  * (See accompanying file LICENSE_1_0.txt or copy at
       4             :  * http://www.boost.org/LICENSE_1_0.txt)
       5             :  *
       6             :  * See http://www.boost.org/libs/multi_index for library home page.
       7             :  */
       8             : 
       9             : #ifndef BOOST_MULTI_INDEX_DETAIL_BUCKET_ARRAY_HPP
      10             : #define BOOST_MULTI_INDEX_DETAIL_BUCKET_ARRAY_HPP
      11             : 
      12             : #if defined(_MSC_VER)
      13             : #pragma once
      14             : #endif
      15             : 
      16             : #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
      17             : #include <algorithm>
      18             : #include <boost/core/noncopyable.hpp>
      19             : #include <boost/multi_index/detail/allocator_traits.hpp>
      20             : #include <boost/multi_index/detail/auto_space.hpp>
      21             : #include <boost/multi_index/detail/hash_index_node.hpp>
      22             : #include <boost/preprocessor/repetition/repeat.hpp>
      23             : #include <boost/preprocessor/seq/elem.hpp>
      24             : #include <boost/preprocessor/seq/enum.hpp>
      25             : #include <boost/preprocessor/seq/size.hpp>
      26             : #include <cstddef>
      27             : #include <limits.h>
      28             : 
      29             : #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
      30             : #include <boost/core/serialization.hpp>
      31             : #include <boost/multi_index/detail/bad_archive_exception.hpp>
      32             : #include <boost/throw_exception.hpp> 
      33             : #endif
      34             : 
      35             : namespace boost{
      36             : 
      37             : namespace multi_index{
      38             : 
      39             : namespace detail{
      40             : 
      41             : /* bucket structure for use by hashed indices */
      42             : 
      43             : #define BOOST_MULTI_INDEX_BA_SIZES_32BIT                                  \
      44             : (53ul)(97ul)(193ul)(389ul)(769ul)                                         \
      45             : (1543ul)(3079ul)(6151ul)(12289ul)(24593ul)                                \
      46             : (49157ul)(98317ul)(196613ul)(393241ul)(786433ul)                          \
      47             : (1572869ul)(3145739ul)(6291469ul)(12582917ul)(25165843ul)                 \
      48             : (50331653ul)(100663319ul)(201326611ul)(402653189ul)(805306457ul)          \
      49             : (1610612741ul)(3221225473ul)
      50             : 
      51             : #if ((((ULONG_MAX>>16)>>16)>>16)>>15)==0 /* unsigned long less than 64 bits */
      52             : #define BOOST_MULTI_INDEX_BA_SIZES                                         \
      53             : BOOST_MULTI_INDEX_BA_SIZES_32BIT                                           \
      54             : (4294967291ul)
      55             : #else
      56             :   /* obtained with aid from
      57             :    *   http://javaboutique.internet.com/prime_numb/
      58             :    *   http://www.rsok.com/~jrm/next_ten_primes.html
      59             :    * and verified with
      60             :    *   http://www.alpertron.com.ar/ECM.HTM
      61             :    */
      62             : 
      63             : #define BOOST_MULTI_INDEX_BA_SIZES                                         \
      64             : BOOST_MULTI_INDEX_BA_SIZES_32BIT                                           \
      65             : (6442450939ul)(12884901893ul)(25769803751ul)(51539607551ul)                \
      66             : (103079215111ul)(206158430209ul)(412316860441ul)(824633720831ul)           \
      67             : (1649267441651ul)(3298534883309ul)(6597069766657ul)(13194139533299ul)      \
      68             : (26388279066623ul)(52776558133303ul)(105553116266489ul)(211106232532969ul) \
      69             : (422212465066001ul)(844424930131963ul)(1688849860263953ul)                 \
      70             : (3377699720527861ul)(6755399441055731ul)(13510798882111483ul)              \
      71             : (27021597764222939ul)(54043195528445957ul)(108086391056891903ul)           \
      72             : (216172782113783843ul)(432345564227567621ul)(864691128455135207ul)         \
      73             : (1729382256910270481ul)(3458764513820540933ul)(6917529027641081903ul)      \
      74             : (13835058055282163729ul)(18446744073709551557ul)
      75             : #endif
      76             : 
      77             : template<bool _=true> /* templatized to have in-header static var defs */
      78             : class bucket_array_base:private noncopyable
      79             : {
      80             : protected:
      81             :   static const std::size_t sizes[
      82             :     BOOST_PP_SEQ_SIZE(BOOST_MULTI_INDEX_BA_SIZES)];
      83             : 
      84      278428 :   static std::size_t size_index(std::size_t n)
      85             :   {
      86      278428 :     const std::size_t *bound=std::lower_bound(sizes,sizes+sizes_length,n);
      87      278428 :     if(bound==sizes+sizes_length)--bound;
      88      278428 :     return bound-sizes;
      89             :   }
      90             : 
      91             : #define BOOST_MULTI_INDEX_BA_POSITION_CASE(z,n,_)                    \
      92             :   case n:return hash%BOOST_PP_SEQ_ELEM(n,BOOST_MULTI_INDEX_BA_SIZES);
      93             : 
      94    39718009 :   static std::size_t position(std::size_t hash,std::size_t size_index_)
      95             :   {
      96             :     /* Accelerate hash%sizes[size_index_] by replacing with a switch on
      97             :      * hash%Ci expressions, each Ci a compile-time constant, which the
      98             :      * compiler can implement without using integer division.
      99             :      */
     100             : 
     101    39718009 :     switch(size_index_){
     102             :       default: /* never used */
     103    39718009 :       BOOST_PP_REPEAT(
     104             :         BOOST_PP_SEQ_SIZE(BOOST_MULTI_INDEX_BA_SIZES),
     105             :         BOOST_MULTI_INDEX_BA_POSITION_CASE,~)
     106             :     }
     107    39718009 :   }
     108             : 
     109             : private:
     110             :   static const std::size_t sizes_length;
     111             : };
     112             : 
     113             : template<bool _>
     114             : const std::size_t bucket_array_base<_>::sizes[]={
     115             :   BOOST_PP_SEQ_ENUM(BOOST_MULTI_INDEX_BA_SIZES)
     116             : };
     117             : 
     118             : template<bool _>
     119             : const std::size_t bucket_array_base<_>::sizes_length=
     120             :   sizeof(bucket_array_base<_>::sizes)/
     121             :   sizeof(bucket_array_base<_>::sizes[0]);
     122             : 
     123             : #undef BOOST_MULTI_INDEX_BA_POSITION_CASE
     124             : #undef BOOST_MULTI_INDEX_BA_SIZES
     125             : #undef BOOST_MULTI_INDEX_BA_SIZES_32BIT
     126             : 
     127             : template<typename Allocator>
     128             : class bucket_array:bucket_array_base<>
     129             : {
     130             :   typedef bucket_array_base<>                        super;
     131             :   typedef hashed_index_base_node_impl<
     132             :     typename rebind_alloc_for<
     133             :       Allocator,
     134             :       char
     135             :     >::type
     136             :   >                                                  base_node_impl_type;
     137             : 
     138             : public:
     139             :   typedef typename base_node_impl_type::base_pointer base_pointer;
     140             :   typedef typename base_node_impl_type::pointer      pointer;
     141             : 
     142      556856 :   bucket_array(const Allocator& al,pointer end_,std::size_t size_):
     143      278428 :     size_index_(super::size_index(size_)),
     144      278428 :     spc(al,static_cast<auto_space_size_type>(super::sizes[size_index_]+1))
     145      278428 :   {
     146      278428 :     clear(end_);
     147      556856 :   }
     148             : 
     149     1213183 :   std::size_t size()const
     150             :   {
     151     1213183 :     return super::sizes[size_index_];
     152             :   }
     153             : 
     154    39718009 :   std::size_t position(std::size_t hash)const
     155             :   {
     156    39718009 :     return super::position(hash,size_index_);
     157             :   }
     158             : 
     159      311585 :   base_pointer begin()const{return buckets();}
     160      934755 :   base_pointer end()const{return buckets()+size();}
     161    39718009 :   base_pointer at(std::size_t n)const{return buckets()+n;}
     162             : 
     163      311585 :   void clear(pointer end_)
     164             :   {
     165    16926636 :     for(base_pointer x=begin(),y=end();x!=y;++x)x->prior()=pointer(0);
     166      311585 :     end()->prior()=end_->prior()=end_;
     167      311585 :     end_->next()=end();
     168      311585 :  }
     169             : 
     170         148 :   void swap(bucket_array& x)
     171             :   {
     172         148 :     std::swap(size_index_,x.size_index_);
     173         148 :     spc.swap(x.spc);
     174         148 :   }
     175             : 
     176             :   template<typename BoolConstant>
     177             :   void swap(bucket_array& x,BoolConstant swap_allocators)
     178             :   {
     179             :     std::swap(size_index_,x.size_index_);
     180             :     spc.swap(x.spc,swap_allocators);
     181             :   }
     182             : 
     183             : private:
     184             :   typedef auto_space<base_node_impl_type,Allocator> auto_space_type;
     185             :   typedef typename auto_space_type::size_type       auto_space_size_type;
     186             : 
     187             :   std::size_t      size_index_;
     188             :   auto_space_type  spc;
     189             : 
     190    40964349 :   base_pointer buckets()const
     191             :   {
     192    40964349 :     return spc.data();
     193             :   }
     194             : 
     195             : #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
     196             :   friend class boost::serialization::access;
     197             :   
     198             :   /* bucket_arrays do not emit any kind of serialization info. They are
     199             :    * fed to Boost.Serialization as hashed index iterators need to track
     200             :    * them during serialization.
     201             :    */
     202             : 
     203             :   template<class Archive>
     204             :   void serialize(Archive&,const unsigned int)
     205             :   {
     206             :   }
     207             : #endif
     208             : };
     209             : 
     210             : template<typename Allocator>
     211             : void swap(bucket_array<Allocator>& x,bucket_array<Allocator>& y)
     212             : {
     213             :   x.swap(y);
     214             : }
     215             : 
     216             : } /* namespace multi_index::detail */
     217             : 
     218             : } /* namespace multi_index */
     219             : 
     220             : #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
     221             : /* bucket_arrays never get constructed directly by Boost.Serialization,
     222             :  * as archives are always fed pointers to previously existent
     223             :  * arrays. So, if this is called it means we are dealing with a
     224             :  * somehow invalid archive.
     225             :  */
     226             : 
     227             : #if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
     228             : namespace serialization{
     229             : #else
     230             : namespace multi_index{
     231             : namespace detail{
     232             : #endif
     233             : 
     234             : template<class Archive,typename Allocator>
     235             : inline void load_construct_data(
     236             :   Archive&,boost::multi_index::detail::bucket_array<Allocator>*,
     237             :   const unsigned int)
     238             : {
     239             :   throw_exception(boost::multi_index::detail::bad_archive_exception());
     240             : }
     241             : 
     242             : #if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
     243             : } /* namespace serialization */
     244             : #else
     245             : } /* namespace multi_index::detail */
     246             : } /* namespace multi_index */
     247             : #endif
     248             : 
     249             : #endif
     250             : 
     251             : } /* namespace boost */
     252             : 
     253             : #endif