williamr@2
|
1 |
/* Copyright 2003-2005 Joaquín M López Muñoz.
|
williamr@2
|
2 |
* Distributed under the Boost Software License, Version 1.0.
|
williamr@2
|
3 |
* (See accompanying file LICENSE_1_0.txt or copy at
|
williamr@2
|
4 |
* http://www.boost.org/LICENSE_1_0.txt)
|
williamr@2
|
5 |
*
|
williamr@2
|
6 |
* See http://www.boost.org/libs/multi_index for library home page.
|
williamr@2
|
7 |
*/
|
williamr@2
|
8 |
|
williamr@2
|
9 |
#ifndef BOOST_MULTI_INDEX_DETAIL_BUCKET_ARRAY_HPP
|
williamr@2
|
10 |
#define BOOST_MULTI_INDEX_DETAIL_BUCKET_ARRAY_HPP
|
williamr@2
|
11 |
|
williamr@2
|
12 |
#if defined(_MSC_VER)&&(_MSC_VER>=1200)
|
williamr@2
|
13 |
#pragma once
|
williamr@2
|
14 |
#endif
|
williamr@2
|
15 |
|
williamr@2
|
16 |
#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
|
williamr@2
|
17 |
#include <algorithm>
|
williamr@2
|
18 |
#include <boost/multi_index/detail/auto_space.hpp>
|
williamr@2
|
19 |
#include <boost/multi_index/detail/hash_index_node.hpp>
|
williamr@2
|
20 |
#include <boost/noncopyable.hpp>
|
williamr@2
|
21 |
#include <cstddef>
|
williamr@2
|
22 |
#include <limits.h>
|
williamr@2
|
23 |
|
williamr@2
|
24 |
#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
|
williamr@2
|
25 |
#include <boost/archive/archive_exception.hpp>
|
williamr@2
|
26 |
#include <boost/serialization/access.hpp>
|
williamr@2
|
27 |
#include <boost/throw_exception.hpp>
|
williamr@2
|
28 |
#endif
|
williamr@2
|
29 |
|
williamr@2
|
30 |
namespace boost{
|
williamr@2
|
31 |
|
williamr@2
|
32 |
namespace multi_index{
|
williamr@2
|
33 |
|
williamr@2
|
34 |
namespace detail{
|
williamr@2
|
35 |
|
williamr@2
|
36 |
/* bucket structure for use by hashed indices */
|
williamr@2
|
37 |
|
williamr@2
|
38 |
class bucket_array_base:private noncopyable
|
williamr@2
|
39 |
{
|
williamr@2
|
40 |
protected:
|
williamr@2
|
41 |
inline static std::size_t next_prime(std::size_t n)
|
williamr@2
|
42 |
{
|
williamr@2
|
43 |
static const std::size_t prime_list[]={
|
williamr@2
|
44 |
53ul, 97ul, 193ul, 389ul, 769ul,
|
williamr@2
|
45 |
1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
|
williamr@2
|
46 |
49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
|
williamr@2
|
47 |
1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
|
williamr@2
|
48 |
50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
|
williamr@2
|
49 |
1610612741ul, 3221225473ul,
|
williamr@2
|
50 |
|
williamr@2
|
51 |
#if ((((ULONG_MAX>>16)>>16)>>16)>>15)==0 /* unsigned long less than 64 bits */
|
williamr@2
|
52 |
4294967291ul
|
williamr@2
|
53 |
#else
|
williamr@2
|
54 |
/* obtained with aid from
|
williamr@2
|
55 |
* http://javaboutique.internet.com/prime_numb/
|
williamr@2
|
56 |
* http://www.rsok.com/~jrm/next_ten_primes.html
|
williamr@2
|
57 |
* and verified with
|
williamr@2
|
58 |
* http://www.alpertron.com.ar/ECM.HTM
|
williamr@2
|
59 |
*/
|
williamr@2
|
60 |
|
williamr@2
|
61 |
6442450939ul, 12884901893ul, 25769803751ul, 51539607551ul,
|
williamr@2
|
62 |
103079215111ul, 206158430209ul, 412316860441ul, 824633720831ul,
|
williamr@2
|
63 |
1649267441651ul, 3298534883309ul, 6597069766657ul, 13194139533299ul,
|
williamr@2
|
64 |
26388279066623ul, 52776558133303ul, 105553116266489ul, 211106232532969ul,
|
williamr@2
|
65 |
422212465066001ul, 844424930131963ul, 1688849860263953ul,
|
williamr@2
|
66 |
3377699720527861ul, 6755399441055731ul, 13510798882111483ul,
|
williamr@2
|
67 |
27021597764222939ul, 54043195528445957ul, 108086391056891903ul,
|
williamr@2
|
68 |
216172782113783843ul, 432345564227567621ul, 864691128455135207ul,
|
williamr@2
|
69 |
1729382256910270481ul, 3458764513820540933ul, 6917529027641081903ul,
|
williamr@2
|
70 |
13835058055282163729ul, 18446744073709551557ul
|
williamr@2
|
71 |
#endif
|
williamr@2
|
72 |
|
williamr@2
|
73 |
};
|
williamr@2
|
74 |
static const std::size_t prime_list_size=
|
williamr@2
|
75 |
sizeof(prime_list)/sizeof(prime_list[0]);
|
williamr@2
|
76 |
|
williamr@2
|
77 |
std::size_t const *bound=
|
williamr@2
|
78 |
std::lower_bound(prime_list,prime_list+prime_list_size,n);
|
williamr@2
|
79 |
if(bound==prime_list+prime_list_size)bound--;
|
williamr@2
|
80 |
return *bound;
|
williamr@2
|
81 |
}
|
williamr@2
|
82 |
};
|
williamr@2
|
83 |
|
williamr@2
|
84 |
template<typename Allocator>
|
williamr@2
|
85 |
class bucket_array:public bucket_array_base
|
williamr@2
|
86 |
{
|
williamr@2
|
87 |
public:
|
williamr@2
|
88 |
bucket_array(const Allocator& al,hashed_index_node_impl* end_,std::size_t size):
|
williamr@2
|
89 |
size_(bucket_array_base::next_prime(size)),
|
williamr@2
|
90 |
spc(al,size_+1)
|
williamr@2
|
91 |
{
|
williamr@2
|
92 |
clear();
|
williamr@2
|
93 |
end()->next()=end_;
|
williamr@2
|
94 |
end_->next()=end();
|
williamr@2
|
95 |
}
|
williamr@2
|
96 |
|
williamr@2
|
97 |
std::size_t size()const
|
williamr@2
|
98 |
{
|
williamr@2
|
99 |
return size_;
|
williamr@2
|
100 |
}
|
williamr@2
|
101 |
|
williamr@2
|
102 |
std::size_t position(std::size_t hash)const
|
williamr@2
|
103 |
{
|
williamr@2
|
104 |
return hash%size_;
|
williamr@2
|
105 |
}
|
williamr@2
|
106 |
|
williamr@2
|
107 |
hashed_index_node_impl* begin()const{return &buckets()[0];}
|
williamr@2
|
108 |
hashed_index_node_impl* end()const{return &buckets()[size_];}
|
williamr@2
|
109 |
hashed_index_node_impl* at(std::size_t n)const{return &buckets()[n];}
|
williamr@2
|
110 |
|
williamr@2
|
111 |
std::size_t first_nonempty(std::size_t n)const
|
williamr@2
|
112 |
{
|
williamr@2
|
113 |
for(;;++n){
|
williamr@2
|
114 |
hashed_index_node_impl* x=at(n);
|
williamr@2
|
115 |
if(x->next()!=x)return n;
|
williamr@2
|
116 |
}
|
williamr@2
|
117 |
}
|
williamr@2
|
118 |
|
williamr@2
|
119 |
void clear()
|
williamr@2
|
120 |
{
|
williamr@2
|
121 |
for(hashed_index_node_impl* x=begin(),*y=end();x!=y;++x)x->next()=x;
|
williamr@2
|
122 |
}
|
williamr@2
|
123 |
|
williamr@2
|
124 |
void swap(bucket_array& x)
|
williamr@2
|
125 |
{
|
williamr@2
|
126 |
std::swap(size_,x.size_);
|
williamr@2
|
127 |
spc.swap(x.spc);
|
williamr@2
|
128 |
}
|
williamr@2
|
129 |
|
williamr@2
|
130 |
private:
|
williamr@2
|
131 |
std::size_t size_;
|
williamr@2
|
132 |
auto_space<hashed_index_node_impl,Allocator> spc;
|
williamr@2
|
133 |
|
williamr@2
|
134 |
hashed_index_node_impl* buckets()const
|
williamr@2
|
135 |
{
|
williamr@2
|
136 |
return spc.data();
|
williamr@2
|
137 |
}
|
williamr@2
|
138 |
|
williamr@2
|
139 |
#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
|
williamr@2
|
140 |
friend class boost::serialization::access;
|
williamr@2
|
141 |
|
williamr@2
|
142 |
/* bucket_arrays do not emit any kind of serialization info. They are
|
williamr@2
|
143 |
* fed to Boost.Serialization as hashed index iterators need to track
|
williamr@2
|
144 |
* them during serialization.
|
williamr@2
|
145 |
*/
|
williamr@2
|
146 |
|
williamr@2
|
147 |
template<class Archive>
|
williamr@2
|
148 |
void serialize(Archive&,const unsigned int)
|
williamr@2
|
149 |
{
|
williamr@2
|
150 |
}
|
williamr@2
|
151 |
#endif
|
williamr@2
|
152 |
};
|
williamr@2
|
153 |
|
williamr@2
|
154 |
template<typename Allocator>
|
williamr@2
|
155 |
void swap(bucket_array<Allocator>& x,bucket_array<Allocator>& y)
|
williamr@2
|
156 |
{
|
williamr@2
|
157 |
x.swap(y);
|
williamr@2
|
158 |
}
|
williamr@2
|
159 |
|
williamr@2
|
160 |
} /* namespace multi_index::detail */
|
williamr@2
|
161 |
|
williamr@2
|
162 |
} /* namespace multi_index */
|
williamr@2
|
163 |
|
williamr@2
|
164 |
#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
|
williamr@2
|
165 |
/* bucket_arrays never get constructed directly by Boost.Serialization,
|
williamr@2
|
166 |
* as archives are always fed pointers to previously existent
|
williamr@2
|
167 |
* arrays. So, if this is called it means we are dealing with a
|
williamr@2
|
168 |
* somehow invalid archive.
|
williamr@2
|
169 |
*/
|
williamr@2
|
170 |
|
williamr@2
|
171 |
#if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
|
williamr@2
|
172 |
namespace serialization{
|
williamr@2
|
173 |
#else
|
williamr@2
|
174 |
namespace multi_index{
|
williamr@2
|
175 |
namespace detail{
|
williamr@2
|
176 |
#endif
|
williamr@2
|
177 |
|
williamr@2
|
178 |
template<class Archive,typename Allocator>
|
williamr@2
|
179 |
inline void load_construct_data(
|
williamr@2
|
180 |
Archive&,boost::multi_index::detail::bucket_array<Allocator>*,
|
williamr@2
|
181 |
const unsigned int)
|
williamr@2
|
182 |
{
|
williamr@2
|
183 |
throw_exception(
|
williamr@2
|
184 |
archive::archive_exception(archive::archive_exception::other_exception));
|
williamr@2
|
185 |
}
|
williamr@2
|
186 |
|
williamr@2
|
187 |
#if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
|
williamr@2
|
188 |
} /* namespace serialization */
|
williamr@2
|
189 |
#else
|
williamr@2
|
190 |
} /* namespace multi_index::detail */
|
williamr@2
|
191 |
} /* namespace multi_index */
|
williamr@2
|
192 |
#endif
|
williamr@2
|
193 |
|
williamr@2
|
194 |
#endif
|
williamr@2
|
195 |
|
williamr@2
|
196 |
} /* namespace boost */
|
williamr@2
|
197 |
|
williamr@2
|
198 |
#endif
|