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