boost/multi_index/detail/bucket_array.hpp

   1 /* Copyright 2003-2007 Joaquín M López Muñoz.
   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)&&(_MSC_VER>=1200)
  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/multi_index/detail/prevent_eti.hpp>
  21 #include <boost/noncopyable.hpp>
  22 #include <cstddef>
  23 #include <limits.h>
  24
  25 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
  26 #include <boost/archive/archive_exception.hpp>
  27 #include <boost/serialization/access.hpp>
  28 #include <boost/throw_exception.hpp>
  29 #endif
  30
  31 namespace boost{
  32
  33 namespace multi_index{
  34
  35 namespace detail{
  36
  37 /* bucket structure for use by hashed indices */
  38
  39 class bucket_array_base:private noncopyable
  40 {
  41 protected:
  42   inline static std::size_t next_prime(std::size_t n)
  43   {
  44     static const std::size_t prime_list[]={
  45       53ul, 97ul, 193ul, 389ul, 769ul,
  46       1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
  47       49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
  48       1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
  49       50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
  50       1610612741ul, 3221225473ul,
  51
  52 #if ((((ULONG_MAX>>16)>>16)>>16)>>15)==0 /* unsigned long less than 64 bits */
  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       6442450939ul, 12884901893ul, 25769803751ul, 51539607551ul,
  63       103079215111ul, 206158430209ul, 412316860441ul, 824633720831ul,
  64       1649267441651ul, 3298534883309ul, 6597069766657ul, 13194139533299ul,
  65       26388279066623ul, 52776558133303ul, 105553116266489ul, 211106232532969ul,
  66       422212465066001ul, 844424930131963ul, 1688849860263953ul,
  67       3377699720527861ul, 6755399441055731ul, 13510798882111483ul,
  68       27021597764222939ul, 54043195528445957ul, 108086391056891903ul,
  69       216172782113783843ul, 432345564227567621ul, 864691128455135207ul,
  70       1729382256910270481ul, 3458764513820540933ul, 6917529027641081903ul,
  71       13835058055282163729ul, 18446744073709551557ul
  72 #endif
  73
  74     };
  75     static const std::size_t prime_list_size=
  76       sizeof(prime_list)/sizeof(prime_list[0]);
  77
  78     std::size_t const *bound=
  79       std::lower_bound(prime_list,prime_list+prime_list_size,n);
  80     if(bound==prime_list+prime_list_size)bound--;
  81     return *bound;
  82   }
  83 };
  84
  85 template<typename Allocator>
  86 class bucket_array:public bucket_array_base
  87 {
  88   typedef typename prevent_eti<
  89     Allocator,
  90     hashed_index_node_impl<
  91       typename boost::detail::allocator::rebind_to<
  92         Allocator,
  93         void
  94       >::type
  95     >
  96   >::type                                           node_impl_type;
  97
  98 public:
  99   typedef typename node_impl_type::pointer          pointer;
 100
 101   bucket_array(const Allocator& al,pointer end_,std::size_t size):
 102     size_(bucket_array_base::next_prime(size)),
 103     spc(al,size_+1)
 104   {
 105     clear();
 106     end()->next()=end_;
 107     end_->next()=end();
 108   }
 109
 110   std::size_t size()const
 111   {
 112     return size_;
 113   }
 114
 115   std::size_t position(std::size_t hash)const
 116   {
 117     return hash%size_;
 118   }
 119
 120   pointer begin()const{return buckets();}
 121   pointer end()const{return buckets()+size_;}
 122   pointer at(std::size_t n)const{return buckets()+n;}
 123
 124   std::size_t first_nonempty(std::size_t n)const
 125   {
 126     for(;;++n){
 127       pointer x=at(n);
 128       if(x->next()!=x)return n;
 129     }
 130   }
 131
 132   void clear()
 133   {
 134     for(pointer x=begin(),y=end();x!=y;++x)x->next()=x;
 135   }
 136
 137   void swap(bucket_array& x)
 138   {
 139     std::swap(size_,x.size_);
 140     spc.swap(x.spc);
 141   }
 142
 143 private:
 144   std::size_t                          size_;
 145   auto_space<node_impl_type,Allocator> spc;
 146
 147   pointer buckets()const
 148   {
 149     return spc.data();
 150   }
 151
 152 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
 153   friend class boost::serialization::access;
 154
 155   /* bucket_arrays do not emit any kind of serialization info. They are
 156    * fed to Boost.Serialization as hashed index iterators need to track
 157    * them during serialization.
 158    */
 159
 160   template<class Archive>
 161   void serialize(Archive&,const unsigned int)
 162   {
 163   }
 164 #endif
 165 };
 166
 167 template<typename Allocator>
 168 void swap(bucket_array<Allocator>& x,bucket_array<Allocator>& y)
 169 {
 170   x.swap(y);
 171 }
 172
 173 } /* namespace multi_index::detail */
 174
 175 } /* namespace multi_index */
 176
 177 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
 178 /* bucket_arrays never get constructed directly by Boost.Serialization,
 179  * as archives are always fed pointers to previously existent
 180  * arrays. So, if this is called it means we are dealing with a
 181  * somehow invalid archive.
 182  */
 183
 184 #if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
 185 namespace serialization{
 186 #else
 187 namespace multi_index{
 188 namespace detail{
 189 #endif
 190
 191 template<class Archive,typename Allocator>
 192 inline void load_construct_data(
 193   Archive&,boost::multi_index::detail::bucket_array<Allocator>*,
 194   const unsigned int)
 195 {
 196   throw_exception(
 197     archive::archive_exception(archive::archive_exception::other_exception));
 198 }
 199
 200 #if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
 201 } /* namespace serialization */
 202 #else
 203 } /* namespace multi_index::detail */
 204 } /* namespace multi_index */
 205 #endif
 206
 207 #endif
 208
 209 } /* namespace boost */
 210
 211 #endif