1 /* Copyright 2003-2008 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)
6 * See http://www.boost.org/libs/multi_index for library home page.
9 #ifndef BOOST_MULTI_INDEX_DETAIL_BUCKET_ARRAY_HPP
10 #define BOOST_MULTI_INDEX_DETAIL_BUCKET_ARRAY_HPP
12 #if defined(_MSC_VER)&&(_MSC_VER>=1200)
16 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
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>
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>
33 namespace multi_index
{
37 /* bucket structure for use by hashed indices */
39 class bucket_array_base
:private noncopyable
42 inline static std::size_t next_prime(std::size_t n
)
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,
52 #if ((((ULONG_MAX>>16)>>16)>>16)>>15)==0 /* unsigned long less than 64 bits */
55 /* obtained with aid from
56 * http://javaboutique.internet.com/prime_numb/
57 * http://www.rsok.com/~jrm/next_ten_primes.html
59 * http://www.alpertron.com.ar/ECM.HTM
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
75 static const std::size_t prime_list_size
=
76 sizeof(prime_list
)/sizeof(prime_list
[0]);
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
--;
85 template<typename Allocator
>
86 class bucket_array
:public bucket_array_base
88 typedef typename prevent_eti
<
90 hashed_index_node_impl
<
91 typename
boost::detail::allocator::rebind_to
<
96 >::type node_impl_type
;
99 typedef typename
node_impl_type::pointer pointer
;
101 bucket_array(const Allocator
& al
,pointer end_
,std::size_t size
):
102 size_(bucket_array_base::next_prime(size
)),
110 std::size_t size()const
115 std::size_t position(std::size_t hash
)const
120 pointer
begin()const{return buckets();}
121 pointer
end()const{return buckets()+size_
;}
122 pointer
at(std::size_t n
)const{return buckets()+n
;}
124 std::size_t first_nonempty(std::size_t n
)const
128 if(x
->next()!=x
)return n
;
134 for(pointer x
=begin(),y
=end();x
!=y
;++x
)x
->next()=x
;
137 void swap(bucket_array
& x
)
139 std::swap(size_
,x
.size_
);
145 auto_space
<node_impl_type
,Allocator
> spc
;
147 pointer
buckets()const
152 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
153 friend class boost::serialization::access
;
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.
160 template<class Archive
>
161 void serialize(Archive
&,const unsigned int)
167 template<typename Allocator
>
168 void swap(bucket_array
<Allocator
>& x
,bucket_array
<Allocator
>& y
)
173 } /* namespace multi_index::detail */
175 } /* namespace multi_index */
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.
184 #if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
185 namespace serialization
{
187 namespace multi_index
{
191 template<class Archive
,typename Allocator
>
192 inline void load_construct_data(
193 Archive
&,boost::multi_index::detail::bucket_array
<Allocator
>*,
197 archive::archive_exception(archive::archive_exception::other_exception
));
200 #if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
201 } /* namespace serialization */
203 } /* namespace multi_index::detail */
204 } /* namespace multi_index */
209 } /* namespace boost */