map-test.c++ (5859B)
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 map.insert(kj::str("foo"), 123); 33 map.insert(kj::str("bar"), 456); 34 35 KJ_EXPECT(KJ_ASSERT_NONNULL(map.find("foo"_kj)) == 123); 36 KJ_EXPECT(KJ_ASSERT_NONNULL(map.find("bar"_kj)) == 456); 37 KJ_EXPECT(map.find("baz"_kj) == nullptr); 38 39 map.upsert(kj::str("foo"), 789, [](int& old, uint newValue) { 40 KJ_EXPECT(old == 123); 41 KJ_EXPECT(newValue == 789); 42 old = 321; 43 }); 44 45 KJ_EXPECT(KJ_ASSERT_NONNULL(map.find("foo"_kj)) == 321); 46 47 KJ_EXPECT( 48 map.findOrCreate("foo"_kj, 49 []() -> HashMap<String, int>::Entry { KJ_FAIL_ASSERT("shouldn't have been called"); }) 50 == 321); 51 KJ_EXPECT(map.findOrCreate("baz"_kj, 52 [](){ return HashMap<String, int>::Entry { kj::str("baz"), 654 }; }) == 654); 53 KJ_EXPECT(KJ_ASSERT_NONNULL(map.find("baz"_kj)) == 654); 54 55 KJ_EXPECT(map.erase("bar"_kj)); 56 KJ_EXPECT(map.erase("baz"_kj)); 57 KJ_EXPECT(!map.erase("qux"_kj)); 58 59 KJ_EXPECT(KJ_ASSERT_NONNULL(map.find("foo"_kj)) == 321); 60 KJ_EXPECT(map.size() == 1); 61 KJ_EXPECT(map.begin()->key == "foo"); 62 auto iter = map.begin(); 63 ++iter; 64 KJ_EXPECT(iter == map.end()); 65 66 map.erase(*map.begin()); 67 KJ_EXPECT(map.size() == 0); 68 } 69 70 KJ_TEST("TreeMap") { 71 TreeMap<String, int> map; 72 73 map.insert(kj::str("foo"), 123); 74 map.insert(kj::str("bar"), 456); 75 76 KJ_EXPECT(KJ_ASSERT_NONNULL(map.find("foo"_kj)) == 123); 77 KJ_EXPECT(KJ_ASSERT_NONNULL(map.find("bar"_kj)) == 456); 78 KJ_EXPECT(map.find("baz"_kj) == nullptr); 79 80 map.upsert(kj::str("foo"), 789, [](int& old, uint newValue) { 81 KJ_EXPECT(old == 123); 82 KJ_EXPECT(newValue == 789); 83 old = 321; 84 }); 85 86 KJ_EXPECT(KJ_ASSERT_NONNULL(map.find("foo"_kj)) == 321); 87 88 KJ_EXPECT( 89 map.findOrCreate("foo"_kj, 90 []() -> TreeMap<String, int>::Entry { KJ_FAIL_ASSERT("shouldn't have been called"); }) 91 == 321); 92 KJ_EXPECT(map.findOrCreate("baz"_kj, 93 [](){ return TreeMap<String, int>::Entry { kj::str("baz"), 654 }; }) == 654); 94 KJ_EXPECT(KJ_ASSERT_NONNULL(map.find("baz"_kj)) == 654); 95 96 KJ_EXPECT(map.erase("bar"_kj)); 97 KJ_EXPECT(map.erase("baz"_kj)); 98 KJ_EXPECT(!map.erase("qux"_kj)); 99 100 KJ_EXPECT(KJ_ASSERT_NONNULL(map.find("foo"_kj)) == 321); 101 KJ_EXPECT(map.size() == 1); 102 KJ_EXPECT(map.begin()->key == "foo"); 103 auto iter = map.begin(); 104 ++iter; 105 KJ_EXPECT(iter == map.end()); 106 107 map.erase(*map.begin()); 108 KJ_EXPECT(map.size() == 0); 109 } 110 111 KJ_TEST("TreeMap range") { 112 TreeMap<String, int> map; 113 114 map.insert(kj::str("foo"), 1); 115 map.insert(kj::str("bar"), 2); 116 map.insert(kj::str("baz"), 3); 117 map.insert(kj::str("qux"), 4); 118 map.insert(kj::str("corge"), 5); 119 120 { 121 auto ordered = KJ_MAP(e, map) -> kj::StringPtr { return e.key; }; 122 KJ_ASSERT(ordered.size() == 5); 123 KJ_EXPECT(ordered[0] == "bar"); 124 KJ_EXPECT(ordered[1] == "baz"); 125 KJ_EXPECT(ordered[2] == "corge"); 126 KJ_EXPECT(ordered[3] == "foo"); 127 KJ_EXPECT(ordered[4] == "qux"); 128 } 129 130 { 131 auto range = map.range("baz", "foo"); 132 auto iter = range.begin(); 133 KJ_EXPECT(iter->key == "baz"); 134 ++iter; 135 KJ_EXPECT(iter->key == "corge"); 136 ++iter; 137 KJ_EXPECT(iter == range.end()); 138 } 139 140 map.eraseRange("baz", "foo"); 141 142 { 143 auto ordered = KJ_MAP(e, map) -> kj::StringPtr { return e.key; }; 144 KJ_ASSERT(ordered.size() == 3); 145 KJ_EXPECT(ordered[0] == "bar"); 146 KJ_EXPECT(ordered[1] == "foo"); 147 KJ_EXPECT(ordered[2] == "qux"); 148 } 149 } 150 151 #if !KJ_NO_EXCEPTIONS 152 KJ_TEST("HashMap findOrCreate throws") { 153 HashMap<int, String> m; 154 try { 155 m.findOrCreate(1, []() -> HashMap<int, String>::Entry { 156 throw "foo"; 157 }); 158 KJ_FAIL_ASSERT("shouldn't get here"); 159 } catch (const char*) { 160 // expected 161 } 162 163 KJ_EXPECT(m.find(1) == nullptr); 164 m.findOrCreate(1, []() { 165 return HashMap<int, String>::Entry { 1, kj::str("ok") }; 166 }); 167 168 KJ_EXPECT(KJ_ASSERT_NONNULL(m.find(1)) == "ok"); 169 } 170 #endif 171 172 template <typename MapType> 173 void testEraseAll(MapType& m) { 174 m.insert(12, "foo"); 175 m.insert(83, "bar"); 176 m.insert(99, "baz"); 177 m.insert(6, "qux"); 178 m.insert(55, "corge"); 179 180 auto count = m.eraseAll([](int i, StringPtr s) { 181 return i == 99 || s == "foo"; 182 }); 183 184 KJ_EXPECT(count == 2); 185 KJ_EXPECT(m.size() == 3); 186 KJ_EXPECT(m.find(12) == nullptr); 187 KJ_EXPECT(m.find(99) == nullptr); 188 KJ_EXPECT(KJ_ASSERT_NONNULL(m.find(83)) == "bar"); 189 KJ_EXPECT(KJ_ASSERT_NONNULL(m.find(6)) == "qux"); 190 KJ_EXPECT(KJ_ASSERT_NONNULL(m.find(55)) == "corge"); 191 } 192 193 KJ_TEST("HashMap eraseAll") { 194 HashMap<int, StringPtr> m; 195 testEraseAll(m); 196 } 197 198 KJ_TEST("TreeMap eraseAll") { 199 TreeMap<int, StringPtr> m; 200 testEraseAll(m); 201 } 202 203 } // namespace 204 } // namespace _ 205 } // namespace kj