Attempt to represent the S^2->S^3 header reorganisation as a series of "hg rename" operations
1 /* Copyright 2003-2005 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)
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/noncopyable.hpp>
24 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
25 #include <boost/archive/archive_exception.hpp>
26 #include <boost/serialization/access.hpp>
27 #include <boost/throw_exception.hpp>
32 namespace multi_index{
36 /* bucket structure for use by hashed indices */
38 class bucket_array_base:private noncopyable
41 inline static std::size_t next_prime(std::size_t n)
43 static const std::size_t prime_list[]={
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,
51 #if ((((ULONG_MAX>>16)>>16)>>16)>>15)==0 /* unsigned long less than 64 bits */
54 /* obtained with aid from
55 * http://javaboutique.internet.com/prime_numb/
56 * http://www.rsok.com/~jrm/next_ten_primes.html
58 * http://www.alpertron.com.ar/ECM.HTM
61 6442450939ul, 12884901893ul, 25769803751ul, 51539607551ul,
62 103079215111ul, 206158430209ul, 412316860441ul, 824633720831ul,
63 1649267441651ul, 3298534883309ul, 6597069766657ul, 13194139533299ul,
64 26388279066623ul, 52776558133303ul, 105553116266489ul, 211106232532969ul,
65 422212465066001ul, 844424930131963ul, 1688849860263953ul,
66 3377699720527861ul, 6755399441055731ul, 13510798882111483ul,
67 27021597764222939ul, 54043195528445957ul, 108086391056891903ul,
68 216172782113783843ul, 432345564227567621ul, 864691128455135207ul,
69 1729382256910270481ul, 3458764513820540933ul, 6917529027641081903ul,
70 13835058055282163729ul, 18446744073709551557ul
74 static const std::size_t prime_list_size=
75 sizeof(prime_list)/sizeof(prime_list[0]);
77 std::size_t const *bound=
78 std::lower_bound(prime_list,prime_list+prime_list_size,n);
79 if(bound==prime_list+prime_list_size)bound--;
84 template<typename Allocator>
85 class bucket_array:public bucket_array_base
88 bucket_array(const Allocator& al,hashed_index_node_impl* end_,std::size_t size):
89 size_(bucket_array_base::next_prime(size)),
97 std::size_t size()const
102 std::size_t position(std::size_t hash)const
107 hashed_index_node_impl* begin()const{return &buckets()[0];}
108 hashed_index_node_impl* end()const{return &buckets()[size_];}
109 hashed_index_node_impl* at(std::size_t n)const{return &buckets()[n];}
111 std::size_t first_nonempty(std::size_t n)const
114 hashed_index_node_impl* x=at(n);
115 if(x->next()!=x)return n;
121 for(hashed_index_node_impl* x=begin(),*y=end();x!=y;++x)x->next()=x;
124 void swap(bucket_array& x)
126 std::swap(size_,x.size_);
132 auto_space<hashed_index_node_impl,Allocator> spc;
134 hashed_index_node_impl* buckets()const
139 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
140 friend class boost::serialization::access;
142 /* bucket_arrays do not emit any kind of serialization info. They are
143 * fed to Boost.Serialization as hashed index iterators need to track
144 * them during serialization.
147 template<class Archive>
148 void serialize(Archive&,const unsigned int)
154 template<typename Allocator>
155 void swap(bucket_array<Allocator>& x,bucket_array<Allocator>& y)
160 } /* namespace multi_index::detail */
162 } /* namespace multi_index */
164 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
165 /* bucket_arrays never get constructed directly by Boost.Serialization,
166 * as archives are always fed pointers to previously existent
167 * arrays. So, if this is called it means we are dealing with a
168 * somehow invalid archive.
171 #if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
172 namespace serialization{
174 namespace multi_index{
178 template<class Archive,typename Allocator>
179 inline void load_construct_data(
180 Archive&,boost::multi_index::detail::bucket_array<Allocator>*,
184 archive::archive_exception(archive::archive_exception::other_exception));
187 #if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
188 } /* namespace serialization */
190 } /* namespace multi_index::detail */
191 } /* namespace multi_index */
196 } /* namespace boost */