include/boost/json /impl /object.ipp
100.00% Lines (442/442) 100.00% Functions (49/49)
[ ] 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_OBJECT_IPP 10   #ifndef BOOST_JSON_IMPL_OBJECT_IPP
11   #define BOOST_JSON_IMPL_OBJECT_IPP 11   #define BOOST_JSON_IMPL_OBJECT_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/object.hpp> 15   #include <boost/json/object.hpp>
16   #include <boost/json/detail/digest.hpp> 16   #include <boost/json/detail/digest.hpp>
17   #include <boost/json/detail/except.hpp> 17   #include <boost/json/detail/except.hpp>
18   #include <algorithm> 18   #include <algorithm>
19   #include <cmath> 19   #include <cmath>
20   #include <cstdlib> 20   #include <cstdlib>
21   #include <cstring> 21   #include <cstring>
22   #include <new> 22   #include <new>
23   #include <stdexcept> 23   #include <stdexcept>
24   #include <type_traits> 24   #include <type_traits>
25   25  
26   namespace boost { 26   namespace boost {
27   namespace json { 27   namespace json {
28   namespace detail { 28   namespace detail {
29   29  
30   template<class CharRange> 30   template<class CharRange>
31   std::pair<key_value_pair*, std::size_t> 31   std::pair<key_value_pair*, std::size_t>
HITCBC 32   42852 find_in_object( 32   42858 find_in_object(
33   object const& obj, 33   object const& obj,
34   CharRange key) noexcept 34   CharRange key) noexcept
35   { 35   {
HITCBC 36   42852 BOOST_ASSERT(obj.t_->capacity > 0); 36   42858 BOOST_ASSERT(obj.t_->capacity > 0);
HITCBC 37   42852 if(obj.t_->is_small()) 37   42858 if(obj.t_->is_small())
38   { 38   {
HITCBC 39   41004 auto it = &(*obj.t_)[0]; 39   41004 auto it = &(*obj.t_)[0];
40   auto const last = 40   auto const last =
HITCBC 41   41004 &(*obj.t_)[obj.t_->size]; 41   41004 &(*obj.t_)[obj.t_->size];
HITCBC 42   75339 for(;it != last; ++it) 42   75339 for(;it != last; ++it)
HITCBC 43   35062 if( key == it->key() ) 43   35062 if( key == it->key() )
HITCBC 44   727 return { it, 0 }; 44   727 return { it, 0 };
HITCBC 45   40277 return { nullptr, 0 }; 45   40277 return { nullptr, 0 };
46   } 46   }
47   std::pair< 47   std::pair<
48   key_value_pair*, 48   key_value_pair*,
HITCBC 49   1848 std::size_t> result; 49   1854 std::size_t> result;
HITCBC 50   1848 BOOST_ASSERT(obj.t_->salt != 0); 50   1854 BOOST_ASSERT(obj.t_->salt != 0);
HITCBC 51   1848 result.second = detail::digest(key.begin(), key.end(), obj.t_->salt); 51   1854 result.second = detail::digest(key.begin(), key.end(), obj.t_->salt);
HITCBC 52   1848 auto i = obj.t_->bucket( 52   1854 auto i = obj.t_->bucket(
53   result.second); 53   result.second);
HITCBC 54   2545 while(i != object::null_index_) 54   2486 while(i != object::null_index_)
55   { 55   {
HITCBC 56   1035 auto& v = (*obj.t_)[i]; 56   971 auto& v = (*obj.t_)[i];
HITCBC 57   1035 if( key == v.key() ) 57   971 if( key == v.key() )
58   { 58   {
HITCBC 59   338 result.first = &v; 59   339 result.first = &v;
HITCBC 60   338 return result; 60   339 return result;
61   } 61   }
HITCBC 62   697 i = access::next(v); 62   632 i = access::next(v);
63   } 63   }
HITCBC 64   1510 result.first = nullptr; 64   1515 result.first = nullptr;
HITCBC 65   1510 return result; 65   1515 return result;
66   } 66   }
67   67  
68   68  
69   template 69   template
70   std::pair<key_value_pair*, std::size_t> 70   std::pair<key_value_pair*, std::size_t>
71   find_in_object<string_view>( 71   find_in_object<string_view>(
72   object const& obj, 72   object const& obj,
73   string_view key) noexcept; 73   string_view key) noexcept;
74   74  
75   } // namespace detail 75   } // namespace detail
76   76  
77   //---------------------------------------------------------- 77   //----------------------------------------------------------
78   78  
79   constexpr object::table::table() = default; 79   constexpr object::table::table() = default;
80   80  
81   // empty objects point here 81   // empty objects point here
82   BOOST_JSON_REQUIRE_CONST_INIT 82   BOOST_JSON_REQUIRE_CONST_INIT
83   object::table object::empty_; 83   object::table object::empty_;
84   84  
85   std::size_t 85   std::size_t
HITCBC 86   7107 object::table:: 86   7637 object::table::
87   digest(string_view key) const noexcept 87   digest(string_view key) const noexcept
88   { 88   {
HITCBC 89   7107 BOOST_ASSERT(salt != 0); 89   7637 BOOST_ASSERT(salt != 0);
HITCBC 90   7107 return detail::digest( 90   7637 return detail::digest(
HITCBC 91   14214 key.begin(), key.end(), salt); 91   15274 key.begin(), key.end(), salt);
92   } 92   }
93   93  
94   auto 94   auto
HITCBC 95   10517 object::table:: 95   11042 object::table::
96   bucket(std::size_t hash) noexcept -> 96   bucket(std::size_t hash) noexcept ->
97   index_t& 97   index_t&
98   { 98   {
99   return reinterpret_cast< 99   return reinterpret_cast<
HITCBC 100   10517 index_t*>(&(*this)[capacity])[ 100   11042 index_t*>(&(*this)[capacity])[
HITCBC 101   10517 hash % capacity]; 101   11042 hash % capacity];
102   } 102   }
103   103  
104   auto 104   auto
HITCBC 105   7082 object::table:: 105   7598 object::table::
106   bucket(string_view key) noexcept -> 106   bucket(string_view key) noexcept ->
107   index_t& 107   index_t&
108   { 108   {
HITCBC 109   7082 return bucket(digest(key)); 109   7598 return bucket(digest(key));
110   } 110   }
111   111  
112   void 112   void
HITCBC 113   392 object::table:: 113   393 object::table::
114   clear() noexcept 114   clear() noexcept
115   { 115   {
HITCBC 116   392 BOOST_ASSERT(! is_small()); 116   393 BOOST_ASSERT(! is_small());
117   // initialize buckets 117   // initialize buckets
HITCBC 118   784 std::memset( 118   786 std::memset(
119   reinterpret_cast<index_t*>( 119   reinterpret_cast<index_t*>(
HITCBC 120   392 &(*this)[capacity]), 120   393 &(*this)[capacity]),
121   0xff, // null_index_ 121   0xff, // null_index_
HITCBC 122   392 capacity * sizeof(index_t)); 122   393 capacity * sizeof(index_t));
HITCBC 123   392 } 123   393 }
124   124  
125   object::table* 125   object::table*
HITCBC 126   35481 object::table:: 126   35482 object::table::
127   allocate( 127   allocate(
128   std::size_t capacity, 128   std::size_t capacity,
129   std::uintptr_t salt, 129   std::uintptr_t salt,
130   storage_ptr const& sp) 130   storage_ptr const& sp)
131   { 131   {
132   BOOST_CORE_STATIC_ASSERT( 132   BOOST_CORE_STATIC_ASSERT(
133   alignof(key_value_pair) >= alignof(index_t)); 133   alignof(key_value_pair) >= alignof(index_t));
HITCBC 134   35481 BOOST_ASSERT(capacity > 0); 134   35482 BOOST_ASSERT(capacity > 0);
HITCBC 135   35481 BOOST_ASSERT(capacity <= max_size()); 135   35482 BOOST_ASSERT(capacity <= max_size());
136   table* p; 136   table* p;
HITCBC 137   35481 if(capacity <= detail::small_object_size_) 137   35482 if(capacity <= detail::small_object_size_)
138   { 138   {
139   p = reinterpret_cast< 139   p = reinterpret_cast<
HITCBC 140   35078 table*>(sp->allocate( 140   35078 table*>(sp->allocate(
HITCBC 141   35078 sizeof(table) + capacity * 141   35078 sizeof(table) + capacity *
142   sizeof(key_value_pair))); 142   sizeof(key_value_pair)));
HITCBC 143   34987 p->capacity = static_cast< 143   34987 p->capacity = static_cast<
144   std::uint32_t>(capacity); 144   std::uint32_t>(capacity);
145   } 145   }
146   else 146   else
147   { 147   {
148   p = reinterpret_cast< 148   p = reinterpret_cast<
HITCBC 149   403 table*>(sp->allocate( 149   404 table*>(sp->allocate(
HITCBC 150   403 sizeof(table) + capacity * ( 150   404 sizeof(table) + capacity * (
151   sizeof(key_value_pair) + 151   sizeof(key_value_pair) +
152   sizeof(index_t)))); 152   sizeof(index_t))));
HITCBC 153   388 p->capacity = static_cast< 153   389 p->capacity = static_cast<
154   std::uint32_t>(capacity); 154   std::uint32_t>(capacity);
HITCBC 155   388 p->clear(); 155   389 p->clear();
156   } 156   }
HITCBC 157   35375 if(salt) 157   35376 if(salt)
158   { 158   {
HITCBC 159   489 p->salt = salt; 159   489 p->salt = salt;
160   } 160   }
161   else 161   else
162   { 162   {
163   // VFALCO This would be better if it 163   // VFALCO This would be better if it
164   // was random, but maybe this 164   // was random, but maybe this
165   // is good enough. 165   // is good enough.
HITCBC 166   34886 p->salt = reinterpret_cast< 166   34887 p->salt = reinterpret_cast<
167   std::uintptr_t>(p); 167   std::uintptr_t>(p);
168   } 168   }
HITCBC 169   35375 return p; 169   35376 return p;
170   } 170   }
171   171  
172   //---------------------------------------------------------- 172   //----------------------------------------------------------
173   173  
174   void 174   void
HITCBC 175   374 object:: 175   374 object::
176   revert_construct:: 176   revert_construct::
177   destroy() noexcept 177   destroy() noexcept
178   { 178   {
HITCBC 179   374 obj_->destroy(); 179   374 obj_->destroy();
HITCBC 180   374 } 180   374 }
181   181  
182   //---------------------------------------------------------- 182   //----------------------------------------------------------
183   183  
184   void 184   void
HITCBC 185   230 object:: 185   231 object::
186   revert_insert:: 186   revert_insert::
187   destroy() noexcept 187   destroy() noexcept
188   { 188   {
ECB 189 - 230 obj_->destroy( 189 + // when no reallocation happened, insert_impl linked each rolled-back
ECB 190 - 230 &(*obj_->t_)[size_], 190 + // element into a bucket of the live table; unlink them while their keys
ECB 191 - 230 obj_->end()); 191 + // are still valid, otherwise a bucket head is left pointing at a slot
  192 + // that is about to be destroyed
HITGNC   193 + 231 if( !t_ && !obj_->t_->is_small() )
  194 + {
HITGNC   195 + 58 key_value_pair* const first = &(*obj_->t_)[size_];
HITGNC   196 + 58 key_value_pair* last = obj_->end();
HITGNC   197 + 574 while( last != first )
  198 + {
HITGNC   199 + 516 --last;
HITGNC   200 + 516 obj_->remove( obj_->t_->bucket( last->key() ), *last );
  201 + }
  202 + }
HITGNC   203 + 231 if(! obj_->sp_.is_not_shared_and_deallocate_is_trivial())
HITGNC   204 + 230 obj_->destroy(
HITGNC   205 + 230 &(*obj_->t_)[size_],
HITGNC   206 + 230 obj_->end());
HITCBC 192   230 } 207   231 }
193   208  
194   //---------------------------------------------------------- 209   //----------------------------------------------------------
195   // 210   //
196   // Construction 211   // Construction
197   // 212   //
198   //---------------------------------------------------------- 213   //----------------------------------------------------------
199   214  
HITCBC 200   34880 object:: 215   34880 object::
HITCBC 201   34880 object(detail::unchecked_object&& uo) 216   34880 object(detail::unchecked_object&& uo)
HITCBC 202   34880 : sp_(uo.storage()) 217   34880 : sp_(uo.storage())
203   { 218   {
HITCBC 204   34880 if(uo.size() == 0) 219   34880 if(uo.size() == 0)
205   { 220   {
HITCBC 206   1049 t_ = &empty_; 221   1049 t_ = &empty_;
HITCBC 207   1049 return; 222   1049 return;
208   } 223   }
209   // should already be checked 224   // should already be checked
HITCBC 210   33831 BOOST_ASSERT( 225   33831 BOOST_ASSERT(
211   uo.size() <= max_size()); 226   uo.size() <= max_size());
HITCBC 212   33831 t_ = table::allocate( 227   33831 t_ = table::allocate(
HITCBC 213   33831 uo.size(), 0, sp_); 228   33831 uo.size(), 0, sp_);
214   229  
215   // insert all elements, keeping 230   // insert all elements, keeping
216   // the last of any duplicate keys. 231   // the last of any duplicate keys.
HITCBC 217   33792 auto dest = begin(); 232   33792 auto dest = begin();
HITCBC 218   33792 auto src = uo.release(); 233   33792 auto src = uo.release();
HITCBC 219   33792 auto const end = src + 2 * uo.size(); 234   33792 auto const end = src + 2 * uo.size();
HITCBC 220   33792 if(t_->is_small()) 235   33792 if(t_->is_small())
221   { 236   {
HITCBC 222   33759 t_->size = 0; 237   33759 t_->size = 0;
HITCBC 223   70269 while(src != end) 238   70269 while(src != end)
224   { 239   {
HITCBC 225   36510 access::construct_key_value_pair( 240   36510 access::construct_key_value_pair(
HITCBC 226   36510 dest, pilfer(src[0]), pilfer(src[1])); 241   36510 dest, pilfer(src[0]), pilfer(src[1]));
HITCBC 227   36510 src += 2; 242   36510 src += 2;
HITCBC 228   36510 auto result = detail::find_in_object(*this, dest->key()); 243   36510 auto result = detail::find_in_object(*this, dest->key());
HITCBC 229   36510 if(! result.first) 244   36510 if(! result.first)
230   { 245   {
HITCBC 231   36500 ++dest; 246   36500 ++dest;
HITCBC 232   36500 ++t_->size; 247   36500 ++t_->size;
HITCBC 233   36500 continue; 248   36500 continue;
234   } 249   }
235   // handle duplicate 250   // handle duplicate
HITCBC 236   10 auto& v = *result.first; 251   10 auto& v = *result.first;
237   // don't bother to check if 252   // don't bother to check if
238   // storage deallocate is trivial 253   // storage deallocate is trivial
HITCBC 239   10 v.~key_value_pair(); 254   10 v.~key_value_pair();
240   // trivial relocate 255   // trivial relocate
HITCBC 241   10 std::memcpy( 256   10 std::memcpy(
242   static_cast<void*>(&v), 257   static_cast<void*>(&v),
243   dest, sizeof(v)); 258   dest, sizeof(v));
244   } 259   }
HITCBC 245   33759 return; 260   33759 return;
246   } 261   }
HITCBC 247   1674 while(src != end) 262   1674 while(src != end)
248   { 263   {
HITCBC 249   1641 access::construct_key_value_pair( 264   1641 access::construct_key_value_pair(
HITCBC 250   1641 dest, pilfer(src[0]), pilfer(src[1])); 265   1641 dest, pilfer(src[0]), pilfer(src[1]));
HITCBC 251   1641 src += 2; 266   1641 src += 2;
HITCBC 252   1641 auto& head = t_->bucket(dest->key()); 267   1641 auto& head = t_->bucket(dest->key());
HITCBC 253   1641 auto i = head; 268   1641 auto i = head;
254   for(;;) 269   for(;;)
255   { 270   {
HITCBC 256   2366 if(i == null_index_) 271   2451 if(i == null_index_)
257   { 272   {
258   // end of bucket 273   // end of bucket
HITCBC 259   1640 access::next( 274   1640 access::next(
HITCBC 260   1640 *dest) = head; 275   1640 *dest) = head;
HITCBC 261   1640 head = static_cast<index_t>( 276   1640 head = static_cast<index_t>(
HITCBC 262   1640 dest - begin()); 277   1640 dest - begin());
HITCBC 263   1640 ++dest; 278   1640 ++dest;
HITCBC 264   1640 break; 279   1640 break;
265   } 280   }
HITCBC 266   726 auto& v = (*t_)[i]; 281   811 auto& v = (*t_)[i];
HITCBC 267   726 if(v.key() != dest->key()) 282   811 if(v.key() != dest->key())
268   { 283   {
HITCBC 269   725 i = access::next(v); 284   810 i = access::next(v);
HITCBC 270   725 continue; 285   810 continue;
271   } 286   }
272   287  
273   // handle duplicate 288   // handle duplicate
HITCBC 274   1 access::next(*dest) = 289   1 access::next(*dest) =
HITCBC 275   1 access::next(v); 290   1 access::next(v);
276   // don't bother to check if 291   // don't bother to check if
277   // storage deallocate is trivial 292   // storage deallocate is trivial
HITCBC 278   1 v.~key_value_pair(); 293   1 v.~key_value_pair();
279   // trivial relocate 294   // trivial relocate
HITCBC 280   1 std::memcpy( 295   1 std::memcpy(
281   static_cast<void*>(&v), 296   static_cast<void*>(&v),
282   dest, sizeof(v)); 297   dest, sizeof(v));
HITCBC 283   1 break; 298   1 break;
HITCBC 284   725 } 299   810 }
285   } 300   }
HITCBC 286   33 t_->size = static_cast< 301   33 t_->size = static_cast<
HITCBC 287   33 index_t>(dest - begin()); 302   33 index_t>(dest - begin());
HITCBC 288   39 } 303   39 }
289   304  
HITCBC 290   35949 object:: 305   35950 object::
HITCBC 291   34398 ~object() noexcept 306   34398 ~object() noexcept
292   { 307   {
HITCBC 293   35949 if(sp_.is_not_shared_and_deallocate_is_trivial()) 308   35950 if(sp_.is_not_shared_and_deallocate_is_trivial())
HITCBC 294   5 return; 309   6 return;
HITCBC 295   35944 if(t_->capacity == 0) 310   35944 if(t_->capacity == 0)
HITCBC 296   1546 return; 311   1546 return;
HITCBC 297   34398 destroy(); 312   34398 destroy();
HITCBC 298   35949 } 313   35950 }
299   314  
HITCBC 300   7 object:: 315   7 object::
301   object( 316   object(
302   std::size_t min_capacity, 317   std::size_t min_capacity,
HITCBC 303   7 storage_ptr sp) 318   7 storage_ptr sp)
HITCBC 304   7 : sp_(std::move(sp)) 319   7 : sp_(std::move(sp))
HITCBC 305   7 , t_(&empty_) 320   7 , t_(&empty_)
306   { 321   {
HITCBC 307   7 reserve(min_capacity); 322   7 reserve(min_capacity);
HITCBC 308   7 } 323   7 }
309   324  
HITCBC 310   71 object:: 325   71 object::
HITCBC 311   71 object(object&& other) noexcept 326   71 object(object&& other) noexcept
HITCBC 312   71 : sp_(other.sp_) 327   71 : sp_(other.sp_)
HITCBC 313   142 , t_(detail::exchange( 328   142 , t_(detail::exchange(
HITCBC 314   71 other.t_, &empty_)) 329   71 other.t_, &empty_))
315   { 330   {
HITCBC 316   71 } 331   71 }
317   332  
HITCBC 318   184 object:: 333   184 object::
319   object( 334   object(
320   object&& other, 335   object&& other,
HITCBC 321   184 storage_ptr sp) 336   184 storage_ptr sp)
HITCBC 322   184 : sp_(std::move(sp)) 337   184 : sp_(std::move(sp))
323   { 338   {
HITCBC 324   184 if(*sp_ == *other.sp_) 339   184 if(*sp_ == *other.sp_)
325   { 340   {
HITCBC 326   192 t_ = detail::exchange( 341   192 t_ = detail::exchange(
HITCBC 327   96 other.t_, &empty_); 342   96 other.t_, &empty_);
HITCBC 328   96 return; 343   96 return;
329   } 344   }
330   345  
HITCBC 331   88 t_ = &empty_; 346   88 t_ = &empty_;
HITCBC 332   151 object(other, sp_).swap(*this); 347   151 object(other, sp_).swap(*this);
HITCBC 333   63 } 348   63 }
334   349  
HITCBC 335   197 object:: 350   197 object::
336   object( 351   object(
337   object const& other, 352   object const& other,
HITCBC 338   197 storage_ptr sp) 353   197 storage_ptr sp)
HITCBC 339   197 : sp_(std::move(sp)) 354   197 : sp_(std::move(sp))
HITCBC 340   197 , t_(&empty_) 355   197 , t_(&empty_)
341   { 356   {
HITCBC 342   197 reserve(other.size()); 357   197 reserve(other.size());
HITCBC 343   185 revert_construct r(*this); 358   185 revert_construct r(*this);
HITCBC 344   185 if(t_->is_small()) 359   185 if(t_->is_small())
345   { 360   {
HITCBC 346   712 for(auto const& v : other) 361   712 for(auto const& v : other)
347   { 362   {
HITCBC 348   724 ::new(end()) 363   724 ::new(end())
HITCBC 349   800 key_value_pair(v, sp_); 364   800 key_value_pair(v, sp_);
HITCBC 350   572 ++t_->size; 365   572 ++t_->size;
351   } 366   }
HITCBC 352   64 r.commit(); 367   64 r.commit();
HITCBC 353   64 return; 368   64 return;
354   } 369   }
HITCBC 355   2485 for(auto const& v : other) 370   2485 for(auto const& v : other)
356   { 371   {
357   // skip duplicate checking 372   // skip duplicate checking
358   auto& head = 373   auto& head =
HITCBC 359   2480 t_->bucket(v.key()); 374   2480 t_->bucket(v.key());
HITCBC 360   2480 auto pv = ::new(end()) 375   2480 auto pv = ::new(end())
HITCBC 361   2520 key_value_pair(v, sp_); 376   2520 key_value_pair(v, sp_);
HITCBC 362   2440 access::next(*pv) = head; 377   2440 access::next(*pv) = head;
HITCBC 363   2440 head = t_->size; 378   2440 head = t_->size;
HITCBC 364   2440 ++t_->size; 379   2440 ++t_->size;
365   } 380   }
HITCBC 366   5 r.commit(); 381   5 r.commit();
HITCBC 367   313 } 382   313 }
368   383  
HITCBC 369   382 object:: 384   382 object::
370   object( 385   object(
371   std::initializer_list<std::pair< 386   std::initializer_list<std::pair<
372   string_view, value_ref>> init, 387   string_view, value_ref>> init,
373   std::size_t min_capacity, 388   std::size_t min_capacity,
HITCBC 374   382 storage_ptr sp) 389   382 storage_ptr sp)
HITCBC 375   382 : sp_(std::move(sp)) 390   382 : sp_(std::move(sp))
HITCBC 376   382 , t_(&empty_) 391   382 , t_(&empty_)
377   { 392   {
HITCBC 378   382 if( min_capacity < init.size()) 393   382 if( min_capacity < init.size())
HITCBC 379   336 min_capacity = init.size(); 394   336 min_capacity = init.size();
HITCBC 380   382 reserve(min_capacity); 395   382 reserve(min_capacity);
HITCBC 381   366 revert_construct r(*this); 396   366 revert_construct r(*this);
HITCBC 382   366 insert(init); 397   366 insert(init);
HITCBC 383   253 r.commit(); 398   253 r.commit();
HITCBC 384   495 } 399   495 }
385   400  
386   //---------------------------------------------------------- 401   //----------------------------------------------------------
387   // 402   //
388   // Assignment 403   // Assignment
389   // 404   //
390   //---------------------------------------------------------- 405   //----------------------------------------------------------
391   406  
392   object& 407   object&
HITCBC 393   22 object:: 408   22 object::
394   operator=(object const& other) 409   operator=(object const& other)
395   { 410   {
HITCBC 396   39 object tmp(other, sp_); 411   39 object tmp(other, sp_);
HITCBC 397   5 this->~object(); 412   5 this->~object();
HITCBC 398   5 ::new(this) object(pilfer(tmp)); 413   5 ::new(this) object(pilfer(tmp));
HITCBC 399   5 return *this; 414   5 return *this;
HITCBC 400   5 } 415   5 }
401   416  
402   object& 417   object&
HITCBC 403   7 object:: 418   7 object::
404   operator=(object&& other) 419   operator=(object&& other)
405   { 420   {
HITCBC 406   11 object tmp(std::move(other), sp_); 421   11 object tmp(std::move(other), sp_);
HITCBC 407   3 this->~object(); 422   3 this->~object();
HITCBC 408   3 ::new(this) object(pilfer(tmp)); 423   3 ::new(this) object(pilfer(tmp));
HITCBC 409   3 return *this; 424   3 return *this;
HITCBC 410   3 } 425   3 }
411   426  
412   object& 427   object&
HITCBC 413   7 object:: 428   7 object::
414   operator=( 429   operator=(
415   std::initializer_list<std::pair< 430   std::initializer_list<std::pair<
416   string_view, value_ref>> init) 431   string_view, value_ref>> init)
417   { 432   {
HITCBC 418   11 object tmp(init, sp_); 433   11 object tmp(init, sp_);
HITCBC 419   3 this->~object(); 434   3 this->~object();
HITCBC 420   3 ::new(this) object(pilfer(tmp)); 435   3 ::new(this) object(pilfer(tmp));
HITCBC 421   3 return *this; 436   3 return *this;
HITCBC 422   3 } 437   3 }
423   438  
424   //---------------------------------------------------------- 439   //----------------------------------------------------------
425   // 440   //
426   // Lookup 441   // Lookup
427   // 442   //
428   //---------------------------------------------------------- 443   //----------------------------------------------------------
429   444  
430   system::result<value&> 445   system::result<value&>
HITCBC 431   4 object:: 446   4 object::
432   try_at(string_view key) noexcept 447   try_at(string_view key) noexcept
433   { 448   {
HITCBC 434   4 auto it = find(key); 449   4 auto it = find(key);
HITCBC 435   4 if( it != end() ) 450   4 if( it != end() )
HITCBC 436   2 return it->value(); 451   2 return it->value();
437   452  
HITCBC 438   2 system::error_code ec; 453   2 system::error_code ec;
HITCBC 439   2 BOOST_JSON_FAIL(ec, error::out_of_range); 454   2 BOOST_JSON_FAIL(ec, error::out_of_range);
HITCBC 440   2 return ec; 455   2 return ec;
441   } 456   }
442   457  
443   system::result<value const&> 458   system::result<value const&>
HITCBC 444   109 object:: 459   109 object::
445   try_at(string_view key) const noexcept 460   try_at(string_view key) const noexcept
446   { 461   {
HITCBC 447   109 auto it = find(key); 462   109 auto it = find(key);
HITCBC 448   109 if( it != end() ) 463   109 if( it != end() )
HITCBC 449   103 return it->value(); 464   103 return it->value();
450   465  
HITCBC 451   6 system::error_code ec; 466   6 system::error_code ec;
HITCBC 452   6 BOOST_JSON_FAIL(ec, error::out_of_range); 467   6 BOOST_JSON_FAIL(ec, error::out_of_range);
HITCBC 453   6 return ec; 468   6 return ec;
454   } 469   }
455   470  
456   value const& 471   value const&
HITCBC 457   105 object:: 472   105 object::
458   at(string_view key, source_location const& loc) const& 473   at(string_view key, source_location const& loc) const&
459   { 474   {
HITCBC 460   105 return try_at(key).value(loc); 475   105 return try_at(key).value(loc);
461   } 476   }
462   477  
463   //---------------------------------------------------------- 478   //----------------------------------------------------------
464   // 479   //
465   // Modifiers 480   // Modifiers
466   // 481   //
467   //---------------------------------------------------------- 482   //----------------------------------------------------------
468   483  
469   void 484   void
HITCBC 470   7 object:: 485   7 object::
471   clear() noexcept 486   clear() noexcept
472   { 487   {
HITCBC 473   7 if(empty()) 488   7 if(empty())
HITCBC 474   2 return; 489   2 return;
HITCBC 475   5 if(! sp_.is_not_shared_and_deallocate_is_trivial()) 490   5 if(! sp_.is_not_shared_and_deallocate_is_trivial())
HITCBC 476   5 destroy(begin(), end()); 491   5 destroy(begin(), end());
HITCBC 477   5 if(! t_->is_small()) 492   5 if(! t_->is_small())
HITCBC 478   4 t_->clear(); 493   4 t_->clear();
HITCBC 479   5 t_->size = 0; 494   5 t_->size = 0;
480   } 495   }
481   496  
482   void 497   void
HITCBC 483   426 object:: 498   426 object::
484   insert( 499   insert(
485   std::initializer_list<std::pair< 500   std::initializer_list<std::pair<
486   string_view, value_ref>> init) 501   string_view, value_ref>> init)
487   { 502   {
HITCBC 488   426 auto const n0 = size(); 503   426 auto const n0 = size();
HITCBC 489   426 if(init.size() > max_size() - n0) 504   426 if(init.size() > max_size() - n0)
490   { 505   {
491   BOOST_STATIC_CONSTEXPR source_location loc = BOOST_CURRENT_LOCATION; 506   BOOST_STATIC_CONSTEXPR source_location loc = BOOST_CURRENT_LOCATION;
HITCBC 492   1 detail::throw_system_error( error::object_too_large, &loc ); 507   1 detail::throw_system_error( error::object_too_large, &loc );
493   } 508   }
HITCBC 494   425 revert_insert r( *this, n0 + init.size() ); 509   425 revert_insert r( *this, n0 + init.size() );
HITCBC 495   418 if(t_->is_small()) 510   418 if(t_->is_small())
496   { 511   {
HITCBC 497   2035 for(auto& iv : init) 512   2035 for(auto& iv : init)
498   { 513   {
499   auto result = 514   auto result =
HITCBC 500   1834 detail::find_in_object(*this, iv.first); 515   1834 detail::find_in_object(*this, iv.first);
HITCBC 501   1834 if(result.first) 516   1834 if(result.first)
502   { 517   {
503   // ignore duplicate 518   // ignore duplicate
HITCBC 504   4 continue; 519   4 continue;
505   } 520   }
HITCBC 506   1907 ::new(end()) key_value_pair( 521   1907 ::new(end()) key_value_pair(
507   iv.first, 522   iv.first,
HITCBC 508   2058 iv.second.make_value(sp_)); 523   2058 iv.second.make_value(sp_));
HITCBC 509   1753 ++t_->size; 524   1753 ++t_->size;
510   } 525   }
HITCBC 511   201 r.commit(); 526   201 r.commit();
HITCBC 512   201 return; 527   201 return;
513   } 528   }
HITCBC 514   1999 for(auto& iv : init) 529   1999 for(auto& iv : init)
515   { 530   {
HITCBC 516   1939 auto& head = t_->bucket(iv.first); 531   1939 auto& head = t_->bucket(iv.first);
HITCBC 517   1939 auto i = head; 532   1939 auto i = head;
518   for(;;) 533   for(;;)
519   { 534   {
HITCBC 520   2749 if(i == null_index_) 535   2391 if(i == null_index_)
521   { 536   {
522   // VFALCO value_ref should construct 537   // VFALCO value_ref should construct
523   // a key_value_pair using placement 538   // a key_value_pair using placement
HITCBC 524   1937 auto& v = *::new(end()) 539   1937 auto& v = *::new(end())
525   key_value_pair( 540   key_value_pair(
526   iv.first, 541   iv.first,
HITCBC 527   2097 iv.second.make_value(sp_)); 542   2097 iv.second.make_value(sp_));
HITCBC 528   1857 access::next(v) = head; 543   1857 access::next(v) = head;
HITCBC 529   1857 head = static_cast<index_t>( 544   1857 head = static_cast<index_t>(
HITCBC 530   1857 t_->size); 545   1857 t_->size);
HITCBC 531   1857 ++t_->size; 546   1857 ++t_->size;
HITCBC 532   1857 break; 547   1857 break;
533   } 548   }
HITCBC 534   812 auto& v = (*t_)[i]; 549   454 auto& v = (*t_)[i];
HITCBC 535   812 if(v.key() == iv.first) 550   454 if(v.key() == iv.first)
536   { 551   {
537   // ignore duplicate 552   // ignore duplicate
HITCBC 538   2 break; 553   2 break;
539   } 554   }
HITCBC 540   810 i = access::next(v); 555   452 i = access::next(v);
HITCBC 541   810 } 556   452 }
542   } 557   }
HITCBC 543   60 r.commit(); 558   60 r.commit();
HITCBC 544   418 } 559   418 }
545   560  
546   auto 561   auto
HITCBC 547   6 object:: 562   6 object::
548   erase(const_iterator pos) noexcept -> 563   erase(const_iterator pos) noexcept ->
549   iterator 564   iterator
550   { 565   {
HITCBC 551   6 return do_erase(pos, 566   6 return do_erase(pos,
HITCBC 552   2 [this](iterator p) { 567   2 [this](iterator p) {
553   // the casts silence warnings 568   // the casts silence warnings
HITCBC 554   2 std::memcpy( 569   2 std::memcpy(
555   static_cast<void*>(p), 570   static_cast<void*>(p),
HITCBC 556   2 static_cast<void const*>(end()), 571   2 static_cast<void const*>(end()),
557   sizeof(*p)); 572   sizeof(*p));
HITCBC 558   2 }, 573   2 },
HITCBC 559   3 [this](iterator p) { 574   3 [this](iterator p) {
HITCBC 560   3 reindex_relocate(end(), p); 575   3 reindex_relocate(end(), p);
HITCBC 561   6 }); 576   6 });
562   } 577   }
563   578  
564   auto 579   auto
HITCBC 565   5 object:: 580   5 object::
566   erase(string_view key) noexcept -> 581   erase(string_view key) noexcept ->
567   std::size_t 582   std::size_t
568   { 583   {
HITCBC 569   5 auto it = find(key); 584   5 auto it = find(key);
HITCBC 570   5 if(it == end()) 585   5 if(it == end())
HITCBC 571   1 return 0; 586   1 return 0;
HITCBC 572   4 erase(it); 587   4 erase(it);
HITCBC 573   4 return 1; 588   4 return 1;
574   } 589   }
575   590  
576   auto 591   auto
HITCBC 577   3 object:: 592   3 object::
578   stable_erase(const_iterator pos) noexcept -> 593   stable_erase(const_iterator pos) noexcept ->
579   iterator 594   iterator
580   { 595   {
HITCBC 581   3 return do_erase(pos, 596   3 return do_erase(pos,
HITCBC 582   2 [this](iterator p) { 597   2 [this](iterator p) {
583   // the casts silence warnings 598   // the casts silence warnings
HITCBC 584   2 std::memmove( 599   2 std::memmove(
585   static_cast<void*>(p), 600   static_cast<void*>(p),
HITCBC 586   2 static_cast<void const*>(p + 1), 601   2 static_cast<void const*>(p + 1),
HITCBC 587   2 sizeof(*p) * (end() - p)); 602   2 sizeof(*p) * (end() - p));
HITCBC 588   2 }, 603   2 },
HITCBC 589   1 [this](iterator p) { 604   1 [this](iterator p) {
HITCBC 590   10 for (; p != end(); ++p) 605   10 for (; p != end(); ++p)
591   { 606   {
HITCBC 592   9 reindex_relocate(p + 1, p); 607   9 reindex_relocate(p + 1, p);
593   } 608   }
HITCBC 594   3 }); 609   3 });
595   } 610   }
596   611  
597   auto 612   auto
HITCBC 598   2 object:: 613   2 object::
599   stable_erase(string_view key) noexcept -> 614   stable_erase(string_view key) noexcept ->
600   std::size_t 615   std::size_t
601   { 616   {
HITCBC 602   2 auto it = find(key); 617   2 auto it = find(key);
HITCBC 603   2 if(it == end()) 618   2 if(it == end())
HITCBC 604   1 return 0; 619   1 return 0;
HITCBC 605   1 stable_erase(it); 620   1 stable_erase(it);
HITCBC 606   1 return 1; 621   1 return 1;
607   } 622   }
608   623  
609   void 624   void
HITCBC 610   36 object:: 625   36 object::
611   swap(object& other) 626   swap(object& other)
612   { 627   {
HITCBC 613   36 if(*sp_ == *other.sp_) 628   36 if(*sp_ == *other.sp_)
614   { 629   {
HITCBC 615   52 t_ = detail::exchange( 630   52 t_ = detail::exchange(
HITCBC 616   26 other.t_, t_); 631   26 other.t_, t_);
HITCBC 617   26 return; 632   26 return;
618   } 633   }
619   object temp1( 634   object temp1(
HITCBC 620   10 std::move(*this), 635   10 std::move(*this),
HITCBC 621   24 other.storage()); 636   24 other.storage());
622   object temp2( 637   object temp2(
HITCBC 623   6 std::move(other), 638   6 std::move(other),
HITCBC 624   16 this->storage()); 639   16 this->storage());
HITCBC 625   2 other.~object(); 640   2 other.~object();
HITCBC 626   2 ::new(&other) object(pilfer(temp1)); 641   2 ::new(&other) object(pilfer(temp1));
HITCBC 627   2 this->~object(); 642   2 this->~object();
HITCBC 628   2 ::new(this) object(pilfer(temp2)); 643   2 ::new(this) object(pilfer(temp2));
HITCBC 629   6 } 644   6 }
630   645  
631   //---------------------------------------------------------- 646   //----------------------------------------------------------
632   // 647   //
633   // Lookup 648   // Lookup
634   // 649   //
635   //---------------------------------------------------------- 650   //----------------------------------------------------------
636   651  
637   auto 652   auto
HITCBC 638   146 object:: 653   147 object::
639   operator[](string_view key) -> 654   operator[](string_view key) ->
640   value& 655   value&
641   { 656   {
642   auto const result = 657   auto const result =
HITCBC 643   146 emplace(key, nullptr); 658   147 emplace(key, nullptr);
HITCBC 644   292 return result.first->value(); 659   294 return result.first->value();
645   } 660   }
646   661  
647   auto 662   auto
HITCBC 648   8 object:: 663   8 object::
649   count(string_view key) const noexcept -> 664   count(string_view key) const noexcept ->
650   std::size_t 665   std::size_t
651   { 666   {
HITCBC 652   8 if(find(key) == end()) 667   8 if(find(key) == end())
HITCBC 653   3 return 0; 668   3 return 0;
HITCBC 654   5 return 1; 669   5 return 1;
655   } 670   }
656   671  
657   auto 672   auto
HITCBC 658   27 object:: 673   31 object::
659   find(string_view key) noexcept -> 674   find(string_view key) noexcept ->
660   iterator 675   iterator
661   { 676   {
HITCBC 662   27 if(empty()) 677   31 if(empty())
HITCBC 663   1 return end(); 678   1 return end();
664   auto const p = 679   auto const p =
HITCBC 665   26 detail::find_in_object(*this, key).first; 680   30 detail::find_in_object(*this, key).first;
HITCBC 666   26 if(p) 681   30 if(p)
HITCBC 667   20 return p; 682   21 return p;
HITCBC 668   6 return end(); 683   9 return end();
669   } 684   }
670   685  
671   auto 686   auto
HITCBC 672   880 object:: 687   880 object::
673   find(string_view key) const noexcept -> 688   find(string_view key) const noexcept ->
674   const_iterator 689   const_iterator
675   { 690   {
HITCBC 676   880 if(empty()) 691   880 if(empty())
HITCBC 677   1 return end(); 692   1 return end();
678   auto const p = 693   auto const p =
HITCBC 679   879 detail::find_in_object(*this, key).first; 694   879 detail::find_in_object(*this, key).first;
HITCBC 680   879 if(p) 695   879 if(p)
HITCBC 681   867 return p; 696   867 return p;
HITCBC 682   12 return end(); 697   12 return end();
683   } 698   }
684   699  
685   bool 700   bool
HITCBC 686   3 object:: 701   3 object::
687   contains( 702   contains(
688   string_view key) const noexcept 703   string_view key) const noexcept
689   { 704   {
HITCBC 690   3 if(empty()) 705   3 if(empty())
HITCBC 691   1 return false; 706   1 return false;
HITCBC 692   2 return detail::find_in_object(*this, key).first 707   2 return detail::find_in_object(*this, key).first
HITCBC 693   2 != nullptr; 708   2 != nullptr;
694   } 709   }
695   710  
696   value const* 711   value const*
HITCBC 697   3 object:: 712   3 object::
698   if_contains( 713   if_contains(
699   string_view key) const noexcept 714   string_view key) const noexcept
700   { 715   {
HITCBC 701   3 auto const it = find(key); 716   3 auto const it = find(key);
HITCBC 702   3 if(it != end()) 717   3 if(it != end())
HITCBC 703   2 return &it->value(); 718   2 return &it->value();
HITCBC 704   1 return nullptr; 719   1 return nullptr;
705   } 720   }
706   721  
707   value* 722   value*
HITCBC 708   5 object:: 723   5 object::
709   if_contains( 724   if_contains(
710   string_view key) noexcept 725   string_view key) noexcept
711   { 726   {
HITCBC 712   5 auto const it = find(key); 727   5 auto const it = find(key);
HITCBC 713   5 if(it != end()) 728   5 if(it != end())
HITCBC 714   4 return &it->value(); 729   4 return &it->value();
HITCBC 715   1 return nullptr; 730   1 return nullptr;
716   } 731   }
717   732  
718   //---------------------------------------------------------- 733   //----------------------------------------------------------
719   // 734   //
720   // (private) 735   // (private)
721   // 736   //
722   //---------------------------------------------------------- 737   //----------------------------------------------------------
723   738  
724   key_value_pair* 739   key_value_pair*
HITCBC 725   3781 object:: 740   3784 object::
726   insert_impl( 741   insert_impl(
727   pilfered<key_value_pair> p, 742   pilfered<key_value_pair> p,
728   std::size_t hash) 743   std::size_t hash)
729   { 744   {
HITCBC 730   3781 BOOST_ASSERT( 745   3784 BOOST_ASSERT(
731   capacity() > size()); 746   capacity() > size());
HITCBC 732   3781 if(t_->is_small()) 747   3784 if(t_->is_small())
733   { 748   {
HITCBC 734   2194 auto const pv = ::new(end()) 749   2194 auto const pv = ::new(end())
HITCBC 735   2194 key_value_pair(p); 750   2194 key_value_pair(p);
HITCBC 736   2194 ++t_->size; 751   2194 ++t_->size;
HITCBC 737   2194 return pv; 752   2194 return pv;
738   } 753   }
739   auto& head = 754   auto& head =
HITCBC 740   1587 t_->bucket(hash); 755   1590 t_->bucket(hash);
HITCBC 741   1587 auto const pv = ::new(end()) 756   1590 auto const pv = ::new(end())
HITCBC 742   1587 key_value_pair(p); 757   1590 key_value_pair(p);
HITCBC 743   1587 access::next(*pv) = head; 758   1590 access::next(*pv) = head;
HITCBC 744   1587 head = t_->size; 759   1590 head = t_->size;
HITCBC 745   1587 ++t_->size; 760   1590 ++t_->size;
HITCBC 746   1587 return pv; 761   1590 return pv;
747   } 762   }
748   763  
749   // allocate new table, copy elements there, and rehash them 764   // allocate new table, copy elements there, and rehash them
750   object::table* 765   object::table*
HITCBC 751   1657 object:: 766   1658 object::
752   reserve_impl(std::size_t new_capacity) 767   reserve_impl(std::size_t new_capacity)
753   { 768   {
HITCBC 754   1657 BOOST_ASSERT( 769   1658 BOOST_ASSERT(
755   new_capacity > t_->capacity); 770   new_capacity > t_->capacity);
HITCBC 756   1650 auto t = table::allocate( 771   1651 auto t = table::allocate(
757   growth(new_capacity), 772   growth(new_capacity),
HITCBC 758   1657 t_->salt, sp_); 773   1658 t_->salt, sp_);
HITCBC 759   1583 if(! empty()) 774   1584 if(! empty())
HITCBC 760   488 std::memcpy( 775   488 std::memcpy(
761   static_cast< 776   static_cast<
HITCBC 762   488 void*>(&(*t)[0]), 777   488 void*>(&(*t)[0]),
HITCBC 763   488 begin(), 778   488 begin(),
HITCBC 764   488 size() * sizeof( 779   488 size() * sizeof(
765   key_value_pair)); 780   key_value_pair));
HITCBC 766   1583 t->size = t_->size; 781   1584 t->size = t_->size;
HITCBC 767   1583 std::swap(t_, t); 782   1584 std::swap(t_, t);
768   783  
HITCBC 769   1583 if(! t_->is_small()) 784   1584 if(! t_->is_small())
770   { 785   {
771   // rebuild hash table, 786   // rebuild hash table,
772   // without dup checks 787   // without dup checks
HITCBC 773   355 auto p = end(); 788   356 auto p = end();
HITCBC 774   355 index_t i = t_->size; 789   356 index_t i = t_->size;
HITCBC 775   1360 while(i-- > 0) 790   1361 while(i-- > 0)
776   { 791   {
HITCBC 777   1005 --p; 792   1005 --p;
778   auto& head = 793   auto& head =
HITCBC 779   1005 t_->bucket(p->key()); 794   1005 t_->bucket(p->key());
HITCBC 780   1005 access::next(*p) = head; 795   1005 access::next(*p) = head;
HITCBC 781   1005 head = i; 796   1005 head = i;
782   } 797   }
783   } 798   }
784   799  
HITCBC 785   1583 return t; 800   1584 return t;
786   } 801   }
787   802  
788   bool 803   bool
HITCBC 789   75 object:: 804   75 object::
790   equal(object const& other) const noexcept 805   equal(object const& other) const noexcept
791   { 806   {
HITCBC 792   75 if(size() != other.size()) 807   75 if(size() != other.size())
HITCBC 793   5 return false; 808   5 return false;
HITCBC 794   70 auto const end_ = other.end(); 809   70 auto const end_ = other.end();
HITCBC 795   825 for(auto e : *this) 810   825 for(auto e : *this)
796   { 811   {
HITCBC 797   757 auto it = other.find(e.key()); 812   757 auto it = other.find(e.key());
HITCBC 798   757 if(it == end_) 813   757 if(it == end_)
HITCBC 799   1 return false; 814   1 return false;
HITCBC 800   756 if(it->value() != e.value()) 815   756 if(it->value() != e.value())
HITCBC 801   1 return false; 816   1 return false;
HITCBC 802   757 } 817   757 }
HITCBC 803   68 return true; 818   68 return true;
804   } 819   }
805   820  
806   std::size_t 821   std::size_t
HITCBC 807   1657 object:: 822   1658 object::
808   growth( 823   growth(
809   std::size_t new_size) const 824   std::size_t new_size) const
810   { 825   {
HITCBC 811   1657 if(new_size > max_size()) 826   1658 if(new_size > max_size())
812   { 827   {
813   BOOST_STATIC_CONSTEXPR source_location loc = BOOST_CURRENT_LOCATION; 828   BOOST_STATIC_CONSTEXPR source_location loc = BOOST_CURRENT_LOCATION;
HITCBC 814   7 detail::throw_system_error( error::object_too_large, &loc ); 829   7 detail::throw_system_error( error::object_too_large, &loc );
815   } 830   }
HITCBC 816   1650 std::size_t const old = capacity(); 831   1651 std::size_t const old = capacity();
HITCBC 817   1650 if(old > max_size() - old / 2) 832   1651 if(old > max_size() - old / 2)
HITCBC 818   2 return new_size; 833   2 return new_size;
HITCBC 819   1648 std::size_t const g = 834   1649 std::size_t const g =
HITCBC 820   1648 old + old / 2; // 1.5x 835   1649 old + old / 2; // 1.5x
HITCBC 821   1648 if(g < new_size) 836   1649 if(g < new_size)
HITCBC 822   1246 return new_size; 837   1247 return new_size;
HITCBC 823   402 return g; 838   402 return g;
824   } 839   }
825   840  
826   void 841   void
HITCBC 827   17 object:: 842   533 object::
828   remove( 843   remove(
829   index_t& head, 844   index_t& head,
830   key_value_pair& v) noexcept 845   key_value_pair& v) noexcept
831   { 846   {
HITCBC 832   17 BOOST_ASSERT(! t_->is_small()); 847   533 BOOST_ASSERT(! t_->is_small());
833   auto const i = static_cast< 848   auto const i = static_cast<
HITCBC 834   17 index_t>(&v - begin()); 849   533 index_t>(&v - begin());
HITCBC 835   17 if(head == i) 850   533 if(head == i)
836   { 851   {
HITCBC 837   15 head = access::next(v); 852   529 head = access::next(v);
HITCBC 838   15 return; 853   529 return;
839   } 854   }
840   auto* pn = 855   auto* pn =
HITCBC 841   2 &access::next((*t_)[head]); 856   4 &access::next((*t_)[head]);
HITCBC 842   3 while(*pn != i) 857   5 while(*pn != i)
HITCBC 843   1 pn = &access::next((*t_)[*pn]); 858   1 pn = &access::next((*t_)[*pn]);
HITCBC 844   2 *pn = access::next(v); 859   4 *pn = access::next(v);
845   } 860   }
846   861  
847   void 862   void
HITCBC 848   34772 object:: 863   34772 object::
849   destroy() noexcept 864   destroy() noexcept
850   { 865   {
HITCBC 851   34772 BOOST_ASSERT(t_->capacity > 0); 866   34772 BOOST_ASSERT(t_->capacity > 0);
HITCBC 852   34772 BOOST_ASSERT(! sp_.is_not_shared_and_deallocate_is_trivial()); 867   34772 BOOST_ASSERT(! sp_.is_not_shared_and_deallocate_is_trivial());
HITCBC 853   34772 destroy(begin(), end()); 868   34772 destroy(begin(), end());
HITCBC 854   34772 table::deallocate(t_, sp_); 869   34772 table::deallocate(t_, sp_);
HITCBC 855   34772 } 870   34772 }
856   871  
857   void 872   void
HITCBC 858   35007 object:: 873   35007 object::
859   destroy( 874   destroy(
860   key_value_pair* first, 875   key_value_pair* first,
861   key_value_pair* last) noexcept 876   key_value_pair* last) noexcept
862   { 877   {
HITCBC 863   35007 BOOST_ASSERT(! sp_.is_not_shared_and_deallocate_is_trivial()); 878   35007 BOOST_ASSERT(! sp_.is_not_shared_and_deallocate_is_trivial());
HITCBC 864   83519 while(last != first) 879   83519 while(last != first)
HITCBC 865   48512 (--last)->~key_value_pair(); 880   48512 (--last)->~key_value_pair();
HITCBC 866   35007 } 881   35007 }
867   882  
868   template<class FS, class FB> 883   template<class FS, class FB>
869   auto 884   auto
HITCBC 870   9 object:: 885   9 object::
871   do_erase( 886   do_erase(
872   const_iterator pos, 887   const_iterator pos,
873   FS small_reloc, 888   FS small_reloc,
874   FB big_reloc) noexcept 889   FB big_reloc) noexcept
875   -> iterator 890   -> iterator
876   { 891   {
HITCBC 877   9 auto p = begin() + (pos - begin()); 892   9 auto p = begin() + (pos - begin());
HITCBC 878   9 if(t_->is_small()) 893   9 if(t_->is_small())
879   { 894   {
HITCBC 880   4 p->~value_type(); 895   4 p->~value_type();
HITCBC 881   4 --t_->size; 896   4 --t_->size;
HITCBC 882   4 if(p != end()) 897   4 if(p != end())
883   { 898   {
HITCBC 884   4 small_reloc(p); 899   4 small_reloc(p);
885   } 900   }
HITCBC 886   4 return p; 901   4 return p;
887   } 902   }
HITCBC 888   5 remove(t_->bucket(p->key()), *p); 903   5 remove(t_->bucket(p->key()), *p);
HITCBC 889   5 p->~value_type(); 904   5 p->~value_type();
HITCBC 890   5 --t_->size; 905   5 --t_->size;
HITCBC 891   5 if(p != end()) 906   5 if(p != end())
892   { 907   {
HITCBC 893   4 big_reloc(p); 908   4 big_reloc(p);
894   } 909   }
HITCBC 895   5 return p; 910   5 return p;
896   } 911   }
897   912  
898   void 913   void
HITCBC 899   12 object:: 914   12 object::
900   reindex_relocate( 915   reindex_relocate(
901   key_value_pair* src, 916   key_value_pair* src,
902   key_value_pair* dst) noexcept 917   key_value_pair* dst) noexcept
903   { 918   {
HITCBC 904   12 BOOST_ASSERT(! t_->is_small()); 919   12 BOOST_ASSERT(! t_->is_small());
HITCBC 905   12 auto& head = t_->bucket(src->key()); 920   12 auto& head = t_->bucket(src->key());
HITCBC 906   12 remove(head, *src); 921   12 remove(head, *src);
907   // the casts silence warnings 922   // the casts silence warnings
HITCBC 908   12 std::memcpy( 923   12 std::memcpy(
909   static_cast<void*>(dst), 924   static_cast<void*>(dst),
910   static_cast<void const*>(src), 925   static_cast<void const*>(src),
911   sizeof(*dst)); 926   sizeof(*dst));
HITCBC 912   12 access::next(*dst) = head; 927   12 access::next(*dst) = head;
HITCBC 913   12 head = static_cast< 928   12 head = static_cast<
HITCBC 914   12 index_t>(dst - begin()); 929   12 index_t>(dst - begin());
HITCBC 915   12 } 930   12 }
916   931  
917   } // namespace json 932   } // namespace json
918   } // namespace boost 933   } // namespace boost
919   934  
920   //---------------------------------------------------------- 935   //----------------------------------------------------------
921   // 936   //
922   // std::hash specialization 937   // std::hash specialization
923   // 938   //
924   //---------------------------------------------------------- 939   //----------------------------------------------------------
925   940  
926   std::size_t 941   std::size_t
HITCBC 927   8 std::hash<::boost::json::object>::operator()( 942   8 std::hash<::boost::json::object>::operator()(
928   ::boost::json::object const& jo) const noexcept 943   ::boost::json::object const& jo) const noexcept
929   { 944   {
HITCBC 930   8 return ::boost::hash< ::boost::json::object >()( jo ); 945   8 return ::boost::hash< ::boost::json::object >()( jo );
931   } 946   }
932   947  
933   //---------------------------------------------------------- 948   //----------------------------------------------------------
934   949  
935   950  
936   #endif 951   #endif