boost/multi_index/detail/rnd_index_ptr_array.hpp

   1 /* Copyright 2003-2007 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_RND_INDEX_PTR_ARRAY_HPP
  10 #define BOOST_MULTI_INDEX_DETAIL_RND_INDEX_PTR_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/detail/allocator_utilities.hpp>
  19 #include <boost/multi_index/detail/auto_space.hpp>
  20 #include <boost/multi_index/detail/prevent_eti.hpp>
  21 #include <boost/multi_index/detail/rnd_index_node.hpp>
  22 #include <boost/noncopyable.hpp>
  23 #include <cstddef>
  24
  25 namespace boost{
  26
  27 namespace multi_index{
  28
  29 namespace detail{
  30
  31 /* pointer structure for use by random access indices */
  32
  33 template<typename Allocator>
  34 class random_access_index_ptr_array:private noncopyable
  35 {
  36   typedef typename prevent_eti<
  37     Allocator,
  38     random_access_index_node_impl<
  39       typename boost::detail::allocator::rebind_to<
  40         Allocator,
  41         void
  42       >::type
  43     >
  44   >::type                                           node_impl_type;
  45
  46 public:
  47   typedef typename node_impl_type::pointer          value_type;
  48   typedef typename prevent_eti<
  49     Allocator,
  50     typename boost::detail::allocator::rebind_to<
  51       Allocator,value_type
  52     >::type
  53   >::type::pointer                                  pointer;
  54
  55   random_access_index_ptr_array(
  56     const Allocator& al,value_type end_,std::size_t size):
  57     size_(size),
  58     capacity_(size),
  59     spc(al,capacity_+1)
  60   {
  61     *end()=end_;
  62     end_->up()=end();
  63   }
  64
  65   std::size_t size()const{return size_;}
  66   std::size_t capacity()const{return capacity_;}
  67
  68   void room_for_one()
  69   {
  70     if(size_==capacity_){
  71       reserve(capacity_<=10?15:capacity_+capacity_/2);
  72     }
  73   }
  74
  75   void reserve(std::size_t c)
  76   {
  77     if(c>capacity_){
  78       auto_space<value_type,Allocator> spc1(spc.get_allocator(),c+1);
  79       node_impl_type::transfer(begin(),end()+1,spc1.data());
  80       spc.swap(spc1);
  81       capacity_=c;
  82     }
  83   }
  84
  85   pointer begin()const{return ptrs();}
  86   pointer end()const{return ptrs()+size_;}
  87   pointer at(std::size_t n)const{return ptrs()+n;}
  88
  89   void push_back(value_type x)
  90   {
  91     *(end()+1)=*end();
  92     (*(end()+1))->up()=end()+1;
  93     *end()=x;
  94     (*end())->up()=end();
  95     ++size_;
  96   }
  97
  98   void erase(value_type x)
  99   {
 100     node_impl_type::extract(x->up(),end()+1);
 101     --size_;
 102   }
 103
 104   void clear()
 105   {
 106     *begin()=*end();
 107     (*begin())->up()=begin();
 108     size_=0;
 109   }
 110
 111   void swap(random_access_index_ptr_array& x)
 112   {
 113     std::swap(size_,x.size_);
 114     std::swap(capacity_,x.capacity_);
 115     spc.swap(x.spc);
 116   }
 117
 118 private:
 119   std::size_t                      size_;
 120   std::size_t                      capacity_;
 121   auto_space<value_type,Allocator> spc;
 122
 123   pointer ptrs()const
 124   {
 125     return spc.data();
 126   }
 127 };
 128
 129 template<typename Allocator>
 130 void swap(
 131   random_access_index_ptr_array<Allocator>& x,
 132   random_access_index_ptr_array<Allocator>& y)
 133 {
 134   x.swap(y);
 135 }
 136
 137 } /* namespace multi_index::detail */
 138
 139 } /* namespace multi_index */
 140
 141 } /* namespace boost */
 142
 143 #endif