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

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

mercurial