|
1 /* |
|
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. |
|
3 * |
|
4 * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved. |
|
5 * |
|
6 * Redistribution and use in source and binary forms, with or without |
|
7 * modification, are permitted provided that the following conditions are met: |
|
8 * |
|
9 * 1. Redistributions of source code must retain the above copyright |
|
10 * notice, this list of conditions and the following disclaimer. |
|
11 * |
|
12 * 2. Redistributions in binary form must reproduce the above copyright |
|
13 * notice, this list of conditions and the following disclaimer in the |
|
14 * documentation and/or other materials provided with the distribution. |
|
15 * |
|
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
|
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
|
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
|
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE |
|
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
|
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
|
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
|
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
|
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
|
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
|
26 * POSSIBILITY OF SUCH DAMAGE. |
|
27 */ |
|
28 |
|
29 #include "cx/hash_map.h" |
|
30 #include "cx/utils.h" |
|
31 #include "util_allocator.h" |
|
32 |
|
33 #include <gtest/gtest.h> |
|
34 #include <unordered_map> |
|
35 #include <unordered_set> |
|
36 |
|
37 struct map_operation { |
|
38 enum { |
|
39 put, rm |
|
40 } op; |
|
41 char const *key; |
|
42 char const *value; |
|
43 }; |
|
44 |
|
45 auto generate_map_operations() -> std::vector<map_operation> { |
|
46 return { |
|
47 {map_operation::put, "key 1", "test"}, |
|
48 {map_operation::put, "key 2", "blub"}, |
|
49 {map_operation::put, "key 3", "hallo"}, |
|
50 {map_operation::put, "key 2", "foobar"}, |
|
51 {map_operation::put, "key 4", "value 4"}, |
|
52 {map_operation::put, "key 5", "value 5"}, |
|
53 {map_operation::put, "key 6", "value 6"}, |
|
54 {map_operation::rm, "key 4", nullptr}, |
|
55 {map_operation::put, "key 7", "value 7"}, |
|
56 {map_operation::put, "key 8", "value 8"}, |
|
57 {map_operation::rm, "does not exist", nullptr}, |
|
58 {map_operation::put, "key 9", "value 9"}, |
|
59 {map_operation::put, "key 6", "other value"}, |
|
60 {map_operation::put, "key 7", "something else"}, |
|
61 {map_operation::rm, "key 8", nullptr}, |
|
62 {map_operation::rm, "key 2", nullptr}, |
|
63 {map_operation::put, "key 8", "new value"}, |
|
64 }; |
|
65 } |
|
66 |
|
67 static void verify_map_contents( |
|
68 CxMap *map, |
|
69 std::unordered_map<std::string, std::string> const &refmap |
|
70 ) { |
|
71 // verify key iterator |
|
72 { |
|
73 auto keyiter = cxMapIteratorKeys(map); |
|
74 std::unordered_set<std::string> keys; |
|
75 cx_foreach(CxHashKey*, elem, keyiter) { |
|
76 keys.insert(std::string(elem->data.cstr, elem->len)); |
|
77 } |
|
78 EXPECT_EQ(keyiter.index, map->size); |
|
79 ASSERT_EQ(keys.size(), map->size); |
|
80 for (auto &&k: keys) { |
|
81 EXPECT_NE(refmap.find(k), refmap.end()); |
|
82 } |
|
83 } |
|
84 |
|
85 // verify value iterator |
|
86 { |
|
87 auto valiter = cxMapIteratorValues(map); |
|
88 std::unordered_set<std::string> values; // we use that the values in our test data are unique strings |
|
89 cx_foreach(char const*, elem, valiter) { |
|
90 values.insert(std::string(elem)); |
|
91 } |
|
92 EXPECT_EQ(valiter.index, map->size); |
|
93 ASSERT_EQ(values.size(), map->size); |
|
94 for (auto &&v: values) { |
|
95 EXPECT_NE(std::find_if(refmap.begin(), refmap.end(), |
|
96 [v](auto const &e) { return e.second == v; }), refmap.end()); |
|
97 } |
|
98 } |
|
99 |
|
100 // verify pair iterator |
|
101 { |
|
102 auto pairiter = cxMapIterator(map); |
|
103 std::unordered_map<std::string, std::string> pairs; |
|
104 cx_foreach(CxMapEntry*, entry, pairiter) { |
|
105 pairs[std::string(entry->key->data.cstr, entry->key->len)] = std::string((char *) entry->value); |
|
106 } |
|
107 EXPECT_EQ(pairiter.index, map->size); |
|
108 ASSERT_EQ(pairs.size(), refmap.size()); |
|
109 for (auto &&p: pairs) { |
|
110 ASSERT_EQ(p.second, refmap.at(p.first)); |
|
111 } |
|
112 } |
|
113 } |
|
114 |
|
115 TEST(CxHashMap, Create) { |
|
116 CxTestingAllocator allocator; |
|
117 auto map = cxHashMapCreate(&allocator, 0); |
|
118 auto hmap = reinterpret_cast<struct cx_hash_map_s *>(map); |
|
119 EXPECT_GT(hmap->bucket_count, 0); |
|
120 cx_for_n(i, hmap->bucket_count) { |
|
121 EXPECT_EQ(hmap->buckets[i], nullptr); |
|
122 } |
|
123 EXPECT_EQ(map->size, 0); |
|
124 EXPECT_EQ(map->allocator, &allocator); |
|
125 |
|
126 cxMapDestroy(map); |
|
127 EXPECT_TRUE(allocator.verify()); |
|
128 } |
|
129 |
|
130 TEST(CxHashMap, BasicOperations) { |
|
131 // create the map |
|
132 CxTestingAllocator allocator; |
|
133 auto map = cxHashMapCreate(&allocator, 8); |
|
134 |
|
135 // create a reference map |
|
136 std::unordered_map<std::string, std::string> refmap; |
|
137 |
|
138 // generate operations |
|
139 auto ops = generate_map_operations(); |
|
140 |
|
141 // verify iterators for empty map |
|
142 verify_map_contents(map, refmap); |
|
143 |
|
144 // execute operations and verify results |
|
145 for (auto &&op: ops) { |
|
146 CxHashKey key = cx_hash_key_str(op.key); |
|
147 key.hash = 0; // force the hash map to compute the hash |
|
148 if (op.op == map_operation::put) { |
|
149 // execute a put operation and verify that the exact value can be read back |
|
150 refmap[std::string(op.key)] = std::string(op.value); |
|
151 int result = cxMapPut(map, key, (void *) op.value); |
|
152 EXPECT_EQ(result, 0); |
|
153 auto added = cxMapGet(map, key); |
|
154 EXPECT_EQ(memcmp(op.value, added, strlen(op.value)), 0); |
|
155 } else { |
|
156 // execute a remove and verify that the removed element was returned (or nullptr) |
|
157 auto found = refmap.find(op.key); |
|
158 auto removed = cxMapRemove(map, key); |
|
159 if (found == refmap.end()) { |
|
160 EXPECT_EQ(removed, nullptr); |
|
161 } else { |
|
162 EXPECT_EQ(std::string((char *) removed), found->second); |
|
163 refmap.erase(found); |
|
164 } |
|
165 } |
|
166 // compare the current map state with the reference map |
|
167 verify_map_contents(map, refmap); |
|
168 } |
|
169 |
|
170 // destroy the map and verify the memory (de)allocations |
|
171 cxMapDestroy(map); |
|
172 EXPECT_TRUE(allocator.verify()); |
|
173 } |
|
174 |
|
175 TEST(CxHashMap, RemoveViaIterator) { |
|
176 CxTestingAllocator allocator; |
|
177 auto map = cxHashMapCreate(&allocator, 4); |
|
178 |
|
179 cxMapPut(map, cx_hash_key_str("key 1"), (void *) "val 1"); |
|
180 cxMapPut(map, cx_hash_key_str("key 2"), (void *) "val 2"); |
|
181 cxMapPut(map, cx_hash_key_str("key 3"), (void *) "val 3"); |
|
182 cxMapPut(map, cx_hash_key_str("key 4"), (void *) "val 4"); |
|
183 cxMapPut(map, cx_hash_key_str("key 5"), (void *) "val 5"); |
|
184 cxMapPut(map, cx_hash_key_str("key 6"), (void *) "val 6"); |
|
185 |
|
186 auto iter = cxMapMutIterator(map); |
|
187 cx_foreach(CxMapEntry*, entry, iter) { |
|
188 if (entry->key->data.cstr[4] % 2 == 1) cxIteratorFlagRemoval(iter); |
|
189 } |
|
190 EXPECT_EQ(map->size, 3); |
|
191 EXPECT_EQ(iter.index, map->size); |
|
192 |
|
193 EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 1")), nullptr); |
|
194 EXPECT_NE(cxMapGet(map, cx_hash_key_str("key 2")), nullptr); |
|
195 EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 3")), nullptr); |
|
196 EXPECT_NE(cxMapGet(map, cx_hash_key_str("key 4")), nullptr); |
|
197 EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 5")), nullptr); |
|
198 EXPECT_NE(cxMapGet(map, cx_hash_key_str("key 6")), nullptr); |
|
199 |
|
200 cxMapDestroy(map); |
|
201 EXPECT_TRUE(allocator.verify()); |
|
202 } |
|
203 |
|
204 TEST(CxHashMap, RehashNotRequired) { |
|
205 CxTestingAllocator allocator; |
|
206 auto map = cxHashMapCreate(&allocator, 8); |
|
207 |
|
208 cxMapPut(map, cx_hash_key_str("key 1"), (void *) "val 1"); |
|
209 cxMapPut(map, cx_hash_key_str("key 2"), (void *) "val 2"); |
|
210 cxMapPut(map, cx_hash_key_str("key 3"), (void *) "val 3"); |
|
211 cxMapPut(map, cx_hash_key_str("key 4"), (void *) "val 4"); |
|
212 cxMapPut(map, cx_hash_key_str("key 5"), (void *) "val 5"); |
|
213 cxMapPut(map, cx_hash_key_str("key 6"), (void *) "val 6"); |
|
214 |
|
215 // 6/8 does not exceed 0.75, therefore the function should not rehash |
|
216 int result = cxMapRehash(map); |
|
217 EXPECT_EQ(result, 0); |
|
218 EXPECT_EQ(reinterpret_cast<struct cx_hash_map_s *>(map)->bucket_count, 8); |
|
219 |
|
220 cxMapDestroy(map); |
|
221 EXPECT_TRUE(allocator.verify()); |
|
222 } |
|
223 |
|
224 TEST(CxHashMap, Rehash) { |
|
225 CxTestingAllocator allocator; |
|
226 auto map = cxHashMapCreate(&allocator, 8); |
|
227 |
|
228 cxMapPut(map, cx_hash_key_str("key 1"), (void *) "val 1"); |
|
229 cxMapPut(map, cx_hash_key_str("key 2"), (void *) "val 2"); |
|
230 cxMapPut(map, cx_hash_key_str("key 3"), (void *) "val 3"); |
|
231 cxMapPut(map, cx_hash_key_str("key 4"), (void *) "val 4"); |
|
232 cxMapPut(map, cx_hash_key_str("key 5"), (void *) "val 5"); |
|
233 cxMapPut(map, cx_hash_key_str("key 6"), (void *) "val 6"); |
|
234 cxMapPut(map, cx_hash_key_str("key 7"), (void *) "val 7"); |
|
235 |
|
236 int result = cxMapRehash(map); |
|
237 EXPECT_EQ(result, 0); |
|
238 EXPECT_EQ(reinterpret_cast<struct cx_hash_map_s *>(map)->bucket_count, 17); |
|
239 EXPECT_EQ(map->size, 7); |
|
240 |
|
241 EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 1")), "val 1"), 0); |
|
242 EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 2")), "val 2"), 0); |
|
243 EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 3")), "val 3"), 0); |
|
244 EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 4")), "val 4"), 0); |
|
245 EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 5")), "val 5"), 0); |
|
246 EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 6")), "val 6"), 0); |
|
247 EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 7")), "val 7"), 0); |
|
248 |
|
249 cxMapDestroy(map); |
|
250 EXPECT_TRUE(allocator.verify()); |
|
251 } |
|
252 |
|
253 TEST(CxHashMap, Clear) { |
|
254 CxTestingAllocator allocator; |
|
255 auto map = cxHashMapCreate(&allocator, 0); |
|
256 |
|
257 cxMapPut(map, cx_hash_key_str("key 1"), (void *) "val 1"); |
|
258 cxMapPut(map, cx_hash_key_str("key 2"), (void *) "val 2"); |
|
259 cxMapPut(map, cx_hash_key_str("key 3"), (void *) "val 3"); |
|
260 |
|
261 EXPECT_EQ(map->size, 3); |
|
262 |
|
263 cxMapClear(map); |
|
264 |
|
265 EXPECT_EQ(map->size, 0); |
|
266 EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 1")), nullptr); |
|
267 EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 2")), nullptr); |
|
268 EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 3")), nullptr); |
|
269 |
|
270 cxMapDestroy(map); |
|
271 EXPECT_TRUE(allocator.verify()); |
|
272 } |