Debian Codegraph @

third_party/hat-trie/tsl/array-hash/array_map.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_MAP_H
25 #define TSL_ARRAY_MAP_H
26
27 #include <cstddef>
28 #include <cstdint>
29 #include <initializer_list>
30 #include <iterator>
31 #include <string>
32 #include <type_traits>
33 #include <utility>
34 #include "array_hash.h"
35
36 namespace tsl {
37
38
39 /**
40 * Implementation of a cache-conscious string hash map.
41 *
42 * The map stores the strings as `const CharT*`. If `StoreNullTerminator` is true,
43 * the strings are stored with the a null-terminator (the `key()` method of the iterators
44 * will return a pointer to this null-terminated string). Otherwise the null character
45 * is not stored (which allow an economy of 1 byte per string).
46 *
47 * The value `T` must be either nothrow move-constructible, copy-constructible or both.
48 *
49 * The size of a key string is limited to `std::numeric_limits<KeySizeT>::max() - 1`.
50 * That is 65 535 characters by default, but can be raised with the `KeySizeT` template parameter.
51 * See `max_key_size()` for an easy access to this limit.
52 *
53 * The number of elements in the map is limited to `std::numeric_limits<IndexSizeT>::max()`.
54 * That is 4 294 967 296 elements, but can be raised with the `IndexSizeT` template parameter.
55 * See `max_size()` for an easy access to this limit.
56 *
57 * Iterators invalidation:
58 * - clear, operator=: always invalidate the iterators.
59 * - insert, emplace, operator[]: always invalidate the iterators.
60 * - erase: always invalidate the iterators.
61 * - shrink_to_fit: always invalidate the iterators.
62 */
63 template<class CharT,
64 class T,
65 class Hash = tsl::ah::str_hash<CharT>,
66 class KeyEqual = tsl::ah::str_equal<CharT>,
67 bool StoreNullTerminator = true,
68 class KeySizeT = std::uint16_t,
69 class IndexSizeT = std::uint32_t,
70 class GrowthPolicy = tsl::ah::power_of_two_growth_policy<2>>
71 class array_map {
72 private:
73 template<typename U>
74 using is_iterator = tsl::detail_array_hash::is_iterator<U>;
75
76 using ht = tsl::detail_array_hash::array_hash<CharT, T, Hash, KeyEqual, StoreNullTerminator,
77 KeySizeT, IndexSizeT, GrowthPolicy>;
78
79 public:
80 using char_type = typename ht::char_type;
81 using mapped_type = T;
82 using key_size_type = typename ht::key_size_type;
83 using index_size_type = typename ht::index_size_type;
84 using size_type = typename ht::size_type;
85 using hasher = typename ht::hasher;
86 using key_equal = typename ht::key_equal;
87 using iterator = typename ht::iterator;
88 using const_iterator = typename ht::const_iterator;
89
90 public:
91 array_map(): array_map(ht::DEFAULT_INIT_BUCKET_COUNT) {
92 }
93
94 explicit array_map(size_type bucket_count,
95 const Hash& hash = Hash()): m_ht(bucket_count, hash, ht::DEFAULT_MAX_LOAD_FACTOR)
96 {
97 }
98
99 template<class InputIt, typename std::enable_if<is_iterator<InputIt>::value>::type* = nullptr>
100 array_map(InputIt first, InputIt last,
101 size_type bucket_count = ht::DEFAULT_INIT_BUCKET_COUNT,
102 const Hash& hash = Hash()): array_map(bucket_count, hash)
103 {
104 insert(first, last);
105 }
106
107
108
109 #ifdef TSL_AH_HAS_STRING_VIEW
110 array_map(std::initializer_list<std::pair<std::basic_string_view<CharT>, T>> init,
111 size_type bucket_count = ht::DEFAULT_INIT_BUCKET_COUNT,
112 const Hash& hash = Hash()): array_map(bucket_count, hash)
113 {
114 insert(init);
115 }
116 #else
117 array_map(std::initializer_list<std::pair<const CharT*, T>> init,
118 size_type bucket_count = ht::DEFAULT_INIT_BUCKET_COUNT,
119 const Hash& hash = Hash()): array_map(bucket_count, hash)
120 {
121 insert(init);
122 }
123 #endif
124
125
126
127 #ifdef TSL_AH_HAS_STRING_VIEW
128 array_map& operator=(std::initializer_list<std::pair<std::basic_string_view<CharT>, T>> ilist) {
129 clear();
130
131 reserve(ilist.size());
132 insert(ilist);
133
134 return *this;
135 }
136 #else
137 array_map& operator=(std::initializer_list<std::pair<const CharT*, T>> ilist) {
138 clear();
139
140 reserve(ilist.size());
141 insert(ilist);
142
143 return *this;
144 }
145 #endif
146
147
148
149 /*
150 * Iterators
151 */
152 iterator begin() noexcept { return m_ht.begin(); }
153 const_iterator begin() const noexcept { return m_ht.begin(); }
154 const_iterator cbegin() const noexcept { return m_ht.cbegin(); }
155
156 iterator end() noexcept { return m_ht.end(); }
157 const_iterator end() const noexcept { return m_ht.end(); }
158 const_iterator cend() const noexcept { return m_ht.cend(); }
159
160
161
162 /*
163 * Capacity
164 */
165 bool empty() const noexcept { return m_ht.empty(); }
166 size_type size() const noexcept { return m_ht.size(); }
167 size_type max_size() const noexcept { return m_ht.max_size(); }
168 size_type max_key_size() const noexcept { return m_ht.max_key_size(); }
169 void shrink_to_fit() { m_ht.shrink_to_fit(); }
170
171
172
173 /*
174 * Modifiers
175 */
176 void clear() noexcept { m_ht.clear(); }
177
178
179
180 #ifdef TSL_AH_HAS_STRING_VIEW
181 std::pair<iterator, bool> insert(const std::basic_string_view<CharT>& key, const T& value) {
182 return m_ht.emplace(key.data(), key.size(), value);
183 }
184 #else
185 std::pair<iterator, bool> insert(const CharT* key, const T& value) {
186 return m_ht.emplace(key, std::char_traits<CharT>::length(key), value);
187 }
188
189 std::pair<iterator, bool> insert(const std::basic_string<CharT>& key, const T& value) {
190 return m_ht.emplace(key.data(), key.size(), value);
191 }
192 #endif
193 std::pair<iterator, bool> insert_ks(const CharT* key, size_type key_size, const T& value) {
194 return m_ht.emplace(key, key_size, value);
195 }
196
197
198
199 #ifdef TSL_AH_HAS_STRING_VIEW
200 std::pair<iterator, bool> insert(const std::basic_string_view<CharT>& key, T&& value) {
201 return m_ht.emplace(key.data(), key.size(), std::move(value));
202 }
203 #else
204 std::pair<iterator, bool> insert(const CharT* key, T&& value) {
205 return m_ht.emplace(key, std::char_traits<CharT>::length(key), std::move(value));
206 }
207
208 std::pair<iterator, bool> insert(const std::basic_string<CharT>& key, T&& value) {
209 return m_ht.emplace(key.data(), key.size(), std::move(value));
210 }
211 #endif
212 std::pair<iterator, bool> insert_ks(const CharT* key, size_type key_size, T&& value) {
213 return m_ht.emplace(key, key_size, std::move(value));
214 }
215
216
217
218 template<class InputIt, typename std::enable_if<is_iterator<InputIt>::value>::type* = nullptr>
219 void insert(InputIt first, InputIt last) {
220 if(std::is_base_of<std::forward_iterator_tag,
221 typename std::iterator_traits<InputIt>::iterator_category>::value)
222 {
223 const auto nb_elements_insert = std::distance(first, last);
224 const std::size_t nb_free_buckets = std::size_t(float(bucket_count())*max_load_factor()) - size();
225
226 if(nb_elements_insert > 0 && nb_free_buckets < std::size_t(nb_elements_insert)) {
227 reserve(size() + std::size_t(nb_elements_insert));
228 }
229 }
230
231 for(auto it = first; it != last; ++it) {
232 insert_pair(*it);
233 }
234 }
235
236
237
238 #ifdef TSL_AH_HAS_STRING_VIEW
239 void insert(std::initializer_list<std::pair<std::basic_string_view<CharT>, T>> ilist) {
240 insert(ilist.begin(), ilist.end());
241 }
242 #else
243 void insert(std::initializer_list<std::pair<const CharT*, T>> ilist) {
244 insert(ilist.begin(), ilist.end());
245 }
246 #endif
247
248
249
250 #ifdef TSL_AH_HAS_STRING_VIEW
251 template<class M>
252 std::pair<iterator, bool> insert_or_assign(const std::basic_string_view<CharT>& key, M&& obj) {
253 return m_ht.insert_or_assign(key.data(), key.size(), std::forward<M>(obj));
254 }
255 #else
256 template<class M>
257 std::pair<iterator, bool> insert_or_assign(const CharT* key, M&& obj) {
258 return m_ht.insert_or_assign(key, std::char_traits<CharT>::length(key), std::forward<M>(obj));
259 }
260
261 template<class M>
262 std::pair<iterator, bool> insert_or_assign(const std::basic_string<CharT>& key, M&& obj) {
263 return m_ht.insert_or_assign(key.data(), key.size(), std::forward<M>(obj));
264 }
265 #endif
266 template<class M>
267 std::pair<iterator, bool> insert_or_assign_ks(const CharT* key, size_type key_size, M&& obj) {
268 return m_ht.insert_or_assign(key, key_size, std::forward<M>(obj));
269 }
270
271
272
273 #ifdef TSL_AH_HAS_STRING_VIEW
274 template<class... Args>
275 std::pair<iterator, bool> emplace(const std::basic_string_view<CharT>& key, Args&&... args) {
276 return m_ht.emplace(key.data(), key.size(), std::forward<Args>(args)...);
277 }
278 #else
279 template<class... Args>
280 std::pair<iterator, bool> emplace(const CharT* key, Args&&... args) {
281 return m_ht.emplace(key, std::char_traits<CharT>::length(key), std::forward<Args>(args)...);
282 }
283
284 template<class... Args>
285 std::pair<iterator, bool> emplace(const std::basic_string<CharT>& key, Args&&... args) {
286 return m_ht.emplace(key.data(), key.size(), std::forward<Args>(args)...);
287 }
288 #endif
289 template<class... Args>
290 std::pair<iterator, bool> emplace_ks(const CharT* key, size_type key_size, Args&&... args) {
291 return m_ht.emplace(key, key_size, std::forward<Args>(args)...);
292 }
293
294
295
296 /**
297 * Erase has an amortized O(1) runtime complexity, but even if it removes the key immediately,
298 * it doesn't do the same for the associated value T.
299 *
300 * T will only be removed when the ratio between the size of the map and
301 * the size of the map + the number of deleted values still stored is low enough.
302 *
303 * To force the deletion you can call shrink_to_fit.
304 */
305 iterator erase(const_iterator pos) { return m_ht.erase(pos); }
306
307 /**
308 * @copydoc erase(const_iterator pos)
309 */
310 iterator erase(const_iterator first, const_iterator last) { return m_ht.erase(first, last); }
311
312
313
314 #ifdef TSL_AH_HAS_STRING_VIEW
315 /**
316 * @copydoc erase(const_iterator pos)
317 */
318 size_type erase(const std::basic_string_view<CharT>& key) {
319 return m_ht.erase(key.data(), key.size());
320 }
321 #else
322 /**
323 * @copydoc erase(const_iterator pos)
324 */
325 size_type erase(const CharT* key) {
326 return m_ht.erase(key, std::char_traits<CharT>::length(key));
327 }
328
329 /**
330 * @copydoc erase(const_iterator pos)
331 */
332 size_type erase(const std::basic_string<CharT>& key) {
333 return m_ht.erase(key.data(), key.size());
334 }
335 #endif
336 /**
337 * @copydoc erase(const_iterator pos)
338 */
339 size_type erase_ks(const CharT* key, size_type key_size) {
340 return m_ht.erase(key, key_size);
341 }
342
343
344
345 #ifdef TSL_AH_HAS_STRING_VIEW
346 /**
347 * @copydoc erase_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
348 */
349 size_type erase(const std::basic_string_view<CharT>& key, std::size_t precalculated_hash) {
350 return m_ht.erase(key.data(), key.size(), precalculated_hash);
351 }
352 #else
353 /**
354 * @copydoc erase_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
355 */
356 size_type erase(const CharT* key, std::size_t precalculated_hash) {
357 return m_ht.erase(key, std::char_traits<CharT>::length(key), precalculated_hash);
358 }
359
360 /**
361 * @copydoc erase_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
362 */
363 size_type erase(const std::basic_string<CharT>& key, std::size_t precalculated_hash) {
364 return m_ht.erase(key.data(), key.size(), precalculated_hash);
365 }
366 #endif
367 /**
368 * @copydoc erase(const_iterator pos)
369 *
370 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
371 * as hash_function()(key). Useful to speed-up the lookup to the value if you already have the hash.
372 */
373 size_type erase_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash) {
374 return m_ht.erase(key, key_size, precalculated_hash);
375 }
376
377
378
379 void swap(array_map& other) { other.m_ht.swap(m_ht); }
380
381
382
383 /*
384 * Lookup
385 */
386 #ifdef TSL_AH_HAS_STRING_VIEW
387 T& at(const std::basic_string_view<CharT>& key) {
388 return m_ht.at(key.data(), key.size());
389 }
390
391 const T& at(const std::basic_string_view<CharT>& key) const {
392 return m_ht.at(key.data(), key.size());
393 }
394 #else
395 T& at(const CharT* key) {
396 return m_ht.at(key, std::char_traits<CharT>::length(key));
397 }
398
399 const T& at(const CharT* key) const {
400 return m_ht.at(key, std::char_traits<CharT>::length(key));
401 }
402
403 T& at(const std::basic_string<CharT>& key) {
404 return m_ht.at(key.data(), key.size());
405 }
406
407 const T& at(const std::basic_string<CharT>& key) const {
408 return m_ht.at(key.data(), key.size());
409 }
410 #endif
411 T& at_ks(const CharT* key, size_type key_size) {
412 return m_ht.at(key, key_size);
413 }
414
415 const T& at_ks(const CharT* key, size_type key_size) const {
416 return m_ht.at(key, key_size);
417 }
418
419
420
421 #ifdef TSL_AH_HAS_STRING_VIEW
422 /**
423 * @copydoc at_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
424 */
425 T& at(const std::basic_string_view<CharT>& key, std::size_t precalculated_hash) {
426 return m_ht.at(key.data(), key.size(), precalculated_hash);
427 }
428
429 /**
430 * @copydoc at_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
431 */
432 const T& at(const std::basic_string_view<CharT>& key, std::size_t precalculated_hash) const {
433 return m_ht.at(key.data(), key.size(), precalculated_hash);
434 }
435 #else
436 /**
437 * @copydoc at_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
438 */
439 T& at(const CharT* key, std::size_t precalculated_hash) {
440 return m_ht.at(key, std::char_traits<CharT>::length(key), precalculated_hash);
441 }
442
443 /**
444 * @copydoc at_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
445 */
446 const T& at(const CharT* key, std::size_t precalculated_hash) const {
447 return m_ht.at(key, std::char_traits<CharT>::length(key), precalculated_hash);
448 }
449
450 /**
451 * @copydoc at_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
452 */
453 T& at(const std::basic_string<CharT>& key, std::size_t precalculated_hash) {
454 return m_ht.at(key.data(), key.size(), precalculated_hash);
455 }
456
457 /**
458 * @copydoc at_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
459 */
460 const T& at(const std::basic_string<CharT>& key, std::size_t precalculated_hash) const {
461 return m_ht.at(key.data(), key.size(), precalculated_hash);
462 }
463 #endif
464 /**
465 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
466 * as hash_function()(key). Useful to speed-up the lookup to the value if you already have the hash.
467 */
468 T& at_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash) {
469 return m_ht.at(key, key_size, precalculated_hash);
470 }
471
472 /**
473 * @copydoc at_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
474 */
475 const T& at_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash) const {
476 return m_ht.at(key, key_size, precalculated_hash);
477 }
478
479
480
481 #ifdef TSL_AH_HAS_STRING_VIEW
482 T& operator[](const std::basic_string_view<CharT>& key) { return m_ht.access_operator(key.data(), key.size()); }
483 #else
484 T& operator[](const CharT* key) { return m_ht.access_operator(key, std::char_traits<CharT>::length(key)); }
485 T& operator[](const std::basic_string<CharT>& key) { return m_ht.access_operator(key.data(), key.size()); }
486 #endif
487
488
489
490 #ifdef TSL_AH_HAS_STRING_VIEW
491 size_type count(const std::basic_string_view<CharT>& key) const {
492 return m_ht.count(key.data(), key.size());
493 }
494 #else
495 size_type count(const CharT* key) const {
496 return m_ht.count(key, std::char_traits<CharT>::length(key));
497 }
498
499 size_type count(const std::basic_string<CharT>& key) const {
500 return m_ht.count(key.data(), key.size());
501 }
502 #endif
503 size_type count_ks(const CharT* key, size_type key_size) const {
504 return m_ht.count(key, key_size);
505 }
506
507
508
509 #ifdef TSL_AH_HAS_STRING_VIEW
510 /**
511 * @copydoc count_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash) const
512 */
513 size_type count(const std::basic_string_view<CharT>& key, std::size_t precalculated_hash) const {
514 return m_ht.count(key.data(), key.size(), precalculated_hash);
515 }
516 #else
517 /**
518 * @copydoc count_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash) const
519 */
520 size_type count(const CharT* key, std::size_t precalculated_hash) const {
521 return m_ht.count(key, std::char_traits<CharT>::length(key), precalculated_hash);
522 }
523
524 /**
525 * @copydoc count_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash) const
526 */
527 size_type count(const std::basic_string<CharT>& key, std::size_t precalculated_hash) const {
528 return m_ht.count(key.data(), key.size(), precalculated_hash);
529 }
530 #endif
531 /**
532 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
533 * as hash_function()(key). Useful to speed-up the lookup to the value if you already have the hash.
534 */
535 size_type count_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash) const {
536 return m_ht.count(key, key_size, precalculated_hash);
537 }
538
539
540
541 #ifdef TSL_AH_HAS_STRING_VIEW
542 iterator find(const std::basic_string_view<CharT>& key) {
543 return m_ht.find(key.data(), key.size());
544 }
545
546 const_iterator find(const std::basic_string_view<CharT>& key) const {
547 return m_ht.find(key.data(), key.size());
548 }
549 #else
550 iterator find(const CharT* key) {
551 return m_ht.find(key, std::char_traits<CharT>::length(key));
552 }
553
554 const_iterator find(const CharT* key) const {
555 return m_ht.find(key, std::char_traits<CharT>::length(key));
556 }
557
558 iterator find(const std::basic_string<CharT>& key) {
559 return m_ht.find(key.data(), key.size());
560 }
561
562 const_iterator find(const std::basic_string<CharT>& key) const {
563 return m_ht.find(key.data(), key.size());
564 }
565 #endif
566 iterator find_ks(const CharT* key, size_type key_size) {
567 return m_ht.find(key, key_size);
568 }
569
570 const_iterator find_ks(const CharT* key, size_type key_size) const {
571 return m_ht.find(key, key_size);
572 }
573
574
575
576 #ifdef TSL_AH_HAS_STRING_VIEW
577 /**
578 * @copydoc find_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
579 */
580 iterator find(const std::basic_string_view<CharT>& key, std::size_t precalculated_hash) {
581 return m_ht.find(key.data(), key.size(), precalculated_hash);
582 }
583
584 /**
585 * @copydoc find_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
586 */
587 const_iterator find(const std::basic_string_view<CharT>& key, std::size_t precalculated_hash) const {
588 return m_ht.find(key.data(), key.size(), precalculated_hash);
589 }
590 #else
591 /**
592 * @copydoc find_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
593 */
594 iterator find(const CharT* key, std::size_t precalculated_hash) {
595 return m_ht.find(key, std::char_traits<CharT>::length(key), precalculated_hash);
596 }
597
598 /**
599 * @copydoc find_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
600 */
601 const_iterator find(const CharT* key, std::size_t precalculated_hash) const {
602 return m_ht.find(key, std::char_traits<CharT>::length(key), precalculated_hash);
603 }
604
605 /**
606 * @copydoc find_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
607 */
608 iterator find(const std::basic_string<CharT>& key, std::size_t precalculated_hash) {
609 return m_ht.find(key.data(), key.size(), precalculated_hash);
610 }
611
612 /**
613 * @copydoc find_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
614 */
615 const_iterator find(const std::basic_string<CharT>& key, std::size_t precalculated_hash) const {
616 return m_ht.find(key.data(), key.size(), precalculated_hash);
617 }
618 #endif
619 /**
620 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
621 * as hash_function()(key). Useful to speed-up the lookup to the value if you already have the hash.
622 */
623 iterator find_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash) {
624 return m_ht.find(key, key_size, precalculated_hash);
625 }
626
627 /**
628 * @copydoc find_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
629 */
630 const_iterator find_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash) const {
631 return m_ht.find(key, key_size, precalculated_hash);
632 }
633
634
635
636 #ifdef TSL_AH_HAS_STRING_VIEW
637 std::pair<iterator, iterator> equal_range(const std::basic_string_view<CharT>& key) {
638 return m_ht.equal_range(key.data(), key.size());
639 }
640
641 std::pair<const_iterator, const_iterator> equal_range(const std::basic_string_view<CharT>& key) const {
642 return m_ht.equal_range(key.data(), key.size());
643 }
644 #else
645 std::pair<iterator, iterator> equal_range(const CharT* key) {
646 return m_ht.equal_range(key, std::char_traits<CharT>::length(key));
647 }
648
649 std::pair<const_iterator, const_iterator> equal_range(const CharT* key) const {
650 return m_ht.equal_range(key, std::char_traits<CharT>::length(key));
651 }
652
653 std::pair<iterator, iterator> equal_range(const std::basic_string<CharT>& key) {
654 return m_ht.equal_range(key.data(), key.size());
655 }
656
657 std::pair<const_iterator, const_iterator> equal_range(const std::basic_string<CharT>& key) const {
658 return m_ht.equal_range(key.data(), key.size());
659 }
660 #endif
661 std::pair<iterator, iterator> equal_range_ks(const CharT* key, size_type key_size) {
662 return m_ht.equal_range(key, key_size);
663 }
664
665 std::pair<const_iterator, const_iterator> equal_range_ks(const CharT* key, size_type key_size) const {
666 return m_ht.equal_range(key, key_size);
667 }
668
669
670
671 #ifdef TSL_AH_HAS_STRING_VIEW
672 /**
673 * @copydoc equal_range_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
674 */
675 std::pair<iterator, iterator> equal_range(const std::basic_string_view<CharT>& key, std::size_t precalculated_hash) {
676 return m_ht.equal_range(key.data(), key.size(), precalculated_hash);
677 }
678
679 /**
680 * @copydoc equal_range_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
681 */
682 std::pair<const_iterator, const_iterator> equal_range(const std::basic_string_view<CharT>& key, std::size_t precalculated_hash) const {
683 return m_ht.equal_range(key.data(), key.size(), precalculated_hash);
684 }
685 #else
686 /**
687 * @copydoc equal_range_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
688 */
689 std::pair<iterator, iterator> equal_range(const CharT* key, std::size_t precalculated_hash) {
690 return m_ht.equal_range(key, std::char_traits<CharT>::length(key), precalculated_hash);
691 }
692
693 /**
694 * @copydoc equal_range_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
695 */
696 std::pair<const_iterator, const_iterator> equal_range(const CharT* key, std::size_t precalculated_hash) const {
697 return m_ht.equal_range(key, std::char_traits<CharT>::length(key), precalculated_hash);
698 }
699
700 /**
701 * @copydoc equal_range_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
702 */
703 std::pair<iterator, iterator> equal_range(const std::basic_string<CharT>& key, std::size_t precalculated_hash) {
704 return m_ht.equal_range(key.data(), key.size(), precalculated_hash);
705 }
706
707 /**
708 * @copydoc equal_range_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
709 */
710 std::pair<const_iterator, const_iterator> equal_range(const std::basic_string<CharT>& key, std::size_t precalculated_hash) const {
711 return m_ht.equal_range(key.data(), key.size(), precalculated_hash);
712 }
713 #endif
714 /**
715 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same
716 * as hash_function()(key). Useful to speed-up the lookup to the value if you already have the hash.
717 */
718 std::pair<iterator, iterator> equal_range_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash) {
719 return m_ht.equal_range(key, key_size, precalculated_hash);
720 }
721
722 /**
723 * @copydoc equal_range_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash)
724 */
725 std::pair<const_iterator, const_iterator> equal_range_ks(const CharT* key, size_type key_size, std::size_t precalculated_hash) const {
726 return m_ht.equal_range(key, key_size, precalculated_hash);
727 }
728
729
730
731 /*
732 * Bucket interface
733 */
734 size_type bucket_count() const { return m_ht.bucket_count(); }
735 size_type max_bucket_count() const { return m_ht.max_bucket_count(); }
736
737
738 /*
739 * Hash policy
740 */
741 float load_factor() const { return m_ht.load_factor(); }
742 float max_load_factor() const { return m_ht.max_load_factor(); }
743 void max_load_factor(float ml) { m_ht.max_load_factor(ml); }
744
745 void rehash(size_type count) { m_ht.rehash(count); }
746 void reserve(size_type count) { m_ht.reserve(count); }
747
748
749 /*
750 * Observers
751 */
752 hasher hash_function() const { return m_ht.hash_function(); }
753 key_equal key_eq() const { return m_ht.key_eq(); }
754
755
756 /*
757 * Other
758 */
759 /**
760 * Return the `const_iterator it` as an `iterator`.
761 */
762 iterator mutable_iterator(const_iterator it) noexcept { return m_ht.mutable_iterator(it); }
763
764 /**
765 * Serialize the map through the `serializer` parameter.
766 *
767 * The `serializer` parameter must be a function object that supports the following calls:
768 * - `template<typename U> void operator()(const U& value);` where the types `std::uint64_t`, `float` and `T` must be supported for U.
769 * - `void operator()(const CharT* value, std::size_t value_size);`
770 *
771 * The implementation leaves binary compatibility (endianness, IEEE 754 for floats, ...) of the types it serializes
772 * in the hands of the `Serializer` function object if compatibility is required.
773 */
774 template<class Serializer>
775 void serialize(Serializer& serializer) const {
776 m_ht.serialize(serializer);
777 }
778
779 /**
780 * Deserialize a previously serialized map through the `deserializer` parameter.
781 *
782 * The `deserializer` parameter must be a function object that supports the following calls:
783 * - `template<typename U> U operator()();` where the types `std::uint64_t`, `float` and `T` must be supported for U.
784 * - `void operator()(CharT* value_out, std::size_t value_size);`
785 *
786 * If the deserialized hash map type is hash compatible with the serialized map, the deserialization process can be
787 * sped up by setting `hash_compatible` to true. To be hash compatible, the Hash (take care of the 32-bits vs 64 bits),
788 * KeyEqual, GrowthPolicy, StoreNullTerminator, KeySizeT and IndexSizeT must behave the same than the ones used on the
789 * serialized map. Otherwise the behaviour is undefined with `hash_compatible` sets to true.
790 *
791 * The behaviour is undefined if the type `CharT` and `T` of the `array_map` are not the same as the
792 * types used during serialization.
793 *
794 * The implementation leaves binary compatibility (endianness, IEEE 754 for floats, size of int, ...) of the types it
795 * deserializes in the hands of the `Deserializer` function object if compatibility is required.
796 */
797 template<class Deserializer>
798 static array_map deserialize(Deserializer& deserializer, bool hash_compatible = false) {
799 array_map map(0);
800 map.m_ht.deserialize(deserializer, hash_compatible);
801
802 return map;
803 }
804
805 friend bool operator==(const array_map& lhs, const array_map& rhs) {
806 if(lhs.size() != rhs.size()) {
807 return false;
808 }
809
810 for(auto it = lhs.cbegin(); it != lhs.cend(); ++it) {
811 const auto it_element_rhs = rhs.find_ks(it.key(), it.key_size());
812 if(it_element_rhs == rhs.cend() || it.value() != it_element_rhs.value()) {
813 return false;
814 }
815 }
816
817 return true;
818 }
819
820 friend bool operator!=(const array_map& lhs, const array_map& rhs) {
821 return !operator==(lhs, rhs);
822 }
823
824 friend void swap(array_map& lhs, array_map& rhs) {
825 lhs.swap(rhs);
826 }
827
828 private:
829 template<class U, class V>
830 void insert_pair(const std::pair<U, V>& value) {
831 insert(value.first, value.second);
832 }
833
834 template<class U, class V>
835 void insert_pair(std::pair<U, V>&& value) {
836 insert(value.first, std::move(value.second));
837 }
838
839 public:
840 static const size_type MAX_KEY_SIZE = ht::MAX_KEY_SIZE;
841
842 private:
843 ht m_ht;
844 };
845
846
847 /**
848 * Same as
849 * `tsl::array_map<CharT, T, Hash, KeyEqual, StoreNullTerminator, KeySizeT, IndexSizeT, tsl::ah::prime_growth_policy>`.
850 */
851 template<class CharT,
852 class T,
853 class Hash = tsl::ah::str_hash<CharT>,
854 class KeyEqual = tsl::ah::str_equal<CharT>,
855 bool StoreNullTerminator = true,
856 class KeySizeT = std::uint16_t,
857 class IndexSizeT = std::uint32_t>
858 using array_pg_map = array_map<CharT, T, Hash, KeyEqual, StoreNullTerminator,
859 KeySizeT, IndexSizeT, tsl::ah::prime_growth_policy>;
860
861 } //end namespace tsl
862
863 #endif