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