ceph/src/boost/boost/multi_index/detail/rnd_index_ptr_array.hpp

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