Debian Codegraph @

third_party/hat-trie/README.md

raw
1 [![Build Status](https://travis-ci.org/Tessil/hat-trie.svg?branch=master)](https://travis-ci.org/Tessil/hat-trie) [![Build status](https://ci.appveyor.com/api/projects/status/ieafyj08ewb7dfa7/branch/master?svg=true)](https://ci.appveyor.com/project/Tessil/hat-trie/branch/master)
2 ## A C++ implementation of a fast and memory efficient HAT-trie
3
4 Trie implementation based on the "HAT-trie: A Cache-conscious Trie-based Data Structure for Strings." (Askitis Nikolas and Sinha Ranjan, 2007) paper. For now, only the pure HAT-trie has been implemented, the hybrid version may arrive later. Details regarding the HAT-trie data structure can be found [here](https://tessil.github.io/2017/06/22/hat-trie.html).
5
6 The library provides an efficient and compact way to store a set or a map of strings by compressing the common prefixes. It also allows to search for keys that match a prefix. Note though that the default parameters of the structure are geared toward optimizing exact searches, if you do a lot of prefix searches you may want to reduce the burst threshold through the `burst_threshold` method.
7
8 It's a well adapted structure to store a large number of strings.
9
10 <p align="center">
11 <img src="https://tessil.github.io/images/hat-trie.png" width="600px" />
12 </p>
13
14 For the array hash part, the [array-hash](https://github.com/Tessil/array-hash) project is used and included in the repository.
15
16 The library provides two classes: `tsl::htrie_map` and `tsl::htrie_set`.
17
18 ### Overview
19
20 - Header-only library, just add the [include](include/) directory to your include path and you are ready to go. If you use CMake, you can also use the `tsl::hat_trie` exported target from the [CMakeLists.txt](CMakeLists.txt).
21 - Low memory usage while keeping reasonable performances (see [benchmark](#benchmark)).
22 - Support prefix searches through `equal_prefix_range` (useful for autocompletion for example) and prefix erasures through `erase_prefix`.
23 - Support longest matching prefix searches through `longest_prefix`.
24 - Support for efficient serialization and deserialization (see [example](#serialization) and the `serialize/deserialize` methods in the [API](https://tessil.github.io/hat-trie/doc/html/classtsl_1_1htrie__map.html) for details).
25 - Keys are not ordered as they are partially stored in a hash map.
26 - All operations modifying the data structure (insert, emplace, erase, ...) invalidate the iterators.
27 - Support null characters in the key (you can thus store binary data in the trie).
28 - Support for any type of value as long at it's either copy-constructible or both nothrow move constructible and nothrow move assignable.
29 - The balance between speed and memory usage can be modified through the `max_load_factor` method. A lower max load factor will increase the speed, a higher one will reduce the memory usage. Its default value is set to 8.0.
30 - The default burst threshold, which is the maximum size of an array hash node before a burst occurs, is set to 16 384 which provides good performances for exact searches. If you mainly use prefix searches, you may want to reduce it to something like 1024 or lower for faster iteration on the results through the `burst_threshold` method.
31 - By default the maximum allowed size for a key is set to 65 535. This can be raised through the `KeySizeT` template parameter.
32
33 Thread-safety and exception guarantees are similar to the STL containers.
34
35 ### Hash function
36
37 The default hash function used by the structure depends on the presence of `std::string_view`. If it is available, `std::hash<std::string_view>` is used, otherwise a simple [FNV-1a](https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function#FNV-1a_hash) hash function is used to avoid any dependency.
38
39 If you can't use C++17 or later, we recommend to replace the hash function with something like [CityHash](https://github.com/google/cityhash), MurmurHash, [FarmHash](https://github.com/google/farmhash), ... for better performances. On the tests we did, CityHash64 offers a ~20% improvement on reads compared to FNV-1a.
40
41
42 ```c++
43 #include <city.h>
44
45 struct str_hash {
46 std::size_t operator()(const char* key, std::size_t key_size) const {
47 return CityHash64(key, key_size);
48 }
49 };
50
51 tsl::htrie_map<char, int, str_hash> map;
52 ```
53
54 The `std::hash<std::string>` can't be used efficiently as the structure doesn't store any `std::string` object. Any time a hash would be needed, a temporary `std::string` would have to be created.
55
56
57 ### Benchmark
58
59 #### Wikipedia dataset
60 The benchmark consists in inserting all the titles from the main namespace of the Wikipedia archive into the data structure, check the used memory space after the insert (including potential memory fragmentation) and search for all the titles again in the data structure. The peak memory usage during the insert process is also measured with [time(1)](https://linux.die.net/man/1/time).
61
62 * Dataset: [enwiki-20170320-all-titles-in-ns0.gz](https://dumps.wikimedia.org/enwiki/20170320/)
63 * Size: 262.7 MiB
64 * Number of keys: 13 099 148
65 * Average key length: 19.90
66 * Median key length: 17
67 * Max key length: 251
68
69 Each title is associated with an int (32 bits). All the hash based structures use [CityHash64](https://github.com/google/cityhash) as hash function. For the tests marked *with reserve*, the `reserve` function is called beforehand to avoid any rehash.
70
71 Note that `tsl::hopscotch_map`, `std::unordered_map`, `google::dense_hash_map` and `spp::sparse_hash_map` use `std::string` as key which imposes a minimum size of 32 bytes (on x64) even if the key is only one character long. Other structures may be able to store one-character keys with 1 byte + 8 bytes for a pointer (on x64).
72
73 The benchmark was compiled with GCC 6.3 and ran on Debian Stretch x64 with an Intel i5-5200u and 8Go of RAM. Best of 20 runs was taken.
74
75 The code of the benchmark can be found on [Gist](https://gist.github.com/Tessil/72e11891fc155f5b2eb53de22cbc4053).
76
77 ##### Unsorted
78
79 The *enwiki-20170320-all-titles-in-ns0.gz* dataset is alphabetically sorted. For this benchmark, we first shuffle the dataset through [shuf(1)](https://linux.die.net/man/1/shuf) to avoid a biased sorted dataset.
80
81 | Library | Data structure | Peak memory (MiB) | Memory (MiB) | Insert (ns/key) | Read (ns/key) |
82 |---------|----------------|------------------:|-------------:|----------------:|--------------:|
83 | [tsl::htrie_map](https://github.com/Tessil/hat-trie) | HAT-trie | **405.22** | **402.25** | 643.10 | 250.87 |
84 | [tsl::htrie_map](https://github.com/Tessil/hat-trie) <br/> max_load_factor=4 | HAT-trie | 471.85 | 468.50 | 638.66 | 212.90 |
85 | [tsl::htrie_map](https://github.com/Tessil/hat-trie) <br/> max_load_factor=2 | HAT-trie | 569.76 | 566.52 | 630.61 | 201.10 |
86 | [tsl::htrie_map](https://github.com/Tessil/hat-trie) <br/> max_load_factor=1 | HAT-trie | 713.44 | 709.81 | 645.76 | 190.87 |
87 | [cedar::da](http://www.tkl.iis.u-tokyo.ac.jp/~ynaga/cedar/) | Double-array trie | 1269.68 | 1254.41 | 1102.93 | 557.20 |
88 | [cedar::da](http://www.tkl.iis.u-tokyo.ac.jp/~ynaga/cedar/) ORDERED=false | Double-array trie | 1269.80 | 1254.41 | 1089.78 | 570.13 |
89 | [cedar::da](http://www.tkl.iis.u-tokyo.ac.jp/~ynaga/cedar/) | Double-array reduced trie | 1183.07 | 1167.79 | 1076.68 | 645.79 |
90 | [cedar::da](http://www.tkl.iis.u-tokyo.ac.jp/~ynaga/cedar/) ORDERED=false | Double-array reduced trie | 1183.14 | 1167.85 | 1065.43 | 641.98 |
91 | [cedar::da](http://www.tkl.iis.u-tokyo.ac.jp/~ynaga/cedar/) | Double-array prefix trie | 498.69 | 496.54 | 1096.90 | 628.01 |
92 | [cedar::da](http://www.tkl.iis.u-tokyo.ac.jp/~ynaga/cedar/) ORDERED=false | Double-array prefix trie | 498.65 | 496.60 | 1048.40 | 628.94 |
93 | [hat-trie](https://github.com/dcjones/hat-trie)<sup>1</sup> (C) | HAT-trie | 504.07 | 501.50 | 917.49 | 261.00 |
94 | [qp trie](https://github.com/fanf2/qp) (C) | QP trie | 941.23 | 938.17 | 1349.25 | 1281.46 |
95 | [crit-bit trie](https://github.com/fanf2/qp) (C) | Crit-bit trie | 1074.96 | 1071.98 | 2930.42 | 2869.74 |
96 | [JudySL](http://judy.sourceforge.net/) (C) | Judy array | 631.09 | 628.37 | 884.29 | 803.58 |
97 | [JudyHS](http://judy.sourceforge.net/) (C) | Judy array | 723.44 | 719.47 | 476.79 | 417.15 |
98 | [tsl::array_map](https://github.com/Tessil/array-hash) | Array hash table | 823.54 | 678.73 | 603.94 | 138.24 |
99 | [tsl::array_map](https://github.com/Tessil/array-hash) <br>with reserve | Array hash table | 564.26 | 555.91 | 249.52 | 128.28 |
100 | [tsl::hopscotch_map](https://github.com/Tessil/hopscotch-map) | Hash table | 1325.83 | 1077.99 | 368.26 | **119.49** |
101 | [tsl::hopscotch_map](https://github.com/Tessil/hopscotch-map) <br>with reserve | Hash table | 1080.51 | 1077.98 | **240.58** | 119.91 |
102 | [google::dense_hash_map](https://github.com/sparsehash/sparsehash) | Hash table | 2319.40 | 1677.11 | 466.60 | 138.87 |
103 | [google::dense_hash_map](https://github.com/sparsehash/sparsehash) <br>with reserve | Hash table | 1592.51 | 1589.99 | 259.56 | 120.40 |
104 | [spp::sparse_hash_map](https://github.com/greg7mdp/sparsepp) | Sparse hash table | 918.67 | 917.10 | 769.00 | 175.59 |
105 | [spp::sparse_hash_map](https://github.com/greg7mdp/sparsepp) <br>with reserve | Sparse hash table | 913.35 | 910.65 | 427.22 | 159.08 |
106 | [std::unordered_map](http://en.cppreference.com/w/cpp/container/unordered_map) | Hash table | 1249.05 | 1246.60 | 590.88 | 173.58 |
107 | [std::unordered_map](http://en.cppreference.com/w/cpp/container/unordered_map) <br>with reserve | Hash table | 1212.23 | 1209.71 | 350.33 | 178.70 |
108
109 1. As the hash function can't be passed in parameter, the code of the library itself is modified to use CityHash64.
110
111 ##### Sorted
112
113 The key are inserted and read in alphabetical order.
114
115 | Library | Data structure | Peak memory (MiB) | Memory (MiB) | Insert (ns/key) | Read (ns/key) |
116 |---------|----------------|------------------:|-------------:|----------------:|--------------:|
117 | [tsl::htrie_map](https://github.com/Tessil/hat-trie) | HAT-trie | **396.10** | **393.22** | 255.76 | 68.08 |
118 | [tsl::htrie_map](https://github.com/Tessil/hat-trie) <br/> max_load_factor=4 | HAT-trie | 465.02 | 461.80 | 248.88 | 59.23 |
119 | [tsl::htrie_map](https://github.com/Tessil/hat-trie) <br/> max_load_factor=2 | HAT-trie | 543.99 | 541.21 | 230.13 | 53.50 |
120 | [tsl::htrie_map](https://github.com/Tessil/hat-trie) <br/> max_load_factor=1 | HAT-trie | 692.29 | 689.70 | 243.84 | **49.22** |
121 | [cedar::da](http://www.tkl.iis.u-tokyo.ac.jp/~ynaga/cedar/) | Double-array trie | 1269.58 | 1254.41 | 278.51 | 54.72 |
122 | [cedar::da](http://www.tkl.iis.u-tokyo.ac.jp/~ynaga/cedar/) ORDERED=false | Double-array trie | 1269.66 | 1254.41 | 264.43 | 56.02 |
123 | [cedar::da](http://www.tkl.iis.u-tokyo.ac.jp/~ynaga/cedar/) | Double-array reduced trie | 1183.01 | 1167.78 | 254.60 | 69.18 |
124 | [cedar::da](http://www.tkl.iis.u-tokyo.ac.jp/~ynaga/cedar/) ORDERED=false | Double-array reduced trie | 1183.03 | 1167.78 | 241.45 | 69.67 |
125 | [cedar::da](http://www.tkl.iis.u-tokyo.ac.jp/~ynaga/cedar/) | Double-array prefix trie | 621.59 | 619.38 | 246.88 | 57.83 |
126 | [cedar::da](http://www.tkl.iis.u-tokyo.ac.jp/~ynaga/cedar/) ORDERED=false | Double-array prefix trie | 621.59 | 619.38 | **187.98** | 58.56 |
127 | [hat-trie](https://github.com/dcjones/hat-trie)<sup>2</sup> (C) | HAT-trie | 521.25 | 518.52 | 503.01 | 86.40 |
128 | [qp trie](https://github.com/fanf2/qp) (C) | QP trie | 940.65 | 937.66 | 392.86 | 190.19 |
129 | [crit-bit trie](https://github.com/fanf2/qp) (C) | Crit-bit trie | 1074.87 | 1071.98 | 430.04 | 347.60 |
130 | [JudySL](http://judy.sourceforge.net/) (C) | Judy array | 616.95 | 614.27 | 279.07 | 114.47 |
131 | [JudyHS](http://judy.sourceforge.net/) (C) | Judy array | 722.29 | 719.47 | 439.66 | 372.25 |
132 | [tsl::array_map](https://github.com/Tessil/array-hash) | Array hash table | 826.98 | 682.99 | 612.31 | 139.16 |
133 | [tsl::array_map](https://github.com/Tessil/array-hash) <br>with reserve | Array hash table | 565.37 | 555.35 | 246.55 | 126.32 |
134 | [tsl::hopscotch_map](https://github.com/Tessil/hopscotch-map) | Hash table | 1331.87 | 1078.02 | 375.19 | 118.08 |
135 | [tsl::hopscotch_map](https://github.com/Tessil/hopscotch-map) <br>with reserve | Hash table | 1080.51 | 1077.97 | 238.93 | 117.20 |
136 | [google::dense_hash_map](https://github.com/sparsehash/sparsehash) | Hash table | 2325.27 | 1683.07 | 483.95 | 137.09 |
137 | [google::dense_hash_map](https://github.com/sparsehash/sparsehash) <br>with reserve | Hash table | 1592.54 | 1589.99 | 257.22 | 113.71 |
138 | [spp::sparse_hash_map](https://github.com/greg7mdp/sparsepp) | Sparse hash table | 920.96 | 918.70 | 772.03 | 176.64 |
139 | [spp::sparse_hash_map](https://github.com/greg7mdp/sparsepp) <br>with reserve | Sparse hash table | 914.84 | 912.47 | 422.85 | 158.73 |
140 | [std::unordered_map](http://en.cppreference.com/w/cpp/container/unordered_map) | Hash table | 1249.09 | 1246.65 | 594.85 | 173.54 |
141 | [std::unordered_map](http://en.cppreference.com/w/cpp/container/unordered_map) <br>with reserve | Hash table | 1212.21 | 1209.71 | 347.40 | 176.49 |
142
143 2. As the hash function can't be passed in parameter, the code of the library itself is modified to use CityHash64.
144
145
146 #### Dr. Askitis dataset
147
148 The benchmark consists in inserting all the words from the "Distinct Strings" dataset of Dr. Askitis into the data structure, check the used memory space and search for all the words from the "Skew String Set 1" dataset (where a string can be present multiple times) in the data structure. Note that the strings in this dataset have a quite short average and median key length (which may not be a realistic use case compared to the Wikipedia dataset used above). It's similar to the one on the [cedar](http://www.tkl.iis.u-tokyo.ac.jp/~ynaga/cedar/) homepage.
149
150 * Dataset: [distinct_1](http://web.archive.org/web/20120206015921/http://www.naskitis.com/) (write) / [skew1_1](http://web.archive.org/web/20120206015921/http://www.naskitis.com/) (read)
151 * Size: 290.45 MiB / 1 029.46 MiB
152 * Number of keys: 28 772 169 / 177 999 203
153 * Average key length: 9.59 / 5.06
154 * Median key length: 8 / 4
155 * Max key length: 126 / 62
156
157 The benchmark protocol is the same as for the [Wikipedia dataset](https://github.com/Tessil/hat-trie#wikipedia-dataset).
158
159
160 | Library | Data structure | Peak memory (MiB) | Memory (MiB) | Insert (ns/key) | Read (ns/key) |
161 |---------|----------------|------------------:|-------------:|----------------:|--------------:|
162 | [tsl::htrie_map](https://github.com/Tessil/hat-trie) | HAT-trie | **604.76** | **601.79** | 485.45 | 77.80 |
163 | [tsl::htrie_map](https://github.com/Tessil/hat-trie) <br/> max_load_factor=4 | HAT-trie | 768.10 | 764.98 | 491.78 | 75.48 |
164 | [tsl::htrie_map](https://github.com/Tessil/hat-trie) <br/> max_load_factor=2 | HAT-trie | 1002.42 | 999.34 | 496.78 | 72.53 |
165 | [tsl::htrie_map](https://github.com/Tessil/hat-trie) <br/> max_load_factor=1 | HAT-trie | 1344.98 | 1341.97 | 520.66 | 72.45 |
166 | [cedar::da](http://www.tkl.iis.u-tokyo.ac.jp/~ynaga/cedar/) | Double-array trie | 1105.45 | 1100.05 | 682.25 | 71.98 |
167 | [cedar::da](http://www.tkl.iis.u-tokyo.ac.jp/~ynaga/cedar/) ORDERED=false | Double-array trie | 1105.47 | 1100.05 | 668.75 | 71.95 |
168 | [cedar::da](http://www.tkl.iis.u-tokyo.ac.jp/~ynaga/cedar/) | Double-array reduced trie | 941.16 | 926.04 | 684.38 | 79.11 |
169 | [cedar::da](http://www.tkl.iis.u-tokyo.ac.jp/~ynaga/cedar/) ORDERED=false | Double-array reduced trie | 941.16 | 925.98 | 672.14 | 79.02 |
170 | [cedar::da](http://www.tkl.iis.u-tokyo.ac.jp/~ynaga/cedar/) | Double-array prefix trie | 714.58 | 712.59 | 831.71 | 75.83 |
171 | [cedar::da](http://www.tkl.iis.u-tokyo.ac.jp/~ynaga/cedar/) ORDERED=false | Double-array prefix trie | 714.66 | 712.31 | 786.93 | 75.89 |
172 | [hat-trie](https://github.com/dcjones/hat-trie)<sup>3</sup> (C) | HAT-trie | 786.93 | 784.32 | 743.34 | 93.58 |
173 | [qp trie](https://github.com/fanf2/qp) (C) | QP trie | 1800.02 | 1797.21 | 987.95 | 428.51 |
174 | [crit-bit trie](https://github.com/fanf2/qp) (C) | Crit-bit trie | 2210.52 | 2207.64 | 1986.19 | 1109.88 |
175 | [JudySL](http://judy.sourceforge.net/) (C) | Judy array | 1025.59 | 1023.11 | 535.02 | 202.36 |
176 | [JudyHS](http://judy.sourceforge.net/) (C) | Judy array | 1002.50 | 999.97 | 456.09 | 148.36 |
177 | [tsl::array_map](https://github.com/Tessil/array-hash) | Array hash table | 1308.08 | 1031.67 | 545.82 | 46.41 |
178 | [tsl::array_map](https://github.com/Tessil/array-hash) <br>with reserve | Array hash table | 979.44 | 921.363 | 244.19 | 45.74 |
179 | [tsl::hopscotch_map](https://github.com/Tessil/hopscotch-map) | Hash table | 2336.39 | 1611.54 | 288.70 | 47.05 |
180 | [tsl::hopscotch_map](https://github.com/Tessil/hopscotch-map) <br>with reserve | Hash table | 1614.22 | 1611.64 | **220.67** | 46.39 |
181 | [google::dense_hash_map](https://github.com/sparsehash/sparsehash) | Hash table | 3913.64 | 2636.31 | 317.66 | 43.62 |
182 | [google::dense_hash_map](https://github.com/sparsehash/sparsehash) <br>with reserve | Hash table | 2638.19 | 2635.68 | 227.58 | **43.09** |
183 | [spp::sparse_hash_map](https://github.com/greg7mdp/sparsepp) | Sparse hash table | 1419.69 | 1417.61 | 586.26 | 56.00 |
184 | [spp::sparse_hash_map](https://github.com/greg7mdp/sparsepp) <br>with reserve | Sparse hash table | 1424.21 | 1421.69 | 392.76 | 55.73 |
185 | [std::unordered_map](http://en.cppreference.com/w/cpp/container/unordered_map) | Hash table | 2112.66 | 2110.19 | 554.02 | 105.05 |
186 | [std::unordered_map](http://en.cppreference.com/w/cpp/container/unordered_map) <br>with reserve | Hash table | 2053.95 | 2051.67 | 309.06 | 109.89 |
187
188 3. As the hash function can't be passed in parameter, the code of the library itself is modified to use CityHash64.
189
190 ### Installation
191 To use the library, just add the [include](include/) directory to your include path. It is a **header-only** library.
192
193 If you use CMake, you can also use the `tsl::hat_trie` exported target from the [CMakeLists.txt](CMakeLists.txt) with `target_link_libraries`.
194 ```cmake
195 # Example where the hat-trie project is stored in a third-party directory
196 add_subdirectory(third-party/hat-trie)
197 target_link_libraries(your_target PRIVATE tsl::hat_trie)
198 ```
199
200 The code should work with any C++11 standard-compliant compiler and has been tested with GCC 4.8.4, Clang 3.5.0 and Visual Studio 2015.
201
202 To run the tests you will need the Boost Test library and CMake.
203
204 ```bash
205 git clone https://github.com/Tessil/hat-trie.git
206 cd hat-trie/tests
207 mkdir build
208 cd build
209 cmake ..
210 cmake --build .
211 ./tsl_hat_trie_tests
212 ```
213
214 ### Usage
215
216 The API can be found [here](https://tessil.github.io/hat-trie/doc_without_string_view/html). If `std::string_view` is available, the API changes slightly and can be found [here](https://tessil.github.io/hat-trie/doc/html/).
217
218 ### Example
219
220 ```c++
221 #include <iostream>
222 #include <string>
223 #include <tsl/htrie_map.h>
224 #include <tsl/htrie_set.h>
225
226
227 int main() {
228 /*
229 * Map of strings to int having char as character type.
230 * There is no support for wchar_t, char16_t or char32_t yet,
231 * but UTF-8 strings will work fine.
232 */
233 tsl::htrie_map<char, int> map = {{"one", 1}, {"two", 2}};
234 map["three"] = 3;
235 map["four"] = 4;
236
237 map.insert("five", 5);
238 map.insert_ks("six_with_extra_chars_we_ignore", 3, 6);
239
240 map.erase("two");
241
242 /*
243 * Due to the compression on the common prefixes, the letters of the string
244 * are not always stored contiguously. When we retrieve the key, we have to
245 * construct it.
246 *
247 * To avoid a heap-allocation at each iteration (when SSO doesn't occur),
248 * we reuse the key_buffer to construct the key.
249 */
250 std::string key_buffer;
251 for(auto it = map.begin(); it != map.end(); ++it) {
252 it.key(key_buffer);
253 std::cout << "{" << key_buffer << ", " << it.value() << "}" << std::endl;
254 }
255
256 /*
257 * If you don't care about the allocation.
258 */
259 for(auto it = map.begin(); it != map.end(); ++it) {
260 std::cout << "{" << it.key() << ", " << *it << "}" << std::endl;
261 }
262
263
264
265
266 tsl::htrie_map<char, int> map2 = {{"apple", 1}, {"mango", 2}, {"apricot", 3},
267 {"mandarin", 4}, {"melon", 5}, {"macadamia", 6}};
268
269 // Prefix search
270 auto prefix_range = map2.equal_prefix_range("ma");
271
272 // {mandarin, 4} {mango, 2} {macadamia, 6}
273 for(auto it = prefix_range.first; it != prefix_range.second; ++it) {
274 std::cout << "{" << it.key() << ", " << *it << "}" << std::endl;
275 }
276
277 // Find longest match prefix.
278 auto longest_prefix = map2.longest_prefix("apple juice");
279 if(longest_prefix != map2.end()) {
280 // {apple, 1}
281 std::cout << "{" << longest_prefix.key() << ", "
282 << *longest_prefix << "}" << std::endl;
283 }
284
285 // Prefix erase
286 map2.erase_prefix("ma");
287
288 // {apricot, 3} {melon, 5} {apple, 1}
289 for(auto it = map2.begin(); it != map2.end(); ++it) {
290 std::cout << "{" << it.key() << ", " << *it << "}" << std::endl;
291 }
292
293
294
295
296 tsl::htrie_set<char> set = {"one", "two", "three"};
297 set.insert({"four", "five"});
298
299 // {one} {two} {five} {four} {three}
300 for(auto it = set.begin(); it != set.end(); ++it) {
301 it.key(key_buffer);
302 std::cout << "{" << key_buffer << "}" << std::endl;
303 }
304 }
305 ```
306
307 #### Serialization
308
309 The library provides an efficient way to serialize and deserialize a map or a set so that it can be saved to a file or send through the network.
310 To do so, it requires the user to provide a function object for both serialization and deserialization.
311
312 ```c++
313 struct serializer {
314 // Must support the following types for U: std::uint64_t, float and T if a map is used.
315 template<typename U>
316 void operator()(const U& value);
317 void operator()(const CharT* value, std::size_t value_size);
318 };
319 ```
320
321 ```c++
322 struct deserializer {
323 // Must support the following types for U: std::uint64_t, float and T if a map is used.
324 template<typename U>
325 U operator()();
326 void operator()(CharT* value_out, std::size_t value_size);
327 };
328 ```
329
330 Note that the implementation leaves binary compatibility (endianness, float binary representation, size of int, ...) of the types it serializes/deserializes in the hands of the provided function objects if compatibility is required.
331
332 More details regarding the `serialize` and `deserialize` methods can be found in the [API](https://tessil.github.io/hat-trie/doc/html/classtsl_1_1htrie__map.html).
333
334 ```c++
335 #include <cassert>
336 #include <cstdint>
337 #include <fstream>
338 #include <type_traits>
339 #include <tsl/htrie_map.h>
340
341
342 class serializer {
343 public:
344 serializer(const char* file_name) {
345 m_ostream.exceptions(m_ostream.badbit | m_ostream.failbit);
346 m_ostream.open(file_name);
347 }
348
349 template<class T,
350 typename std::enable_if<std::is_arithmetic<T>::value>::type* = nullptr>
351 void operator()(const T& value) {
352 m_ostream.write(reinterpret_cast<const char*>(&value), sizeof(T));
353 }
354
355 void operator()(const char* value, std::size_t value_size) {
356 m_ostream.write(value, value_size);
357 }
358
359 private:
360 std::ofstream m_ostream;
361 };
362
363 class deserializer {
364 public:
365 deserializer(const char* file_name) {
366 m_istream.exceptions(m_istream.badbit | m_istream.failbit | m_istream.eofbit);
367 m_istream.open(file_name);
368 }
369
370 template<class T,
371 typename std::enable_if<std::is_arithmetic<T>::value>::type* = nullptr>
372 T operator()() {
373 T value;
374 m_istream.read(reinterpret_cast<char*>(&value), sizeof(T));
375
376 return value;
377 }
378
379 void operator()(char* value_out, std::size_t value_size) {
380 m_istream.read(value_out, value_size);
381 }
382
383 private:
384 std::ifstream m_istream;
385 };
386
387
388 int main() {
389 const tsl::htrie_map<char, std::int64_t> map = {{"one", 1}, {"two", 2},
390 {"three", 3}, {"four", 4}};
391
392
393 const char* file_name = "htrie_map.data";
394 {
395 serializer serial(file_name);
396 map.serialize(serial);
397 }
398
399 {
400 deserializer dserial(file_name);
401 auto map_deserialized = tsl::htrie_map<char, std::int64_t>::deserialize(dserial);
402
403 assert(map == map_deserialized);
404 }
405
406 {
407 deserializer dserial(file_name);
408
409 /**
410 * If the serialized and deserialized map are hash compatibles (see conditions in API),
411 * setting the argument to true speed-up the deserialization process as we don't have
412 * to recalculate the hash of each key. We also know how much space each bucket needs.
413 */
414 const bool hash_compatible = true;
415 auto map_deserialized =
416 tsl::htrie_map<char, std::int64_t>::deserialize(dserial, hash_compatible);
417
418 assert(map == map_deserialized);
419 }
420 }
421 ```
422
423 ##### Serialization with Boost Serialization and compression with zlib
424
425 It's possible to use a serialization library to avoid some of the boilerplate if the types to serialize are more complex.
426
427 The following example uses Boost Serialization with the Boost zlib compression stream to reduce the size of the resulting serialized file.
428
429
430 ```c++
431 #include <boost/archive/binary_iarchive.hpp>
432 #include <boost/archive/binary_oarchive.hpp>
433 #include <boost/iostreams/filter/zlib.hpp>
434 #include <boost/iostreams/filtering_stream.hpp>
435 #include <boost/serialization/split_free.hpp>
436 #include <boost/serialization/utility.hpp>
437 #include <cassert>
438 #include <cstdint>
439 #include <fstream>
440 #include <tsl/htrie_map.h>
441
442
443 template<typename Archive>
444 struct serializer {
445 Archive& ar;
446
447 template<typename T>
448 void operator()(const T& val) { ar & val; }
449
450 template<typename CharT>
451 void operator()(const CharT* val, std::size_t val_size) {
452 ar.save_binary(reinterpret_cast<const void*>(val), val_size*sizeof(CharT));
453 }
454 };
455
456 template<typename Archive>
457 struct deserializer {
458 Archive& ar;
459
460 template<typename T>
461 T operator()() { T val; ar & val; return val; }
462
463 template<typename CharT>
464 void operator()(CharT* val_out, std::size_t val_size) {
465 ar.load_binary(reinterpret_cast<void*>(val_out), val_size*sizeof(CharT));
466 }
467 };
468
469 namespace boost { namespace serialization {
470 template<class Archive, class CharT, class T>
471 void serialize(Archive & ar, tsl::htrie_map<CharT, T>& map, const unsigned int version) {
472 split_free(ar, map, version);
473 }
474
475 template<class Archive, class CharT, class T>
476 void save(Archive & ar, const tsl::htrie_map<CharT, T>& map, const unsigned int version) {
477 serializer<Archive> serial{ar};
478 map.serialize(serial);
479 }
480
481
482 template<class Archive, class CharT, class T>
483 void load(Archive & ar, tsl::htrie_map<CharT, T>& map, const unsigned int version) {
484 deserializer<Archive> deserial{ar};
485 map = tsl::htrie_map<CharT, T>::deserialize(deserial);
486 }
487 }}
488
489
490 int main() {
491 const tsl::htrie_map<char, std::int64_t> map = {{"one", 1}, {"two", 2},
492 {"three", 3}, {"four", 4}};
493
494
495 const char* file_name = "htrie_map.data";
496 {
497 std::ofstream ofs;
498 ofs.exceptions(ofs.badbit | ofs.failbit);
499 ofs.open(file_name, std::ios::binary);
500
501 boost::iostreams::filtering_ostream fo;
502 fo.push(boost::iostreams::zlib_compressor());
503 fo.push(ofs);
504
505 boost::archive::binary_oarchive oa(fo);
506
507 oa << map;
508 }
509
510 {
511 std::ifstream ifs;
512 ifs.exceptions(ifs.badbit | ifs.failbit | ifs.eofbit);
513 ifs.open(file_name, std::ios::binary);
514
515 boost::iostreams::filtering_istream fi;
516 fi.push(boost::iostreams::zlib_decompressor());
517 fi.push(ifs);
518
519 boost::archive::binary_iarchive ia(fi);
520
521 tsl::htrie_map<char, std::int64_t> map_deserialized;
522 ia >> map_deserialized;
523
524 assert(map == map_deserialized);
525 }
526 }
527 ```
528
529 ### License
530
531 The code is licensed under the MIT license, see the [LICENSE file](LICENSE) for details.