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   2626 array:: 35   2626 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   2626 BOOST_ASSERT(capacity > 0); 42   2626 BOOST_ASSERT(capacity > 0);
HITCBC 43   2626 if(capacity > array::max_size()) 43   2626 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   2624 table*>(sp->allocate( 49   2624 table*>(sp->allocate(
50   sizeof(table) + 50   sizeof(table) +
HITCBC 51   2624 capacity * sizeof(value), 51   2624 capacity * sizeof(value),
52   alignof(value))); 52   alignof(value)));
HITCBC 53   2475 p->capacity = static_cast< 53   2475 p->capacity = static_cast<
54   std::uint32_t>(capacity); 54   std::uint32_t>(capacity);
HITCBC 55   2475 return p; 55   2475 return p;
56   } 56   }
57   57  
58   void 58   void
HITCBC 59   4525 array:: 59   4525 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   4525 if(p->capacity == 0) 65   4525 if(p->capacity == 0)
HITCBC 66   2054 return; 66   2054 return;
HITCBC 67   2471 sp->deallocate(p, 67   2471 sp->deallocate(p,
68   sizeof(table) + 68   sizeof(table) +
HITCBC 69   2471 p->capacity * sizeof(value), 69   2471 p->capacity * sizeof(value),
70   alignof(value)); 70   alignof(value));
71   } 71   }
72   72  
73   //---------------------------------------------------------- 73   //----------------------------------------------------------
74   74  
HITCBC 75   49 array:: 75   49 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   49 array& arr) 80   49 array& arr)
HITCBC 81   49 : arr_(&arr) 81   49 : arr_(&arr)
HITCBC 82   49 , i_(pos - arr_->data()) 82   49 , i_(pos - arr_->data())
HITCBC 83   49 , n_(n) 83   49 , n_(n)
84   { 84   {
HITCBC 85   49 BOOST_ASSERT( 85   49 BOOST_ASSERT(
86   pos >= arr_->begin() && 86   pos >= arr_->begin() &&
87   pos <= arr_->end()); 87   pos <= arr_->end());
HITCBC 88   98 if( n_ <= arr_->capacity() - 88   98 if( n_ <= arr_->capacity() -
HITCBC 89   49 arr_->size()) 89   49 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   47 if(n_ > max_size() - arr_->size()) 104   47 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   46 auto t = table::allocate( 109   46 auto t = table::allocate(
HITCBC 110   46 arr_->growth(arr_->size() + n_), 110   46 arr_->growth(arr_->size() + n_),
HITCBC 111   46 arr_->sp_); 111   46 arr_->sp_);
HITCBC 112   33 t->size = static_cast<std::uint32_t>( 112   33 t->size = static_cast<std::uint32_t>(
HITCBC 113   33 arr_->size() + n_); 113   33 arr_->size() + n_);
HITCBC 114   33 p = &(*t)[0] + i_; 114   33 p = &(*t)[0] + i_;
HITCBC 115   33 relocate( 115   33 relocate(
HITCBC 116   33 &(*t)[0], 116   33 &(*t)[0],
HITCBC 117   33 arr_->data(), 117   33 arr_->data(),
HITCBC 118   33 i_); 118   33 i_);
HITCBC 119   33 relocate( 119   33 relocate(
HITCBC 120   33 &(*t)[i_ + n_], 120   33 &(*t)[i_ + n_],
HITCBC 121   33 arr_->data() + i_, 121   33 arr_->data() + i_,
HITCBC 122   33 arr_->size() - i_); 122   33 arr_->size() - i_);
HITCBC 123   33 t = detail::exchange(arr_->t_, t); 123   33 t = detail::exchange(arr_->t_, t);
HITCBC 124   33 table::deallocate(t, arr_->sp_); 124   33 table::deallocate(t, arr_->sp_);
125   } 125   }
126   126  
HITCBC 127   35 array:: 127   35 array::
128   revert_insert:: 128   revert_insert::
HITCBC 129   9 ~revert_insert() 129   9 ~revert_insert()
130   { 130   {
HITCBC 131   35 if(! arr_) 131   35 if(! arr_)
HITCBC 132   26 return; 132   26 return;
HITCBC 133   9 BOOST_ASSERT(n_ != 0); 133   9 BOOST_ASSERT(n_ != 0);
134   auto const pos = 134   auto const pos =
HITCBC 135   9 arr_->data() + i_; 135   9 arr_->data() + i_;
HITCBC 136   9 arr_->destroy(pos, p); 136   9 arr_->destroy(pos, p);
HITCBC 137   9 arr_->t_->size = static_cast< 137   9 arr_->t_->size = static_cast<
138   std::uint32_t>( 138   std::uint32_t>(
HITCBC 139   9 arr_->t_->size - n_); 139   9 arr_->t_->size - n_);
HITCBC 140   9 relocate( 140   9 relocate(
141   pos, 141   pos,
HITCBC 142   9 pos + n_, 142   9 pos + n_,
HITCBC 143   9 arr_->size() - i_); 143   9 arr_->size() - i_);
HITCBC 144   35 } 144   35 }
145   145  
146   //---------------------------------------------------------- 146   //----------------------------------------------------------
147   147  
148   void 148   void
HITCBC 149   26 array:: 149   26 array::
150   destroy( 150   destroy(
151   value* first, value* last) noexcept 151   value* first, value* last) noexcept
152   { 152   {
HITCBC 153   26 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   54 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   3765 array:: 160   3765 array::
161   destroy() noexcept 161   destroy() noexcept
162   { 162   {
HITCBC 163   3765 if(sp_.is_not_shared_and_deallocate_is_trivial()) 163   3765 if(sp_.is_not_shared_and_deallocate_is_trivial())
HITCBC 164   5 return; 164   5 return;
HITCBC 165   3760 auto last = end(); 165   3760 auto last = end();
HITCBC 166   3760 auto const first = begin(); 166   3760 auto const first = begin();
HITCBC 167   21084 while(last-- != first) 167   21084 while(last-- != first)
HITCBC 168   17324 last->~value(); 168   17324 last->~value();
HITCBC 169   3760 table::deallocate(t_, sp_); 169   3760 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   3697 array:: 195   3697 array::
196   ~array() noexcept 196   ~array() noexcept
197   { 197   {
HITCBC 198   3697 destroy(); 198   3697 destroy();
HITCBC 199   3697 } 199   3697 }
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   267 array:: 282   267 array::
283   array( 283   array(
284   array&& other, 284   array&& other,
HITCBC 285   267 storage_ptr sp) 285   267 storage_ptr sp)
HITCBC 286   267 : sp_(std::move(sp)) 286   267 : sp_(std::move(sp))
287   { 287   {
HITCBC 288   267 if(*sp_ == *other.sp_) 288   267 if(*sp_ == *other.sp_)
289   { 289   {
290   // same resource 290   // same resource
HITCBC 291   488 t_ = detail::exchange( 291   488 t_ = detail::exchange(
HITCBC 292   244 other.t_, &empty_); 292   244 other.t_, &empty_);
HITCBC 293   248 return; 293   248 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   276 array:: 318   276 array::
319   array( 319   array(
320   std::initializer_list< 320   std::initializer_list<
321   value_ref> init, 321   value_ref> init,
HITCBC 322   276 storage_ptr sp) 322   276 storage_ptr sp)
HITCBC 323   276 : sp_(std::move(sp)) 323   276 : sp_(std::move(sp))
324   { 324   {
HITCBC 325   276 if(init.size() == 0) 325   276 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   271 t_ = table::allocate( 330   271 t_ = table::allocate(
HITCBC 331   271 init.size(), sp_); 331   271 init.size(), sp_);
HITCBC 332   241 t_->size = 0; 332   241 t_->size = 0;
HITCBC 333   241 revert_construct r(*this); 333   241 revert_construct r(*this);
HITCBC 334   241 value_ref::write_array( 334   241 value_ref::write_array(
HITCBC 335   241 data(), init, sp_); 335   241 data(), init, sp_);
HITCBC 336   223 t_->size = static_cast< 336   223 t_->size = static_cast<
HITCBC 337   223 std::uint32_t>(init.size()); 337   223 std::uint32_t>(init.size());
HITCBC 338   223 r.commit(); 338   223 r.commit();
HITCBC 339   289 } 339   289 }
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   13 array:: 512   13 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 value_refs in init may point into this 519   // the value_refs in init may point into this
520   // array, whose storage revert_insert can 520   // array, whose storage revert_insert can
521   // relocate and free, so buffer them first 521   // relocate and free, so buffer them first
HITCBC 522   17 array temp(init, sp_); 522   17 array temp(init, sp_);
523   revert_insert r( 523   revert_insert r(
HITCBC 524   9 pos, temp.size(), *this); 524   9 pos, temp.size(), *this);
HITCBC 525   7 relocate( 525   7 relocate(
526   r.p, 526   r.p,
527   temp.data(), 527   temp.data(),
528   temp.size()); 528   temp.size());
HITCBC 529   7 temp.t_->size = 0; 529   7 temp.t_->size = 0;
HITCBC 530   14 return r.commit(); 530   14 return r.commit();
HITCBC 531   9 } 531   9 }
532   532  
533   auto 533   auto
HITCBC 534   7 array:: 534   7 array::
535   erase( 535   erase(
536   const_iterator pos) noexcept -> 536   const_iterator pos) noexcept ->
537   iterator 537   iterator
538   { 538   {
HITCBC 539   7 BOOST_ASSERT( 539   7 BOOST_ASSERT(
540   pos >= begin() && 540   pos >= begin() &&
541   pos <= end()); 541   pos <= end());
HITCBC 542   7 return erase(pos, pos + 1); 542   7 return erase(pos, pos + 1);
543   } 543   }
544   544  
545   auto 545   auto
HITCBC 546   8 array:: 546   8 array::
547   erase( 547   erase(
548   const_iterator first, 548   const_iterator first,
549   const_iterator last) noexcept -> 549   const_iterator last) noexcept ->
550   iterator 550   iterator
551   { 551   {
HITCBC 552   8 BOOST_ASSERT( 552   8 BOOST_ASSERT(
553   first >= begin() && 553   first >= begin() &&
554   last >= first && 554   last >= first &&
555   last <= end()); 555   last <= end());
HITCBC 556   8 std::size_t const n = 556   8 std::size_t const n =
HITCBC 557   8 last - first; 557   8 last - first;
HITCBC 558   8 auto const p = &(*t_)[0] + 558   8 auto const p = &(*t_)[0] +
HITCBC 559   8 (first - &(*t_)[0]); 559   8 (first - &(*t_)[0]);
HITCBC 560   8 destroy(p, p + n); 560   8 destroy(p, p + n);
HITCBC 561   8 relocate(p, p + n, 561   8 relocate(p, p + n,
HITCBC 562   8 t_->size - (last - 562   8 t_->size - (last -
HITCBC 563   8 &(*t_)[0])); 563   8 &(*t_)[0]));
HITCBC 564   8 t_->size = static_cast< 564   8 t_->size = static_cast<
HITCBC 565   8 std::uint32_t>(t_->size - n); 565   8 std::uint32_t>(t_->size - n);
HITCBC 566   8 return p; 566   8 return p;
567   } 567   }
568   568  
569   void 569   void
HITCBC 570   4 array:: 570   4 array::
571   push_back(value const& v) 571   push_back(value const& v)
572   { 572   {
HITCBC 573   4 emplace_back(v); 573   4 emplace_back(v);
HITCBC 574   2 } 574   2 }
575   575  
576   void 576   void
HITCBC 577   9 array:: 577   9 array::
578   push_back(value&& v) 578   push_back(value&& v)
579   { 579   {
HITCBC 580   9 emplace_back(std::move(v)); 580   9 emplace_back(std::move(v));
HITCBC 581   7 } 581   7 }
582   582  
583   void 583   void
HITCBC 584   3 array:: 584   3 array::
585   pop_back() noexcept 585   pop_back() noexcept
586   { 586   {
HITCBC 587   3 auto const p = &back(); 587   3 auto const p = &back();
HITCBC 588   3 destroy(p, p + 1); 588   3 destroy(p, p + 1);
HITCBC 589   3 --t_->size; 589   3 --t_->size;
HITCBC 590   3 } 590   3 }
591   591  
592   void 592   void
HITCBC 593   15 array:: 593   15 array::
594   resize(std::size_t count) 594   resize(std::size_t count)
595   { 595   {
HITCBC 596   15 if(count <= t_->size) 596   15 if(count <= t_->size)
597   { 597   {
598   // shrink 598   // shrink
HITCBC 599   4 destroy( 599   4 destroy(
HITCBC 600   2 &(*t_)[0] + count, 600   2 &(*t_)[0] + count,
HITCBC 601   2 &(*t_)[0] + t_->size); 601   2 &(*t_)[0] + t_->size);
HITCBC 602   2 t_->size = static_cast< 602   2 t_->size = static_cast<
603   std::uint32_t>(count); 603   std::uint32_t>(count);
HITCBC 604   2 return; 604   2 return;
605   } 605   }
606   606  
HITCBC 607   13 reserve(count); 607   13 reserve(count);
HITCBC 608   12 auto p = &(*t_)[t_->size]; 608   12 auto p = &(*t_)[t_->size];
HITCBC 609   12 auto const end = &(*t_)[count]; 609   12 auto const end = &(*t_)[count];
HITCBC 610   32 while(p != end) 610   32 while(p != end)
HITCBC 611   20 ::new(p++) value(sp_); 611   20 ::new(p++) value(sp_);
HITCBC 612   12 t_->size = static_cast< 612   12 t_->size = static_cast<
613   std::uint32_t>(count); 613   std::uint32_t>(count);
614   } 614   }
615   615  
616   void 616   void
HITCBC 617   11 array:: 617   11 array::
618   resize( 618   resize(
619   std::size_t count, 619   std::size_t count,
620   value const& v) 620   value const& v)
621   { 621   {
HITCBC 622   11 if(count <= size()) 622   11 if(count <= size())
623   { 623   {
624   // shrink 624   // shrink
HITCBC 625   2 destroy( 625   2 destroy(
HITCBC 626   1 data() + count, 626   1 data() + count,
HITCBC 627   1 data() + size()); 627   1 data() + size());
HITCBC 628   1 t_->size = static_cast< 628   1 t_->size = static_cast<
629   std::uint32_t>(count); 629   std::uint32_t>(count);
HITCBC 630   1 return; 630   1 return;
631   } 631   }
HITCBC 632   10 count -= size(); 632   10 count -= size();
633   // v may refer to an element of this array, whose 633   // v may refer to an element of this array, whose
634   // storage revert_insert can relocate and free, so 634   // storage revert_insert can relocate and free, so
635   // copy it before inserting 635   // copy it before inserting
HITCBC 636   12 value const tmp(v, sp_); 636   12 value const tmp(v, sp_);
637   revert_insert r( 637   revert_insert r(
HITCBC 638   8 end(), count, *this); 638   8 end(), count, *this);
HITCBC 639   18 while(count--) 639   18 while(count--)
640   { 640   {
HITCBC 641   20 ::new(r.p) value(tmp, sp_); 641   20 ::new(r.p) value(tmp, sp_);
HITCBC 642   12 ++r.p; 642   12 ++r.p;
643   } 643   }
HITCBC 644   2 r.commit(); 644   2 r.commit();
HITCBC 645   12 } 645   12 }
646   646  
647   void 647   void
HITCBC 648   28 array:: 648   28 array::
649   swap(array& other) 649   swap(array& other)
650   { 650   {
HITCBC 651   28 if(*sp_ == *other.sp_) 651   28 if(*sp_ == *other.sp_)
652   { 652   {
HITCBC 653   48 t_ = detail::exchange( 653   48 t_ = detail::exchange(
HITCBC 654   24 other.t_, t_); 654   24 other.t_, t_);
HITCBC 655   24 return; 655   24 return;
656   } 656   }
657   array temp1( 657   array temp1(
HITCBC 658   4 std::move(*this), 658   4 std::move(*this),
HITCBC 659   9 other.storage()); 659   9 other.storage());
660   array temp2( 660   array temp2(
HITCBC 661   3 std::move(other), 661   3 std::move(other),
HITCBC 662   7 this->storage()); 662   7 this->storage());
HITCBC 663   2 this->~array(); 663   2 this->~array();
HITCBC 664   6 ::new(this) array( 664   6 ::new(this) array(
HITCBC 665   2 pilfer(temp2)); 665   2 pilfer(temp2));
HITCBC 666   2 other.~array(); 666   2 other.~array();
HITCBC 667   6 ::new(&other) array( 667   6 ::new(&other) array(
HITCBC 668   2 pilfer(temp1)); 668   2 pilfer(temp1));
HITCBC 669   3 } 669   3 }
670   670  
671   //---------------------------------------------------------- 671   //----------------------------------------------------------
672   // 672   //
673   // Private 673   // Private
674   // 674   //
675   //---------------------------------------------------------- 675   //----------------------------------------------------------
676   676  
677   std::size_t 677   std::size_t
HITCBC 678   808 array:: 678   808 array::
679   growth( 679   growth(
680   std::size_t new_size) const 680   std::size_t new_size) const
681   { 681   {
HITCBC 682   808 if(new_size > max_size()) 682   808 if(new_size > max_size())
683   { 683   {
684   BOOST_STATIC_CONSTEXPR source_location loc = BOOST_CURRENT_LOCATION; 684   BOOST_STATIC_CONSTEXPR source_location loc = BOOST_CURRENT_LOCATION;
HITCBC 685   1 detail::throw_system_error( error::array_too_large, &loc ); 685   1 detail::throw_system_error( error::array_too_large, &loc );
686   } 686   }
HITCBC 687   807 std::size_t const old = capacity(); 687   807 std::size_t const old = capacity();
HITCBC 688   807 if(old > max_size() - old / 2) 688   807 if(old > max_size() - old / 2)
HITCBC 689   1 return new_size; 689   1 return new_size;
HITCBC 690   806 std::size_t const g = 690   806 std::size_t const g =
HITCBC 691   806 old + old / 2; // 1.5x 691   806 old + old / 2; // 1.5x
HITCBC 692   806 if(g < new_size) 692   806 if(g < new_size)
HITCBC 693   726 return new_size; 693   726 return new_size;
HITCBC 694   80 return g; 694   80 return g;
695   } 695   }
696   696  
697   // precondition: new_capacity > capacity() 697   // precondition: new_capacity > capacity()
698   void 698   void
HITCBC 699   684 array:: 699   684 array::
700   reserve_impl( 700   reserve_impl(
701   std::size_t new_capacity) 701   std::size_t new_capacity)
702   { 702   {
HITCBC 703   684 BOOST_ASSERT( 703   684 BOOST_ASSERT(
704   new_capacity > t_->capacity); 704   new_capacity > t_->capacity);
HITCBC 705   683 auto t = table::allocate( 705   683 auto t = table::allocate(
HITCBC 706   684 growth(new_capacity), sp_); 706   684 growth(new_capacity), sp_);
HITCBC 707   661 relocate( 707   661 relocate(
HITCBC 708   661 &(*t)[0], 708   661 &(*t)[0],
HITCBC 709   661 &(*t_)[0], 709   661 &(*t_)[0],
HITCBC 710   661 t_->size); 710   661 t_->size);
HITCBC 711   661 t->size = t_->size; 711   661 t->size = t_->size;
HITCBC 712   661 t = detail::exchange(t_, t); 712   661 t = detail::exchange(t_, t);
HITCBC 713   661 table::deallocate(t, sp_); 713   661 table::deallocate(t, sp_);
HITCBC 714   661 } 714   661 }
715   715  
716   // precondition: pv is not aliased 716   // precondition: pv is not aliased
717   value& 717   value&
HITCBC 718   7632 array:: 718   7632 array::
719   push_back( 719   push_back(
720   pilfered<value> pv) 720   pilfered<value> pv)
721   { 721   {
HITCBC 722   7632 auto const n = t_->size; 722   7632 auto const n = t_->size;
HITCBC 723   7632 if(n < t_->capacity) 723   7632 if(n < t_->capacity)
724   { 724   {
725   // fast path 725   // fast path
726   auto& v = *::new( 726   auto& v = *::new(
HITCBC 727   7565 &(*t_)[n]) value(pv); 727   7565 &(*t_)[n]) value(pv);
HITCBC 728   7565 ++t_->size; 728   7565 ++t_->size;
HITCBC 729   7565 return v; 729   7565 return v;
730   } 730   }
731   auto const t = 731   auto const t =
HITCBC 732   67 detail::exchange(t_, 732   67 detail::exchange(t_,
733   table::allocate( 733   table::allocate(
HITCBC 734   67 growth(n + 1), 734   67 growth(n + 1),
HITCBC 735   67 sp_)); 735   67 sp_));
736   auto& v = *::new( 736   auto& v = *::new(
HITCBC 737   62 &(*t_)[n]) value(pv); 737   62 &(*t_)[n]) value(pv);
HITCBC 738   62 relocate( 738   62 relocate(
HITCBC 739   62 &(*t_)[0], 739   62 &(*t_)[0],
HITCBC 740   62 &(*t)[0], 740   62 &(*t)[0],
741   n); 741   n);
HITCBC 742   62 t_->size = n + 1; 742   62 t_->size = n + 1;
HITCBC 743   62 table::deallocate(t, sp_); 743   62 table::deallocate(t, sp_);
HITCBC 744   62 return v; 744   62 return v;
745   } 745   }
746   746  
747   // precondition: pv is not aliased 747   // precondition: pv is not aliased
748   auto 748   auto
HITCBC 749   12 array:: 749   12 array::
750   insert( 750   insert(
751   const_iterator pos, 751   const_iterator pos,
752   pilfered<value> pv) -> 752   pilfered<value> pv) ->
753   iterator 753   iterator
754   { 754   {
HITCBC 755   12 BOOST_ASSERT( 755   12 BOOST_ASSERT(
756   pos >= begin() && 756   pos >= begin() &&
757   pos <= end()); 757   pos <= end());
HITCBC 758   12 std::size_t const n = 758   12 std::size_t const n =
HITCBC 759   12 t_->size; 759   12 t_->size;
760   std::size_t const i = 760   std::size_t const i =
HITCBC 761   12 pos - &(*t_)[0]; 761   12 pos - &(*t_)[0];
HITCBC 762   12 if(n < t_->capacity) 762   12 if(n < t_->capacity)
763   { 763   {
764   // fast path 764   // fast path
765   auto const p = 765   auto const p =
HITCBC 766   1 &(*t_)[i]; 766   1 &(*t_)[i];
HITCBC 767   1 relocate( 767   1 relocate(
768   p + 1, 768   p + 1,
769   p, 769   p,
770   n - i); 770   n - i);
HITCBC 771   1 ::new(p) value(pv); 771   1 ::new(p) value(pv);
HITCBC 772   1 ++t_->size; 772   1 ++t_->size;
HITCBC 773   1 return p; 773   1 return p;
774   } 774   }
775   auto t = 775   auto t =
HITCBC 776   11 table::allocate( 776   11 table::allocate(
HITCBC 777   11 growth(n + 1), sp_); 777   11 growth(n + 1), sp_);
HITCBC 778   6 auto const p = &(*t)[i]; 778   6 auto const p = &(*t)[i];
HITCBC 779   6 ::new(p) value(pv); 779   6 ::new(p) value(pv);
HITCBC 780   6 relocate( 780   6 relocate(
HITCBC 781   6 &(*t)[0], 781   6 &(*t)[0],
HITCBC 782   6 &(*t_)[0], 782   6 &(*t_)[0],
783   i); 783   i);
HITCBC 784   6 relocate( 784   6 relocate(
785   p + 1, 785   p + 1,
HITCBC 786   6 &(*t_)[i], 786   6 &(*t_)[i],
787   n - i); 787   n - i);
HITCBC 788   6 t->size = static_cast< 788   6 t->size = static_cast<
HITCBC 789   6 std::uint32_t>(size() + 1); 789   6 std::uint32_t>(size() + 1);
HITCBC 790   6 t = detail::exchange(t_, t); 790   6 t = detail::exchange(t_, t);
HITCBC 791   6 table::deallocate(t, sp_); 791   6 table::deallocate(t, sp_);
HITCBC 792   6 return p; 792   6 return p;
793   } 793   }
794   794  
795   //---------------------------------------------------------- 795   //----------------------------------------------------------
796   796  
797   bool 797   bool
HITCBC 798   81 array:: 798   81 array::
799   equal( 799   equal(
800   array const& other) const noexcept 800   array const& other) const noexcept
801   { 801   {
HITCBC 802   81 if(size() != other.size()) 802   81 if(size() != other.size())
HITCBC 803   2 return false; 803   2 return false;
HITCBC 804   3254 for(std::size_t i = 0; i < size(); ++i) 804   3254 for(std::size_t i = 0; i < size(); ++i)
HITCBC 805   3181 if((*this)[i] != other[i]) 805   3181 if((*this)[i] != other[i])
HITCBC 806   6 return false; 806   6 return false;
HITCBC 807   73 return true; 807   73 return true;
808   } 808   }
809   809  
810   } // namespace json 810   } // namespace json
811   } // namespace boost 811   } // namespace boost
812   812  
813   //---------------------------------------------------------- 813   //----------------------------------------------------------
814   // 814   //
815   // std::hash specialization 815   // std::hash specialization
816   // 816   //
817   //---------------------------------------------------------- 817   //----------------------------------------------------------
818   818  
819   std::size_t 819   std::size_t
HITCBC 820   12 std::hash<::boost::json::array>::operator()( 820   12 std::hash<::boost::json::array>::operator()(
821   ::boost::json::array const& ja) const noexcept 821   ::boost::json::array const& ja) const noexcept
822   { 822   {
HITCBC 823   12 return ::boost::hash< ::boost::json::array >()( ja ); 823   12 return ::boost::hash< ::boost::json::array >()( ja );
824   } 824   }
825   825  
826   //---------------------------------------------------------- 826   //----------------------------------------------------------
827   827  
828   #endif 828   #endif