source: NonGTP/Boost/boost/multi_index/detail/bucket_array.hpp @ 857

Revision 857, 5.5 KB checked in by igarcia, 19 years ago (diff)
Line 
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)
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)&&(_MSC_VER>=1200)
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 <cstddef>
22#include <limits.h>
23
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>
28#endif
29
30namespace boost{
31
32namespace multi_index{
33
34namespace detail{
35
36/* bucket structure for use by hashed indices */
37
38class bucket_array_base:private noncopyable
39{
40protected:
41  inline static std::size_t next_prime(std::size_t n)
42  {
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,
50
51#if ((((ULONG_MAX>>16)>>16)>>16)>>15)==0 /* unsigned long less than 64 bits */
52      4294967291ul
53#else
54      /* obtained with aid from
55       *   http://javaboutique.internet.com/prime_numb/
56       *   http://www.rsok.com/~jrm/next_ten_primes.html
57       * and verified with
58       *   http://www.alpertron.com.ar/ECM.HTM
59       */
60
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
71#endif
72
73    };
74    static const std::size_t prime_list_size=
75      sizeof(prime_list)/sizeof(prime_list[0]);
76
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--;
80    return *bound;
81  }
82};
83
84template<typename Allocator>
85class bucket_array:public bucket_array_base
86{
87public:
88  bucket_array(const Allocator& al,hashed_index_node_impl* end_,std::size_t size):
89    size_(bucket_array_base::next_prime(size)),
90    spc(al,size_+1)
91  {
92    clear();
93    end()->next()=end_;
94    end_->next()=end();
95  }
96
97  std::size_t size()const
98  {
99    return size_;
100  }
101
102  std::size_t position(std::size_t hash)const
103  {
104    return hash%size_;
105  }
106
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];}
110
111  std::size_t first_nonempty(std::size_t n)const
112  {
113    for(;;++n){
114      hashed_index_node_impl* x=at(n);
115      if(x->next()!=x)return n;
116    }
117  }
118
119  void clear()
120  {
121    for(hashed_index_node_impl* x=begin(),*y=end();x!=y;++x)x->next()=x;
122  }
123
124  void swap(bucket_array& x)
125  {
126    std::swap(size_,x.size_);
127    spc.swap(x.spc);
128  }
129
130private:
131  std::size_t                                  size_;
132  auto_space<hashed_index_node_impl,Allocator> spc;
133
134  hashed_index_node_impl* buckets()const
135  {
136    return spc.data();
137  }
138
139#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
140  friend class boost::serialization::access;
141 
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.
145   */
146
147  template<class Archive>
148  void serialize(Archive&,const unsigned int)
149  {
150  }
151#endif
152};
153
154template<typename Allocator>
155void swap(bucket_array<Allocator>& x,bucket_array<Allocator>& y)
156{
157  x.swap(y);
158}
159
160} /* namespace multi_index::detail */
161
162} /* namespace multi_index */
163
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.
169 */
170
171#if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
172namespace serialization{
173#else
174namespace multi_index{
175namespace detail{
176#endif
177
178template<class Archive,typename Allocator>
179inline void load_construct_data(
180  Archive&,boost::multi_index::detail::bucket_array<Allocator>*,
181  const unsigned int)
182{
183  throw_exception(
184    archive::archive_exception(archive::archive_exception::other_exception));
185}
186
187#if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
188} /* namespace serialization */
189#else
190} /* namespace multi_index::detail */
191} /* namespace multi_index */
192#endif
193
194#endif
195
196} /* namespace boost */
197
198#endif
Note: See TracBrowser for help on using the repository browser.