include/boost/json /impl /array.ipp
100.00% Lines (392/392) 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   2589 array:: 35   2602 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   2589 BOOST_ASSERT(capacity > 0); 42   2602 BOOST_ASSERT(capacity > 0);
HITCBC 43   2589 if(capacity > array::max_size()) 43   2602 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   2587 table*>(sp->allocate( 49   2600 table*>(sp->allocate(
50   sizeof(table) + 50   sizeof(table) +
HITCBC 51   2587 capacity * sizeof(value), 51   2600 capacity * sizeof(value),
52   alignof(value))); 52   alignof(value)));
HITCBC 53   2442 p->capacity = static_cast< 53   2451 p->capacity = static_cast<
54   std::uint32_t>(capacity); 54   std::uint32_t>(capacity);
HITCBC 55   2442 return p; 55   2451 return p;
56   } 56   }
57   57  
58   void 58   void
HITCBC 59   4483 array:: 59   4496 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   4483 if(p->capacity == 0) 65   4496 if(p->capacity == 0)
HITCBC 66   2045 return; 66   2049 return;
HITCBC 67   2438 sp->deallocate(p, 67   2447 sp->deallocate(p,
68   sizeof(table) + 68   sizeof(table) +
HITCBC 69   2438 p->capacity * sizeof(value), 69   2447 p->capacity * sizeof(value),
70   alignof(value)); 70   alignof(value));
71   } 71   }
72   72  
73   //---------------------------------------------------------- 73   //----------------------------------------------------------
74   74  
HITCBC 75   43 array:: 75   44 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   43 array& arr) 80   44 array& arr)
HITCBC 81   43 : arr_(&arr) 81   44 : arr_(&arr)
HITCBC 82   43 , i_(pos - arr_->data()) 82   44 , i_(pos - arr_->data())
HITCBC 83   43 , n_(n) 83   44 , n_(n)
84   { 84   {
HITCBC 85   43 BOOST_ASSERT( 85   44 BOOST_ASSERT(
86   pos >= arr_->begin() && 86   pos >= arr_->begin() &&
87   pos <= arr_->end()); 87   pos <= arr_->end());
HITCBC 88   86 if( n_ <= arr_->capacity() - 88   88 if( n_ <= arr_->capacity() -
HITCBC 89   43 arr_->size()) 89   44 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   41 if(n_ > max_size() - arr_->size()) 104   42 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   40 auto t = table::allocate( 109   41 auto t = table::allocate(
HITCBC 110   40 arr_->growth(arr_->size() + n_), 110   41 arr_->growth(arr_->size() + n_),
HITCBC 111   40 arr_->sp_); 111   41 arr_->sp_);
HITCBC 112   28 t->size = static_cast<std::uint32_t>( 112   28 t->size = static_cast<std::uint32_t>(
HITCBC 113   28 arr_->size() + n_); 113   28 arr_->size() + n_);
HITCBC 114   28 p = &(*t)[0] + i_; 114   28 p = &(*t)[0] + i_;
HITCBC 115   28 relocate( 115   28 relocate(
HITCBC 116   28 &(*t)[0], 116   28 &(*t)[0],
HITCBC 117   28 arr_->data(), 117   28 arr_->data(),
HITCBC 118   28 i_); 118   28 i_);
HITCBC 119   28 relocate( 119   28 relocate(
HITCBC 120   28 &(*t)[i_ + n_], 120   28 &(*t)[i_ + n_],
HITCBC 121   28 arr_->data() + i_, 121   28 arr_->data() + i_,
HITCBC 122   28 arr_->size() - i_); 122   28 arr_->size() - i_);
HITCBC 123   28 t = detail::exchange(arr_->t_, t); 123   28 t = detail::exchange(arr_->t_, t);
HITCBC 124   28 table::deallocate(t, arr_->sp_); 124   28 table::deallocate(t, arr_->sp_);
125   } 125   }
126   126  
HITCBC 127   30 array:: 127   30 array::
128   revert_insert:: 128   revert_insert::
HITCBC 129   10 ~revert_insert() 129   9 ~revert_insert()
130   { 130   {
HITCBC 131   30 if(! arr_) 131   30 if(! arr_)
HITCBC 132   20 return; 132   21 return;
HITCBC 133   10 BOOST_ASSERT(n_ != 0); 133   9 BOOST_ASSERT(n_ != 0);
134   auto const pos = 134   auto const pos =
HITCBC 135   10 arr_->data() + i_; 135   9 arr_->data() + i_;
HITCBC 136   10 arr_->destroy(pos, p); 136   9 arr_->destroy(pos, p);
HITCBC 137   10 arr_->t_->size = static_cast< 137   9 arr_->t_->size = static_cast<
138   std::uint32_t>( 138   std::uint32_t>(
HITCBC 139   10 arr_->t_->size - n_); 139   9 arr_->t_->size - n_);
HITCBC 140   10 relocate( 140   9 relocate(
141   pos, 141   pos,
HITCBC 142   10 pos + n_, 142   9 pos + n_,
HITCBC 143   10 arr_->size() - i_); 143   9 arr_->size() - i_);
HITCBC 144   30 } 144   30 }
145   145  
146   //---------------------------------------------------------- 146   //----------------------------------------------------------
147   147  
148   void 148   void
HITCBC 149   27 array:: 149   26 array::
150   destroy( 150   destroy(
151   value* first, value* last) noexcept 151   value* first, value* last) noexcept
152   { 152   {
HITCBC 153   27 if(sp_.is_not_shared_and_deallocate_is_trivial()) 153   26 if(sp_.is_not_shared_and_deallocate_is_trivial())
HITCBC 154   1 return; 154   1 return;
HITCBC 155   55 while(last-- != first) 155   54 while(last-- != first)
HITCBC 156   29 last->~value(); 156   29 last->~value();
157   } 157   }
158   158  
159   void 159   void
HITCBC 160   3731 array:: 160   3741 array::
161   destroy() noexcept 161   destroy() noexcept
162   { 162   {
HITCBC 163   3731 if(sp_.is_not_shared_and_deallocate_is_trivial()) 163   3741 if(sp_.is_not_shared_and_deallocate_is_trivial())
HITCBC 164   5 return; 164   5 return;
HITCBC 165   3726 auto last = end(); 165   3736 auto last = end();
HITCBC 166   3726 auto const first = begin(); 166   3736 auto const first = begin();
HITCBC 167   20996 while(last-- != first) 167   21027 while(last-- != first)
HITCBC 168   17270 last->~value(); 168   17291 last->~value();
HITCBC 169   3726 table::deallocate(t_, sp_); 169   3736 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   3666 array:: 195   3675 array::
196   ~array() noexcept 196   ~array() noexcept
197   { 197   {
HITCBC 198   3666 destroy(); 198   3675 destroy();
HITCBC 199   3666 } 199   3675 }
200   200  
HITCBC 201   37 array:: 201   37 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   37 storage_ptr sp) 205   37 storage_ptr sp)
HITCBC 206   37 : sp_(std::move(sp)) 206   37 : sp_(std::move(sp))
207   { 207   {
HITCBC 208   37 if(count == 0) 208   37 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   67 t_= table::allocate( 213   67 t_= table::allocate(
HITCBC 214   36 count, sp_); 214   36 count, sp_);
HITCBC 215   31 t_->size = 0; 215   31 t_->size = 0;
HITCBC 216   31 revert_construct r(*this); 216   31 revert_construct r(*this);
HITCBC 217   106 while(count--) 217   106 while(count--)
218   { 218   {
HITCBC 219   107 ::new(end()) value(v, sp_); 219   107 ::new(end()) value(v, sp_);
HITCBC 220   75 ++t_->size; 220   75 ++t_->size;
221   } 221   }
HITCBC 222   15 r.commit(); 222   15 r.commit();
HITCBC 223   52 } 223   52 }
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   173 array:: 254   173 array::
255   array( 255   array(
256   array const& other, 256   array const& other,
HITCBC 257   173 storage_ptr sp) 257   173 storage_ptr sp)
HITCBC 258   173 : sp_(std::move(sp)) 258   173 : sp_(std::move(sp))
259   { 259   {
HITCBC 260   173 if(other.empty()) 260   173 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   159 t_ = table::allocate( 265   159 t_ = table::allocate(
HITCBC 266   159 other.size(), sp_); 266   159 other.size(), sp_);
HITCBC 267   138 t_->size = 0; 267   138 t_->size = 0;
HITCBC 268   138 revert_construct r(*this); 268   138 revert_construct r(*this);
HITCBC 269   138 auto src = other.data(); 269   138 auto src = other.data();
HITCBC 270   138 auto dest = data(); 270   138 auto dest = data();
HITCBC 271   138 auto const n = other.size(); 271   138 auto const n = other.size();
272   do 272   do
273   { 273   {
HITCBC 274   14 ::new(dest++) value( 274   14 ::new(dest++) value(
HITCBC 275   2468 *src++, sp_); 275   2468 *src++, sp_);
HITCBC 276   2426 ++t_->size; 276   2426 ++t_->size;
277   } 277   }
HITCBC 278   2426 while(t_->size < n); 278   2426 while(t_->size < n);
HITCBC 279   124 r.commit(); 279   124 r.commit();
HITCBC 280   173 } 280   173 }
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   248 array:: 318   256 array::
319   array( 319   array(
320   std::initializer_list< 320   std::initializer_list<
321   value_ref> init, 321   value_ref> init,
HITCBC 322   248 storage_ptr sp) 322   256 storage_ptr sp)
HITCBC 323   248 : sp_(std::move(sp)) 323   256 : sp_(std::move(sp))
324   { 324   {
HITCBC 325   248 if(init.size() == 0) 325   256 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   243 t_ = table::allocate( 330   251 t_ = table::allocate(
HITCBC 331   243 init.size(), sp_); 331   251 init.size(), sp_);
HITCBC 332   216 t_->size = 0; 332   222 t_->size = 0;
HITCBC 333   216 revert_construct r(*this); 333   222 revert_construct r(*this);
HITCBC 334   216 value_ref::write_array( 334   222 value_ref::write_array(
HITCBC 335   216 data(), init, sp_); 335   222 data(), init, sp_);
HITCBC 336   201 t_->size = static_cast< 336   206 t_->size = static_cast<
HITCBC 337   201 std::uint32_t>(init.size()); 337   206 std::uint32_t>(init.size());
HITCBC 338   201 r.commit(); 338   206 r.commit();
HITCBC 339   258 } 339   267 }
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   13 array:: 490   13 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   // v may refer to an element of this array, whose 497   // v may refer to an element of this array, whose
498   // storage revert_insert can relocate and free, so 498   // storage revert_insert can relocate and free, so
499   // copy it before inserting 499   // copy it before inserting
HITCBC 500   14 value const tmp(v, sp_); 500   14 value const tmp(v, sp_);
501   revert_insert r( 501   revert_insert r(
HITCBC 502   12 pos, count, *this); 502   12 pos, count, *this);
HITCBC 503   24 while(count--) 503   24 while(count--)
504   { 504   {
HITCBC 505   22 ::new(r.p) value(tmp, sp_); 505   22 ::new(r.p) value(tmp, sp_);
HITCBC 506   16 ++r.p; 506   16 ++r.p;
507   } 507   }
HITCBC 508   10 return r.commit(); 508   10 return r.commit();
HITCBC 509   15 } 509   15 }
510   510  
511   auto 511   auto
HITCBC 512   3 array:: 512   7 array::
513   insert( 513   insert(
514   const_iterator pos, 514   const_iterator pos,
515   std::initializer_list< 515   std::initializer_list<
516   value_ref> init) -> 516   value_ref> init) ->
517   iterator 517   iterator
518   { 518   {
  519 + // the initializer_list elements may reference elements of this
  520 + // array, whose storage revert_insert can relocate and free, so
  521 + // materialise them into a temporary before inserting
HITGNC   522 + 10 array temp(init, sp_);
519   revert_insert r( 523   revert_insert r(
HITCBC 520 - 3 pos, init.size(), *this); 524 + 4 pos, temp.size(), *this);
HITCBC 521 - 2 value_ref::write_array( 525 + 2 relocate(
ECB 522 - 2 r.p, init, sp_); 526 + r.p,
  527 + temp.data(),
  528 + temp.size());
HITGNC   529 + 2 temp.t_->size = 0;
HITCBC 523   2 return r.commit(); 530   4 return r.commit();
HITCBC 524   2 } 531   4 }
525   532  
526   auto 533   auto
HITCBC 527   7 array:: 534   7 array::
528   erase( 535   erase(
529   const_iterator pos) noexcept -> 536   const_iterator pos) noexcept ->
530   iterator 537   iterator
531   { 538   {
HITCBC 532   7 BOOST_ASSERT( 539   7 BOOST_ASSERT(
533   pos >= begin() && 540   pos >= begin() &&
534   pos <= end()); 541   pos <= end());
HITCBC 535   7 return erase(pos, pos + 1); 542   7 return erase(pos, pos + 1);
536   } 543   }
537   544  
538   auto 545   auto
HITCBC 539   8 array:: 546   8 array::
540   erase( 547   erase(
541   const_iterator first, 548   const_iterator first,
542   const_iterator last) noexcept -> 549   const_iterator last) noexcept ->
543   iterator 550   iterator
544   { 551   {
HITCBC 545   8 BOOST_ASSERT( 552   8 BOOST_ASSERT(
546   first >= begin() && 553   first >= begin() &&
547   last >= first && 554   last >= first &&
548   last <= end()); 555   last <= end());
HITCBC 549   8 std::size_t const n = 556   8 std::size_t const n =
HITCBC 550   8 last - first; 557   8 last - first;
HITCBC 551   8 auto const p = &(*t_)[0] + 558   8 auto const p = &(*t_)[0] +
HITCBC 552   8 (first - &(*t_)[0]); 559   8 (first - &(*t_)[0]);
HITCBC 553   8 destroy(p, p + n); 560   8 destroy(p, p + n);
HITCBC 554   8 relocate(p, p + n, 561   8 relocate(p, p + n,
HITCBC 555   8 t_->size - (last - 562   8 t_->size - (last -
HITCBC 556   8 &(*t_)[0])); 563   8 &(*t_)[0]));
HITCBC 557   8 t_->size = static_cast< 564   8 t_->size = static_cast<
HITCBC 558   8 std::uint32_t>(t_->size - n); 565   8 std::uint32_t>(t_->size - n);
HITCBC 559   8 return p; 566   8 return p;
560   } 567   }
561   568  
562   void 569   void
HITCBC 563   4 array:: 570   4 array::
564   push_back(value const& v) 571   push_back(value const& v)
565   { 572   {
HITCBC 566   4 emplace_back(v); 573   4 emplace_back(v);
HITCBC 567   2 } 574   2 }
568   575  
569   void 576   void
HITCBC 570   9 array:: 577   9 array::
571   push_back(value&& v) 578   push_back(value&& v)
572   { 579   {
HITCBC 573   9 emplace_back(std::move(v)); 580   9 emplace_back(std::move(v));
HITCBC 574   7 } 581   7 }
575   582  
576   void 583   void
HITCBC 577   3 array:: 584   3 array::
578   pop_back() noexcept 585   pop_back() noexcept
579   { 586   {
HITCBC 580   3 auto const p = &back(); 587   3 auto const p = &back();
HITCBC 581   3 destroy(p, p + 1); 588   3 destroy(p, p + 1);
HITCBC 582   3 --t_->size; 589   3 --t_->size;
HITCBC 583   3 } 590   3 }
584   591  
585   void 592   void
HITCBC 586   15 array:: 593   15 array::
587   resize(std::size_t count) 594   resize(std::size_t count)
588   { 595   {
HITCBC 589   15 if(count <= t_->size) 596   15 if(count <= t_->size)
590   { 597   {
591   // shrink 598   // shrink
HITCBC 592   4 destroy( 599   4 destroy(
HITCBC 593   2 &(*t_)[0] + count, 600   2 &(*t_)[0] + count,
HITCBC 594   2 &(*t_)[0] + t_->size); 601   2 &(*t_)[0] + t_->size);
HITCBC 595   2 t_->size = static_cast< 602   2 t_->size = static_cast<
596   std::uint32_t>(count); 603   std::uint32_t>(count);
HITCBC 597   2 return; 604   2 return;
598   } 605   }
599   606  
HITCBC 600   13 reserve(count); 607   13 reserve(count);
HITCBC 601   12 auto p = &(*t_)[t_->size]; 608   12 auto p = &(*t_)[t_->size];
HITCBC 602   12 auto const end = &(*t_)[count]; 609   12 auto const end = &(*t_)[count];
HITCBC 603   32 while(p != end) 610   32 while(p != end)
HITCBC 604   20 ::new(p++) value(sp_); 611   20 ::new(p++) value(sp_);
HITCBC 605   12 t_->size = static_cast< 612   12 t_->size = static_cast<
606   std::uint32_t>(count); 613   std::uint32_t>(count);
607   } 614   }
608   615  
609   void 616   void
HITCBC 610   11 array:: 617   11 array::
611   resize( 618   resize(
612   std::size_t count, 619   std::size_t count,
613   value const& v) 620   value const& v)
614   { 621   {
HITCBC 615   11 if(count <= size()) 622   11 if(count <= size())
616   { 623   {
617   // shrink 624   // shrink
HITCBC 618   2 destroy( 625   2 destroy(
HITCBC 619   1 data() + count, 626   1 data() + count,
HITCBC 620   1 data() + size()); 627   1 data() + size());
HITCBC 621   1 t_->size = static_cast< 628   1 t_->size = static_cast<
622   std::uint32_t>(count); 629   std::uint32_t>(count);
HITCBC 623   1 return; 630   1 return;
624   } 631   }
HITCBC 625   10 count -= size(); 632   10 count -= size();
626   // v may refer to an element of this array, whose 633   // v may refer to an element of this array, whose
627   // storage revert_insert can relocate and free, so 634   // storage revert_insert can relocate and free, so
628   // copy it before inserting 635   // copy it before inserting
HITCBC 629   12 value const tmp(v, sp_); 636   12 value const tmp(v, sp_);
630   revert_insert r( 637   revert_insert r(
HITCBC 631   8 end(), count, *this); 638   8 end(), count, *this);
HITCBC 632   18 while(count--) 639   18 while(count--)
633   { 640   {
HITCBC 634   20 ::new(r.p) value(tmp, sp_); 641   20 ::new(r.p) value(tmp, sp_);
HITCBC 635   12 ++r.p; 642   12 ++r.p;
636   } 643   }
HITCBC 637   2 r.commit(); 644   2 r.commit();
HITCBC 638   12 } 645   12 }
639   646  
640   void 647   void
HITCBC 641   28 array:: 648   28 array::
642   swap(array& other) 649   swap(array& other)
643   { 650   {
HITCBC 644   28 if(*sp_ == *other.sp_) 651   28 if(*sp_ == *other.sp_)
645   { 652   {
HITCBC 646   48 t_ = detail::exchange( 653   48 t_ = detail::exchange(
HITCBC 647   24 other.t_, t_); 654   24 other.t_, t_);
HITCBC 648   24 return; 655   24 return;
649   } 656   }
650   array temp1( 657   array temp1(
HITCBC 651   4 std::move(*this), 658   4 std::move(*this),
HITCBC 652   9 other.storage()); 659   9 other.storage());
653   array temp2( 660   array temp2(
HITCBC 654   3 std::move(other), 661   3 std::move(other),
HITCBC 655   7 this->storage()); 662   7 this->storage());
HITCBC 656   2 this->~array(); 663   2 this->~array();
HITCBC 657   6 ::new(this) array( 664   6 ::new(this) array(
HITCBC 658   2 pilfer(temp2)); 665   2 pilfer(temp2));
HITCBC 659   2 other.~array(); 666   2 other.~array();
HITCBC 660   6 ::new(&other) array( 667   6 ::new(&other) array(
HITCBC 661   2 pilfer(temp1)); 668   2 pilfer(temp1));
HITCBC 662   3 } 669   3 }
663   670  
664   //---------------------------------------------------------- 671   //----------------------------------------------------------
665   // 672   //
666   // Private 673   // Private
667   // 674   //
668   //---------------------------------------------------------- 675   //----------------------------------------------------------
669   676  
670   std::size_t 677   std::size_t
HITCBC 671   799 array:: 678   804 array::
672   growth( 679   growth(
673   std::size_t new_size) const 680   std::size_t new_size) const
674   { 681   {
HITCBC 675   799 if(new_size > max_size()) 682   804 if(new_size > max_size())
676   { 683   {
677   BOOST_STATIC_CONSTEXPR source_location loc = BOOST_CURRENT_LOCATION; 684   BOOST_STATIC_CONSTEXPR source_location loc = BOOST_CURRENT_LOCATION;
HITCBC 678   1 detail::throw_system_error( error::array_too_large, &loc ); 685   1 detail::throw_system_error( error::array_too_large, &loc );
679   } 686   }
HITCBC 680   798 std::size_t const old = capacity(); 687   803 std::size_t const old = capacity();
HITCBC 681   798 if(old > max_size() - old / 2) 688   803 if(old > max_size() - old / 2)
HITCBC 682   1 return new_size; 689   1 return new_size;
HITCBC 683   797 std::size_t const g = 690   802 std::size_t const g =
HITCBC 684   797 old + old / 2; // 1.5x 691   802 old + old / 2; // 1.5x
HITCBC 685   797 if(g < new_size) 692   802 if(g < new_size)
HITCBC 686   717 return new_size; 693   720 return new_size;
HITCBC 687   80 return g; 694   82 return g;
688   } 695   }
689   696  
690   // precondition: new_capacity > capacity() 697   // precondition: new_capacity > capacity()
691   void 698   void
HITCBC 692   681 array:: 699   685 array::
693   reserve_impl( 700   reserve_impl(
694   std::size_t new_capacity) 701   std::size_t new_capacity)
695   { 702   {
HITCBC 696   681 BOOST_ASSERT( 703   685 BOOST_ASSERT(
697   new_capacity > t_->capacity); 704   new_capacity > t_->capacity);
HITCBC 698   680 auto t = table::allocate( 705   684 auto t = table::allocate(
HITCBC 699   681 growth(new_capacity), sp_); 706   685 growth(new_capacity), sp_);
HITCBC 700   658 relocate( 707   661 relocate(
HITCBC 701   658 &(*t)[0], 708   661 &(*t)[0],
HITCBC 702   658 &(*t_)[0], 709   661 &(*t_)[0],
HITCBC 703   658 t_->size); 710   661 t_->size);
HITCBC 704   658 t->size = t_->size; 711   661 t->size = t_->size;
HITCBC 705   658 t = detail::exchange(t_, t); 712   661 t = detail::exchange(t_, t);
HITCBC 706   658 table::deallocate(t, sp_); 713   661 table::deallocate(t, sp_);
HITCBC 707   658 } 714   661 }
708   715  
709   // precondition: pv is not aliased 716   // precondition: pv is not aliased
710   value& 717   value&
HITCBC 711   7623 array:: 718   7635 array::
712   push_back( 719   push_back(
713   pilfered<value> pv) 720   pilfered<value> pv)
714   { 721   {
HITCBC 715   7623 auto const n = t_->size; 722   7635 auto const n = t_->size;
HITCBC 716   7623 if(n < t_->capacity) 723   7635 if(n < t_->capacity)
717   { 724   {
718   // fast path 725   // fast path
719   auto& v = *::new( 726   auto& v = *::new(
HITCBC 720   7556 &(*t_)[n]) value(pv); 727   7568 &(*t_)[n]) value(pv);
HITCBC 721   7556 ++t_->size; 728   7568 ++t_->size;
HITCBC 722   7556 return v; 729   7568 return v;
723   } 730   }
724   auto const t = 731   auto const t =
HITCBC 725   67 detail::exchange(t_, 732   67 detail::exchange(t_,
726   table::allocate( 733   table::allocate(
HITCBC 727   67 growth(n + 1), 734   67 growth(n + 1),
HITCBC 728   67 sp_)); 735   67 sp_));
729   auto& v = *::new( 736   auto& v = *::new(
HITCBC 730   62 &(*t_)[n]) value(pv); 737   62 &(*t_)[n]) value(pv);
HITCBC 731   62 relocate( 738   62 relocate(
HITCBC 732   62 &(*t_)[0], 739   62 &(*t_)[0],
HITCBC 733   62 &(*t)[0], 740   62 &(*t)[0],
734   n); 741   n);
HITCBC 735   62 t_->size = n + 1; 742   62 t_->size = n + 1;
HITCBC 736   62 table::deallocate(t, sp_); 743   62 table::deallocate(t, sp_);
HITCBC 737   62 return v; 744   62 return v;
738   } 745   }
739   746  
740   // precondition: pv is not aliased 747   // precondition: pv is not aliased
741   auto 748   auto
HITCBC 742   12 array:: 749   12 array::
743   insert( 750   insert(
744   const_iterator pos, 751   const_iterator pos,
745   pilfered<value> pv) -> 752   pilfered<value> pv) ->
746   iterator 753   iterator
747   { 754   {
HITCBC 748   12 BOOST_ASSERT( 755   12 BOOST_ASSERT(
749   pos >= begin() && 756   pos >= begin() &&
750   pos <= end()); 757   pos <= end());
HITCBC 751   12 std::size_t const n = 758   12 std::size_t const n =
HITCBC 752   12 t_->size; 759   12 t_->size;
753   std::size_t const i = 760   std::size_t const i =
HITCBC 754   12 pos - &(*t_)[0]; 761   12 pos - &(*t_)[0];
HITCBC 755   12 if(n < t_->capacity) 762   12 if(n < t_->capacity)
756   { 763   {
757   // fast path 764   // fast path
758   auto const p = 765   auto const p =
HITCBC 759   1 &(*t_)[i]; 766   1 &(*t_)[i];
HITCBC 760   1 relocate( 767   1 relocate(
761   p + 1, 768   p + 1,
762   p, 769   p,
763   n - i); 770   n - i);
HITCBC 764   1 ::new(p) value(pv); 771   1 ::new(p) value(pv);
HITCBC 765   1 ++t_->size; 772   1 ++t_->size;
HITCBC 766   1 return p; 773   1 return p;
767   } 774   }
768   auto t = 775   auto t =
HITCBC 769   11 table::allocate( 776   11 table::allocate(
HITCBC 770   11 growth(n + 1), sp_); 777   11 growth(n + 1), sp_);
HITCBC 771   6 auto const p = &(*t)[i]; 778   6 auto const p = &(*t)[i];
HITCBC 772   6 ::new(p) value(pv); 779   6 ::new(p) value(pv);
HITCBC 773   6 relocate( 780   6 relocate(
HITCBC 774   6 &(*t)[0], 781   6 &(*t)[0],
HITCBC 775   6 &(*t_)[0], 782   6 &(*t_)[0],
776   i); 783   i);
HITCBC 777   6 relocate( 784   6 relocate(
778   p + 1, 785   p + 1,
HITCBC 779   6 &(*t_)[i], 786   6 &(*t_)[i],
780   n - i); 787   n - i);
HITCBC 781   6 t->size = static_cast< 788   6 t->size = static_cast<
HITCBC 782   6 std::uint32_t>(size() + 1); 789   6 std::uint32_t>(size() + 1);
HITCBC 783   6 t = detail::exchange(t_, t); 790   6 t = detail::exchange(t_, t);
HITCBC 784   6 table::deallocate(t, sp_); 791   6 table::deallocate(t, sp_);
HITCBC 785   6 return p; 792   6 return p;
786   } 793   }
787   794  
788   //---------------------------------------------------------- 795   //----------------------------------------------------------
789   796  
790   bool 797   bool
HITCBC 791   79 array:: 798   79 array::
792   equal( 799   equal(
793   array const& other) const noexcept 800   array const& other) const noexcept
794   { 801   {
HITCBC 795   79 if(size() != other.size()) 802   79 if(size() != other.size())
HITCBC 796   2 return false; 803   2 return false;
HITCBC 797   3250 for(std::size_t i = 0; i < size(); ++i) 804   3250 for(std::size_t i = 0; i < size(); ++i)
HITCBC 798   3179 if((*this)[i] != other[i]) 805   3179 if((*this)[i] != other[i])
HITCBC 799   6 return false; 806   6 return false;
HITCBC 800   71 return true; 807   71 return true;
801   } 808   }
802   809  
803   } // namespace json 810   } // namespace json
804   } // namespace boost 811   } // namespace boost
805   812  
806   //---------------------------------------------------------- 813   //----------------------------------------------------------
807   // 814   //
808   // std::hash specialization 815   // std::hash specialization
809   // 816   //
810   //---------------------------------------------------------- 817   //----------------------------------------------------------
811   818  
812   std::size_t 819   std::size_t
HITCBC 813   12 std::hash<::boost::json::array>::operator()( 820   12 std::hash<::boost::json::array>::operator()(
814   ::boost::json::array const& ja) const noexcept 821   ::boost::json::array const& ja) const noexcept
815   { 822   {
HITCBC 816   12 return ::boost::hash< ::boost::json::array >()( ja ); 823   12 return ::boost::hash< ::boost::json::array >()( ja );
817   } 824   }
818   825  
819   //---------------------------------------------------------- 826   //----------------------------------------------------------
820   827  
821   #endif 828   #endif