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
williamr@2
     1
/* Copyright 2003-2005 Joaquín M López Muñoz.
williamr@2
     2
 * Distributed under the Boost Software License, Version 1.0.
williamr@2
     3
 * (See accompanying file LICENSE_1_0.txt or copy at
williamr@2
     4
 * http://www.boost.org/LICENSE_1_0.txt)
williamr@2
     5
 *
williamr@2
     6
 * See http://www.boost.org/libs/multi_index for library home page.
williamr@2
     7
 */
williamr@2
     8
williamr@2
     9
#ifndef BOOST_MULTI_INDEX_DETAIL_BUCKET_ARRAY_HPP
williamr@2
    10
#define BOOST_MULTI_INDEX_DETAIL_BUCKET_ARRAY_HPP
williamr@2
    11
williamr@2
    12
#if defined(_MSC_VER)&&(_MSC_VER>=1200)
williamr@2
    13
#pragma once
williamr@2
    14
#endif
williamr@2
    15
williamr@2
    16
#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
williamr@2
    17
#include <algorithm>
williamr@2
    18
#include <boost/multi_index/detail/auto_space.hpp>
williamr@2
    19
#include <boost/multi_index/detail/hash_index_node.hpp>
williamr@2
    20
#include <boost/noncopyable.hpp>
williamr@2
    21
#include <cstddef>
williamr@2
    22
#include <limits.h>
williamr@2
    23
williamr@2
    24
#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
williamr@2
    25
#include <boost/archive/archive_exception.hpp>
williamr@2
    26
#include <boost/serialization/access.hpp>
williamr@2
    27
#include <boost/throw_exception.hpp> 
williamr@2
    28
#endif
williamr@2
    29
williamr@2
    30
namespace boost{
williamr@2
    31
williamr@2
    32
namespace multi_index{
williamr@2
    33
williamr@2
    34
namespace detail{
williamr@2
    35
williamr@2
    36
/* bucket structure for use by hashed indices */
williamr@2
    37
williamr@2
    38
class bucket_array_base:private noncopyable
williamr@2
    39
{
williamr@2
    40
protected:
williamr@2
    41
  inline static std::size_t next_prime(std::size_t n)
williamr@2
    42
  {
williamr@2
    43
    static const std::size_t prime_list[]={
williamr@2
    44
      53ul, 97ul, 193ul, 389ul, 769ul,
williamr@2
    45
      1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
williamr@2
    46
      49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
williamr@2
    47
      1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
williamr@2
    48
      50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
williamr@2
    49
      1610612741ul, 3221225473ul,
williamr@2
    50
williamr@2
    51
#if ((((ULONG_MAX>>16)>>16)>>16)>>15)==0 /* unsigned long less than 64 bits */
williamr@2
    52
      4294967291ul
williamr@2
    53
#else
williamr@2
    54
      /* obtained with aid from
williamr@2
    55
       *   http://javaboutique.internet.com/prime_numb/
williamr@2
    56
       *   http://www.rsok.com/~jrm/next_ten_primes.html
williamr@2
    57
       * and verified with
williamr@2
    58
       *   http://www.alpertron.com.ar/ECM.HTM
williamr@2
    59
       */
williamr@2
    60
williamr@2
    61
      6442450939ul, 12884901893ul, 25769803751ul, 51539607551ul,
williamr@2
    62
      103079215111ul, 206158430209ul, 412316860441ul, 824633720831ul,
williamr@2
    63
      1649267441651ul, 3298534883309ul, 6597069766657ul, 13194139533299ul,
williamr@2
    64
      26388279066623ul, 52776558133303ul, 105553116266489ul, 211106232532969ul,
williamr@2
    65
      422212465066001ul, 844424930131963ul, 1688849860263953ul,
williamr@2
    66
      3377699720527861ul, 6755399441055731ul, 13510798882111483ul,
williamr@2
    67
      27021597764222939ul, 54043195528445957ul, 108086391056891903ul,
williamr@2
    68
      216172782113783843ul, 432345564227567621ul, 864691128455135207ul,
williamr@2
    69
      1729382256910270481ul, 3458764513820540933ul, 6917529027641081903ul,
williamr@2
    70
      13835058055282163729ul, 18446744073709551557ul
williamr@2
    71
#endif
williamr@2
    72
williamr@2
    73
    };
williamr@2
    74
    static const std::size_t prime_list_size=
williamr@2
    75
      sizeof(prime_list)/sizeof(prime_list[0]);
williamr@2
    76
williamr@2
    77
    std::size_t const *bound=
williamr@2
    78
      std::lower_bound(prime_list,prime_list+prime_list_size,n);
williamr@2
    79
    if(bound==prime_list+prime_list_size)bound--;
williamr@2
    80
    return *bound;
williamr@2
    81
  }
williamr@2
    82
};
williamr@2
    83
williamr@2
    84
template<typename Allocator>
williamr@2
    85
class bucket_array:public bucket_array_base
williamr@2
    86
{
williamr@2
    87
public:
williamr@2
    88
  bucket_array(const Allocator& al,hashed_index_node_impl* end_,std::size_t size):
williamr@2
    89
    size_(bucket_array_base::next_prime(size)),
williamr@2
    90
    spc(al,size_+1)
williamr@2
    91
  {
williamr@2
    92
    clear();
williamr@2
    93
    end()->next()=end_;
williamr@2
    94
    end_->next()=end();
williamr@2
    95
  }
williamr@2
    96
williamr@2
    97
  std::size_t size()const
williamr@2
    98
  {
williamr@2
    99
    return size_;
williamr@2
   100
  }
williamr@2
   101
williamr@2
   102
  std::size_t position(std::size_t hash)const
williamr@2
   103
  {
williamr@2
   104
    return hash%size_;
williamr@2
   105
  }
williamr@2
   106
williamr@2
   107
  hashed_index_node_impl* begin()const{return &buckets()[0];}
williamr@2
   108
  hashed_index_node_impl* end()const{return &buckets()[size_];}
williamr@2
   109
  hashed_index_node_impl* at(std::size_t n)const{return &buckets()[n];}
williamr@2
   110
williamr@2
   111
  std::size_t first_nonempty(std::size_t n)const
williamr@2
   112
  {
williamr@2
   113
    for(;;++n){
williamr@2
   114
      hashed_index_node_impl* x=at(n);
williamr@2
   115
      if(x->next()!=x)return n;
williamr@2
   116
    }
williamr@2
   117
  }
williamr@2
   118
williamr@2
   119
  void clear()
williamr@2
   120
  {
williamr@2
   121
    for(hashed_index_node_impl* x=begin(),*y=end();x!=y;++x)x->next()=x;
williamr@2
   122
  }
williamr@2
   123
williamr@2
   124
  void swap(bucket_array& x)
williamr@2
   125
  {
williamr@2
   126
    std::swap(size_,x.size_);
williamr@2
   127
    spc.swap(x.spc);
williamr@2
   128
  }
williamr@2
   129
williamr@2
   130
private:
williamr@2
   131
  std::size_t                                  size_;
williamr@2
   132
  auto_space<hashed_index_node_impl,Allocator> spc;
williamr@2
   133
williamr@2
   134
  hashed_index_node_impl* buckets()const
williamr@2
   135
  {
williamr@2
   136
    return spc.data();
williamr@2
   137
  }
williamr@2
   138
williamr@2
   139
#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
williamr@2
   140
  friend class boost::serialization::access;
williamr@2
   141
  
williamr@2
   142
  /* bucket_arrays do not emit any kind of serialization info. They are
williamr@2
   143
   * fed to Boost.Serialization as hashed index iterators need to track
williamr@2
   144
   * them during serialization.
williamr@2
   145
   */
williamr@2
   146
williamr@2
   147
  template<class Archive>
williamr@2
   148
  void serialize(Archive&,const unsigned int)
williamr@2
   149
  {
williamr@2
   150
  }
williamr@2
   151
#endif
williamr@2
   152
};
williamr@2
   153
williamr@2
   154
template<typename Allocator>
williamr@2
   155
void swap(bucket_array<Allocator>& x,bucket_array<Allocator>& y)
williamr@2
   156
{
williamr@2
   157
  x.swap(y);
williamr@2
   158
}
williamr@2
   159
williamr@2
   160
} /* namespace multi_index::detail */
williamr@2
   161
williamr@2
   162
} /* namespace multi_index */
williamr@2
   163
williamr@2
   164
#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
williamr@2
   165
/* bucket_arrays never get constructed directly by Boost.Serialization,
williamr@2
   166
 * as archives are always fed pointers to previously existent
williamr@2
   167
 * arrays. So, if this is called it means we are dealing with a
williamr@2
   168
 * somehow invalid archive.
williamr@2
   169
 */
williamr@2
   170
williamr@2
   171
#if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
williamr@2
   172
namespace serialization{
williamr@2
   173
#else
williamr@2
   174
namespace multi_index{
williamr@2
   175
namespace detail{
williamr@2
   176
#endif
williamr@2
   177
williamr@2
   178
template<class Archive,typename Allocator>
williamr@2
   179
inline void load_construct_data(
williamr@2
   180
  Archive&,boost::multi_index::detail::bucket_array<Allocator>*,
williamr@2
   181
  const unsigned int)
williamr@2
   182
{
williamr@2
   183
  throw_exception(
williamr@2
   184
    archive::archive_exception(archive::archive_exception::other_exception));
williamr@2
   185
}
williamr@2
   186
williamr@2
   187
#if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
williamr@2
   188
} /* namespace serialization */
williamr@2
   189
#else
williamr@2
   190
} /* namespace multi_index::detail */
williamr@2
   191
} /* namespace multi_index */
williamr@2
   192
#endif
williamr@2
   193
williamr@2
   194
#endif
williamr@2
   195
williamr@2
   196
} /* namespace boost */
williamr@2
   197
williamr@2
   198
#endif