epoc32/include/stdapis/boost/multi_index/detail/bucket_array.hpp
author William Roberts <williamr@symbian.org>
Wed, 31 Mar 2010 12:27:01 +0100
branchSymbian2
changeset 3 e1b950c65cb4
permissions -rw-r--r--
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)
     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 
    30 namespace boost{
    31 
    32 namespace multi_index{
    33 
    34 namespace detail{
    35 
    36 /* bucket structure for use by hashed indices */
    37 
    38 class bucket_array_base:private noncopyable
    39 {
    40 protected:
    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 
    84 template<typename Allocator>
    85 class bucket_array:public bucket_array_base
    86 {
    87 public:
    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 
   130 private:
   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 
   154 template<typename Allocator>
   155 void 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)
   172 namespace serialization{
   173 #else
   174 namespace multi_index{
   175 namespace detail{
   176 #endif
   177 
   178 template<class Archive,typename Allocator>
   179 inline 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