test/test_map.cpp@7df0bcaecffa
test/test_map.cpp
Tue, 04 Oct 2022 19:25:07 +0200
- author
- Mike Becker <universe@uap-core.de>
- date
- Tue, 04 Oct 2022 19:25:07 +0200
- changeset 591
- 7df0bcaecffa
- parent 563
- 69a83fad8a35
- child 594
- d90cfa6721f9
- permissions
- -rw-r--r--
fix over-optimization of strstr
1. it's actually less performant to frequently read bytes
from an array instead of using the native word length
2. the SBO buffer should be local and not static to allow
multi-threading usage
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 */
29 #include "cx/hash_map.h"
30 #include "cx/utils.h"
31 #include "util_allocator.h"
33 #include <gtest/gtest.h>
34 #include <unordered_map>
35 #include <unordered_set>
37 struct map_operation {
38 enum {
39 put, rm
40 } op;
41 char const *key;
42 char const *value;
43 };
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 }
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 // we use that our test keys contain NULL-terminated strings
77 keys.insert(std::string(elem->data.cstr));
78 }
79 EXPECT_EQ(keyiter.index, map->size);
80 ASSERT_EQ(keys.size(), map->size);
81 for (auto &&k: keys) {
82 EXPECT_NE(refmap.find(k), refmap.end());
83 }
84 }
86 // verify value iterator
87 {
88 auto valiter = cxMapIteratorValues(map);
89 std::unordered_set<std::string> values; // we use that the values in our test data are unique strings
90 cx_foreach(char const*, elem, valiter) {
91 values.insert(std::string(elem));
92 }
93 EXPECT_EQ(valiter.index, map->size);
94 ASSERT_EQ(values.size(), map->size);
95 for (auto &&v: values) {
96 EXPECT_NE(std::find_if(refmap.begin(), refmap.end(),
97 [v](auto const &e) { return e.second == v; }), refmap.end());
98 }
99 }
101 // verify pair iterator
102 {
103 auto pairiter = cxMapIterator(map);
104 std::unordered_map<std::string, std::string> pairs;
105 cx_foreach(CxMapEntry*, entry, pairiter) {
106 pairs[std::string(entry->key->data.cstr)] = std::string((char *) entry->value);
107 }
108 EXPECT_EQ(pairiter.index, map->size);
109 ASSERT_EQ(pairs.size(), refmap.size());
110 for (auto &&p: pairs) {
111 ASSERT_EQ(p.second, refmap.at(p.first));
112 }
113 }
114 }
116 TEST(CxHashMap, Create) {
117 CxTestingAllocator allocator;
118 auto map = cxHashMapCreate(&allocator, 0);
119 auto hmap = reinterpret_cast<struct cx_hash_map_s *>(map);
120 EXPECT_GT(hmap->bucket_count, 0);
121 cx_for_n(i, hmap->bucket_count) {
122 EXPECT_EQ(hmap->buckets[i], nullptr);
123 }
124 EXPECT_EQ(map->size, 0);
125 EXPECT_EQ(map->allocator, &allocator);
127 cxMapDestroy(map);
128 EXPECT_TRUE(allocator.verify());
129 }
131 TEST(CxHashMap, BasicOperations) {
132 // create the map
133 CxTestingAllocator allocator;
134 auto map = cxHashMapCreate(&allocator, 8);
136 // create a reference map
137 std::unordered_map<std::string, std::string> refmap;
139 // generate operations
140 auto ops = generate_map_operations();
142 // verify iterators for empty map
143 verify_map_contents(map, refmap);
145 // execute operations and verify results
146 for (auto &&op: ops) {
147 CxHashKey key = cx_hash_key_str(op.key);
148 key.hash = 0; // force the hash map to compute the hash
149 if (op.op == map_operation::put) {
150 // execute a put operation and verify that the exact value can be read back
151 refmap[std::string(op.key)] = std::string(op.value);
152 int result = cxMapPut(map, key, (void *) op.value);
153 EXPECT_EQ(result, 0);
154 auto added = cxMapGet(map, key);
155 EXPECT_EQ(memcmp(op.value, added, strlen(op.value)), 0);
156 } else {
157 // execute a remove and verify that the removed element was returned (or nullptr)
158 auto found = refmap.find(op.key);
159 auto removed = cxMapRemove(map, key);
160 if (found == refmap.end()) {
161 EXPECT_EQ(removed, nullptr);
162 } else {
163 EXPECT_EQ(std::string((char *) removed), found->second);
164 refmap.erase(found);
165 }
166 }
167 // compare the current map state with the reference map
168 verify_map_contents(map, refmap);
169 }
171 // destroy the map and verify the memory (de)allocations
172 cxMapDestroy(map);
173 EXPECT_TRUE(allocator.verify());
174 }
176 TEST(CxHashMap, RemoveViaIterator) {
177 CxTestingAllocator allocator;
178 auto map = cxHashMapCreate(&allocator, 4);
180 cxMapPut(map, cx_hash_key_str("key 1"), (void *) "val 1");
181 cxMapPut(map, cx_hash_key_str("key 2"), (void *) "val 2");
182 cxMapPut(map, cx_hash_key_str("key 3"), (void *) "val 3");
183 cxMapPut(map, cx_hash_key_str("key 4"), (void *) "val 4");
184 cxMapPut(map, cx_hash_key_str("key 5"), (void *) "val 5");
185 cxMapPut(map, cx_hash_key_str("key 6"), (void *) "val 6");
187 auto iter = cxMapIterator(map);
188 cx_foreach(CxMapEntry*, entry, iter) {
189 if (entry->key->data.cstr[4] % 2 == 1) iter.remove = true;
190 }
191 EXPECT_EQ(map->size, 3);
192 EXPECT_EQ(iter.index, map->size);
194 EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 1")), nullptr);
195 EXPECT_NE(cxMapGet(map, cx_hash_key_str("key 2")), nullptr);
196 EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 3")), nullptr);
197 EXPECT_NE(cxMapGet(map, cx_hash_key_str("key 4")), nullptr);
198 EXPECT_EQ(cxMapGet(map, cx_hash_key_str("key 5")), nullptr);
199 EXPECT_NE(cxMapGet(map, cx_hash_key_str("key 6")), nullptr);
201 cxMapDestroy(map);
202 EXPECT_TRUE(allocator.verify());
203 }
205 TEST(CxHashMap, RehashNotRequired) {
206 CxTestingAllocator allocator;
207 auto map = cxHashMapCreate(&allocator, 8);
209 cxMapPut(map, cx_hash_key_str("key 1"), (void *) "val 1");
210 cxMapPut(map, cx_hash_key_str("key 2"), (void *) "val 2");
211 cxMapPut(map, cx_hash_key_str("key 3"), (void *) "val 3");
212 cxMapPut(map, cx_hash_key_str("key 4"), (void *) "val 4");
213 cxMapPut(map, cx_hash_key_str("key 5"), (void *) "val 5");
214 cxMapPut(map, cx_hash_key_str("key 6"), (void *) "val 6");
216 // 6/8 does not exceed 0.75, therefore the function should not rehash
217 int result = cxMapRehash(map);
218 EXPECT_EQ(result, 0);
219 EXPECT_EQ(reinterpret_cast<struct cx_hash_map_s *>(map)->bucket_count, 8);
221 cxMapDestroy(map);
222 EXPECT_TRUE(allocator.verify());
223 }
225 TEST(CxHashMap, Rehash) {
226 CxTestingAllocator allocator;
227 auto map = cxHashMapCreate(&allocator, 8);
229 cxMapPut(map, cx_hash_key_str("key 1"), (void *) "val 1");
230 cxMapPut(map, cx_hash_key_str("key 2"), (void *) "val 2");
231 cxMapPut(map, cx_hash_key_str("key 3"), (void *) "val 3");
232 cxMapPut(map, cx_hash_key_str("key 4"), (void *) "val 4");
233 cxMapPut(map, cx_hash_key_str("key 5"), (void *) "val 5");
234 cxMapPut(map, cx_hash_key_str("key 6"), (void *) "val 6");
235 cxMapPut(map, cx_hash_key_str("key 7"), (void *) "val 7");
237 int result = cxMapRehash(map);
238 EXPECT_EQ(result, 0);
239 EXPECT_EQ(reinterpret_cast<struct cx_hash_map_s *>(map)->bucket_count, 17);
240 EXPECT_EQ(map->size, 7);
242 EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 1")), "val 1"), 0);
243 EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 2")), "val 2"), 0);
244 EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 3")), "val 3"), 0);
245 EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 4")), "val 4"), 0);
246 EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 5")), "val 5"), 0);
247 EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 6")), "val 6"), 0);
248 EXPECT_EQ(strcmp((char *) cxMapGet(map, cx_hash_key_str("key 7")), "val 7"), 0);
250 cxMapDestroy(map);
251 EXPECT_TRUE(allocator.verify());
252 }
