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