Debian Codegraph @

src/kj/map-test.c++

raw
1 // Copyright (c) 2018 Kenton Varda and contributors
2 // Licensed under the MIT License:
3 //
4 // Permission is hereby granted, free of charge, to any person obtaining a copy
5 // of this software and associated documentation files (the "Software"), to deal
6 // in the Software without restriction, including without limitation the rights
7 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8 // copies of the Software, and to permit persons to whom the Software is
9 // furnished to do so, subject to the following conditions:
10 //
11 // The above copyright notice and this permission notice shall be included in
12 // all copies or substantial portions of the Software.
13 //
14 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
20 // THE SOFTWARE.
21
22 #include "map.h"
23 #include <kj/test.h>
24
25 namespace kj {
26 namespace _ {
27 namespace {
28
29 KJ_TEST("HashMap") {
30 HashMap<String, int> map;
31
32 kj::String ownFoo = kj::str("foo");
33 const char* origFoo = ownFoo.begin();
34 map.insert(kj::mv(ownFoo), 123);
35 map.insert(kj::str("bar"), 456);
36
37 KJ_EXPECT(KJ_ASSERT_NONNULL(map.find("foo"_kj)) == 123);
38 KJ_EXPECT(KJ_ASSERT_NONNULL(map.find("bar"_kj)) == 456);
39 KJ_EXPECT(map.find("baz"_kj) == nullptr);
40
41 map.upsert(kj::str("foo"), 789, [](int& old, uint newValue) {
42 KJ_EXPECT(old == 123);
43 KJ_EXPECT(newValue == 789);
44 old = 4321;
45 });
46
47 KJ_EXPECT(KJ_ASSERT_NONNULL(map.find("foo"_kj)) == 4321);
48 KJ_EXPECT(KJ_ASSERT_NONNULL(map.findEntry("foo"_kj)).key.begin() == origFoo);
49
50 map.upsert(kj::str("foo"), 321);
51
52 KJ_EXPECT(KJ_ASSERT_NONNULL(map.find("foo"_kj)) == 321);
53 KJ_EXPECT(KJ_ASSERT_NONNULL(map.findEntry("foo"_kj)).key.begin() == origFoo);
54
55 KJ_EXPECT(
56 map.findOrCreate("foo"_kj,
57 []() -> HashMap<String, int>::Entry { KJ_FAIL_ASSERT("shouldn't have been called"); })
58 == 321);
59 KJ_EXPECT(map.findOrCreate("baz"_kj,
60 [](){ return HashMap<String, int>::Entry { kj::str("baz"), 654 }; }) == 654);
61 KJ_EXPECT(KJ_ASSERT_NONNULL(map.find("baz"_kj)) == 654);
62
63 KJ_EXPECT(map.erase("bar"_kj));
64 KJ_EXPECT(map.erase("baz"_kj));
65 KJ_EXPECT(!map.erase("qux"_kj));
66
67 KJ_EXPECT(KJ_ASSERT_NONNULL(map.find("foo"_kj)) == 321);
68 KJ_EXPECT(map.size() == 1);
69 KJ_EXPECT(map.begin()->key == "foo");
70 auto iter = map.begin();
71 ++iter;
72 KJ_EXPECT(iter == map.end());
73
74 map.erase(*map.begin());
75 KJ_EXPECT(map.size() == 0);
76 }
77
78 KJ_TEST("TreeMap") {
79 TreeMap<String, int> map;
80
81 kj::String ownFoo = kj::str("foo");
82 const char* origFoo = ownFoo.begin();
83 map.insert(kj::mv(ownFoo), 123);
84 map.insert(kj::str("bar"), 456);
85
86 KJ_EXPECT(KJ_ASSERT_NONNULL(map.find("foo"_kj)) == 123);
87 KJ_EXPECT(KJ_ASSERT_NONNULL(map.find("bar"_kj)) == 456);
88 KJ_EXPECT(map.find("baz"_kj) == nullptr);
89
90 map.upsert(kj::str("foo"), 789, [](int& old, uint newValue) {
91 KJ_EXPECT(old == 123);
92 KJ_EXPECT(newValue == 789);
93 old = 4321;
94 });
95
96 KJ_EXPECT(KJ_ASSERT_NONNULL(map.find("foo"_kj)) == 4321);
97 KJ_EXPECT(KJ_ASSERT_NONNULL(map.findEntry("foo"_kj)).key.begin() == origFoo);
98
99 map.upsert(kj::str("foo"), 321);
100
101 KJ_EXPECT(KJ_ASSERT_NONNULL(map.find("foo"_kj)) == 321);
102 KJ_EXPECT(KJ_ASSERT_NONNULL(map.findEntry("foo"_kj)).key.begin() == origFoo);
103
104 KJ_EXPECT(
105 map.findOrCreate("foo"_kj,
106 []() -> TreeMap<String, int>::Entry { KJ_FAIL_ASSERT("shouldn't have been called"); })
107 == 321);
108 KJ_EXPECT(map.findOrCreate("baz"_kj,
109 [](){ return TreeMap<String, int>::Entry { kj::str("baz"), 654 }; }) == 654);
110 KJ_EXPECT(KJ_ASSERT_NONNULL(map.find("baz"_kj)) == 654);
111
112 KJ_EXPECT(map.erase("bar"_kj));
113 KJ_EXPECT(map.erase("baz"_kj));
114 KJ_EXPECT(!map.erase("qux"_kj));
115
116 KJ_EXPECT(KJ_ASSERT_NONNULL(map.find("foo"_kj)) == 321);
117 KJ_EXPECT(map.size() == 1);
118 KJ_EXPECT(map.begin()->key == "foo");
119 auto iter = map.begin();
120 ++iter;
121 KJ_EXPECT(iter == map.end());
122
123 map.erase(*map.begin());
124 KJ_EXPECT(map.size() == 0);
125 }
126
127 KJ_TEST("TreeMap range") {
128 TreeMap<String, int> map;
129
130 map.insert(kj::str("foo"), 1);
131 map.insert(kj::str("bar"), 2);
132 map.insert(kj::str("baz"), 3);
133 map.insert(kj::str("qux"), 4);
134 map.insert(kj::str("corge"), 5);
135
136 {
137 auto ordered = KJ_MAP(e, map) -> kj::StringPtr { return e.key; };
138 KJ_ASSERT(ordered.size() == 5);
139 KJ_EXPECT(ordered[0] == "bar");
140 KJ_EXPECT(ordered[1] == "baz");
141 KJ_EXPECT(ordered[2] == "corge");
142 KJ_EXPECT(ordered[3] == "foo");
143 KJ_EXPECT(ordered[4] == "qux");
144 }
145
146 {
147 auto range = map.range("baz", "foo");
148 auto iter = range.begin();
149 KJ_EXPECT(iter->key == "baz");
150 ++iter;
151 KJ_EXPECT(iter->key == "corge");
152 ++iter;
153 KJ_EXPECT(iter == range.end());
154 }
155
156 map.eraseRange("baz", "foo");
157
158 {
159 auto ordered = KJ_MAP(e, map) -> kj::StringPtr { return e.key; };
160 KJ_ASSERT(ordered.size() == 3);
161 KJ_EXPECT(ordered[0] == "bar");
162 KJ_EXPECT(ordered[1] == "foo");
163 KJ_EXPECT(ordered[2] == "qux");
164 }
165 }
166
167 #if !KJ_NO_EXCEPTIONS
168 KJ_TEST("HashMap findOrCreate throws") {
169 HashMap<int, String> m;
170 try {
171 m.findOrCreate(1, []() -> HashMap<int, String>::Entry {
172 throw "foo";
173 });
174 KJ_FAIL_ASSERT("shouldn't get here");
175 } catch (const char*) {
176 // expected
177 }
178
179 KJ_EXPECT(m.find(1) == nullptr);
180 m.findOrCreate(1, []() {
181 return HashMap<int, String>::Entry { 1, kj::str("ok") };
182 });
183
184 KJ_EXPECT(KJ_ASSERT_NONNULL(m.find(1)) == "ok");
185 }
186 #endif
187
188 template <typename MapType>
189 void testEraseAll(MapType& m) {
190 m.insert(12, "foo");
191 m.insert(83, "bar");
192 m.insert(99, "baz");
193 m.insert(6, "qux");
194 m.insert(55, "corge");
195
196 auto count = m.eraseAll([](int i, StringPtr s) {
197 return i == 99 || s == "foo";
198 });
199
200 KJ_EXPECT(count == 2);
201 KJ_EXPECT(m.size() == 3);
202 KJ_EXPECT(m.find(12) == nullptr);
203 KJ_EXPECT(m.find(99) == nullptr);
204 KJ_EXPECT(KJ_ASSERT_NONNULL(m.find(83)) == "bar");
205 KJ_EXPECT(KJ_ASSERT_NONNULL(m.find(6)) == "qux");
206 KJ_EXPECT(KJ_ASSERT_NONNULL(m.find(55)) == "corge");
207 }
208
209 KJ_TEST("HashMap eraseAll") {
210 HashMap<int, StringPtr> m;
211 testEraseAll(m);
212 }
213
214 KJ_TEST("TreeMap eraseAll") {
215 TreeMap<int, StringPtr> m;
216 testEraseAll(m);
217 }
218
219 } // namespace
220 } // namespace _
221 } // namespace kj