Debian Codegraph @

third_party/hat-trie/tsl/array-hash/array_hash.h

raw
1 /**
2 * MIT License
3 *
4 * Copyright (c) 2017 Thibaut Goetghebuer-Planchon <[email protected]>
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a copy
7 * of this software and associated documentation files (the "Software"), to deal
8 * in the Software without restriction, including without limitation the rights
9 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
10 * copies of the Software, and to permit persons to whom the Software is
11 * furnished to do so, subject to the following conditions:
12 *
13 * The above copyright notice and this permission notice shall be included in all
14 * copies or substantial portions of the Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22 * SOFTWARE.
23 */
24 #ifndef TSL_ARRAY_HASH_H
25 #define TSL_ARRAY_HASH_H
26
27 #include <algorithm>
28 #include <cassert>
29 #include <cmath>
30 #include <cstddef>
31 #include <cstdint>
32 #include <cstdlib>
33 #include <cstring>
34 #include <iterator>
35 #include <limits>
36 #include <memory>
37 #include <stdexcept>
38 #include <type_traits>
39 #include <utility>
40 #include <vector>
41 #include "array_growth_policy.h"
42
43
44 /*
45 * __has_include is a bit useless (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=79433),
46 * check also __cplusplus version.
47 */
48 #ifdef __has_include
49 # if __has_include(<string_view>) && __cplusplus >= 201703L
50 # define TSL_AH_HAS_STRING_VIEW
51 # endif
52 #endif
53
54
55 #ifdef TSL_AH_HAS_STRING_VIEW
56 # include <string_view>
57 #endif
58
59
60 #ifdef TSL_DEBUG
61 # define tsl_ah_assert(expr) assert(expr)
62 #else
63 # define tsl_ah_assert(expr) (static_cast<void>(0))
64 #endif
65
66
67
68 /**
69 * Implementation of the array hash structure described in the
70 * "Cache-conscious collision resolution in string hash tables." (Askitis Nikolas and Justin Zobel, 2005) paper.
71 */
72 namespace tsl {
73
74 namespace ah {
75
76 template<class CharT>
77 struct str_hash {
78 #ifdef TSL_AH_HAS_STRING_VIEW
79 std::size_t operator()(const CharT* key, std::size_t key_size) const {
80 return std::hash<std::basic_string_view<CharT>>()(std::basic_string_view<CharT>(key, key_size));
81 }
82 #else
83 /**
84 * FNV-1a hash
85 */
86 std::size_t operator()(const CharT* key, std::size_t key_size) const {
87 static const std::size_t init = std::size_t((sizeof(std::size_t) == 8)?0xcbf29ce484222325:0x811c9dc5);
88 static const std::size_t multiplier = std::size_t((sizeof(std::size_t) == 8)?0x100000001b3:0x1000193);
89
90 std::size_t hash = init;
91 for (std::size_t i = 0; i < key_size; ++i) {
92 hash ^= key[i];
93 hash *= multiplier;
94 }
95
96 return hash;
97 }
98 #endif
99 };
100
101 template<class CharT>
102 struct str_equal {
103 bool operator()(const CharT* key_lhs, std::size_t key_size_lhs,
104 const CharT* key_rhs, std::size_t key_size_rhs) const
105 {
106 if(key_size_lhs != key_size_rhs) {
107 return false;
108 }
109 else {
110 return std::memcmp(key_lhs, key_rhs, key_size_lhs * sizeof(CharT)) == 0;
111 }
112 }
113 };
114 }
115
116
117 namespace detail_array_hash {
118
119 template<typename T, typename = void>
120 struct is_iterator: std::false_type {
121 };
122
123 template<typename T>
124 struct is_iterator<T, typename std::enable_if<!std::is_same<typename std::iterator_traits<T>::iterator_category, void>::value>::type>: std::true_type {
125 };
126
127 static constexpr bool is_power_of_two(std::size_t value) {
128 return value != 0 && (value & (value - 1)) == 0;
129 }
130
131 template<typename T, typename U>
132 static T numeric_cast(U value, const char* error_message = "numeric_cast() failed.") {
133 T ret = static_cast<T>(value);
134 if(static_cast<U>(ret) != value) {
135 THROW(std::runtime_error, error_message);
136 }
137
138 const bool is_same_signedness = (std::is_unsigned<T>::value && std::is_unsigned<U>::value) ||
139 (std::is_signed<T>::value && std::is_signed<U>::value);
140 if(!is_same_signedness && (ret < T{}) != (value < U{})) {
141 THROW(std::runtime_error, error_message);
142 }
143
144 return ret;
145 }
146
147
148
149 /**
150 * Fixed size type used to represent size_type values on serialization. Need to be big enough
151 * to represent a std::size_t on 32 and 64 bits platforms, and must be the same size on both platforms.
152 */
153 using slz_size_type = std::uint64_t;
154
155 template<class T, class Deserializer>
156 static T deserialize_value(Deserializer& deserializer) {
157 // MSVC < 2017 is not conformant, circumvent the problem by removing the template keyword
158 #if defined (_MSC_VER) && _MSC_VER < 1910
159 return deserializer.Deserializer::operator()<T>();
160 #else
161 return deserializer.Deserializer::template operator()<T>();
162 #endif
163 }
164
165 /**
166 * For each string in the bucket, store the size of the string, the chars of the string
167 * and T, if it's not void. T should be either void or an unsigned type.
168 *
169 * End the buffer with END_OF_BUCKET flag. END_OF_BUCKET has the same type as the string size variable.
170 *
171 * m_buffer (CharT*):
172 * | size of str1 (KeySizeT) | str1 (const CharT*) | value (T if T != void) | ... |
173 * | size of strN (KeySizeT) | strN (const CharT*) | value (T if T != void) | END_OF_BUCKET (KeySizeT) |
174 *
175 * m_buffer is null if there is no string in the bucket.
176 *
177 * KeySizeT and T are extended to be a multiple of CharT when stored in the buffer.
178 *
179 * Use std::malloc and std::free instead of new and delete so we can have access to std::realloc.
180 */
181 template<class CharT,
182 class T,
183 class KeyEqual,
184 class KeySizeT,
185 bool StoreNullTerminator>
186 class array_bucket {
187 template<typename U>
188 using has_mapped_type = typename std::integral_constant<bool, !std::is_same<U, void>::value>;
189
190 static_assert(!has_mapped_type<T>::value || std::is_unsigned<T>::value,
191 "T should be either void or an unsigned type.");
192
193 static_assert(std::is_unsigned<KeySizeT>::value, "KeySizeT should be an unsigned type.");
194
195 public:
196 template<bool IsConst>
197 class array_bucket_iterator;
198
199 using char_type = CharT;
200 using key_size_type = KeySizeT;
201 using mapped_type = T;
202 using size_type = std::size_t;
203 using key_equal = KeyEqual;
204 using iterator = array_bucket_iterator<false>;
205 using const_iterator = array_bucket_iterator<true>;
206
207 static_assert(sizeof(KeySizeT) <= sizeof(size_type), "sizeof(KeySizeT) should be <= sizeof(std::size_t;)");
208 static_assert(std::is_unsigned<size_type>::value, "");
209
210 private:
211 /**
212 * Return how much space in bytes the type U will take when stored in the buffer.
213 * As the buffer is of type CharT, U may take more space than sizeof(U).
214 *
215 * Example: sizeof(CharT) = 4, sizeof(U) = 2 => U will take 4 bytes in the buffer instead of 2.
216 */
217 template<typename U>
218 static constexpr size_type sizeof_in_buff() noexcept {
219 static_assert(is_power_of_two(sizeof(U)), "sizeof(U) should be a power of two.");
220 static_assert(is_power_of_two(sizeof(CharT)), "sizeof(CharT) should be a power of two.");
221
222 return std::max(sizeof(U), sizeof(CharT));
223 }
224
225 /**
226 * Same as sizeof_in_buff<U>, but instead of returning the size in bytes return it in term of sizeof(CharT).
227 */
228 template<typename U>
229 static constexpr size_type size_as_char_t() noexcept {
230 return sizeof_in_buff<U>() / sizeof(CharT);
231 }
232
233 static key_size_type read_key_size(const CharT* buffer) noexcept {
234 key_size_type key_size;
235 std::memcpy(&key_size, buffer, sizeof(key_size));
236
237 return key_size;
238 }
239
240 static mapped_type read_value(const CharT* buffer) noexcept {
241 mapped_type value;
242 std::memcpy(&value, buffer, sizeof(value));
243
244 return value;
245 }
246
247 static bool is_end_of_bucket(const CharT* buffer) noexcept {
248 return read_key_size(buffer) == END_OF_BUCKET;
249 }
250
251 public:
252 /**
253 * Return the size required for an entry with a key of size 'key_size'.
254 */
255 template<class U = T, typename std::enable_if<!has_mapped_type<U>::value>::type* = nullptr>
256 static size_type entry_required_bytes(size_type key_size) noexcept {
257 return sizeof_in_buff<key_size_type>() + (key_size + KEY_EXTRA_SIZE) * sizeof(CharT);
258 }
259
260 template<class U = T, typename std::enable_if<has_mapped_type<U>::value>::type* = nullptr>
261 static size_type entry_required_bytes(size_type key_size) noexcept {
262 return sizeof_in_buff<key_size_type>() + (key_size + KEY_EXTRA_SIZE) * sizeof(CharT) +
263 sizeof_in_buff<mapped_type>();
264 }
265
266 private:
267 /**
268 * Return the size of the current entry in buffer.
269 */
270 static size_type entry_size_bytes(const CharT* buffer) noexcept {
271 return entry_required_bytes(read_key_size(buffer));
272 }
273
274 public:
275 template<bool IsConst>
276 class array_bucket_iterator {
277 friend class array_bucket;
278
279 using buffer_type = typename std::conditional<IsConst, const CharT, CharT>::type;
280
281 explicit array_bucket_iterator(buffer_type* position) noexcept: m_position(position) {
282 }
283
284 public:
285 using iterator_category = std::forward_iterator_tag;
286 using value_type = void;
287 using difference_type = std::ptrdiff_t;
288 using reference = void;
289 using pointer = void;
290
291 public:
292 array_bucket_iterator() noexcept: m_position(nullptr) {
293 }
294
295 const CharT* key() const {
296 return m_position + size_as_char_t<key_size_type>();
297 }
298
299 size_type key_size() const {
300 return read_key_size(m_position);
301 }
302
303 template<class U = T, typename std::enable_if<has_mapped_type<U>::value>::type* = nullptr>
304 U value() const {
305 return read_value(m_position + size_as_char_t<key_size_type>() + key_size() + KEY_EXTRA_SIZE);
306 }
307
308
309 template<class U = T, typename std::enable_if<has_mapped_type<U>::value && !IsConst && std::is_same<U, T>::value>::type* = nullptr>
310 void set_value(U value) noexcept {
311 std::memcpy(m_position + size_as_char_t<key_size_type>() + key_size() + KEY_EXTRA_SIZE,
312 &value, sizeof(value));
313 }
314
315 array_bucket_iterator& operator++() {
316 m_position += entry_size_bytes(m_position)/sizeof(CharT);
317 if(is_end_of_bucket(m_position)) {
318 m_position = nullptr;
319 }
320
321 return *this;
322 }
323
324 array_bucket_iterator operator++(int) {
325 array_bucket_iterator tmp(*this);
326 ++*this;
327
328 return tmp;
329 }
330
331 friend bool operator==(const array_bucket_iterator& lhs, const array_bucket_iterator& rhs) {
332 return lhs.m_position == rhs.m_position;
333 }
334
335 friend bool operator!=(const array_bucket_iterator& lhs, const array_bucket_iterator& rhs) {
336 return !(lhs == rhs);
337 }
338
339 private:
340 buffer_type* m_position;
341 };
342
343
344
345 static iterator end_it() noexcept {
346 return iterator(nullptr);
347 }
348
349 static const_iterator cend_it() noexcept {
350 return const_iterator(nullptr);
351 }
352
353 public:
354 array_bucket(): m_buffer(nullptr) {
355 }
356
357 /**
358 * Reserve 'size' in the buffer of the bucket. The created bucket is empty.
359 */
360 array_bucket(std::size_t size): m_buffer(nullptr) {
361 if(size == 0) {
362 return;
363 }
364
365 m_buffer = static_cast<CharT*>(std::malloc(size*sizeof(CharT) + sizeof_in_buff<decltype(END_OF_BUCKET)>()));
366 if(m_buffer == nullptr) {
367 THROW(std::runtime_error, "Out of memory");
368 }
369
370 const auto end_of_bucket = END_OF_BUCKET;
371 std::memcpy(m_buffer, &end_of_bucket, sizeof(end_of_bucket));
372 }
373
374 ~array_bucket() {
375 clear();
376 }
377
378 array_bucket(const array_bucket& other) {
379 if(other.m_buffer == nullptr) {
380 m_buffer = nullptr;
381 return;
382 }
383
384 const size_type other_buffer_size = other.size();
385 m_buffer = static_cast<CharT*>(std::malloc(other_buffer_size*sizeof(CharT) + sizeof_in_buff<decltype(END_OF_BUCKET)>()));
386 if(m_buffer == nullptr) {
387 THROW(std::runtime_error, "Out of memory");
388 }
389
390 std::memcpy(m_buffer, other.m_buffer, other_buffer_size*sizeof(CharT));
391
392 const auto end_of_bucket = END_OF_BUCKET;
393 std::memcpy(m_buffer + other_buffer_size, &end_of_bucket, sizeof(end_of_bucket));
394 }
395
396 array_bucket(array_bucket&& other) noexcept: m_buffer(other.m_buffer) {
397 other.m_buffer = nullptr;
398 }
399
400 array_bucket& operator=(array_bucket other) noexcept {
401 other.swap(*this);
402
403 return *this;
404 }
405
406 void swap(array_bucket& other) noexcept {
407 std::swap(m_buffer, other.m_buffer);
408 }
409
410 iterator begin() noexcept { return iterator(m_buffer); }
411 iterator end() noexcept { return iterator(nullptr); }
412 const_iterator begin() const noexcept { return cbegin(); }
413 const_iterator end() const noexcept { return cend(); }
414 const_iterator cbegin() const noexcept { return const_iterator(m_buffer); }
415 const_iterator cend() const noexcept { return const_iterator(nullptr); }
416
417 /**
418 * Return an iterator pointing to the key entry if presents or, if not there, to the position
419 * past the last element of the bucket. Return end() if the bucket has not be initialized yet.
420 *
421 * The boolean of the pair is set to true if the key is there, false otherwise.
422 */
423 std::pair<const_iterator, bool> find_or_end_of_bucket(const CharT* key, size_type key_size) const noexcept {
424 if(m_buffer == nullptr) {
425 return std::make_pair(cend(), false);
426 }
427
428 const CharT* buffer_ptr_in_out = m_buffer;
429 const bool found = find_or_end_of_bucket_impl(key, key_size, buffer_ptr_in_out);
430
431 return std::make_pair(const_iterator(buffer_ptr_in_out), found);
432 }
433
434 /**
435 * Append the element 'key' with its potential value at the end of the bucket.
436 * 'end_of_bucket' should point past the end of the last element in the bucket, end() if the bucket
437 * was not initialized yet. You usually get this value from find_or_end_of_bucket.
438 *
439 * Return the position where the element was actually inserted.
440 */
441 template<class... ValueArgs>
442 const_iterator append(const_iterator end_of_bucket, const CharT* key, size_type key_size,
443 ValueArgs&&... value)
444 {
445 const key_size_type key_sz = as_key_size_type(key_size);
446
447 if(end_of_bucket == cend()) {
448 tsl_ah_assert(m_buffer == nullptr);
449
450 const size_type buffer_size = entry_required_bytes(key_sz) + sizeof_in_buff<decltype(END_OF_BUCKET)>();
451
452 m_buffer = static_cast<CharT*>(std::malloc(buffer_size));
453 if(m_buffer == nullptr) {
454 THROW(std::runtime_error, "Out of memory");
455 }
456
457 append_impl(key, key_sz, m_buffer, std::forward<ValueArgs>(value)...);
458
459 return const_iterator(m_buffer);
460 }
461 else {
462 tsl_ah_assert(is_end_of_bucket(end_of_bucket.m_position));
463
464 const size_type current_size = ((end_of_bucket.m_position + size_as_char_t<decltype(END_OF_BUCKET)>()) -
465 m_buffer) * sizeof(CharT);
466 const size_type new_size = current_size + entry_required_bytes(key_sz);
467
468
469 CharT* new_buffer = static_cast<CharT*>(std::realloc(m_buffer, new_size));
470 if(new_buffer == nullptr) {
471 THROW(std::runtime_error, "Out of memory");
472 }
473 m_buffer = new_buffer;
474
475
476 CharT* buffer_append_pos = m_buffer + current_size / sizeof(CharT) -
477 size_as_char_t<decltype(END_OF_BUCKET)>();
478 append_impl(key, key_sz, buffer_append_pos, std::forward<ValueArgs>(value)...);
479
480 return const_iterator(buffer_append_pos);
481 }
482
483 }
484
485 const_iterator erase(const_iterator position) noexcept {
486 tsl_ah_assert(position.m_position != nullptr && !is_end_of_bucket(position.m_position));
487
488 // get mutable pointers
489 CharT* start_entry = m_buffer + (position.m_position - m_buffer);
490 CharT* start_next_entry = start_entry + entry_size_bytes(start_entry) / sizeof(CharT);
491
492
493 CharT* end_buffer_ptr = start_next_entry;
494 while(!is_end_of_bucket(end_buffer_ptr)) {
495 end_buffer_ptr += entry_size_bytes(end_buffer_ptr) / sizeof(CharT);
496 }
497 end_buffer_ptr += size_as_char_t<decltype(END_OF_BUCKET)>();
498
499
500 const size_type size_to_move = (end_buffer_ptr - start_next_entry) * sizeof(CharT);
501 std::memmove(start_entry, start_next_entry, size_to_move);
502
503
504 if(is_end_of_bucket(m_buffer)) {
505 clear();
506 return cend();
507 }
508 else if(is_end_of_bucket(start_entry)) {
509 return cend();
510 }
511 else {
512 return const_iterator(start_entry);
513 }
514 }
515
516 /**
517 * Return true if an element has been erased
518 */
519 bool erase(const CharT* key, size_type key_size) noexcept {
520 if(m_buffer == nullptr) {
521 return false;
522 }
523
524 const CharT* entry_buffer_ptr_in_out = m_buffer;
525 bool found = find_or_end_of_bucket_impl(key, key_size, entry_buffer_ptr_in_out);
526 if(found) {
527 erase(const_iterator(entry_buffer_ptr_in_out));
528
529 return true;
530 }
531 else {
532 return false;
533 }
534 }
535
536 /**
537 * Bucket should be big enough and there is no check to see if the key already exists.
538 * No check on key_size.
539 */
540 template<class... ValueArgs>
541 void append_in_reserved_bucket_no_check(const CharT* key, size_type key_size, ValueArgs&&... value) noexcept {
542 CharT* buffer_ptr = m_buffer;
543 while(!is_end_of_bucket(buffer_ptr)) {
544 buffer_ptr += entry_size_bytes(buffer_ptr)/sizeof(CharT);
545 }
546
547 append_impl(key, key_size_type(key_size), buffer_ptr, std::forward<ValueArgs>(value)...);
548 }
549
550 bool empty() const noexcept {
551 return m_buffer == nullptr || is_end_of_bucket(m_buffer);
552 }
553
554 void clear() noexcept {
555 std::free(m_buffer);
556 m_buffer = nullptr;
557 }
558
559 iterator mutable_iterator(const_iterator pos) noexcept {
560 return iterator(m_buffer + (pos.m_position - m_buffer));
561 }
562
563 template<class Serializer>
564 void serialize(Serializer& serializer) const {
565 const slz_size_type bucket_size = size();
566 tsl_ah_assert(m_buffer != nullptr || bucket_size == 0);
567
568 serializer(bucket_size);
569 serializer(m_buffer, bucket_size);
570 }
571
572 template<class Deserializer>
573 static array_bucket deserialize(Deserializer& deserializer) {
574 array_bucket bucket;
575 const slz_size_type bucket_size_ds = deserialize_value<slz_size_type>(deserializer);
576
577 if(bucket_size_ds == 0) {
578 return bucket;
579 }
580
581 const std::size_t bucket_size = numeric_cast<std::size_t>(bucket_size_ds, "Deserialized bucket_size is too big.");
582 bucket.m_buffer = static_cast<CharT*>(std::malloc(bucket_size*sizeof(CharT) + sizeof_in_buff<decltype(END_OF_BUCKET)>()));
583 if(bucket.m_buffer == nullptr) {
584 THROW(std::runtime_error, "Out of memory");
585 }
586
587
588 deserializer(bucket.m_buffer, bucket_size);
589
590 const auto end_of_bucket = END_OF_BUCKET;
591 std::memcpy(bucket.m_buffer + bucket_size, &end_of_bucket, sizeof(end_of_bucket));
592
593
594 tsl_ah_assert(bucket.size() == bucket_size);
595 return bucket;
596 }
597
598 private:
599 key_size_type as_key_size_type(size_type key_size) const {
600 if(key_size > MAX_KEY_SIZE) {
601 THROW(std::length_error, "Key is too long.");
602 }
603
604 return key_size_type(key_size);
605 }
606
607 /*
608 * Return true if found, false otherwise.
609 * If true, buffer_ptr_in_out points to the start of the entry matching 'key'.
610 * If false, buffer_ptr_in_out points to where the 'key' should be inserted.
611 *
612 * Start search from buffer_ptr_in_out.
613 */
614 bool find_or_end_of_bucket_impl(const CharT* key, size_type key_size,
615 const CharT* & buffer_ptr_in_out) const noexcept
616 {
617 while(!is_end_of_bucket(buffer_ptr_in_out)) {
618 const key_size_type buffer_key_size = read_key_size(buffer_ptr_in_out);
619 const CharT* buffer_str = buffer_ptr_in_out + size_as_char_t<key_size_type>();
620 if(KeyEqual()(buffer_str, buffer_key_size, key, key_size)) {
621 return true;
622 }
623
624 buffer_ptr_in_out += entry_size_bytes(buffer_ptr_in_out)/sizeof(CharT);
625 }
626
627 return false;
628 }
629
630 template<typename U = T, typename std::enable_if<!has_mapped_type<U>::value>::type* = nullptr>
631 void append_impl(const CharT* key, key_size_type key_size, CharT* buffer_append_pos) noexcept {
632 std::memcpy(buffer_append_pos, &key_size, sizeof(key_size));
633 buffer_append_pos += size_as_char_t<key_size_type>();
634
635 std::memcpy(buffer_append_pos, key, key_size * sizeof(CharT));
636 buffer_append_pos += key_size;
637
638 const CharT zero = 0;
639 std::memcpy(buffer_append_pos, &zero, KEY_EXTRA_SIZE * sizeof(CharT));
640 buffer_append_pos += KEY_EXTRA_SIZE;
641
642 const auto end_of_bucket = END_OF_BUCKET;
643 std::memcpy(buffer_append_pos, &end_of_bucket, sizeof(end_of_bucket));
644 }
645
646 template<typename U = T, typename std::enable_if<has_mapped_type<U>::value>::type* = nullptr>
647 void append_impl(const CharT* key, key_size_type key_size, CharT* buffer_append_pos,
648 typename array_bucket<CharT, U, KeyEqual, KeySizeT, StoreNullTerminator>::mapped_type value) noexcept
649 {
650 std::memcpy(buffer_append_pos, &key_size, sizeof(key_size));
651 buffer_append_pos += size_as_char_t<key_size_type>();
652
653 std::memcpy(buffer_append_pos, key, key_size * sizeof(CharT));
654 buffer_append_pos += key_size;
655
656 const CharT zero = 0;
657 std::memcpy(buffer_append_pos, &zero, KEY_EXTRA_SIZE * sizeof(CharT));
658 buffer_append_pos += KEY_EXTRA_SIZE;
659
660 std::memcpy(buffer_append_pos, &value, sizeof(value));
661 buffer_append_pos += size_as_char_t<mapped_type>();
662
663 const auto end_of_bucket = END_OF_BUCKET;
664 std::memcpy(buffer_append_pos, &end_of_bucket, sizeof(end_of_bucket));
665 }
666
667 /**
668 * Return the number of CharT in m_buffer. As the size of the buffer is not stored to gain some space,
669 * the method need to find the EOF marker and is thus in O(n).
670 */
671 size_type size() const noexcept {
672 if(m_buffer == nullptr) {
673 return 0;
674 }
675
676 CharT* buffer_ptr = m_buffer;
677 while(!is_end_of_bucket(buffer_ptr)) {
678 buffer_ptr += entry_size_bytes(buffer_ptr)/sizeof(CharT);
679 }
680
681 return buffer_ptr - m_buffer;
682 }
683
684 private:
685 static const key_size_type END_OF_BUCKET = std::numeric_limits<key_size_type>::max();
686 static const key_size_type KEY_EXTRA_SIZE = StoreNullTerminator?1:0;
687
688 CharT* m_buffer;
689
690 public:
691 static const key_size_type MAX_KEY_SIZE =
692 // -1 for END_OF_BUCKET
693 key_size_type(std::numeric_limits<key_size_type>::max() - KEY_EXTRA_SIZE - 1);
694 };
695
696
697 template<class T>
698 class value_container {
699 public:
700 void clear() noexcept {
701 m_values.clear();
702 }
703
704 void reserve(std::size_t new_cap) {
705 m_values.reserve(new_cap);
706 }
707
708 void shrink_to_fit() {
709 m_values.shrink_to_fit();
710 }
711
712 friend void swap(value_container& lhs, value_container& rhs) {
713 lhs.m_values.swap(rhs.m_values);
714 }
715
716 protected:
717 static constexpr float VECTOR_GROWTH_RATE = 1.5f;
718
719 // TODO use a sparse array? or a std::deque
720 std::vector<T> m_values;
721 };
722
723 template<>
724 class value_container<void> {
725 public:
726 void clear() noexcept {
727 }
728
729 void shrink_to_fit() {
730 }
731
732 void reserve(std::size_t /*new_cap*/) {
733 }
734 };
735
736
737
738 /**
739 * If there is no value in the array_hash (in the case of a set for example), T should be void.
740 *
741 * The size of a key string is limited to std::numeric_limits<KeySizeT>::max() - 1.
742 *
743 * The number of elements in the map is limited to std::numeric_limits<IndexSizeT>::max().
744 */
745 template<class CharT,
746 class T,
747 class Hash,
748 class KeyEqual,
749 bool StoreNullTerminator,
750 class KeySizeT,
751 class IndexSizeT,
752 class GrowthPolicy>
753 class array_hash: private value_container<T>, private Hash, private GrowthPolicy {
754 private:
755 template<typename U>
756 using has_mapped_type = typename std::integral_constant<bool, !std::is_same<U, void>::value>;
757
758 /**
759 * If there is a mapped type in array_hash, we store the values in m_values of value_container class
760 * and we store an index to m_values in the bucket. The index is of type IndexSizeT.
761 */
762 using array_bucket = tsl::detail_array_hash::array_bucket<CharT,
763 typename std::conditional<has_mapped_type<T>::value,
764 IndexSizeT,
765 void>::type,
766 KeyEqual, KeySizeT, StoreNullTerminator>;
767
768 public:
769 template<bool IsConst>
770 class array_hash_iterator;
771
772 using char_type = CharT;
773 using key_size_type = KeySizeT;
774 using index_size_type = IndexSizeT;
775 using size_type = std::size_t;
776 using hasher = Hash;
777 using key_equal = KeyEqual;
778 using iterator = array_hash_iterator<false>;
779 using const_iterator = array_hash_iterator<true>;
780
781
782 /*
783 * Iterator classes
784 */
785 public:
786 template<bool IsConst>
787 class array_hash_iterator {
788 friend class array_hash;
789
790 private:
791 using iterator_array_bucket = typename array_bucket::const_iterator;
792
793 using iterator_buckets = typename std::conditional<IsConst,
794 typename std::vector<array_bucket>::const_iterator,
795 typename std::vector<array_bucket>::iterator>::type;
796
797 using array_hash_ptr = typename std::conditional<IsConst,
798 const array_hash*,
799 array_hash*>::type;
800
801 public:
802 using iterator_category = std::forward_iterator_tag;
803 using value_type = typename std::conditional<has_mapped_type<T>::value, T, void>::type;
804 using difference_type = std::ptrdiff_t;
805 using reference = typename std::conditional<has_mapped_type<T>::value,
806 typename std::conditional<
807 IsConst,
808 typename std::add_lvalue_reference<const T>::type,
809 typename std::add_lvalue_reference<T>::type>::type,
810 void>::type;
811 using pointer = typename std::conditional<has_mapped_type<T>::value,
812 typename std::conditional<IsConst, const T*, T*>::type,
813 void>::type;
814
815
816 private:
817 array_hash_iterator(iterator_buckets buckets_iterator, iterator_array_bucket array_bucket_iterator,
818 array_hash_ptr array_hash_p) noexcept:
819 m_buckets_iterator(buckets_iterator),
820 m_array_bucket_iterator(array_bucket_iterator),
821 m_array_hash(array_hash_p)
822 {
823 tsl_ah_assert(m_array_hash != nullptr);
824 }
825
826 public:
827 array_hash_iterator() noexcept: m_array_hash(nullptr) {
828 }
829
830 template<bool TIsConst = IsConst, typename std::enable_if<TIsConst>::type* = nullptr>
831 array_hash_iterator(const array_hash_iterator<!TIsConst>& other) noexcept :
832 m_buckets_iterator(other.m_buckets_iterator),
833 m_array_bucket_iterator(other.m_array_bucket_iterator),
834 m_array_hash(other.m_array_hash)
835 {
836 }
837
838 array_hash_iterator(const array_hash_iterator& other) = default;
839 array_hash_iterator(array_hash_iterator&& other) = default;
840 array_hash_iterator& operator=(const array_hash_iterator& other) = default;
841 array_hash_iterator& operator=(array_hash_iterator&& other) = default;
842
843 const CharT* key() const {
844 return m_array_bucket_iterator.key();
845 }
846
847 size_type key_size() const {
848 return m_array_bucket_iterator.key_size();
849 }
850
851 #ifdef TSL_AH_HAS_STRING_VIEW
852 std::basic_string_view<CharT> key_sv() const {
853 return std::basic_string_view<CharT>(key(), key_size());
854 }
855 #endif
856
857 template<class U = T, typename std::enable_if<has_mapped_type<U>::value>::type* = nullptr>
858 reference value() const {
859 return this->m_array_hash->m_values[value_position()];
860 }
861
862 template<class U = T, typename std::enable_if<has_mapped_type<U>::value>::type* = nullptr>
863 reference operator*() const {
864 return value();
865 }
866
867 template<class U = T, typename std::enable_if<has_mapped_type<U>::value>::type* = nullptr>
868 pointer operator->() const {
869 return std::addressof(value());
870 }
871
872 array_hash_iterator& operator++() {
873 tsl_ah_assert(m_buckets_iterator != m_array_hash->m_buckets_data.end());
874 tsl_ah_assert(m_array_bucket_iterator != m_buckets_iterator->cend());
875
876 ++m_array_bucket_iterator;
877 if(m_array_bucket_iterator == m_buckets_iterator->cend()) {
878 do {
879 ++m_buckets_iterator;
880 } while(m_buckets_iterator != m_array_hash->m_buckets_data.end() &&
881 m_buckets_iterator->empty());
882
883 if(m_buckets_iterator != m_array_hash->m_buckets_data.end()) {
884 m_array_bucket_iterator = m_buckets_iterator->cbegin();
885 }
886 }
887
888 return *this;
889 }
890
891 array_hash_iterator operator++(int) {
892 array_hash_iterator tmp(*this);
893 ++*this;
894
895 return tmp;
896 }
897
898 friend bool operator==(const array_hash_iterator& lhs, const array_hash_iterator& rhs) {
899 return lhs.m_buckets_iterator == rhs.m_buckets_iterator &&
900 lhs.m_array_bucket_iterator == rhs.m_array_bucket_iterator &&
901 lhs.m_array_hash == rhs.m_array_hash;
902 }
903
904 friend bool operator!=(const array_hash_iterator& lhs, const array_hash_iterator& rhs) {
905 return !(lhs == rhs);
906 }
907
908 private:
909 template<class U = T, typename std::enable_if<has_mapped_type<U>::value>::type* = nullptr>
910 IndexSizeT value_position() const {
911 return this->m_array_bucket_iterator.value();
912 }
913
914 private:
915 iterator_buckets m_buckets_iterator;
916 iterator_array_bucket m_array_bucket_iterator;
917
918 array_hash_ptr m_array_hash;
919 };
920
921
922
923 public:
924 array_hash(size_type bucket_count,
925 const Hash& hash,
926 float max_load_factor): value_container<T>(),
927 Hash(hash),
928 GrowthPolicy(bucket_count),
929 m_buckets_data(bucket_count > max_bucket_count()?
930 max_bucket_count():
931 bucket_count),
932 m_buckets(m_buckets_data.empty()?static_empty_bucket_ptr():m_buckets_data.data()),
933 m_nb_elements(0)
934 {
935 this->max_load_factor(max_load_factor);
936 }
937
938 array_hash(const array_hash& other): value_container<T>(other),
939 Hash(other),
940 GrowthPolicy(other),
941 m_buckets_data(other.m_buckets_data),
942 m_buckets(m_buckets_data.empty()?static_empty_bucket_ptr():m_buckets_data.data()),
943 m_nb_elements(other.m_nb_elements),
944 m_max_load_factor(other.m_max_load_factor),
945 m_load_threshold(other.m_load_threshold)
946 {
947 }
948
949 array_hash(array_hash&& other) noexcept(std::is_nothrow_move_constructible<value_container<T>>::value &&
950 std::is_nothrow_move_constructible<Hash>::value &&
951 std::is_nothrow_move_constructible<GrowthPolicy>::value &&
952 std::is_nothrow_move_constructible<std::vector<array_bucket>>::value)
953 : value_container<T>(std::move(other)),
954 Hash(std::move(other)),
955 GrowthPolicy(std::move(other)),
956 m_buckets_data(std::move(other.m_buckets_data)),
957 m_buckets(m_buckets_data.empty()?static_empty_bucket_ptr():m_buckets_data.data()),
958 m_nb_elements(other.m_nb_elements),
959 m_max_load_factor(other.m_max_load_factor),
960 m_load_threshold(other.m_load_threshold)
961 {
962 other.value_container<T>::clear();
963 other.GrowthPolicy::clear();
964 other.m_buckets_data.clear();
965 other.m_buckets = static_empty_bucket_ptr();
966 other.m_nb_elements = 0;
967 other.m_load_threshold = 0;
968 }
969
970 array_hash& operator=(const array_hash& other) {
971 if(&other != this) {
972 value_container<T>::operator=(other);
973 Hash::operator=(other);
974 GrowthPolicy::operator=(other);
975
976 m_buckets_data = other.m_buckets_data;
977 m_buckets = m_buckets_data.empty()?static_empty_bucket_ptr():
978 m_buckets_data.data();
979 m_nb_elements = other.m_nb_elements;
980 m_max_load_factor = other.m_max_load_factor;
981 m_load_threshold = other.m_load_threshold;
982 }
983
984 return *this;
985 }
986
987 array_hash& operator=(array_hash&& other) {
988 other.swap(*this);
989 other.clear();
990
991 return *this;
992 }
993
994
995 /*
996 * Iterators
997 */
998 iterator begin() noexcept {
999 auto begin = m_buckets_data.begin();
1000 while(begin != m_buckets_data.end() && begin->empty()) {
1001 ++begin;
1002 }
1003
1004 return (begin != m_buckets_data.end())?iterator(begin, begin->cbegin(), this):end();
1005 }
1006
1007 const_iterator begin() const noexcept {
1008 return cbegin();
1009 }
1010
1011 const_iterator cbegin() const noexcept {
1012 auto begin = m_buckets_data.cbegin();
1013 while(begin != m_buckets_data.cend() && begin->empty()) {
1014 ++begin;
1015 }
1016
1017 return (begin != m_buckets_data.cend())?const_iterator(begin, begin->cbegin(), this):cend();
1018 }
1019
1020 iterator end() noexcept {
1021 return iterator(m_buckets_data.end(), array_bucket::cend_it(), this);
1022 }
1023
1024 const_iterator end() const noexcept {
1025 return cend();
1026 }
1027
1028 const_iterator cend() const noexcept {
1029 return const_iterator(m_buckets_data.end(), array_bucket::cend_it(), this);
1030 }
1031
1032
1033 /*
1034 * Capacity
1035 */
1036 bool empty() const noexcept {
1037 return m_nb_elements == 0;
1038 }
1039
1040 size_type size() const noexcept {
1041 return m_nb_elements;
1042 }
1043
1044 size_type max_size() const noexcept {
1045 return std::numeric_limits<IndexSizeT>::max();
1046 }
1047
1048 size_type max_key_size() const noexcept {
1049 return MAX_KEY_SIZE;
1050 }
1051
1052 void shrink_to_fit() {
1053 clear_old_erased_values();
1054 value_container<T>::shrink_to_fit();
1055
1056 rehash_impl(size_type(std::ceil(float(size())/max_load_factor())));
1057 }
1058
1059 /*
1060 * Modifiers
1061 */
1062 void clear() noexcept {
1063 value_container<T>::clear();
1064
1065 for(auto& bucket: m_buckets_data) {
1066 bucket.clear();
1067 }
1068
1069 m_nb_elements = 0;
1070 }
1071
1072
1073
1074 template<class... ValueArgs>
1075 std::pair<iterator, bool> emplace(const CharT* key, size_type key_size, ValueArgs&&... value_args) {
1076 const std::size_t hash = hash_key(key, key_size);
1077 std::size_t ibucket = bucket_for_hash(hash);
1078
1079 auto it_find = m_buckets[ibucket].find_or_end_of_bucket(key, key_size);
1080 if(it_find.second) {
1081 return std::make_pair(iterator(m_buckets_data.begin() + ibucket, it_find.first, this), false);
1082 }
1083
1084 if(grow_on_high_load()) {
1085 ibucket = bucket_for_hash(hash);
1086 it_find = m_buckets[ibucket].find_or_end_of_bucket(key, key_size);
1087 }
1088
1089 return emplace_impl(ibucket, it_find.first, key, key_size, std::forward<ValueArgs>(value_args)...);
1090 }
1091
1092 template<class M>
1093 std::pair<iterator, bool> insert_or_assign(const CharT* key, size_type key_size, M&& obj) {
1094 auto it = emplace(key, key_size, std::forward<M>(obj));
1095 if(!it.second) {
1096 it.first.value() = std::forward<M>(obj);
1097 }
1098
1099 return it;
1100 }
1101
1102
1103
1104 iterator erase(const_iterator pos) {
1105 if(should_clear_old_erased_values()) {
1106 clear_old_erased_values();
1107 }
1108
1109 return erase_from_bucket(mutable_iterator(pos));
1110 }
1111
1112 iterator erase(const_iterator first, const_iterator last) {
1113 if(first == last) {
1114 return mutable_iterator(first);
1115 }
1116
1117 /**
1118 * When erasing an element from a bucket with erase_from_bucket, it invalidates all the iterators
1119 * in the array bucket of the element (m_array_bucket_iterator) but not the iterators of the buckets
1120 * itself (m_buckets_iterator).
1121 *
1122 * So first erase all the values between first and last which are not part of the bucket of last,
1123 * and then erase carefully the values in last's bucket.
1124 */
1125 auto to_delete = mutable_iterator(first);
1126 while(to_delete.m_buckets_iterator != last.m_buckets_iterator) {
1127 to_delete = erase_from_bucket(to_delete);
1128 }
1129
1130 std::size_t nb_elements_until_last = std::distance(to_delete.m_array_bucket_iterator,
1131 last.m_array_bucket_iterator);
1132 while(nb_elements_until_last > 0) {
1133 to_delete = erase_from_bucket(to_delete);
1134 nb_elements_until_last--;
1135 }
1136
1137 if(should_clear_old_erased_values()) {
1138 clear_old_erased_values();
1139 }
1140
1141 return to_delete;
1142 }
1143
1144
1145
1146 size_type erase(const CharT* key, size_type key_size) {
1147 return erase(key, key_size, hash_key(key, key_size));
1148 }
1149
1150 size_type erase(const CharT* key, size_type key_size, std::size_t hash) {
1151 if(should_clear_old_erased_values()) {
1152 clear_old_erased_values();
1153 }
1154
1155 const std::size_t ibucket = bucket_for_hash(hash);
1156 if(m_buckets[ibucket].erase(key, key_size)) {
1157 m_nb_elements--;
1158 return 1;
1159 }
1160 else {
1161 return 0;
1162 }
1163 }
1164
1165
1166
1167 void swap(array_hash& other) {
1168 using std::swap;
1169
1170 swap(static_cast<value_container<T>&>(*this), static_cast<value_container<T>&>(other));
1171 swap(static_cast<Hash&>(*this), static_cast<Hash&>(other));
1172 swap(static_cast<GrowthPolicy&>(*this), static_cast<GrowthPolicy&>(other));
1173 swap(m_buckets_data, other.m_buckets_data);
1174 swap(m_buckets, other.m_buckets);
1175 swap(m_nb_elements, other.m_nb_elements);
1176 swap(m_max_load_factor, other.m_max_load_factor);
1177 swap(m_load_threshold, other.m_load_threshold);
1178 }
1179
1180 /*
1181 * Lookup
1182 */
1183 template<class U = T, typename std::enable_if<has_mapped_type<U>::value>::type* = nullptr>
1184 U& at(const CharT* key, size_type key_size) {
1185 return at(key, key_size, hash_key(key, key_size));
1186 }
1187
1188 template<class U = T, typename std::enable_if<has_mapped_type<U>::value>::type* = nullptr>
1189 const U& at(const CharT* key, size_type key_size) const {
1190 return at(key, key_size, hash_key(key, key_size));
1191 }
1192
1193 template<class U = T, typename std::enable_if<has_mapped_type<U>::value>::type* = nullptr>
1194 U& at(const CharT* key, size_type key_size, std::size_t hash) {
1195 return const_cast<U&>(static_cast<const array_hash*>(this)->at(key, key_size, hash));
1196 }
1197
1198 template<class U = T, typename std::enable_if<has_mapped_type<U>::value>::type* = nullptr>
1199 const U& at(const CharT* key, size_type key_size, std::size_t hash) const {
1200 const std::size_t ibucket = bucket_for_hash(hash);
1201
1202 auto it_find = m_buckets[ibucket].find_or_end_of_bucket(key, key_size);
1203 if(it_find.second) {
1204 return this->m_values[it_find.first.value()];
1205 }
1206 else {
1207 THROW(std::out_of_range, "Couldn't find key.");
1208 }
1209 }
1210
1211
1212
1213 template<class U = T, typename std::enable_if<has_mapped_type<U>::value>::type* = nullptr>
1214 U& access_operator(const CharT* key, size_type key_size) {
1215 const std::size_t hash = hash_key(key, key_size);
1216 std::size_t ibucket = bucket_for_hash(hash);
1217
1218 auto it_find = m_buckets[ibucket].find_or_end_of_bucket(key, key_size);
1219 if(it_find.second) {
1220 return this->m_values[it_find.first.value()];
1221 }
1222 else {
1223 if(grow_on_high_load()) {
1224 ibucket = bucket_for_hash(hash);
1225 it_find = m_buckets[ibucket].find_or_end_of_bucket(key, key_size);
1226 }
1227
1228 return emplace_impl(ibucket, it_find.first, key, key_size, U{}).first.value();
1229 }
1230 }
1231
1232
1233
1234 size_type count(const CharT* key, size_type key_size) const {
1235 return count(key, key_size, hash_key(key, key_size));
1236 }
1237
1238 size_type count(const CharT* key, size_type key_size, std::size_t hash) const {
1239 const std::size_t ibucket = bucket_for_hash(hash);
1240
1241 auto it_find = m_buckets[ibucket].find_or_end_of_bucket(key, key_size);
1242 if(it_find.second) {
1243 return 1;
1244 }
1245 else {
1246 return 0;
1247 }
1248 }
1249
1250
1251
1252 iterator find(const CharT* key, size_type key_size) {
1253 return find(key, key_size, hash_key(key, key_size));
1254 }
1255
1256 const_iterator find(const CharT* key, size_type key_size) const {
1257 return find(key, key_size, hash_key(key, key_size));
1258 }
1259
1260 iterator find(const CharT* key, size_type key_size, std::size_t hash) {
1261 const std::size_t ibucket = bucket_for_hash(hash);
1262
1263 auto it_find = m_buckets[ibucket].find_or_end_of_bucket(key, key_size);
1264 if(it_find.second) {
1265 return iterator(m_buckets_data.begin() + ibucket, it_find.first, this);
1266 }
1267 else {
1268 return end();
1269 }
1270 }
1271
1272 const_iterator find(const CharT* key, size_type key_size, std::size_t hash) const {
1273 const std::size_t ibucket = bucket_for_hash(hash);
1274
1275 auto it_find = m_buckets[ibucket].find_or_end_of_bucket(key, key_size);
1276 if(it_find.second) {
1277 return const_iterator(m_buckets_data.cbegin() + ibucket, it_find.first, this);
1278 }
1279 else {
1280 return cend();
1281 }
1282 }
1283
1284
1285
1286 std::pair<iterator, iterator> equal_range(const CharT* key, size_type key_size) {
1287 return equal_range(key, key_size, hash_key(key, key_size));
1288 }
1289
1290 std::pair<const_iterator, const_iterator> equal_range(const CharT* key, size_type key_size) const {
1291 return equal_range(key, key_size, hash_key(key, key_size));
1292 }
1293
1294 std::pair<iterator, iterator> equal_range(const CharT* key, size_type key_size, std::size_t hash) {
1295 iterator it = find(key, key_size, hash);
1296 return std::make_pair(it, (it == end())?it:std::next(it));
1297 }
1298
1299 std::pair<const_iterator, const_iterator> equal_range(const CharT* key, size_type key_size,
1300 std::size_t hash) const
1301 {
1302 const_iterator it = find(key, key_size, hash);
1303 return std::make_pair(it, (it == cend())?it:std::next(it));
1304 }
1305
1306 /*
1307 * Bucket interface
1308 */
1309 size_type bucket_count() const {
1310 return m_buckets_data.size();
1311 }
1312
1313 size_type max_bucket_count() const {
1314 return std::min(GrowthPolicy::max_bucket_count(), m_buckets_data.max_size());
1315 }
1316
1317
1318 /*
1319 * Hash policy
1320 */
1321 float load_factor() const {
1322 if(bucket_count() == 0) {
1323 return 0;
1324 }
1325
1326 return float(m_nb_elements) / float(bucket_count());
1327 }
1328
1329 float max_load_factor() const {
1330 return m_max_load_factor;
1331 }
1332
1333 void max_load_factor(float ml) {
1334 m_max_load_factor = std::max(0.1f, ml);
1335 m_load_threshold = size_type(float(bucket_count())*m_max_load_factor);
1336 }
1337
1338 void rehash(size_type count) {
1339 count = std::max(count, size_type(std::ceil(float(size())/max_load_factor())));
1340 rehash_impl(count);
1341 }
1342
1343 void reserve(size_type count) {
1344 rehash(size_type(std::ceil(float(count)/max_load_factor())));
1345 }
1346
1347 /*
1348 * Observers
1349 */
1350 hasher hash_function() const {
1351 return static_cast<const hasher&>(*this);
1352 }
1353
1354 // TODO add support for statefull KeyEqual
1355 key_equal key_eq() const {
1356 return KeyEqual();
1357 }
1358
1359 /*
1360 * Other
1361 */
1362 iterator mutable_iterator(const_iterator it) noexcept {
1363 auto it_bucket = m_buckets_data.begin() + std::distance(m_buckets_data.cbegin(), it.m_buckets_iterator);
1364 return iterator(it_bucket, it.m_array_bucket_iterator, this);
1365 }
1366
1367 template<class Serializer>
1368 void serialize(Serializer& serializer) const {
1369 serialize_impl(serializer);
1370 }
1371
1372 template<class Deserializer>
1373 void deserialize(Deserializer& deserializer, bool hash_compatible) {
1374 deserialize_impl(deserializer, hash_compatible);
1375 }
1376
1377 private:
1378 std::size_t hash_key(const CharT* key, size_type key_size) const {
1379 return Hash::operator()(key, key_size);
1380 }
1381
1382 std::size_t bucket_for_hash(std::size_t hash) const {
1383 return GrowthPolicy::bucket_for_hash(hash);
1384 }
1385
1386 /**
1387 * If there is a mapped_type, the mapped value in m_values is not erased now.
1388 * It will be erased when the ratio between the size of the map and
1389 * the size of the map + the number of deleted values still stored is low enough (see clear_old_erased_values).
1390 */
1391 iterator erase_from_bucket(iterator pos) noexcept {
1392 auto array_bucket_next_it = pos.m_buckets_iterator->erase(pos.m_array_bucket_iterator);
1393 m_nb_elements--;
1394
1395 if(array_bucket_next_it != pos.m_buckets_iterator->cend()) {
1396 return iterator(pos.m_buckets_iterator, array_bucket_next_it, this);
1397 }
1398 else {
1399 do {
1400 ++pos.m_buckets_iterator;
1401 } while(pos.m_buckets_iterator != m_buckets_data.end() && pos.m_buckets_iterator->empty());
1402
1403 if(pos.m_buckets_iterator != m_buckets_data.end()) {
1404 return iterator(pos.m_buckets_iterator, pos.m_buckets_iterator->cbegin(), this);
1405 }
1406 else {
1407 return end();
1408 }
1409 }
1410 }
1411
1412
1413 template<class U = T, typename std::enable_if<!has_mapped_type<U>::value>::type* = nullptr>
1414 bool should_clear_old_erased_values(float /*threshold*/ = DEFAULT_CLEAR_OLD_ERASED_VALUE_THRESHOLD) const {
1415 return false;
1416 }
1417
1418 template<class U = T, typename std::enable_if<has_mapped_type<U>::value>::type* = nullptr>
1419 bool should_clear_old_erased_values(float threshold = DEFAULT_CLEAR_OLD_ERASED_VALUE_THRESHOLD) const {
1420 if(this->m_values.size() == 0) {
1421 return false;
1422 }
1423
1424 return float(m_nb_elements)/float(this->m_values.size()) < threshold;
1425 }
1426
1427 template<class U = T, typename std::enable_if<!has_mapped_type<U>::value>::type* = nullptr>
1428 void clear_old_erased_values() {
1429 }
1430
1431 template<class U = T, typename std::enable_if<has_mapped_type<U>::value>::type* = nullptr>
1432 void clear_old_erased_values() {
1433 static_assert(std::is_nothrow_move_constructible<U>::value ||
1434 std::is_copy_constructible<U>::value,
1435 "mapped_value must be either copy constructible or nothrow move constructible.");
1436
1437 if(m_nb_elements == this->m_values.size()) {
1438 return;
1439 }
1440
1441 std::vector<T> new_values;
1442 new_values.reserve(size());
1443
1444 for(auto it = begin(); it != end(); ++it) {
1445 new_values.push_back(std::move_if_noexcept(it.value()));
1446 }
1447
1448
1449 IndexSizeT ivalue = 0;
1450 for(auto it = begin(); it != end(); ++it) {
1451 auto it_array_bucket = it.m_buckets_iterator->mutable_iterator(it.m_array_bucket_iterator);
1452 it_array_bucket.set_value(ivalue);
1453 ivalue++;
1454 }
1455
1456 new_values.swap(this->m_values);
1457 tsl_ah_assert(m_nb_elements == this->m_values.size());
1458 }
1459
1460 /**
1461 * Return true if a rehash occurred.
1462 */
1463 bool grow_on_high_load() {
1464 if(size() >= m_load_threshold) {
1465 rehash_impl(GrowthPolicy::next_bucket_count());
1466 return true;
1467 }
1468
1469 return false;
1470 }
1471
1472 template<class... ValueArgs, class U = T, typename std::enable_if<has_mapped_type<U>::value>::type* = nullptr>
1473 std::pair<iterator, bool> emplace_impl(std::size_t ibucket, typename array_bucket::const_iterator end_of_bucket,
1474 const CharT* key, size_type key_size, ValueArgs&&... value_args)
1475 {
1476 if(this->m_values.size() >= max_size()) {
1477 // Try to clear old erased values lingering in m_values. Throw if it doesn't change anything.
1478 clear_old_erased_values();
1479 if(this->m_values.size() >= max_size()) {
1480 THROW(std::length_error, "Can't insert value, too much values in the map.");
1481 }
1482 }
1483
1484 if(this->m_values.size() == this->m_values.capacity()) {
1485 this->m_values.reserve(std::size_t(float(this->m_values.size()) * value_container<T>::VECTOR_GROWTH_RATE));
1486 }
1487
1488
1489 this->m_values.emplace_back(std::forward<ValueArgs>(value_args)...);
1490
1491 auto it = m_buckets[ibucket].append(end_of_bucket, key, key_size, IndexSizeT(this->m_values.size() - 1));
1492 m_nb_elements++;
1493
1494 return std::make_pair(iterator(m_buckets_data.begin() + ibucket, it, this), true);
1495 }
1496
1497 template<class U = T, typename std::enable_if<!has_mapped_type<U>::value>::type* = nullptr>
1498 std::pair<iterator, bool> emplace_impl(std::size_t ibucket, typename array_bucket::const_iterator end_of_bucket,
1499 const CharT* key, size_type key_size)
1500 {
1501 if(m_nb_elements >= max_size()) {
1502 THROW(std::length_error, "Can't insert value, too much values in the map.");
1503 }
1504
1505 auto it = m_buckets[ibucket].append(end_of_bucket, key, key_size);
1506 m_nb_elements++;
1507
1508 return std::make_pair(iterator(m_buckets_data.begin() + ibucket, it, this), true);
1509 }
1510
1511 void rehash_impl(size_type bucket_count) {
1512 GrowthPolicy new_growth_policy(bucket_count);
1513 if(bucket_count == this->bucket_count()) {
1514 return;
1515 }
1516
1517
1518 if(should_clear_old_erased_values(REHASH_CLEAR_OLD_ERASED_VALUE_THRESHOLD)) {
1519 clear_old_erased_values();
1520 }
1521
1522
1523 std::vector<std::size_t> required_size_for_bucket(bucket_count, 0);
1524 std::vector<std::size_t> bucket_for_ivalue(size(), 0);
1525
1526 std::size_t ivalue = 0;
1527 for(auto it = begin(); it != end(); ++it) {
1528 const std::size_t hash = hash_key(it.key(), it.key_size());
1529 const std::size_t ibucket = new_growth_policy.bucket_for_hash(hash);
1530
1531 bucket_for_ivalue[ivalue] = ibucket;
1532 required_size_for_bucket[ibucket] += array_bucket::entry_required_bytes(it.key_size());
1533 ivalue++;
1534 }
1535
1536
1537
1538
1539 std::vector<array_bucket> new_buckets;
1540 new_buckets.reserve(bucket_count);
1541 for(std::size_t ibucket = 0; ibucket < bucket_count; ibucket++) {
1542 new_buckets.emplace_back(required_size_for_bucket[ibucket]);
1543 }
1544
1545
1546 ivalue = 0;
1547 for(auto it = begin(); it != end(); ++it) {
1548 const std::size_t ibucket = bucket_for_ivalue[ivalue];
1549 append_iterator_in_reserved_bucket_no_check(new_buckets[ibucket], it);
1550
1551 ivalue++;
1552 }
1553
1554
1555 using std::swap;
1556 swap(static_cast<GrowthPolicy&>(*this), new_growth_policy);
1557
1558 m_buckets_data.swap(new_buckets);
1559 m_buckets = !m_buckets_data.empty()?m_buckets_data.data():
1560 static_empty_bucket_ptr();
1561
1562 // Call max_load_factor to change m_load_threshold
1563 max_load_factor(m_max_load_factor);
1564 }
1565
1566 template<class U = T, typename std::enable_if<!has_mapped_type<U>::value>::type* = nullptr>
1567 void append_iterator_in_reserved_bucket_no_check(array_bucket& bucket, iterator it) {
1568 bucket.append_in_reserved_bucket_no_check(it.key(), it.key_size());
1569 }
1570
1571 template<class U = T, typename std::enable_if<has_mapped_type<U>::value>::type* = nullptr>
1572 void append_iterator_in_reserved_bucket_no_check(array_bucket& bucket, iterator it) {
1573 bucket.append_in_reserved_bucket_no_check(it.key(), it.key_size(), it.value_position());
1574 }
1575
1576
1577
1578 /**
1579 * On serialization the values of each bucket (if has_mapped_type is true) are serialized
1580 * next to the bucket. The potential old erased values in value_container are thus not serialized.
1581 *
1582 * On deserialization, when hash_compatible is true, we reaffect the value index (IndexSizeT) of each
1583 * bucket with set_value as the position of each value is no more the same in value_container compared
1584 * to when they were serialized.
1585 *
1586 * It's done this way as we can't call clear_old_erased_values() because we want the serialize
1587 * method to remain const and we don't want to serialize/deserialize old erased values. As we may
1588 * not serialize all the values in value_container, the values we keep can change of index.
1589 * We thus have to modify the value indexes in the buckets.
1590 */
1591 template<class Serializer>
1592 void serialize_impl(Serializer& serializer) const {
1593 const slz_size_type version = SERIALIZATION_PROTOCOL_VERSION;
1594 serializer(version);
1595
1596 const slz_size_type bucket_count = m_buckets_data.size();
1597 serializer(bucket_count);
1598
1599 const slz_size_type nb_elements = m_nb_elements;
1600 serializer(nb_elements);
1601
1602 const float max_load_factor = m_max_load_factor;
1603 serializer(max_load_factor);
1604
1605 for(const array_bucket& bucket: m_buckets_data) {
1606 bucket.serialize(serializer);
1607 serialize_bucket_values(serializer, bucket);
1608 }
1609 }
1610
1611 template<class Serializer, class U = T,
1612 typename std::enable_if<!has_mapped_type<U>::value>::type* = nullptr>
1613 void serialize_bucket_values(Serializer& /*serializer*/, const array_bucket& /*bucket*/) const {
1614 }
1615
1616 template<class Serializer, class U = T,
1617 typename std::enable_if<has_mapped_type<U>::value>::type* = nullptr>
1618 void serialize_bucket_values(Serializer& serializer, const array_bucket& bucket) const {
1619 for(auto it = bucket.begin(); it != bucket.end(); ++it) {
1620 serializer(this->m_values[it.value()]);
1621 }
1622 }
1623
1624 template<class Deserializer>
1625 void deserialize_impl(Deserializer& deserializer, bool hash_compatible) {
1626 tsl_ah_assert(m_buckets_data.empty()); // Current hash table must be empty
1627
1628 const slz_size_type version = deserialize_value<slz_size_type>(deserializer);
1629 // For now we only have one version of the serialization protocol.
1630 // If it doesn't match there is a problem with the file.
1631 if(version != SERIALIZATION_PROTOCOL_VERSION) {
1632 THROW(std::runtime_error, "Can't deserialize the array_map/set. The protocol version header is invalid.");
1633 }
1634
1635 const slz_size_type bucket_count_ds = deserialize_value<slz_size_type>(deserializer);
1636 const slz_size_type nb_elements = deserialize_value<slz_size_type>(deserializer);
1637 const float max_load_factor = deserialize_value<float>(deserializer);
1638
1639
1640 m_nb_elements = numeric_cast<IndexSizeT>(nb_elements, "Deserialized nb_elements is too big.");
1641
1642 size_type bucket_count = numeric_cast<size_type>(bucket_count_ds, "Deserialized bucket_count is too big.");
1643 GrowthPolicy::operator=(GrowthPolicy(bucket_count));
1644
1645
1646 this->max_load_factor(max_load_factor);
1647 value_container<T>::reserve(m_nb_elements);
1648
1649
1650 if(hash_compatible) {
1651 if(bucket_count != bucket_count_ds) {
1652 THROW(std::runtime_error, "The GrowthPolicy is not the same even though hash_compatible is true.");
1653 }
1654
1655 m_buckets_data.reserve(bucket_count);
1656 for(size_type i = 0; i < bucket_count; i++) {
1657 m_buckets_data.push_back(array_bucket::deserialize(deserializer));
1658 deserialize_bucket_values(deserializer, m_buckets_data.back());
1659 }
1660 }
1661 else {
1662 m_buckets_data.resize(bucket_count);
1663 for(size_type i = 0; i < bucket_count; i++) {
1664 // TODO use buffer to avoid reallocation on each deserialization.
1665 array_bucket bucket = array_bucket::deserialize(deserializer);
1666 deserialize_bucket_values(deserializer, bucket);
1667
1668 for(auto it_val = bucket.cbegin(); it_val != bucket.cend(); ++it_val) {
1669 const std::size_t ibucket = bucket_for_hash(hash_key(it_val.key(), it_val.key_size()));
1670
1671 auto it_find = m_buckets_data[ibucket].find_or_end_of_bucket(it_val.key(), it_val.key_size());
1672 if(it_find.second) {
1673 THROW(std::runtime_error, "Error on deserialization, the same key is presents multiple times.");
1674 }
1675
1676 append_array_bucket_iterator_in_bucket(m_buckets_data[ibucket], it_find.first, it_val);
1677 }
1678 }
1679 }
1680
1681 m_buckets = m_buckets_data.data();
1682
1683
1684 if(load_factor() > this->max_load_factor()) {
1685 THROW(std::runtime_error, "Invalid max_load_factor. Check that the serializer and deserializer support "
1686 "floats correctly as they can be converted implicitely to ints.");
1687 }
1688 }
1689
1690 template<class Deserializer, class U = T,
1691 typename std::enable_if<!has_mapped_type<U>::value>::type* = nullptr>
1692 void deserialize_bucket_values(Deserializer& /*deserializer*/, array_bucket& /*bucket*/) {
1693 }
1694
1695 template<class Deserializer, class U = T,
1696 typename std::enable_if<has_mapped_type<U>::value>::type* = nullptr>
1697 void deserialize_bucket_values(Deserializer& deserializer, array_bucket& bucket) {
1698 for(auto it = bucket.begin(); it != bucket.end(); ++it) {
1699 this->m_values.emplace_back(deserialize_value<U>(deserializer));
1700
1701 tsl_ah_assert(this->m_values.size() - 1 <= std::numeric_limits<IndexSizeT>::max());
1702 it.set_value(static_cast<IndexSizeT>(this->m_values.size() - 1));
1703 }
1704 }
1705
1706 template<class U = T, typename std::enable_if<!has_mapped_type<U>::value>::type* = nullptr>
1707 void append_array_bucket_iterator_in_bucket(array_bucket& bucket,
1708 typename array_bucket::const_iterator end_of_bucket,
1709 typename array_bucket::const_iterator it_val)
1710 {
1711 bucket.append(end_of_bucket, it_val.key(), it_val.key_size());
1712 }
1713
1714 template<class U = T, typename std::enable_if<has_mapped_type<U>::value>::type* = nullptr>
1715 void append_array_bucket_iterator_in_bucket(array_bucket& bucket,
1716 typename array_bucket::const_iterator end_of_bucket,
1717 typename array_bucket::const_iterator it_val)
1718 {
1719 bucket.append(end_of_bucket, it_val.key(), it_val.key_size(), it_val.value());
1720 }
1721
1722 public:
1723 static const size_type DEFAULT_INIT_BUCKET_COUNT = 0;
1724 static constexpr float DEFAULT_MAX_LOAD_FACTOR = 2.0f;
1725 static const size_type MAX_KEY_SIZE = array_bucket::MAX_KEY_SIZE;
1726
1727 private:
1728 /**
1729 * Protocol version currenlty used for serialization.
1730 */
1731 static const slz_size_type SERIALIZATION_PROTOCOL_VERSION = 1;
1732
1733
1734 static constexpr float DEFAULT_CLEAR_OLD_ERASED_VALUE_THRESHOLD = 0.6f;
1735 static constexpr float REHASH_CLEAR_OLD_ERASED_VALUE_THRESHOLD = 0.9f;
1736
1737
1738 /**
1739 * Return an always valid pointer to a static empty array_bucket.
1740 */
1741 array_bucket* static_empty_bucket_ptr() {
1742 static array_bucket empty_bucket;
1743 return &empty_bucket;
1744 }
1745
1746 private:
1747 std::vector<array_bucket> m_buckets_data;
1748
1749 /**
1750 * Points to m_buckets_data.data() if !m_buckets_data.empty() otherwise points to static_empty_bucket_ptr.
1751 * This variable is useful to avoid the cost of checking if m_buckets_data is empty when trying
1752 * to find an element.
1753 *
1754 * TODO Remove m_buckets_data and only use a pointer+size instead of a pointer+vector to save some space in the array_hash object.
1755 */
1756 array_bucket* m_buckets;
1757
1758 IndexSizeT m_nb_elements;
1759 float m_max_load_factor;
1760 size_type m_load_threshold;
1761 };
1762
1763 } // end namespace detail_array_hash
1764 } //end namespace tsl
1765
1766 #endif