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