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