multi_index/detail/rnd_index_ptr_array.hpp

0001 /* Copyright 2003-2022 Joaquin M Lopez Munoz.
0002  * Distributed under the Boost Software License, Version 1.0.
0003  * (See accompanying file LICENSE_1_0.txt or copy at
0004  * http://www.boost.org/LICENSE_1_0.txt)
0005  *
0006  * See http://www.boost.org/libs/multi_index for library home page.
0007  */
0008
0009 #ifndef BOOST_MULTI_INDEX_DETAIL_RND_INDEX_PTR_ARRAY_HPP
0010 #define BOOST_MULTI_INDEX_DETAIL_RND_INDEX_PTR_ARRAY_HPP
0011
0012 #if defined(_MSC_VER)
0013 #pragma once
0014 #endif
0015
0016 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
0017 #include <algorithm>
0018 #include <boost/core/noncopyable.hpp>
0019 #include <boost/multi_index/detail/allocator_traits.hpp>
0020 #include <boost/multi_index/detail/auto_space.hpp>
0021 #include <boost/multi_index/detail/rnd_index_node.hpp>
0022
0023 namespace boost{
0024
0025 namespace multi_index{
0026
0027 namespace detail{
0028
0029 /* pointer structure for use by random access indices */
0030
0031 template<typename Allocator>
0032 class random_access_index_ptr_array:private noncopyable
0033 {
0034   typedef random_access_index_node_impl<
0035     typename rebind_alloc_for<
0036       Allocator,
0037       char
0038     >::type
0039   >                                         node_impl_type;
0040
0041 public:
0042   typedef typename node_impl_type::pointer  value_type;
0043   typedef typename rebind_alloc_for<
0044     Allocator,value_type
0045   >::type                                   value_allocator;
0046   typedef allocator_traits<value_allocator> alloc_traits;
0047   typedef typename alloc_traits::pointer    pointer;
0048   typedef typename alloc_traits::size_type  size_type;
0049
0050   random_access_index_ptr_array(
0051     const Allocator& al,value_type end_,size_type sz):
0052     size_(sz),
0053     capacity_(sz),
0054     spc(al,capacity_+1)
0055   {
0056     *end()=end_;
0057     end_->up()=end();
0058   }
0059
0060   size_type size()const{return size_;}
0061   size_type capacity()const{return capacity_;}
0062
0063   void room_for_one()
0064   {
0065     if(size_==capacity_){
0066       reserve(capacity_<=10?15:capacity_+capacity_/2);
0067     }
0068   }
0069
0070   void reserve(size_type c)
0071   {
0072     if(c>capacity_)set_capacity(c);
0073   }
0074
0075   void shrink_to_fit()
0076   {
0077     if(capacity_>size_)set_capacity(size_);
0078   }
0079
0080   pointer begin()const{return ptrs();}
0081   pointer end()const{return ptrs()+size_;}
0082   pointer at(size_type n)const{return ptrs()+n;}
0083
0084   void push_back(value_type x)
0085   {
0086     *(end()+1)=*end();
0087     (*(end()+1))->up()=end()+1;
0088     *end()=x;
0089     (*end())->up()=end();
0090     ++size_;
0091   }
0092
0093   void erase(value_type x)
0094   {
0095     node_impl_type::extract(x->up(),end()+1);
0096     --size_;
0097   }
0098
0099   void clear()
0100   {
0101     *begin()=*end();
0102     (*begin())->up()=begin();
0103     size_=0;
0104   }
0105
0106   void swap(random_access_index_ptr_array& x)
0107   {
0108     std::swap(size_,x.size_);
0109     std::swap(capacity_,x.capacity_);
0110     spc.swap(x.spc);
0111   }
0112
0113   template<typename BoolConstant>
0114   void swap(random_access_index_ptr_array& x,BoolConstant swap_allocators)
0115   {
0116     std::swap(size_,x.size_);
0117     std::swap(capacity_,x.capacity_);
0118     spc.swap(x.spc,swap_allocators);
0119   }
0120
0121 private:
0122   size_type                        size_;
0123   size_type                        capacity_;
0124   auto_space<value_type,Allocator> spc;
0125
0126   pointer ptrs()const
0127   {
0128     return spc.data();
0129   }
0130
0131   void set_capacity(size_type c)
0132   {
0133     auto_space<value_type,Allocator> spc1(spc.get_allocator(),c+1);
0134     node_impl_type::transfer(begin(),end()+1,spc1.data());
0135     spc.swap(spc1);
0136     capacity_=c;
0137   }
0138 };
0139
0140 template<typename Allocator>
0141 void swap(
0142   random_access_index_ptr_array<Allocator>& x,
0143   random_access_index_ptr_array<Allocator>& y)
0144 {
0145   x.swap(y);
0146 }
0147
0148 } /* namespace multi_index::detail */
0149
0150 } /* namespace multi_index */
0151
0152 } /* namespace boost */
0153
0154 #endif