]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |