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