hash_map.cc (5603B)
1 #include "hash_map.hh" 2 3 #include "clock.hh" 4 #include "string.hh" 5 #include "unit_tests.hh" 6 #include "format.hh" 7 #include "debug.hh" 8 9 #include <random> 10 #include <algorithm> 11 #include <unordered_map> 12 13 namespace Kakoune 14 { 15 16 UnitTest test_hash_map{[] { 17 // Basic usage 18 { 19 HashMap<int, int> map; 20 map.insert({10, 1}); 21 map.insert({20, 2}); 22 kak_assert(map.find_index(0) == -1); 23 kak_assert(map.find_index(10) == 0); 24 kak_assert(map.find_index(20) == 1); 25 kak_assert(map[10] == 1); 26 kak_assert(map[20] == 2); 27 kak_assert(map[30] == 0); 28 map[30] = 3; 29 kak_assert(map.find_index(30) == 2); 30 map.remove(20); 31 kak_assert(map.find_index(30) == 1); 32 kak_assert(map.size() == 2); 33 } 34 35 // Replace Multiple entries with the same key 36 { 37 HashMap<int, int> map; 38 map.insert({10, 1}); 39 map.insert({10, 2}); 40 kak_assert(map.find_index(10) == 0); 41 kak_assert(map.size() == 1); 42 kak_assert(map[10] == 2); 43 map.remove(10); 44 kak_assert(map.find_index(10) == -1); 45 } 46 47 // Multiple entries with the same key 48 { 49 MultiHashMap<int, int> map; 50 map.insert({10, 1}); 51 map.insert({10, 2}); 52 kak_assert(map.find_index(10) == 0); 53 map.remove(10); 54 kak_assert(map.find_index(10) == 0); 55 map.remove(10); 56 kak_assert(map.find_index(10) == -1); 57 map.insert({20, 1}); 58 map.insert({20, 2}); 59 map.remove_all(20); 60 kak_assert(map.find_index(20) == -1); 61 } 62 63 // Check hash compatible support 64 { 65 HashMap<String, int> map; 66 map.insert({"test", 10}); 67 kak_assert(map["test"_sv] == 10); 68 map.remove("test"_sv); 69 } 70 71 // make sure we get what we expect from the hash map 72 { 73 std::random_device dev; 74 std::default_random_engine re{dev()}; 75 std::uniform_int_distribution<int> dist; 76 77 HashMap<int, int> map; 78 Vector<std::pair<int, int>> ref; 79 80 for (int i = 0; i < 100; ++i) 81 { 82 auto key = dist(re), value = dist(re); 83 ref.push_back({key, value}); 84 map.insert({key, value}); 85 86 std::shuffle(ref.begin(), ref.end(), re); 87 for (auto& elem : ref) 88 { 89 auto it = map.find(elem.first); 90 kak_assert(it != map.end() and it->value == elem.second); 91 } 92 } 93 } 94 }}; 95 96 UnitTest test_hash_set{[] { 97 // Basic usage 98 { 99 HashSet<int> set; 100 set.insert(10); 101 set.insert(20); 102 kak_assert(set.find_index(0) == -1); 103 kak_assert(set.find_index(10) == 0); 104 kak_assert(set.find_index(20) == 1); 105 kak_assert(set[10] == 10); 106 kak_assert(set[20] == 20); 107 kak_assert(set[30] == 30); 108 set[30]; 109 kak_assert(set.find_index(30) == 2); 110 set.remove(20); 111 kak_assert(set.find_index(30) == 1); 112 kak_assert(set.size() == 2); 113 } 114 115 // Replace Multiple entries with the same key 116 { 117 HashSet<int> set; 118 set.insert(10); 119 set.insert(10); 120 kak_assert(set.find_index(10) == 0); 121 kak_assert(set.size() == 1); 122 set.remove(10); 123 kak_assert(set.find_index(10) == -1); 124 } 125 126 // Multiple entries with the same key 127 { 128 MultiHashSet<int> set; 129 set.insert(10); 130 set.insert(10); 131 kak_assert(set.find_index(10) == 0); 132 set.remove(10); 133 kak_assert(set.find_index(10) == 0); 134 set.remove(10); 135 kak_assert(set.find_index(10) == -1); 136 set.insert(20); 137 set.insert(20); 138 set.remove_all(20); 139 kak_assert(set.find_index(20) == -1); 140 } 141 142 // Check hash compatible support 143 { 144 HashSet<String> set; 145 set.insert("test"); 146 kak_assert(set["test"_sv] == "test"); 147 set.remove("test"_sv); 148 } 149 }}; 150 151 template<typename Map> 152 void do_profile(size_t count, StringView type) 153 { 154 std::random_device dev; 155 std::default_random_engine re{dev()}; 156 std::uniform_int_distribution<size_t> dist{0, count}; 157 158 Vector<size_t> vec; 159 for (size_t i = 0; i < count; ++i) 160 vec.push_back(i); 161 std::shuffle(vec.begin(), vec.end(), re); 162 163 Map map; 164 auto start = Clock::now(); 165 166 for (auto v : vec) 167 map.insert({v, dist(re)}); 168 auto after_insert = Clock::now(); 169 170 for (size_t i = 0; i < count; ++i) 171 ++map[dist(re)]; 172 auto after_read = Clock::now(); 173 174 for (size_t i = 0; i < count; ++i) 175 map.erase(dist(re)); 176 auto after_remove = Clock::now(); 177 178 int c = 0; 179 for (auto v : vec) 180 { 181 auto it = map.find(v); 182 if (it != map.end()) 183 ++c; 184 } 185 auto after_find = Clock::now(); 186 187 using namespace std::chrono; 188 write_to_debug_buffer(format("{} ({}) -- inserts: {}us, reads: {}us, remove: {}us, find: {}us ({})", type, count, 189 duration_cast<microseconds>(after_insert - start).count(), 190 duration_cast<microseconds>(after_read - after_insert).count(), 191 duration_cast<microseconds>(after_remove - after_read).count(), 192 duration_cast<microseconds>(after_find - after_remove).count(), 193 c)); 194 } 195 196 void profile_hash_maps() 197 { 198 for (auto i : { 1000, 10000, 100000, 1000000, 10000000 }) 199 { 200 do_profile<std::unordered_map<size_t, size_t>>(i, "UnorderedMap"); 201 do_profile<HashMap<size_t, size_t>>(i, " HashMap"); 202 } 203 } 204 205 }