williamr@2: /* Copyright 2003-2005 Joaquín M López Muñoz. williamr@2: * Distributed under the Boost Software License, Version 1.0. williamr@2: * (See accompanying file LICENSE_1_0.txt or copy at williamr@2: * http://www.boost.org/LICENSE_1_0.txt) williamr@2: * williamr@2: * See http://www.boost.org/libs/multi_index for library home page. williamr@2: */ williamr@2: williamr@2: #ifndef BOOST_MULTI_INDEX_DETAIL_BUCKET_ARRAY_HPP williamr@2: #define BOOST_MULTI_INDEX_DETAIL_BUCKET_ARRAY_HPP williamr@2: williamr@2: #if defined(_MSC_VER)&&(_MSC_VER>=1200) williamr@2: #pragma once williamr@2: #endif williamr@2: williamr@2: #include /* keep it first to prevent nasty warns in MSVC */ williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: williamr@2: #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) williamr@2: #include williamr@2: #include williamr@2: #include williamr@2: #endif williamr@2: williamr@2: namespace boost{ williamr@2: williamr@2: namespace multi_index{ williamr@2: williamr@2: namespace detail{ williamr@2: williamr@2: /* bucket structure for use by hashed indices */ williamr@2: williamr@2: class bucket_array_base:private noncopyable williamr@2: { williamr@2: protected: williamr@2: inline static std::size_t next_prime(std::size_t n) williamr@2: { williamr@2: static const std::size_t prime_list[]={ williamr@2: 53ul, 97ul, 193ul, 389ul, 769ul, williamr@2: 1543ul, 3079ul, 6151ul, 12289ul, 24593ul, williamr@2: 49157ul, 98317ul, 196613ul, 393241ul, 786433ul, williamr@2: 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul, williamr@2: 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul, williamr@2: 1610612741ul, 3221225473ul, williamr@2: williamr@2: #if ((((ULONG_MAX>>16)>>16)>>16)>>15)==0 /* unsigned long less than 64 bits */ williamr@2: 4294967291ul williamr@2: #else williamr@2: /* obtained with aid from williamr@2: * http://javaboutique.internet.com/prime_numb/ williamr@2: * http://www.rsok.com/~jrm/next_ten_primes.html williamr@2: * and verified with williamr@2: * http://www.alpertron.com.ar/ECM.HTM williamr@2: */ williamr@2: williamr@2: 6442450939ul, 12884901893ul, 25769803751ul, 51539607551ul, williamr@2: 103079215111ul, 206158430209ul, 412316860441ul, 824633720831ul, williamr@2: 1649267441651ul, 3298534883309ul, 6597069766657ul, 13194139533299ul, williamr@2: 26388279066623ul, 52776558133303ul, 105553116266489ul, 211106232532969ul, williamr@2: 422212465066001ul, 844424930131963ul, 1688849860263953ul, williamr@2: 3377699720527861ul, 6755399441055731ul, 13510798882111483ul, williamr@2: 27021597764222939ul, 54043195528445957ul, 108086391056891903ul, williamr@2: 216172782113783843ul, 432345564227567621ul, 864691128455135207ul, williamr@2: 1729382256910270481ul, 3458764513820540933ul, 6917529027641081903ul, williamr@2: 13835058055282163729ul, 18446744073709551557ul williamr@2: #endif williamr@2: williamr@2: }; williamr@2: static const std::size_t prime_list_size= williamr@2: sizeof(prime_list)/sizeof(prime_list[0]); williamr@2: williamr@2: std::size_t const *bound= williamr@2: std::lower_bound(prime_list,prime_list+prime_list_size,n); williamr@2: if(bound==prime_list+prime_list_size)bound--; williamr@2: return *bound; williamr@2: } williamr@2: }; williamr@2: williamr@2: template williamr@2: class bucket_array:public bucket_array_base williamr@2: { williamr@2: public: williamr@2: bucket_array(const Allocator& al,hashed_index_node_impl* end_,std::size_t size): williamr@2: size_(bucket_array_base::next_prime(size)), williamr@2: spc(al,size_+1) williamr@2: { williamr@2: clear(); williamr@2: end()->next()=end_; williamr@2: end_->next()=end(); williamr@2: } williamr@2: williamr@2: std::size_t size()const williamr@2: { williamr@2: return size_; williamr@2: } williamr@2: williamr@2: std::size_t position(std::size_t hash)const williamr@2: { williamr@2: return hash%size_; williamr@2: } williamr@2: williamr@2: hashed_index_node_impl* begin()const{return &buckets()[0];} williamr@2: hashed_index_node_impl* end()const{return &buckets()[size_];} williamr@2: hashed_index_node_impl* at(std::size_t n)const{return &buckets()[n];} williamr@2: williamr@2: std::size_t first_nonempty(std::size_t n)const williamr@2: { williamr@2: for(;;++n){ williamr@2: hashed_index_node_impl* x=at(n); williamr@2: if(x->next()!=x)return n; williamr@2: } williamr@2: } williamr@2: williamr@2: void clear() williamr@2: { williamr@2: for(hashed_index_node_impl* x=begin(),*y=end();x!=y;++x)x->next()=x; williamr@2: } williamr@2: williamr@2: void swap(bucket_array& x) williamr@2: { williamr@2: std::swap(size_,x.size_); williamr@2: spc.swap(x.spc); williamr@2: } williamr@2: williamr@2: private: williamr@2: std::size_t size_; williamr@2: auto_space spc; williamr@2: williamr@2: hashed_index_node_impl* buckets()const williamr@2: { williamr@2: return spc.data(); williamr@2: } williamr@2: williamr@2: #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) williamr@2: friend class boost::serialization::access; williamr@2: williamr@2: /* bucket_arrays do not emit any kind of serialization info. They are williamr@2: * fed to Boost.Serialization as hashed index iterators need to track williamr@2: * them during serialization. williamr@2: */ williamr@2: williamr@2: template williamr@2: void serialize(Archive&,const unsigned int) williamr@2: { williamr@2: } williamr@2: #endif williamr@2: }; williamr@2: williamr@2: template williamr@2: void swap(bucket_array& x,bucket_array& y) williamr@2: { williamr@2: x.swap(y); williamr@2: } williamr@2: williamr@2: } /* namespace multi_index::detail */ williamr@2: williamr@2: } /* namespace multi_index */ williamr@2: williamr@2: #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) williamr@2: /* bucket_arrays never get constructed directly by Boost.Serialization, williamr@2: * as archives are always fed pointers to previously existent williamr@2: * arrays. So, if this is called it means we are dealing with a williamr@2: * somehow invalid archive. williamr@2: */ williamr@2: williamr@2: #if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP) williamr@2: namespace serialization{ williamr@2: #else williamr@2: namespace multi_index{ williamr@2: namespace detail{ williamr@2: #endif williamr@2: williamr@2: template williamr@2: inline void load_construct_data( williamr@2: Archive&,boost::multi_index::detail::bucket_array*, williamr@2: const unsigned int) williamr@2: { williamr@2: throw_exception( williamr@2: archive::archive_exception(archive::archive_exception::other_exception)); williamr@2: } williamr@2: williamr@2: #if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP) williamr@2: } /* namespace serialization */ williamr@2: #else williamr@2: } /* namespace multi_index::detail */ williamr@2: } /* namespace multi_index */ williamr@2: #endif williamr@2: williamr@2: #endif williamr@2: williamr@2: } /* namespace boost */ williamr@2: williamr@2: #endif