ceph/src/boost/boost/multi_index/detail/bucket_array.hpp

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