Debian Codegraph @

third_party/hat-trie/tsl/htrie_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_HTRIE_MAP_H
25 #define TSL_HTRIE_MAP_H
26
27 #include <cstddef>
28 #include <cstring>
29 #include <initializer_list>
30 #include <string>
31 #include <utility>
32 #include "htrie_hash.h"
33
34 namespace tsl {
35
36 /**
37 * Implementation of a hat-trie map.
38 *
39 * The value T must be either nothrow move-constructible/assignable, copy-constructible or both.
40 *
41 * The size of a key string is limited to std::numeric_limits<KeySizeT>::max() - 1.
42 * That is 65 535 characters by default, but can be raised with the KeySizeT template parameter.
43 * See max_key_size() for an easy access to this limit.
44 *
45 * Iterators invalidation:
46 * - clear, operator=: always invalidate the iterators.
47 * - insert, emplace, operator[]: always invalidate the iterators.
48 * - erase: always invalidate the iterators.
49 */
50 template<class CharT,
51 class T,
52 class Hash = tsl::ah::str_hash<CharT>,
53 class KeySizeT = std::uint16_t>
54 class htrie_map {
55 private:
56 template<typename U>
57 using is_iterator = tsl::detail_array_hash::is_iterator<U>;
58
59 using ht = tsl::detail_htrie_hash::htrie_hash<CharT, T, Hash, KeySizeT>;
60
61 public:
62 using char_type = typename ht::char_type;
63 using mapped_type = T;
64 using key_size_type = typename ht::key_size_type;
65 using size_type = typename ht::size_type;
66 using hasher = typename ht::hasher;
67 using iterator = typename ht::iterator;
68 using const_iterator = typename ht::const_iterator;
69 using prefix_iterator = typename ht::prefix_iterator;
70 using const_prefix_iterator = typename ht::const_prefix_iterator;
71
72 public:
73 explicit htrie_map(const Hash& hash = Hash()): m_ht(hash, ht::HASH_NODE_DEFAULT_MAX_LOAD_FACTOR,
74 ht::DEFAULT_BURST_THRESHOLD)
75 {
76 }
77
78 explicit htrie_map(size_type burst_threshold,
79 const Hash& hash = Hash()): m_ht(hash, ht::HASH_NODE_DEFAULT_MAX_LOAD_FACTOR,
80 burst_threshold)
81 {
82 }
83
84 template<class InputIt, typename std::enable_if<is_iterator<InputIt>::value>::type* = nullptr>
85 htrie_map(InputIt first, InputIt last,
86 const Hash& hash = Hash()): htrie_map(hash)
87 {
88 insert(first, last);
89 }
90
91
92
93 #ifdef TSL_HT_HAS_STRING_VIEW
94 htrie_map(std::initializer_list<std::pair<std::basic_string_view<CharT>, T>> init,
95 const Hash& hash = Hash()): htrie_map(hash)
96 {
97 insert(init);
98 }
99 #else
100 htrie_map(std::initializer_list<std::pair<const CharT*, T>> init,
101 const Hash& hash = Hash()): htrie_map(hash)
102 {
103 insert(init);
104 }
105 #endif
106
107
108
109 #ifdef TSL_HT_HAS_STRING_VIEW
110 htrie_map& operator=(std::initializer_list<std::pair<std::basic_string_view<CharT>, T>> ilist) {
111 clear();
112 insert(ilist);
113
114 return *this;
115 }
116 #else
117 htrie_map& operator=(std::initializer_list<std::pair<const CharT*, T>> ilist) {
118 clear();
119 insert(ilist);
120
121 return *this;
122 }
123 #endif
124
125
126
127 /*
128 * Iterators
129 */
130 iterator begin() noexcept { return m_ht.begin(); }
131 const_iterator begin() const noexcept { return m_ht.begin(); }
132 const_iterator cbegin() const noexcept { return m_ht.cbegin(); }
133
134 iterator end() noexcept { return m_ht.end(); }
135 const_iterator end() const noexcept { return m_ht.end(); }
136 const_iterator cend() const noexcept { return m_ht.cend(); }
137
138
139 /*
140 * Capacity
141 */
142 bool empty() const noexcept { return m_ht.empty(); }
143 size_type size() const noexcept { return m_ht.size(); }
144 size_type max_size() const noexcept { return m_ht.max_size(); }
145 size_type max_key_size() const noexcept { return m_ht.max_key_size(); }
146
147 /**
148 * Call shrink_to_fit() on each hash node of the hat-trie to reduce its size.
149 */
150 void shrink_to_fit() { m_ht.shrink_to_fit(); }
151
152
153 /*
154 * Modifiers
155 */
156 void clear() noexcept { m_ht.clear(); }
157
158
159
160 std::pair<iterator, bool> insert_ks(const CharT* key, size_type key_size, const T& value) {
161 return m_ht.insert(key, key_size, value);
162 }
163 #ifdef TSL_HT_HAS_STRING_VIEW
164 std::pair<iterator, bool> insert(const std::basic_string_view<CharT>& key, const T& value) {
165 return m_ht.insert(key.data(), key.size(), value);
166 }
167 #else
168 std::pair<iterator, bool> insert(const CharT* key, const T& value) {
169 return m_ht.insert(key, std::strlen(key), value);
170 }
171
172 std::pair<iterator, bool> insert(const std::basic_string<CharT>& key, const T& value) {
173 return m_ht.insert(key.data(), key.size(), value);
174 }
175 #endif
176
177
178
179 std::pair<iterator, bool> insert_ks(const CharT* key, size_type key_size, T&& value) {
180 return m_ht.insert(key, key_size, std::move(value));
181 }
182 #ifdef TSL_HT_HAS_STRING_VIEW
183 std::pair<iterator, bool> insert(const std::basic_string_view<CharT>& key, T&& value) {
184 return m_ht.insert(key.data(), key.size(), std::move(value));
185 }
186 #else
187 std::pair<iterator, bool> insert(const CharT* key, T&& value) {
188 return m_ht.insert(key, std::strlen(key), std::move(value));
189 }
190
191 std::pair<iterator, bool> insert(const std::basic_string<CharT>& key, T&& value) {
192 return m_ht.insert(key.data(), key.size(), std::move(value));
193 }
194 #endif
195
196
197
198 template<class InputIt, typename std::enable_if<is_iterator<InputIt>::value>::type* = nullptr>
199 void insert(InputIt first, InputIt last) {
200 for(auto it = first; it != last; ++it) {
201 insert_pair(*it);
202 }
203 }
204
205
206
207 #ifdef TSL_HT_HAS_STRING_VIEW
208 void insert(std::initializer_list<std::pair<std::basic_string_view<CharT>, T>> ilist) {
209 insert(ilist.begin(), ilist.end());
210 }
211 #else
212 void insert(std::initializer_list<std::pair<const CharT*, T>> ilist) {
213 insert(ilist.begin(), ilist.end());
214 }
215 #endif
216
217
218
219 template<class... Args>
220 std::pair<iterator, bool> emplace_ks(const CharT* key, size_type key_size, Args&&... args) {
221 return m_ht.insert(key, key_size, std::forward<Args>(args)...);
222 }
223 #ifdef TSL_HT_HAS_STRING_VIEW
224 template<class... Args>
225 std::pair<iterator, bool> emplace(const std::basic_string_view<CharT>& key, Args&&... args) {
226 return m_ht.insert(key.data(), key.size(), std::forward<Args>(args)...);
227 }
228 #else
229 template<class... Args>
230 std::pair<iterator, bool> emplace(const CharT* key, Args&&... args) {
231 return m_ht.insert(key, std::strlen(key), std::forward<Args>(args)...);
232 }
233
234 template<class... Args>
235 std::pair<iterator, bool> emplace(const std::basic_string<CharT>& key, Args&&... args) {
236 return m_ht.insert(key.data(), key.size(), std::forward<Args>(args)...);
237 }
238 #endif
239
240
241
242 iterator erase(const_iterator pos) { return m_ht.erase(pos); }
243 iterator erase(const_iterator first, const_iterator last) { return m_ht.erase(first, last); }
244
245
246
247 size_type erase_ks(const CharT* key, size_type key_size) {
248 return m_ht.erase(key, key_size);
249 }
250 #ifdef TSL_HT_HAS_STRING_VIEW
251 size_type erase(const std::basic_string_view<CharT>& key) {
252 return m_ht.erase(key.data(), key.size());
253 }
254 #else
255 size_type erase(const CharT* key) {
256 return m_ht.erase(key, std::strlen(key));
257 }
258
259 size_type erase(const std::basic_string<CharT>& key) {
260 return m_ht.erase(key.data(), key.size());
261 }
262 #endif
263
264
265
266 /**
267 * Erase all the elements which have 'prefix' as prefix. Return the number of erase elements.
268 */
269 size_type erase_prefix_ks(const CharT* prefix, size_type prefix_size) {
270 return m_ht.erase_prefix(prefix, prefix_size);
271 }
272 #ifdef TSL_HT_HAS_STRING_VIEW
273 /**
274 * @copydoc erase_prefix_ks(const CharT* prefix, size_type prefix_size)
275 */
276 size_type erase_prefix(const std::basic_string_view<CharT>& prefix) {
277 return m_ht.erase_prefix(prefix.data(), prefix.size());
278 }
279 #else
280 /**
281 * @copydoc erase_prefix_ks(const CharT* prefix, size_type prefix_size)
282 */
283 size_type erase_prefix(const CharT* prefix) {
284 return m_ht.erase_prefix(prefix, std::strlen(prefix));
285 }
286
287 /**
288 * @copydoc erase_prefix_ks(const CharT* prefix, size_type prefix_size)
289 */
290 size_type erase_prefix(const std::basic_string<CharT>& prefix) {
291 return m_ht.erase_prefix(prefix.data(), prefix.size());
292 }
293 #endif
294
295
296
297 void swap(htrie_map& other) { other.m_ht.swap(m_ht); }
298
299 /*
300 * Lookup
301 */
302 T& at_ks(const CharT* key, size_type key_size) { return m_ht.at(key, key_size); }
303 const T& at_ks(const CharT* key, size_type key_size) const { return m_ht.at(key, key_size); }
304
305 #ifdef TSL_HT_HAS_STRING_VIEW
306 T& at(const std::basic_string_view<CharT>& key) { return m_ht.at(key.data(), key.size()); }
307 const T& at(const std::basic_string_view<CharT>& key) const { return m_ht.at(key.data(), key.size()); }
308 #else
309 T& at(const CharT* key) { return m_ht.at(key, std::strlen(key)); }
310 const T& at(const CharT* key) const { return m_ht.at(key, std::strlen(key)); }
311
312 T& at(const std::basic_string<CharT>& key) { return m_ht.at(key.data(), key.size()); }
313 const T& at(const std::basic_string<CharT>& key) const { return m_ht.at(key.data(), key.size()); }
314 #endif
315
316
317
318 #ifdef TSL_HT_HAS_STRING_VIEW
319 T& operator[](const std::basic_string_view<CharT>& key) { return m_ht.access_operator(key.data(), key.size()); }
320 #else
321 T& operator[](const CharT* key) { return m_ht.access_operator(key, std::strlen(key)); }
322 T& operator[](const std::basic_string<CharT>& key) { return m_ht.access_operator(key.data(), key.size()); }
323 #endif
324
325
326
327 size_type count_ks(const CharT* key, size_type key_size) const { return m_ht.count(key, key_size); }
328 #ifdef TSL_HT_HAS_STRING_VIEW
329 size_type count(const std::basic_string_view<CharT>& key) const { return m_ht.count(key.data(), key.size()); }
330 #else
331 size_type count(const CharT* key) const { return m_ht.count(key, std::strlen(key)); }
332 size_type count(const std::basic_string<CharT>& key) const { return m_ht.count(key.data(), key.size()); }
333 #endif
334
335
336
337 iterator find_ks(const CharT* key, size_type key_size) {
338 return m_ht.find(key, key_size);
339 }
340
341 const_iterator find_ks(const CharT* key, size_type key_size) const {
342 return m_ht.find(key, key_size);
343 }
344 #ifdef TSL_HT_HAS_STRING_VIEW
345 iterator find(const std::basic_string_view<CharT>& key) {
346 return m_ht.find(key.data(), key.size());
347 }
348
349 const_iterator find(const std::basic_string_view<CharT>& key) const {
350 return m_ht.find(key.data(), key.size());
351 }
352 #else
353 iterator find(const CharT* key) {
354 return m_ht.find(key, std::strlen(key));
355 }
356
357 const_iterator find(const CharT* key) const {
358 return m_ht.find(key, std::strlen(key));
359 }
360
361 iterator find(const std::basic_string<CharT>& key) {
362 return m_ht.find(key.data(), key.size());
363 }
364
365 const_iterator find(const std::basic_string<CharT>& key) const {
366 return m_ht.find(key.data(), key.size());
367 }
368 #endif
369
370
371
372 std::pair<iterator, iterator> equal_range_ks(const CharT* key, size_type key_size) {
373 return m_ht.equal_range(key, key_size);
374 }
375
376 std::pair<const_iterator, const_iterator> equal_range_ks(const CharT* key, size_type key_size) const {
377 return m_ht.equal_range(key, key_size);
378 }
379 #ifdef TSL_HT_HAS_STRING_VIEW
380 std::pair<iterator, iterator> equal_range(const std::basic_string_view<CharT>& key) {
381 return m_ht.equal_range(key.data(), key.size());
382 }
383
384 std::pair<const_iterator, const_iterator> equal_range(const std::basic_string_view<CharT>& key) const {
385 return m_ht.equal_range(key.data(), key.size());
386 }
387 #else
388 std::pair<iterator, iterator> equal_range(const CharT* key) {
389 return m_ht.equal_range(key, std::strlen(key));
390 }
391
392 std::pair<const_iterator, const_iterator> equal_range(const CharT* key) const {
393 return m_ht.equal_range(key, std::strlen(key));
394 }
395
396 std::pair<iterator, iterator> equal_range(const std::basic_string<CharT>& key) {
397 return m_ht.equal_range(key.data(), key.size());
398 }
399
400 std::pair<const_iterator, const_iterator> equal_range(const std::basic_string<CharT>& key) const {
401 return m_ht.equal_range(key.data(), key.size());
402 }
403 #endif
404
405
406 /**
407 * Return a range containing all the elements which have 'prefix' as prefix. The range is defined by a pair
408 * of iterator, the first being the begin iterator and the second being the end iterator.
409 */
410 std::pair<prefix_iterator, prefix_iterator> equal_prefix_range_ks(const CharT* prefix, size_type prefix_size) {
411 return m_ht.equal_prefix_range(prefix, prefix_size);
412 }
413
414 /**
415 * @copydoc equal_prefix_range_ks(const CharT* prefix, size_type prefix_size)
416 */
417 std::pair<const_prefix_iterator, const_prefix_iterator> equal_prefix_range_ks(const CharT* prefix, size_type prefix_size) const {
418 return m_ht.equal_prefix_range(prefix, prefix_size);
419 }
420 #ifdef TSL_HT_HAS_STRING_VIEW
421 /**
422 * @copydoc equal_prefix_range_ks(const CharT* prefix, size_type prefix_size)
423 */
424 std::pair<prefix_iterator, prefix_iterator> equal_prefix_range(const std::basic_string_view<CharT>& prefix) {
425 return m_ht.equal_prefix_range(prefix.data(), prefix.size());
426 }
427
428 /**
429 * @copydoc equal_prefix_range_ks(const CharT* prefix, size_type prefix_size)
430 */
431 std::pair<const_prefix_iterator, const_prefix_iterator> equal_prefix_range(const std::basic_string_view<CharT>& prefix) const {
432 return m_ht.equal_prefix_range(prefix.data(), prefix.size());
433 }
434 #else
435 /**
436 * @copydoc equal_prefix_range_ks(const CharT* prefix, size_type prefix_size)
437 */
438 std::pair<prefix_iterator, prefix_iterator> equal_prefix_range(const CharT* prefix) {
439 return m_ht.equal_prefix_range(prefix, std::strlen(prefix));
440 }
441
442 /**
443 * @copydoc equal_prefix_range_ks(const CharT* prefix, size_type prefix_size)
444 */
445 std::pair<const_prefix_iterator, const_prefix_iterator> equal_prefix_range(const CharT* prefix) const {
446 return m_ht.equal_prefix_range(prefix, std::strlen(prefix));
447 }
448
449 /**
450 * @copydoc equal_prefix_range_ks(const CharT* prefix, size_type prefix_size)
451 */
452 std::pair<prefix_iterator, prefix_iterator> equal_prefix_range(const std::basic_string<CharT>& prefix) {
453 return m_ht.equal_prefix_range(prefix.data(), prefix.size());
454 }
455
456 /**
457 * @copydoc equal_prefix_range_ks(const CharT* prefix, size_type prefix_size)
458 */
459 std::pair<const_prefix_iterator, const_prefix_iterator> equal_prefix_range(const std::basic_string<CharT>& prefix) const {
460 return m_ht.equal_prefix_range(prefix.data(), prefix.size());
461 }
462 #endif
463
464
465
466 /**
467 * Return the element in the trie which is the longest prefix of `key`. If no
468 * element in the trie is a prefix of `key`, the end iterator is returned.
469 *
470 * Example:
471 *
472 * tsl::htrie_map<char, int> map = {{"/foo", 1}, {"/foo/bar", 1}};
473 *
474 * map.longest_prefix("/foo"); // returns {"/foo", 1}
475 * map.longest_prefix("/foo/baz"); // returns {"/foo", 1}
476 * map.longest_prefix("/foo/bar/baz"); // returns {"/foo/bar", 1}
477 * map.longest_prefix("/foo/bar/"); // returns {"/foo/bar", 1}
478 * map.longest_prefix("/bar"); // returns end()
479 * map.longest_prefix(""); // returns end()
480 */
481 iterator longest_prefix_ks(const CharT* key, size_type key_size) {
482 return m_ht.longest_prefix(key, key_size);
483 }
484
485 /**
486 * @copydoc longest_prefix_ks(const CharT* key, size_type key_size)
487 */
488 const_iterator longest_prefix_ks(const CharT* key, size_type key_size) const {
489 return m_ht.longest_prefix(key, key_size);
490 }
491 #ifdef TSL_HT_HAS_STRING_VIEW
492 /**
493 * @copydoc longest_prefix_ks(const CharT* key, size_type key_size)
494 */
495 iterator longest_prefix(const std::basic_string_view<CharT>& key) {
496 return m_ht.longest_prefix(key.data(), key.size());
497 }
498
499 /**
500 * @copydoc longest_prefix_ks(const CharT* key, size_type key_size)
501 */
502 const_iterator longest_prefix(const std::basic_string_view<CharT>& key) const {
503 return m_ht.longest_prefix(key.data(), key.size());
504 }
505 #else
506 /**
507 * @copydoc longest_prefix_ks(const CharT* key, size_type key_size)
508 */
509 iterator longest_prefix(const CharT* key) {
510 return m_ht.longest_prefix(key, std::strlen(key));
511 }
512
513 /**
514 * @copydoc longest_prefix_ks(const CharT* key, size_type key_size)
515 */
516 const_iterator longest_prefix(const CharT* key) const {
517 return m_ht.longest_prefix(key, std::strlen(key));
518 }
519
520 /**
521 * @copydoc longest_prefix_ks(const CharT* key, size_type key_size)
522 */
523 iterator longest_prefix(const std::basic_string<CharT>& key) {
524 return m_ht.longest_prefix(key.data(), key.size());
525 }
526
527 /**
528 * @copydoc longest_prefix_ks(const CharT* key, size_type key_size)
529 */
530 const_iterator longest_prefix(const std::basic_string<CharT>& key) const {
531 return m_ht.longest_prefix(key.data(), key.size());
532 }
533 #endif
534
535
536
537 /*
538 * Hash policy
539 */
540 float max_load_factor() const { return m_ht.max_load_factor(); }
541 void max_load_factor(float ml) { m_ht.max_load_factor(ml); }
542
543
544 /*
545 * Burst policy
546 */
547 size_type burst_threshold() const { return m_ht.burst_threshold(); }
548 void burst_threshold(size_type threshold) { m_ht.burst_threshold(threshold); }
549
550
551 /*
552 * Observers
553 */
554 hasher hash_function() const { return m_ht.hash_function(); }
555
556
557
558 /*
559 * Other
560 */
561
562 /**
563 * Serialize the map through the `serializer` parameter.
564 *
565 * The `serializer` parameter must be a function object that supports the following calls:
566 * - `void operator()(const U& value);` where the types `std::uint64_t`, `float` and `T` must be supported for U.
567 * - `void operator()(const CharT* value, std::size_t value_size);`
568 *
569 * The implementation leaves binary compatibility (endianness, IEEE 754 for floats, ...) of the types it serializes
570 * in the hands of the `Serializer` function object if compatibility is required.
571 */
572 template<class Serializer>
573 void serialize(Serializer& serializer) const {
574 m_ht.serialize(serializer);
575 }
576
577
578 /**
579 * Deserialize a previously serialized map through the `deserializer` parameter.
580 *
581 * The `deserializer` parameter must be a function object that supports the following calls:
582 * - `template<typename U> U operator()();` where the types `std::uint64_t`, `float` and `T` must be supported for U.
583 * - `void operator()(CharT* value_out, std::size_t value_size);`
584 *
585 * If the deserialized hash map part of the hat-trie is hash compatible with the serialized map, the deserialization process
586 * can be sped up by setting `hash_compatible` to true. To be hash compatible, the Hash (take care of the 32-bits vs 64 bits),
587 * and KeySizeT must behave the same than the ones used in the serialized map. Otherwise the behaviour is undefined
588 * with `hash_compatible` sets to true.
589 *
590 * The behaviour is undefined if the type `CharT` and `T` of the `htrie_map` are not the same as the
591 * types used during serialization.
592 *
593 * The implementation leaves binary compatibility (endianness, IEEE 754 for floats, size of int, ...) of the types it
594 * deserializes in the hands of the `Deserializer` function object if compatibility is required.
595 */
596 template<class Deserializer>
597 static htrie_map deserialize(Deserializer& deserializer, bool hash_compatible = false) {
598 htrie_map map;
599 map.m_ht.deserialize(deserializer, hash_compatible);
600
601 return map;
602 }
603
604 friend bool operator==(const htrie_map& lhs, const htrie_map& rhs) {
605 if(lhs.size() != rhs.size()) {
606 return false;
607 }
608
609 std::string key_buffer;
610 for(auto it = lhs.cbegin(); it != lhs.cend(); ++it) {
611 it.key(key_buffer);
612
613 const auto it_element_rhs = rhs.find(key_buffer);
614 if(it_element_rhs == rhs.cend() || it.value() != it_element_rhs.value()) {
615 return false;
616 }
617 }
618
619 return true;
620 }
621
622 friend bool operator!=(const htrie_map& lhs, const htrie_map& rhs) {
623 return !operator==(lhs, rhs);
624 }
625
626 friend void swap(htrie_map& lhs, htrie_map& rhs) {
627 lhs.swap(rhs);
628 }
629
630 private:
631 template<class U, class V>
632 void insert_pair(const std::pair<U, V>& value) {
633 insert(value.first, value.second);
634 }
635
636 template<class U, class V>
637 void insert_pair(std::pair<U, V>&& value) {
638 insert(value.first, std::move(value.second));
639 }
640
641 private:
642 ht m_ht;
643 };
644
645 } // end namespace tsl
646
647 #endif