multi_index/detail/bucket_array.hpp

0001 /* Copyright 2003-2023 Joaquin M Lopez Munoz.
0002  * Distributed under the Boost Software License, Version 1.0.
0003  * (See accompanying file LICENSE_1_0.txt or copy at
0004  * http://www.boost.org/LICENSE_1_0.txt)
0005  *
0006  * See http://www.boost.org/libs/multi_index for library home page.
0007  */
0008
0009 #ifndef BOOST_MULTI_INDEX_DETAIL_BUCKET_ARRAY_HPP
0010 #define BOOST_MULTI_INDEX_DETAIL_BUCKET_ARRAY_HPP
0011
0012 #if defined(_MSC_VER)
0013 #pragma once
0014 #endif
0015
0016 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
0017 #include <algorithm>
0018 #include <boost/core/noncopyable.hpp>
0019 #include <boost/multi_index/detail/allocator_traits.hpp>
0020 #include <boost/multi_index/detail/auto_space.hpp>
0021 #include <boost/multi_index/detail/hash_index_node.hpp>
0022 #include <boost/preprocessor/repetition/repeat.hpp>
0023 #include <boost/preprocessor/seq/elem.hpp>
0024 #include <boost/preprocessor/seq/enum.hpp>
0025 #include <boost/preprocessor/seq/size.hpp>
0026 #include <cstddef>
0027 #include <limits.h>
0028
0029 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
0030 #include <boost/core/serialization.hpp>
0031 #include <boost/multi_index/detail/bad_archive_exception.hpp>
0032 #include <boost/throw_exception.hpp>
0033 #endif
0034
0035 namespace boost{
0036
0037 namespace multi_index{
0038
0039 namespace detail{
0040
0041 /* bucket structure for use by hashed indices */
0042
0043 #define BOOST_MULTI_INDEX_BA_SIZES_32BIT                                  \
0044 (53ul)(97ul)(193ul)(389ul)(769ul)                                         \
0045 (1543ul)(3079ul)(6151ul)(12289ul)(24593ul)                                \
0046 (49157ul)(98317ul)(196613ul)(393241ul)(786433ul)                          \
0047 (1572869ul)(3145739ul)(6291469ul)(12582917ul)(25165843ul)                 \
0048 (50331653ul)(100663319ul)(201326611ul)(402653189ul)(805306457ul)          \
0049 (1610612741ul)(3221225473ul)
0050
0051 #if ((((ULONG_MAX>>16)>>16)>>16)>>15)==0 /* unsigned long less than 64 bits */
0052 #define BOOST_MULTI_INDEX_BA_SIZES                                         \
0053 BOOST_MULTI_INDEX_BA_SIZES_32BIT                                           \
0054 (4294967291ul)
0055 #else
0056   /* obtained with aid from
0057    *   http://javaboutique.internet.com/prime_numb/
0058    *   http://www.rsok.com/~jrm/next_ten_primes.html
0059    * and verified with
0060    *   http://www.alpertron.com.ar/ECM.HTM
0061    */
0062
0063 #define BOOST_MULTI_INDEX_BA_SIZES                                         \
0064 BOOST_MULTI_INDEX_BA_SIZES_32BIT                                           \
0065 (6442450939ul)(12884901893ul)(25769803751ul)(51539607551ul)                \
0066 (103079215111ul)(206158430209ul)(412316860441ul)(824633720831ul)           \
0067 (1649267441651ul)(3298534883309ul)(6597069766657ul)(13194139533299ul)      \
0068 (26388279066623ul)(52776558133303ul)(105553116266489ul)(211106232532969ul) \
0069 (422212465066001ul)(844424930131963ul)(1688849860263953ul)                 \
0070 (3377699720527861ul)(6755399441055731ul)(13510798882111483ul)              \
0071 (27021597764222939ul)(54043195528445957ul)(108086391056891903ul)           \
0072 (216172782113783843ul)(432345564227567621ul)(864691128455135207ul)         \
0073 (1729382256910270481ul)(3458764513820540933ul)(6917529027641081903ul)      \
0074 (13835058055282163729ul)(18446744073709551557ul)
0075 #endif
0076
0077 template<bool _=true> /* templatized to have in-header static var defs */
0078 class bucket_array_base:private noncopyable
0079 {
0080 protected:
0081   static const std::size_t sizes[
0082     BOOST_PP_SEQ_SIZE(BOOST_MULTI_INDEX_BA_SIZES)];
0083
0084   static std::size_t size_index(std::size_t n)
0085   {
0086     const std::size_t *bound=std::lower_bound(sizes,sizes+sizes_length,n);
0087     if(bound==sizes+sizes_length)--bound;
0088     return bound-sizes;
0089   }
0090
0091 #define BOOST_MULTI_INDEX_BA_POSITION_CASE(z,n,_)                    \
0092   case n:return hash%BOOST_PP_SEQ_ELEM(n,BOOST_MULTI_INDEX_BA_SIZES);
0093
0094   static std::size_t position(std::size_t hash,std::size_t size_index_)
0095   {
0096     /* Accelerate hash%sizes[size_index_] by replacing with a switch on
0097      * hash%Ci expressions, each Ci a compile-time constant, which the
0098      * compiler can implement without using integer division.
0099      */
0100
0101     switch(size_index_){
0102       default: /* never used */
0103       BOOST_PP_REPEAT(
0104         BOOST_PP_SEQ_SIZE(BOOST_MULTI_INDEX_BA_SIZES),
0105         BOOST_MULTI_INDEX_BA_POSITION_CASE,~)
0106     }
0107   }
0108
0109 private:
0110   static const std::size_t sizes_length;
0111 };
0112
0113 template<bool _>
0114 const std::size_t bucket_array_base<_>::sizes[]={
0115   BOOST_PP_SEQ_ENUM(BOOST_MULTI_INDEX_BA_SIZES)
0116 };
0117
0118 template<bool _>
0119 const std::size_t bucket_array_base<_>::sizes_length=
0120   sizeof(bucket_array_base<_>::sizes)/
0121   sizeof(bucket_array_base<_>::sizes[0]);
0122
0123 #undef BOOST_MULTI_INDEX_BA_POSITION_CASE
0124 #undef BOOST_MULTI_INDEX_BA_SIZES
0125 #undef BOOST_MULTI_INDEX_BA_SIZES_32BIT
0126
0127 template<typename Allocator>
0128 class bucket_array:bucket_array_base<>
0129 {
0130   typedef bucket_array_base<>                        super;
0131   typedef hashed_index_base_node_impl<
0132     typename rebind_alloc_for<
0133       Allocator,
0134       char
0135     >::type
0136   >                                                  base_node_impl_type;
0137
0138 public:
0139   typedef typename base_node_impl_type::base_pointer base_pointer;
0140   typedef typename base_node_impl_type::pointer      pointer;
0141
0142   bucket_array(const Allocator& al,pointer end_,std::size_t size_):
0143     size_index_(super::size_index(size_)),
0144     spc(al,static_cast<auto_space_size_type>(super::sizes[size_index_]+1))
0145   {
0146     clear(end_);
0147   }
0148
0149   std::size_t size()const
0150   {
0151     return super::sizes[size_index_];
0152   }
0153
0154   std::size_t position(std::size_t hash)const
0155   {
0156     return super::position(hash,size_index_);
0157   }
0158
0159   base_pointer begin()const{return buckets();}
0160   base_pointer end()const{return buckets()+size();}
0161   base_pointer at(std::size_t n)const{return buckets()+n;}
0162
0163   void clear(pointer end_)
0164   {
0165     for(base_pointer x=begin(),y=end();x!=y;++x)x->prior()=pointer(0);
0166     end()->prior()=end_->prior()=end_;
0167     end_->next()=end();
0168  }
0169
0170   void swap(bucket_array& x)
0171   {
0172     std::swap(size_index_,x.size_index_);
0173     spc.swap(x.spc);
0174   }
0175
0176   template<typename BoolConstant>
0177   void swap(bucket_array& x,BoolConstant swap_allocators)
0178   {
0179     std::swap(size_index_,x.size_index_);
0180     spc.swap(x.spc,swap_allocators);
0181   }
0182
0183 private:
0184   typedef auto_space<base_node_impl_type,Allocator> auto_space_type;
0185   typedef typename auto_space_type::size_type       auto_space_size_type;
0186
0187   std::size_t      size_index_;
0188   auto_space_type  spc;
0189
0190   base_pointer buckets()const
0191   {
0192     return spc.data();
0193   }
0194
0195 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
0196   friend class boost::serialization::access;
0197
0198   /* bucket_arrays do not emit any kind of serialization info. They are
0199    * fed to Boost.Serialization as hashed index iterators need to track
0200    * them during serialization.
0201    */
0202
0203   template<class Archive>
0204   void serialize(Archive&,const unsigned int)
0205   {
0206   }
0207 #endif
0208 };
0209
0210 template<typename Allocator>
0211 void swap(bucket_array<Allocator>& x,bucket_array<Allocator>& y)
0212 {
0213   x.swap(y);
0214 }
0215
0216 } /* namespace multi_index::detail */
0217
0218 } /* namespace multi_index */
0219
0220 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
0221 /* bucket_arrays never get constructed directly by Boost.Serialization,
0222  * as archives are always fed pointers to previously existent
0223  * arrays. So, if this is called it means we are dealing with a
0224  * somehow invalid archive.
0225  */
0226
0227 #if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
0228 namespace serialization{
0229 #else
0230 namespace multi_index{
0231 namespace detail{
0232 #endif
0233
0234 template<class Archive,typename Allocator>
0235 inline void load_construct_data(
0236   Archive&,boost::multi_index::detail::bucket_array<Allocator>*,
0237   const unsigned int)
0238 {
0239   throw_exception(boost::multi_index::detail::bad_archive_exception());
0240 }
0241
0242 #if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
0243 } /* namespace serialization */
0244 #else
0245 } /* namespace multi_index::detail */
0246 } /* namespace multi_index */
0247 #endif
0248
0249 #endif
0250
0251 } /* namespace boost */
0252
0253 #endif