include/boost/json /impl /array.ipp
100.00% Lines (389/389) 100.00% Functions (40/40)
[ ] prev/next file n p prev/next uncovered line
TLA Baseline Branch
Line Hits Code Line Hits Code
1   // 1   //
2   // Copyright (c) 2019 Vinnie Falco (vinnie.falco@gmail.com) 2   // Copyright (c) 2019 Vinnie Falco (vinnie.falco@gmail.com)
3   // 3   //
4   // Distributed under the Boost Software License, Version 1.0. (See accompanying 4   // Distributed under the Boost Software License, Version 1.0. (See accompanying
5   // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 5   // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6   // 6   //
7   // Official repository: https://github.com/boostorg/json 7   // Official repository: https://github.com/boostorg/json
8   // 8   //
9   9  
10   #ifndef BOOST_JSON_IMPL_ARRAY_IPP 10   #ifndef BOOST_JSON_IMPL_ARRAY_IPP
11   #define BOOST_JSON_IMPL_ARRAY_IPP 11   #define BOOST_JSON_IMPL_ARRAY_IPP
12   12  
13   #include <boost/core/detail/static_assert.hpp> 13   #include <boost/core/detail/static_assert.hpp>
14   #include <boost/container_hash/hash.hpp> 14   #include <boost/container_hash/hash.hpp>
15   #include <boost/json/array.hpp> 15   #include <boost/json/array.hpp>
16   #include <boost/json/pilfer.hpp> 16   #include <boost/json/pilfer.hpp>
17   #include <boost/json/detail/except.hpp> 17   #include <boost/json/detail/except.hpp>
18   #include <cstdlib> 18   #include <cstdlib>
19   #include <limits> 19   #include <limits>
20   #include <new> 20   #include <new>
21   #include <utility> 21   #include <utility>
22   22  
23   namespace boost { 23   namespace boost {
24   namespace json { 24   namespace json {
25   25  
26   //---------------------------------------------------------- 26   //----------------------------------------------------------
27   27  
28   constexpr array::table::table() = default; 28   constexpr array::table::table() = default;
29   29  
30   // empty arrays point here 30   // empty arrays point here
31   BOOST_JSON_REQUIRE_CONST_INIT 31   BOOST_JSON_REQUIRE_CONST_INIT
32   array::table array::empty_; 32   array::table array::empty_;
33   33  
34   auto 34   auto
HITCBC 35   2553 array:: 35   2553 array::
36   table:: 36   table::
37   allocate( 37   allocate(
38   std::size_t capacity, 38   std::size_t capacity,
39   storage_ptr const& sp) -> 39   storage_ptr const& sp) ->
40   table* 40   table*
41   { 41   {
HITCBC 42   2553 BOOST_ASSERT(capacity > 0); 42   2553 BOOST_ASSERT(capacity > 0);
HITCBC 43   2553 if(capacity > array::max_size()) 43   2553 if(capacity > array::max_size())
44   { 44   {
45   BOOST_STATIC_CONSTEXPR source_location loc = BOOST_CURRENT_LOCATION; 45   BOOST_STATIC_CONSTEXPR source_location loc = BOOST_CURRENT_LOCATION;
HITCBC 46   2 detail::throw_system_error( error::array_too_large, &loc ); 46   2 detail::throw_system_error( error::array_too_large, &loc );
47   } 47   }
48   auto p = reinterpret_cast< 48   auto p = reinterpret_cast<
HITCBC 49   2551 table*>(sp->allocate( 49   2551 table*>(sp->allocate(
50   sizeof(table) + 50   sizeof(table) +
HITCBC 51   2551 capacity * sizeof(value), 51   2551 capacity * sizeof(value),
52   alignof(value))); 52   alignof(value)));
HITCBC 53   2412 p->capacity = static_cast< 53   2412 p->capacity = static_cast<
54   std::uint32_t>(capacity); 54   std::uint32_t>(capacity);
HITCBC 55   2412 return p; 55   2412 return p;
56   } 56   }
57   57  
58   void 58   void
HITCBC 59   4442 array:: 59   4442 array::
60   table:: 60   table::
61   deallocate( 61   deallocate(
62   table* p, 62   table* p,
63   storage_ptr const& sp) 63   storage_ptr const& sp)
64   { 64   {
HITCBC 65   4442 if(p->capacity == 0) 65   4442 if(p->capacity == 0)
HITCBC 66   2034 return; 66   2034 return;
HITCBC 67   2408 sp->deallocate(p, 67   2408 sp->deallocate(p,
68   sizeof(table) + 68   sizeof(table) +
HITCBC 69   2408 p->capacity * sizeof(value), 69   2408 p->capacity * sizeof(value),
70   alignof(value)); 70   alignof(value));
71   } 71   }
72   72  
73   //---------------------------------------------------------- 73   //----------------------------------------------------------
74   74  
HITCBC 75   37 array:: 75   37 array::
76   revert_insert:: 76   revert_insert::
77   revert_insert( 77   revert_insert(
78   const_iterator pos, 78   const_iterator pos,
79   std::size_t n, 79   std::size_t n,
HITCBC 80   37 array& arr) 80   37 array& arr)
HITCBC 81   37 : arr_(&arr) 81   37 : arr_(&arr)
HITCBC 82   37 , i_(pos - arr_->data()) 82   37 , i_(pos - arr_->data())
HITCBC 83   37 , n_(n) 83   37 , n_(n)
84   { 84   {
HITCBC 85   37 BOOST_ASSERT( 85   37 BOOST_ASSERT(
86   pos >= arr_->begin() && 86   pos >= arr_->begin() &&
87   pos <= arr_->end()); 87   pos <= arr_->end());
HITCBC 88   74 if( n_ <= arr_->capacity() - 88   74 if( n_ <= arr_->capacity() -
HITCBC 89   37 arr_->size()) 89   37 arr_->size())
90   { 90   {
91   // fast path 91   // fast path
HITCBC 92   2 p = arr_->data() + i_; 92   2 p = arr_->data() + i_;
HITCBC 93   2 if(n_ == 0) 93   2 if(n_ == 0)
HITCBC 94   1 return; 94   1 return;
HITCBC 95   1 relocate( 95   1 relocate(
HITCBC 96   1 p + n_, 96   1 p + n_,
97   p, 97   p,
HITCBC 98   1 arr_->size() - i_); 98   1 arr_->size() - i_);
HITCBC 99   1 arr_->t_->size = static_cast< 99   1 arr_->t_->size = static_cast<
100   std::uint32_t>( 100   std::uint32_t>(
HITCBC 101   1 arr_->t_->size + n_); 101   1 arr_->t_->size + n_);
HITCBC 102   1 return; 102   1 return;
103   } 103   }
HITCBC 104   35 if(n_ > max_size() - arr_->size()) 104   35 if(n_ > max_size() - arr_->size())
105   { 105   {
106   BOOST_STATIC_CONSTEXPR source_location loc = BOOST_CURRENT_LOCATION; 106   BOOST_STATIC_CONSTEXPR source_location loc = BOOST_CURRENT_LOCATION;
HITCBC 107   1 detail::throw_system_error( error::array_too_large, &loc ); 107   1 detail::throw_system_error( error::array_too_large, &loc );
108   } 108   }
HITCBC 109   34 auto t = table::allocate( 109   34 auto t = table::allocate(
HITCBC 110   34 arr_->growth(arr_->size() + n_), 110   34 arr_->growth(arr_->size() + n_),
HITCBC 111   34 arr_->sp_); 111   34 arr_->sp_);
HITCBC 112   24 t->size = static_cast<std::uint32_t>( 112   24 t->size = static_cast<std::uint32_t>(
HITCBC 113   24 arr_->size() + n_); 113   24 arr_->size() + n_);
HITCBC 114   24 p = &(*t)[0] + i_; 114   24 p = &(*t)[0] + i_;
HITCBC 115   24 relocate( 115   24 relocate(
HITCBC 116   24 &(*t)[0], 116   24 &(*t)[0],
HITCBC 117   24 arr_->data(), 117   24 arr_->data(),
HITCBC 118   24 i_); 118   24 i_);
HITCBC 119   24 relocate( 119   24 relocate(
HITCBC 120   24 &(*t)[i_ + n_], 120   24 &(*t)[i_ + n_],
HITCBC 121   24 arr_->data() + i_, 121   24 arr_->data() + i_,
HITCBC 122   24 arr_->size() - i_); 122   24 arr_->size() - i_);
HITCBC 123   24 t = detail::exchange(arr_->t_, t); 123   24 t = detail::exchange(arr_->t_, t);
HITCBC 124   24 table::deallocate(t, arr_->sp_); 124   24 table::deallocate(t, arr_->sp_);
125   } 125   }
126   126  
HITCBC 127   26 array:: 127   26 array::
128   revert_insert:: 128   revert_insert::
HITCBC 129   8 ~revert_insert() 129   8 ~revert_insert()
130   { 130   {
HITCBC 131   26 if(! arr_) 131   26 if(! arr_)
HITCBC 132   18 return; 132   18 return;
HITCBC 133   8 BOOST_ASSERT(n_ != 0); 133   8 BOOST_ASSERT(n_ != 0);
134   auto const pos = 134   auto const pos =
HITCBC 135   8 arr_->data() + i_; 135   8 arr_->data() + i_;
HITCBC 136   8 arr_->destroy(pos, p); 136   8 arr_->destroy(pos, p);
HITCBC 137   8 arr_->t_->size = static_cast< 137   8 arr_->t_->size = static_cast<
138   std::uint32_t>( 138   std::uint32_t>(
HITCBC 139   8 arr_->t_->size - n_); 139   8 arr_->t_->size - n_);
HITCBC 140   8 relocate( 140   8 relocate(
141   pos, 141   pos,
HITCBC 142   8 pos + n_, 142   8 pos + n_,
HITCBC 143   8 arr_->size() - i_); 143   8 arr_->size() - i_);
HITCBC 144   26 } 144   26 }
145   145  
146   //---------------------------------------------------------- 146   //----------------------------------------------------------
147   147  
148   void 148   void
HITCBC 149   25 array:: 149   25 array::
150   destroy( 150   destroy(
151   value* first, value* last) noexcept 151   value* first, value* last) noexcept
152   { 152   {
HITCBC 153   25 if(sp_.is_not_shared_and_deallocate_is_trivial()) 153   25 if(sp_.is_not_shared_and_deallocate_is_trivial())
HITCBC 154   1 return; 154   1 return;
HITCBC 155   50 while(last-- != first) 155   50 while(last-- != first)
HITCBC 156   26 last->~value(); 156   26 last->~value();
157   } 157   }
158   158  
159   void 159   void
HITCBC 160   3699 array:: 160   3699 array::
161   destroy() noexcept 161   destroy() noexcept
162   { 162   {
HITCBC 163   3699 if(sp_.is_not_shared_and_deallocate_is_trivial()) 163   3699 if(sp_.is_not_shared_and_deallocate_is_trivial())
HITCBC 164   5 return; 164   5 return;
HITCBC 165   3694 auto last = end(); 165   3694 auto last = end();
HITCBC 166   3694 auto const first = begin(); 166   3694 auto const first = begin();
HITCBC 167   20870 while(last-- != first) 167   20870 while(last-- != first)
HITCBC 168   17176 last->~value(); 168   17176 last->~value();
HITCBC 169   3694 table::deallocate(t_, sp_); 169   3694 table::deallocate(t_, sp_);
170   } 170   }
171   171  
172   //---------------------------------------------------------- 172   //----------------------------------------------------------
173   // 173   //
174   // Special Members 174   // Special Members
175   // 175   //
176   //---------------------------------------------------------- 176   //----------------------------------------------------------
177   177  
HITCBC 178   2120 array:: 178   2120 array::
HITCBC 179   2120 array(detail::unchecked_array&& ua) 179   2120 array(detail::unchecked_array&& ua)
HITCBC 180   2120 : sp_(ua.storage()) 180   2120 : sp_(ua.storage())
181   { 181   {
182   BOOST_CORE_STATIC_ASSERT( alignof(table) == alignof(value) ); 182   BOOST_CORE_STATIC_ASSERT( alignof(table) == alignof(value) );
HITCBC 183   2120 if(ua.size() == 0) 183   2120 if(ua.size() == 0)
184   { 184   {
HITCBC 185   819 t_ = &empty_; 185   819 t_ = &empty_;
HITCBC 186   819 return; 186   819 return;
187   } 187   }
HITCBC 188   1301 t_= table::allocate( 188   1301 t_= table::allocate(
HITCBC 189   1301 ua.size(), sp_); 189   1301 ua.size(), sp_);
HITCBC 190   1263 t_->size = static_cast< 190   1263 t_->size = static_cast<
HITCBC 191   1263 std::uint32_t>(ua.size()); 191   1263 std::uint32_t>(ua.size());
HITCBC 192   1263 ua.relocate(data()); 192   1263 ua.relocate(data());
HITCBC 193   38 } 193   38 }
194   194  
HITCBC 195   3635 array:: 195   3635 array::
196   ~array() noexcept 196   ~array() noexcept
197   { 197   {
HITCBC 198   3635 destroy(); 198   3635 destroy();
HITCBC 199   3635 } 199   3635 }
200   200  
HITCBC 201   35 array:: 201   35 array::
202   array( 202   array(
203   std::size_t count, 203   std::size_t count,
204   value const& v, 204   value const& v,
HITCBC 205   35 storage_ptr sp) 205   35 storage_ptr sp)
HITCBC 206   35 : sp_(std::move(sp)) 206   35 : sp_(std::move(sp))
207   { 207   {
HITCBC 208   35 if(count == 0) 208   35 if(count == 0)
209   { 209   {
HITCBC 210   1 t_ = &empty_; 210   1 t_ = &empty_;
HITCBC 211   1 return; 211   1 return;
212   } 212   }
HITCBC 213   63 t_= table::allocate( 213   63 t_= table::allocate(
HITCBC 214   34 count, sp_); 214   34 count, sp_);
HITCBC 215   29 t_->size = 0; 215   29 t_->size = 0;
HITCBC 216   29 revert_construct r(*this); 216   29 revert_construct r(*this);
HITCBC 217   98 while(count--) 217   98 while(count--)
218   { 218   {
HITCBC 219   101 ::new(end()) value(v, sp_); 219   101 ::new(end()) value(v, sp_);
HITCBC 220   69 ++t_->size; 220   69 ++t_->size;
221   } 221   }
HITCBC 222   13 r.commit(); 222   13 r.commit();
HITCBC 223   50 } 223   50 }
224   224  
HITCBC 225   16 array:: 225   16 array::
226   array( 226   array(
227   std::size_t count, 227   std::size_t count,
HITCBC 228   16 storage_ptr sp) 228   16 storage_ptr sp)
HITCBC 229   16 : sp_(std::move(sp)) 229   16 : sp_(std::move(sp))
230   { 230   {
HITCBC 231   16 if(count == 0) 231   16 if(count == 0)
232   { 232   {
HITCBC 233   1 t_ = &empty_; 233   1 t_ = &empty_;
HITCBC 234   1 return; 234   1 return;
235   } 235   }
HITCBC 236   26 t_ = table::allocate( 236   26 t_ = table::allocate(
HITCBC 237   15 count, sp_); 237   15 count, sp_);
HITCBC 238   11 t_->size = static_cast< 238   11 t_->size = static_cast<
239   std::uint32_t>(count); 239   std::uint32_t>(count);
HITCBC 240   11 auto p = data(); 240   11 auto p = data();
241   do 241   do
242   { 242   {
HITCBC 243   34 ::new(p++) value(sp_); 243   34 ::new(p++) value(sp_);
244   } 244   }
HITCBC 245   34 while(--count); 245   34 while(--count);
HITCBC 246   4 } 246   4 }
247   247  
HITCBC 248   8 array:: 248   8 array::
HITCBC 249   8 array(array const& other) 249   8 array(array const& other)
HITCBC 250   8 : array(other, other.sp_) 250   8 : array(other, other.sp_)
251   { 251   {
HITCBC 252   8 } 252   8 }
253   253  
HITCBC 254   153 array:: 254   153 array::
255   array( 255   array(
256   array const& other, 256   array const& other,
HITCBC 257   153 storage_ptr sp) 257   153 storage_ptr sp)
HITCBC 258   153 : sp_(std::move(sp)) 258   153 : sp_(std::move(sp))
259   { 259   {
HITCBC 260   153 if(other.empty()) 260   153 if(other.empty())
261   { 261   {
HITCBC 262   14 t_ = &empty_; 262   14 t_ = &empty_;
HITCBC 263   14 return; 263   14 return;
264   } 264   }
HITCBC 265   139 t_ = table::allocate( 265   139 t_ = table::allocate(
HITCBC 266   139 other.size(), sp_); 266   139 other.size(), sp_);
HITCBC 267   120 t_->size = 0; 267   120 t_->size = 0;
HITCBC 268   120 revert_construct r(*this); 268   120 revert_construct r(*this);
HITCBC 269   120 auto src = other.data(); 269   120 auto src = other.data();
HITCBC 270   120 auto dest = data(); 270   120 auto dest = data();
HITCBC 271   120 auto const n = other.size(); 271   120 auto const n = other.size();
272   do 272   do
273   { 273   {
HITCBC 274   13 ::new(dest++) value( 274   13 ::new(dest++) value(
HITCBC 275   2412 *src++, sp_); 275   2412 *src++, sp_);
HITCBC 276   2373 ++t_->size; 276   2373 ++t_->size;
277   } 277   }
HITCBC 278   2373 while(t_->size < n); 278   2373 while(t_->size < n);
HITCBC 279   107 r.commit(); 279   107 r.commit();
HITCBC 280   152 } 280   152 }
281   281  
HITCBC 282   265 array:: 282   265 array::
283   array( 283   array(
284   array&& other, 284   array&& other,
HITCBC 285   265 storage_ptr sp) 285   265 storage_ptr sp)
HITCBC 286   265 : sp_(std::move(sp)) 286   265 : sp_(std::move(sp))
287   { 287   {
HITCBC 288   265 if(*sp_ == *other.sp_) 288   265 if(*sp_ == *other.sp_)
289   { 289   {
290   // same resource 290   // same resource
HITCBC 291   484 t_ = detail::exchange( 291   484 t_ = detail::exchange(
HITCBC 292   242 other.t_, &empty_); 292   242 other.t_, &empty_);
HITCBC 293   246 return; 293   246 return;
294   } 294   }
HITCBC 295   23 else if(other.empty()) 295   23 else if(other.empty())
296   { 296   {
HITCBC 297   4 t_ = &empty_; 297   4 t_ = &empty_;
HITCBC 298   4 return; 298   4 return;
299   } 299   }
300   // copy 300   // copy
HITCBC 301   19 t_ = table::allocate( 301   19 t_ = table::allocate(
HITCBC 302   19 other.size(), sp_); 302   19 other.size(), sp_);
HITCBC 303   14 t_->size = 0; 303   14 t_->size = 0;
HITCBC 304   14 revert_construct r(*this); 304   14 revert_construct r(*this);
HITCBC 305   14 auto src = other.data(); 305   14 auto src = other.data();
HITCBC 306   14 auto dest = data(); 306   14 auto dest = data();
HITCBC 307   14 auto const n = other.size(); 307   14 auto const n = other.size();
308   do 308   do
309   { 309   {
HITCBC 310   6 ::new(dest++) value( 310   6 ::new(dest++) value(
HITCBC 311   48 *src++, sp_); 311   48 *src++, sp_);
HITCBC 312   30 ++t_->size; 312   30 ++t_->size;
313   } 313   }
HITCBC 314   30 while(t_->size < n); 314   30 while(t_->size < n);
HITCBC 315   8 r.commit(); 315   8 r.commit();
HITCBC 316   25 } 316   25 }
317   317  
HITCBC 318   247 array:: 318   247 array::
319   array( 319   array(
320   std::initializer_list< 320   std::initializer_list<
321   value_ref> init, 321   value_ref> init,
HITCBC 322   247 storage_ptr sp) 322   247 storage_ptr sp)
HITCBC 323   247 : sp_(std::move(sp)) 323   247 : sp_(std::move(sp))
324   { 324   {
HITCBC 325   247 if(init.size() == 0) 325   247 if(init.size() == 0)
326   { 326   {
HITCBC 327   5 t_ = &empty_; 327   5 t_ = &empty_;
HITCBC 328   5 return; 328   5 return;
329   } 329   }
HITCBC 330   242 t_ = table::allocate( 330   242 t_ = table::allocate(
HITCBC 331   242 init.size(), sp_); 331   242 init.size(), sp_);
HITCBC 332   215 t_->size = 0; 332   215 t_->size = 0;
HITCBC 333   215 revert_construct r(*this); 333   215 revert_construct r(*this);
HITCBC 334   215 value_ref::write_array( 334   215 value_ref::write_array(
HITCBC 335   215 data(), init, sp_); 335   215 data(), init, sp_);
HITCBC 336   200 t_->size = static_cast< 336   200 t_->size = static_cast<
HITCBC 337   200 std::uint32_t>(init.size()); 337   200 std::uint32_t>(init.size());
HITCBC 338   200 r.commit(); 338   200 r.commit();
HITCBC 339   257 } 339   257 }
340   340  
341   //---------------------------------------------------------- 341   //----------------------------------------------------------
342   342  
343   array& 343   array&
HITCBC 344   16 array:: 344   16 array::
345   operator=(array const& other) 345   operator=(array const& other)
346   { 346   {
HITCBC 347   32 array(other, 347   32 array(other,
HITCBC 348   12 storage()).swap(*this); 348   12 storage()).swap(*this);
HITCBC 349   12 return *this; 349   12 return *this;
350   } 350   }
351   351  
352   array& 352   array&
HITCBC 353   7 array:: 353   7 array::
354   operator=(array&& other) 354   operator=(array&& other)
355   { 355   {
HITCBC 356   14 array(std::move(other), 356   14 array(std::move(other),
HITCBC 357   5 storage()).swap(*this); 357   5 storage()).swap(*this);
HITCBC 358   5 return *this; 358   5 return *this;
359   } 359   }
360   360  
361   array& 361   array&
HITCBC 362   9 array:: 362   9 array::
363   operator=( 363   operator=(
364   std::initializer_list<value_ref> init) 364   std::initializer_list<value_ref> init)
365   { 365   {
HITCBC 366   18 array(init, 366   18 array(init,
HITCBC 367   5 storage()).swap(*this); 367   5 storage()).swap(*this);
HITCBC 368   5 return *this; 368   5 return *this;
369   } 369   }
370   370  
371   //---------------------------------------------------------- 371   //----------------------------------------------------------
372   // 372   //
373   // Element access 373   // Element access
374   // 374   //
375   //---------------------------------------------------------- 375   //----------------------------------------------------------
376   376  
377   system::result<value&> 377   system::result<value&>
HITCBC 378   12 array::try_at(std::size_t pos) noexcept 378   12 array::try_at(std::size_t pos) noexcept
379   { 379   {
HITCBC 380   12 if(pos >= t_->size) 380   12 if(pos >= t_->size)
381   { 381   {
HITCBC 382   8 system::error_code ec; 382   8 system::error_code ec;
HITCBC 383   8 BOOST_JSON_FAIL(ec, error::out_of_range); 383   8 BOOST_JSON_FAIL(ec, error::out_of_range);
HITCBC 384   8 return ec; 384   8 return ec;
385   } 385   }
HITCBC 386   4 return (*t_)[pos]; 386   4 return (*t_)[pos];
387   } 387   }
388   388  
389   system::result<value const&> 389   system::result<value const&>
HITCBC 390   106 array::try_at(std::size_t pos) const noexcept 390   106 array::try_at(std::size_t pos) const noexcept
391   { 391   {
HITCBC 392   106 if(pos >= t_->size) 392   106 if(pos >= t_->size)
393   { 393   {
HITCBC 394   12 system::error_code ec; 394   12 system::error_code ec;
HITCBC 395   12 BOOST_JSON_FAIL(ec, error::out_of_range); 395   12 BOOST_JSON_FAIL(ec, error::out_of_range);
HITCBC 396   12 return ec; 396   12 return ec;
397   } 397   }
HITCBC 398   94 return (*t_)[pos]; 398   94 return (*t_)[pos];
399   } 399   }
400   400  
401   value const& 401   value const&
HITCBC 402   100 array:: 402   100 array::
403   array::at(std::size_t pos, source_location const& loc) const& 403   array::at(std::size_t pos, source_location const& loc) const&
404   { 404   {
HITCBC 405   100 return try_at(pos).value(loc); 405   100 return try_at(pos).value(loc);
406   } 406   }
407   407  
408   //---------------------------------------------------------- 408   //----------------------------------------------------------
409   // 409   //
410   // Capacity 410   // Capacity
411   // 411   //
412   //---------------------------------------------------------- 412   //----------------------------------------------------------
413   413  
414   void 414   void
HITCBC 415   6 array:: 415   6 array::
416   shrink_to_fit() noexcept 416   shrink_to_fit() noexcept
417   { 417   {
HITCBC 418   6 if(capacity() <= size()) 418   6 if(capacity() <= size())
HITCBC 419   2 return; 419   2 return;
HITCBC 420   4 if(size() == 0) 420   4 if(size() == 0)
421   { 421   {
HITCBC 422   1 table::deallocate(t_, sp_); 422   1 table::deallocate(t_, sp_);
HITCBC 423   1 t_ = &empty_; 423   1 t_ = &empty_;
HITCBC 424   1 return; 424   1 return;
425   } 425   }
426   426  
427   #ifndef BOOST_NO_EXCEPTIONS 427   #ifndef BOOST_NO_EXCEPTIONS
428   try 428   try
429   { 429   {
430   #endif 430   #endif
HITCBC 431   3 auto t = table::allocate( 431   3 auto t = table::allocate(
HITCBC 432   3 size(), sp_); 432   3 size(), sp_);
HITCBC 433   4 relocate( 433   4 relocate(
HITCBC 434   2 &(*t)[0], 434   2 &(*t)[0],
435   data(), 435   data(),
436   size()); 436   size());
HITCBC 437   2 t->size = static_cast< 437   2 t->size = static_cast<
HITCBC 438   2 std::uint32_t>(size()); 438   2 std::uint32_t>(size());
HITCBC 439   2 t = detail::exchange( 439   2 t = detail::exchange(
HITCBC 440   2 t_, t); 440   2 t_, t);
HITCBC 441   2 table::deallocate(t, sp_); 441   2 table::deallocate(t, sp_);
442   #ifndef BOOST_NO_EXCEPTIONS 442   #ifndef BOOST_NO_EXCEPTIONS
443   } 443   }
HITCBC 444   1 catch(...) 444   1 catch(...)
445   { 445   {
446   // eat the exception 446   // eat the exception
HITCBC 447   1 return; 447   1 return;
HITCBC 448   1 } 448   1 }
449   #endif 449   #endif
450   } 450   }
451   451  
452   //---------------------------------------------------------- 452   //----------------------------------------------------------
453   // 453   //
454   // Modifiers 454   // Modifiers
455   // 455   //
456   //---------------------------------------------------------- 456   //----------------------------------------------------------
457   457  
458   void 458   void
HITCBC 459   4 array:: 459   4 array::
460   clear() noexcept 460   clear() noexcept
461   { 461   {
HITCBC 462   4 if(size() == 0) 462   4 if(size() == 0)
HITCBC 463   1 return; 463   1 return;
HITCBC 464   3 destroy( 464   3 destroy(
465   begin(), end()); 465   begin(), end());
HITCBC 466   3 t_->size = 0; 466   3 t_->size = 0;
467   } 467   }
468   468  
469   auto 469   auto
HITCBC 470   3 array:: 470   3 array::
471   insert( 471   insert(
472   const_iterator pos, 472   const_iterator pos,
473   value const& v) -> 473   value const& v) ->
474   iterator 474   iterator
475   { 475   {
HITCBC 476   3 return emplace(pos, v); 476   3 return emplace(pos, v);
477   } 477   }
478   478  
479   auto 479   auto
HITCBC 480   3 array:: 480   3 array::
481   insert( 481   insert(
482   const_iterator pos, 482   const_iterator pos,
483   value&& v) -> 483   value&& v) ->
484   iterator 484   iterator
485   { 485   {
HITCBC 486   3 return emplace(pos, std::move(v)); 486   3 return emplace(pos, std::move(v));
487   } 487   }
488   488  
489   auto 489   auto
HITCBC 490   10 array:: 490   10 array::
491   insert( 491   insert(
492   const_iterator pos, 492   const_iterator pos,
493   std::size_t count, 493   std::size_t count,
494   value const& v) -> 494   value const& v) ->
495   iterator 495   iterator
496   { 496   {
497   revert_insert r( 497   revert_insert r(
HITCBC 498   10 pos, count, *this); 498   10 pos, count, *this);
HITCBC 499   17 while(count--) 499   17 while(count--)
500   { 500   {
HITCBC 501   16 ::new(r.p) value(v, sp_); 501   16 ::new(r.p) value(v, sp_);
HITCBC 502   10 ++r.p; 502   10 ++r.p;
503   } 503   }
HITCBC 504   8 return r.commit(); 504   8 return r.commit();
HITCBC 505   7 } 505   7 }
506   506  
507   auto 507   auto
HITCBC 508   3 array:: 508   3 array::
509   insert( 509   insert(
510   const_iterator pos, 510   const_iterator pos,
511   std::initializer_list< 511   std::initializer_list<
512   value_ref> init) -> 512   value_ref> init) ->
513   iterator 513   iterator
514   { 514   {
515   revert_insert r( 515   revert_insert r(
HITCBC 516   3 pos, init.size(), *this); 516   3 pos, init.size(), *this);
HITCBC 517   2 value_ref::write_array( 517   2 value_ref::write_array(
HITCBC 518   2 r.p, init, sp_); 518   2 r.p, init, sp_);
HITCBC 519   2 return r.commit(); 519   2 return r.commit();
HITCBC 520   2 } 520   2 }
521   521  
522   auto 522   auto
HITCBC 523   7 array:: 523   7 array::
524   erase( 524   erase(
525   const_iterator pos) noexcept -> 525   const_iterator pos) noexcept ->
526   iterator 526   iterator
527   { 527   {
HITCBC 528   7 BOOST_ASSERT( 528   7 BOOST_ASSERT(
529   pos >= begin() && 529   pos >= begin() &&
530   pos <= end()); 530   pos <= end());
HITCBC 531   7 return erase(pos, pos + 1); 531   7 return erase(pos, pos + 1);
532   } 532   }
533   533  
534   auto 534   auto
HITCBC 535   8 array:: 535   8 array::
536   erase( 536   erase(
537   const_iterator first, 537   const_iterator first,
538   const_iterator last) noexcept -> 538   const_iterator last) noexcept ->
539   iterator 539   iterator
540   { 540   {
HITCBC 541   8 BOOST_ASSERT( 541   8 BOOST_ASSERT(
542   first >= begin() && 542   first >= begin() &&
543   last >= first && 543   last >= first &&
544   last <= end()); 544   last <= end());
HITCBC 545   8 std::size_t const n = 545   8 std::size_t const n =
HITCBC 546   8 last - first; 546   8 last - first;
HITCBC 547   8 auto const p = &(*t_)[0] + 547   8 auto const p = &(*t_)[0] +
HITCBC 548   8 (first - &(*t_)[0]); 548   8 (first - &(*t_)[0]);
HITCBC 549   8 destroy(p, p + n); 549   8 destroy(p, p + n);
HITCBC 550   8 relocate(p, p + n, 550   8 relocate(p, p + n,
HITCBC 551   8 t_->size - (last - 551   8 t_->size - (last -
HITCBC 552   8 &(*t_)[0])); 552   8 &(*t_)[0]));
HITCBC 553   8 t_->size = static_cast< 553   8 t_->size = static_cast<
HITCBC 554   8 std::uint32_t>(t_->size - n); 554   8 std::uint32_t>(t_->size - n);
HITCBC 555   8 return p; 555   8 return p;
556   } 556   }
557   557  
558   void 558   void
HITCBC 559   4 array:: 559   4 array::
560   push_back(value const& v) 560   push_back(value const& v)
561   { 561   {
HITCBC 562   4 emplace_back(v); 562   4 emplace_back(v);
HITCBC 563   2 } 563   2 }
564   564  
565   void 565   void
HITCBC 566   9 array:: 566   9 array::
567   push_back(value&& v) 567   push_back(value&& v)
568   { 568   {
HITCBC 569   9 emplace_back(std::move(v)); 569   9 emplace_back(std::move(v));
HITCBC 570   7 } 570   7 }
571   571  
572   void 572   void
HITCBC 573   3 array:: 573   3 array::
574   pop_back() noexcept 574   pop_back() noexcept
575   { 575   {
HITCBC 576   3 auto const p = &back(); 576   3 auto const p = &back();
HITCBC 577   3 destroy(p, p + 1); 577   3 destroy(p, p + 1);
HITCBC 578   3 --t_->size; 578   3 --t_->size;
HITCBC 579   3 } 579   3 }
580   580  
581   void 581   void
HITCBC 582   15 array:: 582   15 array::
583   resize(std::size_t count) 583   resize(std::size_t count)
584   { 584   {
HITCBC 585   15 if(count <= t_->size) 585   15 if(count <= t_->size)
586   { 586   {
587   // shrink 587   // shrink
HITCBC 588   4 destroy( 588   4 destroy(
HITCBC 589   2 &(*t_)[0] + count, 589   2 &(*t_)[0] + count,
HITCBC 590   2 &(*t_)[0] + t_->size); 590   2 &(*t_)[0] + t_->size);
HITCBC 591   2 t_->size = static_cast< 591   2 t_->size = static_cast<
592   std::uint32_t>(count); 592   std::uint32_t>(count);
HITCBC 593   2 return; 593   2 return;
594   } 594   }
595   595  
HITCBC 596   13 reserve(count); 596   13 reserve(count);
HITCBC 597   12 auto p = &(*t_)[t_->size]; 597   12 auto p = &(*t_)[t_->size];
HITCBC 598   12 auto const end = &(*t_)[count]; 598   12 auto const end = &(*t_)[count];
HITCBC 599   32 while(p != end) 599   32 while(p != end)
HITCBC 600   20 ::new(p++) value(sp_); 600   20 ::new(p++) value(sp_);
HITCBC 601   12 t_->size = static_cast< 601   12 t_->size = static_cast<
602   std::uint32_t>(count); 602   std::uint32_t>(count);
603   } 603   }
604   604  
605   void 605   void
HITCBC 606   7 array:: 606   7 array::
607   resize( 607   resize(
608   std::size_t count, 608   std::size_t count,
609   value const& v) 609   value const& v)
610   { 610   {
HITCBC 611   7 if(count <= size()) 611   7 if(count <= size())
612   { 612   {
613   // shrink 613   // shrink
HITCBC 614   2 destroy( 614   2 destroy(
HITCBC 615   1 data() + count, 615   1 data() + count,
HITCBC 616   1 data() + size()); 616   1 data() + size());
HITCBC 617   1 t_->size = static_cast< 617   1 t_->size = static_cast<
618   std::uint32_t>(count); 618   std::uint32_t>(count);
HITCBC 619   1 return; 619   1 return;
620   } 620   }
HITCBC 621   6 count -= size(); 621   6 count -= size();
622   revert_insert r( 622   revert_insert r(
HITCBC 623   6 end(), count, *this); 623   6 end(), count, *this);
HITCBC 624   9 while(count--) 624   9 while(count--)
625   { 625   {
HITCBC 626   12 ::new(r.p) value(v, sp_); 626   12 ::new(r.p) value(v, sp_);
HITCBC 627   4 ++r.p; 627   4 ++r.p;
628   } 628   }
HITCBC 629   1 r.commit(); 629   1 r.commit();
HITCBC 630   5 } 630   5 }
631   631  
632   void 632   void
HITCBC 633   28 array:: 633   28 array::
634   swap(array& other) 634   swap(array& other)
635   { 635   {
HITCBC 636   28 if(*sp_ == *other.sp_) 636   28 if(*sp_ == *other.sp_)
637   { 637   {
HITCBC 638   48 t_ = detail::exchange( 638   48 t_ = detail::exchange(
HITCBC 639   24 other.t_, t_); 639   24 other.t_, t_);
HITCBC 640   24 return; 640   24 return;
641   } 641   }
642   array temp1( 642   array temp1(
HITCBC 643   4 std::move(*this), 643   4 std::move(*this),
HITCBC 644   9 other.storage()); 644   9 other.storage());
645   array temp2( 645   array temp2(
HITCBC 646   3 std::move(other), 646   3 std::move(other),
HITCBC 647   7 this->storage()); 647   7 this->storage());
HITCBC 648   2 this->~array(); 648   2 this->~array();
HITCBC 649   6 ::new(this) array( 649   6 ::new(this) array(
HITCBC 650   2 pilfer(temp2)); 650   2 pilfer(temp2));
HITCBC 651   2 other.~array(); 651   2 other.~array();
HITCBC 652   6 ::new(&other) array( 652   6 ::new(&other) array(
HITCBC 653   2 pilfer(temp1)); 653   2 pilfer(temp1));
HITCBC 654   3 } 654   3 }
655   655  
656   //---------------------------------------------------------- 656   //----------------------------------------------------------
657   // 657   //
658   // Private 658   // Private
659   // 659   //
660   //---------------------------------------------------------- 660   //----------------------------------------------------------
661   661  
662   std::size_t 662   std::size_t
HITCBC 663   786 array:: 663   786 array::
664   growth( 664   growth(
665   std::size_t new_size) const 665   std::size_t new_size) const
666   { 666   {
HITCBC 667   786 if(new_size > max_size()) 667   786 if(new_size > max_size())
668   { 668   {
669   BOOST_STATIC_CONSTEXPR source_location loc = BOOST_CURRENT_LOCATION; 669   BOOST_STATIC_CONSTEXPR source_location loc = BOOST_CURRENT_LOCATION;
HITCBC 670   1 detail::throw_system_error( error::array_too_large, &loc ); 670   1 detail::throw_system_error( error::array_too_large, &loc );
671   } 671   }
HITCBC 672   785 std::size_t const old = capacity(); 672   785 std::size_t const old = capacity();
HITCBC 673   785 if(old > max_size() - old / 2) 673   785 if(old > max_size() - old / 2)
HITCBC 674   1 return new_size; 674   1 return new_size;
HITCBC 675   784 std::size_t const g = 675   784 std::size_t const g =
HITCBC 676   784 old + old / 2; // 1.5x 676   784 old + old / 2; // 1.5x
HITCBC 677   784 if(g < new_size) 677   784 if(g < new_size)
HITCBC 678   704 return new_size; 678   704 return new_size;
HITCBC 679   80 return g; 679   80 return g;
680   } 680   }
681   681  
682   // precondition: new_capacity > capacity() 682   // precondition: new_capacity > capacity()
683   void 683   void
HITCBC 684   674 array:: 684   674 array::
685   reserve_impl( 685   reserve_impl(
686   std::size_t new_capacity) 686   std::size_t new_capacity)
687   { 687   {
HITCBC 688   674 BOOST_ASSERT( 688   674 BOOST_ASSERT(
689   new_capacity > t_->capacity); 689   new_capacity > t_->capacity);
HITCBC 690   673 auto t = table::allocate( 690   673 auto t = table::allocate(
HITCBC 691   674 growth(new_capacity), sp_); 691   674 growth(new_capacity), sp_);
HITCBC 692   653 relocate( 692   653 relocate(
HITCBC 693   653 &(*t)[0], 693   653 &(*t)[0],
HITCBC 694   653 &(*t_)[0], 694   653 &(*t_)[0],
HITCBC 695   653 t_->size); 695   653 t_->size);
HITCBC 696   653 t->size = t_->size; 696   653 t->size = t_->size;
HITCBC 697   653 t = detail::exchange(t_, t); 697   653 t = detail::exchange(t_, t);
HITCBC 698   653 table::deallocate(t, sp_); 698   653 table::deallocate(t, sp_);
HITCBC 699   653 } 699   653 }
700   700  
701   // precondition: pv is not aliased 701   // precondition: pv is not aliased
702   value& 702   value&
HITCBC 703   7604 array:: 703   7604 array::
704   push_back( 704   push_back(
705   pilfered<value> pv) 705   pilfered<value> pv)
706   { 706   {
HITCBC 707   7604 auto const n = t_->size; 707   7604 auto const n = t_->size;
HITCBC 708   7604 if(n < t_->capacity) 708   7604 if(n < t_->capacity)
709   { 709   {
710   // fast path 710   // fast path
711   auto& v = *::new( 711   auto& v = *::new(
HITCBC 712   7537 &(*t_)[n]) value(pv); 712   7537 &(*t_)[n]) value(pv);
HITCBC 713   7537 ++t_->size; 713   7537 ++t_->size;
HITCBC 714   7537 return v; 714   7537 return v;
715   } 715   }
716   auto const t = 716   auto const t =
HITCBC 717   67 detail::exchange(t_, 717   67 detail::exchange(t_,
718   table::allocate( 718   table::allocate(
HITCBC 719   67 growth(n + 1), 719   67 growth(n + 1),
HITCBC 720   67 sp_)); 720   67 sp_));
721   auto& v = *::new( 721   auto& v = *::new(
HITCBC 722   62 &(*t_)[n]) value(pv); 722   62 &(*t_)[n]) value(pv);
HITCBC 723   62 relocate( 723   62 relocate(
HITCBC 724   62 &(*t_)[0], 724   62 &(*t_)[0],
HITCBC 725   62 &(*t)[0], 725   62 &(*t)[0],
726   n); 726   n);
HITCBC 727   62 t_->size = n + 1; 727   62 t_->size = n + 1;
HITCBC 728   62 table::deallocate(t, sp_); 728   62 table::deallocate(t, sp_);
HITCBC 729   62 return v; 729   62 return v;
730   } 730   }
731   731  
732   // precondition: pv is not aliased 732   // precondition: pv is not aliased
733   auto 733   auto
HITCBC 734   12 array:: 734   12 array::
735   insert( 735   insert(
736   const_iterator pos, 736   const_iterator pos,
737   pilfered<value> pv) -> 737   pilfered<value> pv) ->
738   iterator 738   iterator
739   { 739   {
HITCBC 740   12 BOOST_ASSERT( 740   12 BOOST_ASSERT(
741   pos >= begin() && 741   pos >= begin() &&
742   pos <= end()); 742   pos <= end());
HITCBC 743   12 std::size_t const n = 743   12 std::size_t const n =
HITCBC 744   12 t_->size; 744   12 t_->size;
745   std::size_t const i = 745   std::size_t const i =
HITCBC 746   12 pos - &(*t_)[0]; 746   12 pos - &(*t_)[0];
HITCBC 747   12 if(n < t_->capacity) 747   12 if(n < t_->capacity)
748   { 748   {
749   // fast path 749   // fast path
750   auto const p = 750   auto const p =
HITCBC 751   1 &(*t_)[i]; 751   1 &(*t_)[i];
HITCBC 752   1 relocate( 752   1 relocate(
753   p + 1, 753   p + 1,
754   p, 754   p,
755   n - i); 755   n - i);
HITCBC 756   1 ::new(p) value(pv); 756   1 ::new(p) value(pv);
HITCBC 757   1 ++t_->size; 757   1 ++t_->size;
HITCBC 758   1 return p; 758   1 return p;
759   } 759   }
760   auto t = 760   auto t =
HITCBC 761   11 table::allocate( 761   11 table::allocate(
HITCBC 762   11 growth(n + 1), sp_); 762   11 growth(n + 1), sp_);
HITCBC 763   6 auto const p = &(*t)[i]; 763   6 auto const p = &(*t)[i];
HITCBC 764   6 ::new(p) value(pv); 764   6 ::new(p) value(pv);
HITCBC 765   6 relocate( 765   6 relocate(
HITCBC 766   6 &(*t)[0], 766   6 &(*t)[0],
HITCBC 767   6 &(*t_)[0], 767   6 &(*t_)[0],
768   i); 768   i);
HITCBC 769   6 relocate( 769   6 relocate(
770   p + 1, 770   p + 1,
HITCBC 771   6 &(*t_)[i], 771   6 &(*t_)[i],
772   n - i); 772   n - i);
HITCBC 773   6 t->size = static_cast< 773   6 t->size = static_cast<
HITCBC 774   6 std::uint32_t>(size() + 1); 774   6 std::uint32_t>(size() + 1);
HITCBC 775   6 t = detail::exchange(t_, t); 775   6 t = detail::exchange(t_, t);
HITCBC 776   6 table::deallocate(t, sp_); 776   6 table::deallocate(t, sp_);
HITCBC 777   6 return p; 777   6 return p;
778   } 778   }
779   779  
780   //---------------------------------------------------------- 780   //----------------------------------------------------------
781   781  
782   bool 782   bool
HITCBC 783   79 array:: 783   79 array::
784   equal( 784   equal(
785   array const& other) const noexcept 785   array const& other) const noexcept
786   { 786   {
HITCBC 787   79 if(size() != other.size()) 787   79 if(size() != other.size())
HITCBC 788   2 return false; 788   2 return false;
HITCBC 789   3250 for(std::size_t i = 0; i < size(); ++i) 789   3250 for(std::size_t i = 0; i < size(); ++i)
HITCBC 790   3179 if((*this)[i] != other[i]) 790   3179 if((*this)[i] != other[i])
HITCBC 791   6 return false; 791   6 return false;
HITCBC 792   71 return true; 792   71 return true;
793   } 793   }
794   794  
795   } // namespace json 795   } // namespace json
796   } // namespace boost 796   } // namespace boost
797   797  
798   //---------------------------------------------------------- 798   //----------------------------------------------------------
799   // 799   //
800   // std::hash specialization 800   // std::hash specialization
801   // 801   //
802   //---------------------------------------------------------- 802   //----------------------------------------------------------
803   803  
804   std::size_t 804   std::size_t
HITCBC 805   12 std::hash<::boost::json::array>::operator()( 805   12 std::hash<::boost::json::array>::operator()(
806   ::boost::json::array const& ja) const noexcept 806   ::boost::json::array const& ja) const noexcept
807   { 807   {
HITCBC 808   12 return ::boost::hash< ::boost::json::array >()( ja ); 808   12 return ::boost::hash< ::boost::json::array >()( ja );
809   } 809   }
810   810  
811   //---------------------------------------------------------- 811   //----------------------------------------------------------
812   812  
813   #endif 813   #endif