1 /* Copyright 2003-2020 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/allocator_traits.hpp>
19 #include <boost/multi_index/detail/auto_space.hpp>
20 #include <boost/multi_index/detail/hash_index_node.hpp>
21 #include <boost/noncopyable.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/archive/archive_exception.hpp>
31 #include <boost/serialization/access.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
size_index(std::size_t n)84 static std::size_t size_index(std::size_t n)
85 {
86 const std::size_t *bound=std::lower_bound(sizes,sizes+sizes_length,n);
87 if(bound==sizes+sizes_length)--bound;
88 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
position(std::size_t hash,std::size_t size_index_)94 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 switch(size_index_){
102 default: /* never used */
103 BOOST_PP_REPEAT(
104 BOOST_PP_SEQ_SIZE(BOOST_MULTI_INDEX_BA_SIZES),
105 BOOST_MULTI_INDEX_BA_POSITION_CASE,~)
106 }
107 }
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
bucket_array(const Allocator & al,pointer end_,std::size_t size_)142 bucket_array(const Allocator& al,pointer end_,std::size_t size_):
143 size_index_(super::size_index(size_)),
144 spc(al,static_cast<auto_space_size_type>(super::sizes[size_index_]+1))
145 {
146 clear(end_);
147 }
148
size() const149 std::size_t size()const
150 {
151 return super::sizes[size_index_];
152 }
153
position(std::size_t hash) const154 std::size_t position(std::size_t hash)const
155 {
156 return super::position(hash,size_index_);
157 }
158
begin() const159 base_pointer begin()const{return buckets();}
end() const160 base_pointer end()const{return buckets()+size();}
at(std::size_t n) const161 base_pointer at(std::size_t n)const{return buckets()+n;}
162
clear(pointer end_)163 void clear(pointer end_)
164 {
165 for(base_pointer x=begin(),y=end();x!=y;++x)x->prior()=pointer(0);
166 end()->prior()=end_->prior()=end_;
167 end_->next()=end();
168 }
169
swap(bucket_array & x)170 void swap(bucket_array& x)
171 {
172 std::swap(size_index_,x.size_index_);
173 spc.swap(x.spc);
174 }
175
176 template<typename BoolConstant>
swap(bucket_array & x,BoolConstant swap_allocators)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
buckets() const190 base_pointer buckets()const
191 {
192 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>
serialize(Archive &,const unsigned int)204 void serialize(Archive&,const unsigned int)
205 {
206 }
207 #endif
208 };
209
210 template<typename Allocator>
swap(bucket_array<Allocator> & x,bucket_array<Allocator> & y)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>
load_construct_data(Archive &,boost::multi_index::detail::bucket_array<Allocator> *,const unsigned int)235 inline void load_construct_data(
236 Archive&,boost::multi_index::detail::bucket_array<Allocator>*,
237 const unsigned int)
238 {
239 throw_exception(
240 archive::archive_exception(archive::archive_exception::other_exception));
241 }
242
243 #if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
244 } /* namespace serialization */
245 #else
246 } /* namespace multi_index::detail */
247 } /* namespace multi_index */
248 #endif
249
250 #endif
251
252 } /* namespace boost */
253
254 #endif
255