]>
Commit | Line | Data |
---|---|---|
20effc67 TL |
1 | // |
2 | // Copyright (c) 2019 Vinnie Falco (vinnie.falco@gmail.com) | |
3 | // | |
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) | |
6 | // | |
7 | // Official repository: https://github.com/boostorg/json | |
8 | // | |
9 | ||
10 | #ifndef BOOST_JSON_IMPL_OBJECT_HPP | |
11 | #define BOOST_JSON_IMPL_OBJECT_HPP | |
12 | ||
13 | #include <boost/json/value.hpp> | |
14 | #include <iterator> | |
15 | #include <cmath> | |
16 | #include <type_traits> | |
17 | #include <utility> | |
18 | ||
19 | BOOST_JSON_NS_BEGIN | |
20 | ||
21 | namespace detail { | |
22 | ||
23 | // Objects with size less than or equal | |
24 | // to this number will use a linear search | |
25 | // instead of the more expensive hash function. | |
26 | static | |
27 | constexpr | |
28 | std::size_t | |
29 | small_object_size_ = 18; | |
30 | ||
31 | BOOST_STATIC_ASSERT( | |
32 | small_object_size_ < | |
33 | BOOST_JSON_MAX_STRUCTURED_SIZE); | |
34 | ||
35 | } // detail | |
36 | ||
37 | //---------------------------------------------------------- | |
38 | ||
39 | struct alignas(key_value_pair) | |
40 | object::table | |
41 | { | |
42 | std::uint32_t size = 0; | |
43 | std::uint32_t capacity = 0; | |
44 | std::uintptr_t salt = 0; | |
45 | ||
46 | #if defined(_MSC_VER) && BOOST_JSON_ARCH == 32 | |
47 | // VFALCO If we make key_value_pair smaller, | |
48 | // then we might want to revisit this | |
49 | // padding. | |
50 | BOOST_STATIC_ASSERT( | |
51 | sizeof(key_value_pair) == 32); | |
52 | char pad[4] = {}; // silence warnings | |
53 | #endif | |
54 | ||
55 | constexpr table(); | |
56 | ||
57 | // returns true if we use a linear | |
58 | // search instead of the hash table. | |
59 | bool is_small() const noexcept | |
60 | { | |
61 | return capacity <= | |
62 | detail::small_object_size_; | |
63 | } | |
64 | ||
65 | key_value_pair& | |
66 | operator[]( | |
67 | std::size_t pos) noexcept | |
68 | { | |
69 | return reinterpret_cast< | |
70 | key_value_pair*>( | |
71 | this + 1)[pos]; | |
72 | } | |
73 | ||
74 | // VFALCO This is exported for tests | |
75 | BOOST_JSON_DECL | |
76 | std::size_t | |
77 | digest(string_view key) const noexcept; | |
78 | ||
79 | inline | |
80 | index_t& | |
81 | bucket(std::size_t hash) noexcept; | |
82 | ||
83 | inline | |
84 | index_t& | |
85 | bucket(string_view key) noexcept; | |
86 | ||
87 | inline | |
88 | void | |
89 | clear() noexcept; | |
90 | ||
91 | static | |
92 | inline | |
93 | table* | |
94 | allocate( | |
95 | std::size_t capacity, | |
96 | std::uintptr_t salt, | |
97 | storage_ptr const& sp); | |
98 | ||
99 | static | |
100 | void | |
101 | deallocate( | |
102 | table* p, | |
103 | storage_ptr const& sp) noexcept | |
104 | { | |
105 | if(p->capacity == 0) | |
106 | return; | |
107 | if(p->is_small()) | |
108 | sp->deallocate(p, | |
109 | sizeof(table) + p->capacity * ( | |
110 | sizeof(key_value_pair) + | |
111 | sizeof(index_t))); | |
112 | else | |
113 | sp->deallocate(p, | |
114 | sizeof(table) + p->capacity * | |
115 | sizeof(key_value_pair)); | |
116 | } | |
117 | }; | |
118 | ||
119 | //---------------------------------------------------------- | |
120 | ||
121 | class object::revert_construct | |
122 | { | |
123 | object* obj_; | |
124 | ||
125 | BOOST_JSON_DECL | |
126 | void | |
127 | destroy() noexcept; | |
128 | ||
129 | public: | |
130 | explicit | |
131 | revert_construct( | |
132 | object& obj) noexcept | |
133 | : obj_(&obj) | |
134 | { | |
135 | } | |
136 | ||
137 | ~revert_construct() | |
138 | { | |
139 | if(! obj_) | |
140 | return; | |
141 | destroy(); | |
142 | } | |
143 | ||
144 | void | |
145 | commit() noexcept | |
146 | { | |
147 | obj_ = nullptr; | |
148 | } | |
149 | }; | |
150 | ||
151 | //---------------------------------------------------------- | |
152 | ||
153 | class object::revert_insert | |
154 | { | |
155 | object* obj_; | |
156 | std::size_t size_; | |
157 | ||
158 | BOOST_JSON_DECL | |
159 | void | |
160 | destroy() noexcept; | |
161 | ||
162 | public: | |
163 | explicit | |
164 | revert_insert( | |
165 | object& obj) noexcept | |
166 | : obj_(&obj) | |
167 | , size_(obj_->size()) | |
168 | { | |
169 | } | |
170 | ||
171 | ~revert_insert() | |
172 | { | |
173 | if(! obj_) | |
174 | return; | |
175 | destroy(); | |
176 | obj_->t_->size = static_cast< | |
177 | index_t>(size_); | |
178 | } | |
179 | ||
180 | void | |
181 | commit() noexcept | |
182 | { | |
183 | obj_ = nullptr; | |
184 | } | |
185 | }; | |
186 | ||
187 | //---------------------------------------------------------- | |
188 | // | |
189 | // Iterators | |
190 | // | |
191 | //---------------------------------------------------------- | |
192 | ||
193 | auto | |
194 | object:: | |
195 | begin() noexcept -> | |
196 | iterator | |
197 | { | |
198 | return &(*t_)[0]; | |
199 | } | |
200 | ||
201 | auto | |
202 | object:: | |
203 | begin() const noexcept -> | |
204 | const_iterator | |
205 | { | |
206 | return &(*t_)[0]; | |
207 | } | |
208 | ||
209 | auto | |
210 | object:: | |
211 | cbegin() const noexcept -> | |
212 | const_iterator | |
213 | { | |
214 | return &(*t_)[0]; | |
215 | } | |
216 | ||
217 | auto | |
218 | object:: | |
219 | end() noexcept -> | |
220 | iterator | |
221 | { | |
222 | return &(*t_)[t_->size]; | |
223 | } | |
224 | ||
225 | auto | |
226 | object:: | |
227 | end() const noexcept -> | |
228 | const_iterator | |
229 | { | |
230 | return &(*t_)[t_->size]; | |
231 | } | |
232 | ||
233 | auto | |
234 | object:: | |
235 | cend() const noexcept -> | |
236 | const_iterator | |
237 | { | |
238 | return &(*t_)[t_->size]; | |
239 | } | |
240 | ||
241 | auto | |
242 | object:: | |
243 | rbegin() noexcept -> | |
244 | reverse_iterator | |
245 | { | |
246 | return reverse_iterator(end()); | |
247 | } | |
248 | ||
249 | auto | |
250 | object:: | |
251 | rbegin() const noexcept -> | |
252 | const_reverse_iterator | |
253 | { | |
254 | return const_reverse_iterator(end()); | |
255 | } | |
256 | ||
257 | auto | |
258 | object:: | |
259 | crbegin() const noexcept -> | |
260 | const_reverse_iterator | |
261 | { | |
262 | return const_reverse_iterator(end()); | |
263 | } | |
264 | ||
265 | auto | |
266 | object:: | |
267 | rend() noexcept -> | |
268 | reverse_iterator | |
269 | { | |
270 | return reverse_iterator(begin()); | |
271 | } | |
272 | ||
273 | auto | |
274 | object:: | |
275 | rend() const noexcept -> | |
276 | const_reverse_iterator | |
277 | { | |
278 | return const_reverse_iterator(begin()); | |
279 | } | |
280 | ||
281 | auto | |
282 | object:: | |
283 | crend() const noexcept -> | |
284 | const_reverse_iterator | |
285 | { | |
286 | return const_reverse_iterator(begin()); | |
287 | } | |
288 | ||
289 | //---------------------------------------------------------- | |
290 | // | |
291 | // Capacity | |
292 | // | |
293 | //---------------------------------------------------------- | |
294 | ||
295 | bool | |
296 | object:: | |
297 | empty() const noexcept | |
298 | { | |
299 | return t_->size == 0; | |
300 | } | |
301 | ||
302 | auto | |
303 | object:: | |
304 | size() const noexcept -> | |
305 | std::size_t | |
306 | { | |
307 | return t_->size; | |
308 | } | |
309 | ||
310 | constexpr | |
311 | std::size_t | |
312 | object:: | |
313 | max_size() noexcept | |
314 | { | |
315 | // max_size depends on the address model | |
316 | using min = std::integral_constant<std::size_t, | |
317 | (std::size_t(-1) - sizeof(table)) / | |
318 | (sizeof(key_value_pair) + sizeof(index_t))>; | |
319 | return min::value < BOOST_JSON_MAX_STRUCTURED_SIZE ? | |
320 | min::value : BOOST_JSON_MAX_STRUCTURED_SIZE; | |
321 | } | |
322 | ||
323 | auto | |
324 | object:: | |
325 | capacity() const noexcept -> | |
326 | std::size_t | |
327 | { | |
328 | return t_->capacity; | |
329 | } | |
330 | ||
331 | //---------------------------------------------------------- | |
332 | // | |
333 | // Lookup | |
334 | // | |
335 | //---------------------------------------------------------- | |
336 | ||
337 | auto | |
338 | object:: | |
339 | at(string_view key) -> | |
340 | value& | |
341 | { | |
342 | auto it = find(key); | |
343 | if(it == end()) | |
344 | detail::throw_out_of_range( | |
345 | BOOST_CURRENT_LOCATION); | |
346 | return it->value(); | |
347 | } | |
348 | ||
349 | auto | |
350 | object:: | |
351 | at(string_view key) const -> | |
352 | value const& | |
353 | { | |
354 | auto it = find(key); | |
355 | if(it == end()) | |
356 | detail::throw_out_of_range( | |
357 | BOOST_CURRENT_LOCATION); | |
358 | return it->value(); | |
359 | } | |
360 | ||
361 | //---------------------------------------------------------- | |
362 | ||
363 | template<class P, class> | |
364 | auto | |
365 | object:: | |
366 | insert(P&& p) -> | |
367 | std::pair<iterator, bool> | |
368 | { | |
369 | key_value_pair v( | |
370 | std::forward<P>(p), sp_); | |
371 | return insert_impl(pilfer(v)); | |
372 | } | |
373 | ||
374 | template<class M> | |
375 | auto | |
376 | object:: | |
377 | insert_or_assign( | |
378 | string_view key, M&& m) -> | |
379 | std::pair<iterator, bool> | |
380 | { | |
381 | reserve(size() + 1); | |
382 | auto const result = find_impl(key); | |
383 | if(result.first) | |
384 | { | |
385 | value(std::forward<M>(m), | |
386 | sp_).swap(result.first->value()); | |
387 | return { result.first, false }; | |
388 | } | |
389 | key_value_pair kv(key, | |
390 | std::forward<M>(m), sp_); | |
391 | return { insert_impl(pilfer(kv), | |
392 | result.second), true }; | |
393 | } | |
394 | ||
395 | template<class Arg> | |
396 | auto | |
397 | object:: | |
398 | emplace( | |
399 | string_view key, | |
400 | Arg&& arg) -> | |
401 | std::pair<iterator, bool> | |
402 | { | |
403 | reserve(size() + 1); | |
404 | auto const result = find_impl(key); | |
405 | if(result.first) | |
406 | return { result.first, false }; | |
407 | key_value_pair kv(key, | |
408 | std::forward<Arg>(arg), sp_); | |
409 | return { insert_impl(pilfer(kv), | |
410 | result.second), true }; | |
411 | } | |
412 | ||
413 | //---------------------------------------------------------- | |
414 | // | |
415 | // (private) | |
416 | // | |
417 | //---------------------------------------------------------- | |
418 | ||
419 | template<class InputIt> | |
420 | void | |
421 | object:: | |
422 | construct( | |
423 | InputIt first, | |
424 | InputIt last, | |
425 | std::size_t min_capacity, | |
426 | std::input_iterator_tag) | |
427 | { | |
428 | reserve(min_capacity); | |
429 | revert_construct r(*this); | |
430 | while(first != last) | |
431 | { | |
432 | insert(*first); | |
433 | ++first; | |
434 | } | |
435 | r.commit(); | |
436 | } | |
437 | ||
438 | template<class InputIt> | |
439 | void | |
440 | object:: | |
441 | construct( | |
442 | InputIt first, | |
443 | InputIt last, | |
444 | std::size_t min_capacity, | |
445 | std::forward_iterator_tag) | |
446 | { | |
447 | auto n = static_cast< | |
448 | std::size_t>(std::distance( | |
449 | first, last)); | |
450 | if( n < min_capacity) | |
451 | n = min_capacity; | |
452 | reserve(n); | |
453 | revert_construct r(*this); | |
454 | while(first != last) | |
455 | { | |
456 | insert(*first); | |
457 | ++first; | |
458 | } | |
459 | r.commit(); | |
460 | } | |
461 | ||
462 | template<class InputIt> | |
463 | void | |
464 | object:: | |
465 | insert( | |
466 | InputIt first, | |
467 | InputIt last, | |
468 | std::input_iterator_tag) | |
469 | { | |
470 | // Since input iterators cannot be rewound, | |
471 | // we keep inserted elements on an exception. | |
472 | // | |
473 | while(first != last) | |
474 | { | |
475 | insert(*first); | |
476 | ++first; | |
477 | } | |
478 | } | |
479 | ||
480 | template<class InputIt> | |
481 | void | |
482 | object:: | |
483 | insert( | |
484 | InputIt first, | |
485 | InputIt last, | |
486 | std::forward_iterator_tag) | |
487 | { | |
488 | auto const n = | |
489 | static_cast<std::size_t>( | |
490 | std::distance(first, last)); | |
491 | auto const n0 = size(); | |
492 | if(n > max_size() - n0) | |
493 | detail::throw_length_error( | |
494 | "object too large", | |
495 | BOOST_CURRENT_LOCATION); | |
496 | reserve(n0 + n); | |
497 | revert_insert r(*this); | |
498 | while(first != last) | |
499 | { | |
500 | insert(*first); | |
501 | ++first; | |
502 | } | |
503 | r.commit(); | |
504 | } | |
505 | ||
506 | //---------------------------------------------------------- | |
507 | ||
508 | namespace detail { | |
509 | ||
510 | unchecked_object:: | |
511 | ~unchecked_object() | |
512 | { | |
513 | if(! data_) | |
514 | return; | |
515 | if(sp_.is_not_shared_and_deallocate_is_trivial()) | |
516 | return; | |
517 | value* p = data_; | |
518 | while(size_--) | |
519 | { | |
520 | p[0].~value(); | |
521 | p[1].~value(); | |
522 | p += 2; | |
523 | } | |
524 | } | |
525 | ||
526 | } // detail | |
527 | ||
528 | BOOST_JSON_NS_END | |
529 | ||
530 | #endif |