1 // Copyright (c) Microsoft Corporation. All rights reserved. 2 // Licensed under the MIT license. 3 4 #include "kuku/kuku.h" 5 #include "gtest/gtest.h" 6 #include <algorithm> 7 #include <cmath> 8 9 using namespace kuku; 10 using namespace std; 11 12 namespace kuku_tests 13 { TEST(KukuTableTests,Create)14 TEST(KukuTableTests, Create) 15 { 16 ASSERT_THROW(KukuTable(0, 0, 2, make_zero_item(), 1, make_zero_item()), invalid_argument); 17 ASSERT_THROW(KukuTable(1, 0, 0, make_zero_item(), 1, make_zero_item()), invalid_argument); 18 ASSERT_THROW(KukuTable(1, 0, 2, make_zero_item(), 0, make_zero_item()), invalid_argument); 19 ASSERT_NO_THROW(KukuTable(min_table_size, 0, 2, make_zero_item(), 1, make_zero_item())); 20 ASSERT_NO_THROW(KukuTable(1, 0, min_loc_func_count, make_zero_item(), 1, make_zero_item())); 21 } 22 TEST(KukuTableTests,Populate1)23 TEST(KukuTableTests, Populate1) 24 { 25 { 26 KukuTable ct(1, 0, 1, make_zero_item(), 10, make_zero_item()); 27 ASSERT_TRUE(ct.is_empty(0)); 28 ASSERT_TRUE(ct.insert(make_item(1, 0))); 29 ASSERT_FALSE(ct.insert(make_item(0, 1))); 30 ASSERT_THROW(ct.insert(ct.empty_item()), invalid_argument); 31 ASSERT_THROW(ct.insert(make_item(0, 0)), invalid_argument); 32 ASSERT_FALSE(ct.is_empty(0)); 33 } 34 { 35 KukuTable ct(1, 0, 2, make_zero_item(), 10, make_zero_item()); 36 ASSERT_TRUE(ct.is_empty(0)); 37 ASSERT_TRUE(ct.insert(make_item(1, 0))); 38 ASSERT_FALSE(ct.insert(make_item(0, 1))); 39 ASSERT_THROW(ct.insert(ct.empty_item()), invalid_argument); 40 ASSERT_THROW(ct.insert(make_item(0, 0)), invalid_argument); 41 ASSERT_FALSE(ct.is_empty(0)); 42 } 43 { 44 KukuTable ct(2, 0, 1, make_zero_item(), 10, make_zero_item()); 45 ASSERT_TRUE(ct.is_empty(0)); 46 ASSERT_TRUE(ct.insert(make_item(1, 0))); 47 48 // Collision 49 ASSERT_FALSE(ct.insert(make_item(0, 1))); 50 51 // No collision 52 ASSERT_TRUE(ct.insert(make_item(0, 2))); 53 54 ASSERT_FALSE(ct.is_empty(0)); 55 ASSERT_FALSE(ct.is_empty(1)); 56 } 57 } 58 TEST(KukuTableTests,Populate2)59 TEST(KukuTableTests, Populate2) 60 { 61 KukuTable ct(1 << 10, 0, 2, make_zero_item(), 10, make_zero_item()); 62 for (location_type i = 0; i < ct.table_size(); i++) 63 { 64 ASSERT_TRUE(ct.is_empty(i)); 65 } 66 67 ASSERT_TRUE(ct.insert(make_item(1, 0))); 68 ASSERT_TRUE(ct.insert(make_item(0, 1))); 69 ASSERT_TRUE(ct.insert(make_item(1, 1))); 70 ASSERT_TRUE(ct.insert(make_item(2, 2))); 71 ASSERT_THROW(ct.insert(ct.empty_item()), invalid_argument); 72 ASSERT_THROW(ct.insert(make_item(0, 0)), invalid_argument); 73 74 int non_empties = 0; 75 for (location_type i = 0; i < ct.table_size(); i++) 76 { 77 non_empties += ct.is_empty(i) ? 0 : 1; 78 } 79 ASSERT_EQ(non_empties, 4); 80 81 ASSERT_TRUE(ct.query(make_item(1, 0))); 82 ASSERT_TRUE(ct.query(make_item(0, 1))); 83 ASSERT_TRUE(ct.query(make_item(1, 1))); 84 ASSERT_TRUE(ct.query(make_item(2, 2))); 85 ASSERT_FALSE(ct.query(make_item(3, 3))); 86 } 87 TEST(KukuTableTests,Populate3)88 TEST(KukuTableTests, Populate3) 89 { 90 KukuTable ct(1 << 10, 0, 2, make_zero_item(), 10, make_random_item()); 91 for (location_type i = 0; i < ct.table_size(); i++) 92 { 93 ASSERT_TRUE(ct.is_empty(i)); 94 } 95 96 ASSERT_TRUE(ct.insert(make_item(0, 0))); 97 ASSERT_TRUE(ct.insert(make_item(1, 0))); 98 ASSERT_TRUE(ct.insert(make_item(0, 1))); 99 ASSERT_TRUE(ct.insert(make_item(1, 1))); 100 ASSERT_TRUE(ct.insert(make_item(2, 2))); 101 102 // Fails 103 ASSERT_FALSE(ct.insert(make_item(2, 2))); 104 105 ASSERT_THROW(ct.insert(ct.empty_item()), invalid_argument); 106 107 int non_empties = 0; 108 for (location_type i = 0; i < ct.table_size(); i++) 109 { 110 non_empties += ct.is_empty(i) ? 0 : 1; 111 } 112 ASSERT_EQ(non_empties, 5); 113 114 ASSERT_TRUE(ct.query(make_item(0, 0))); 115 ASSERT_TRUE(ct.query(make_item(1, 0))); 116 ASSERT_TRUE(ct.query(make_item(0, 1))); 117 ASSERT_TRUE(ct.query(make_item(1, 1))); 118 ASSERT_TRUE(ct.query(make_item(2, 2))); 119 ASSERT_FALSE(ct.query(make_item(3, 3))); 120 } 121 TEST(KukuTableTests,Fill1)122 TEST(KukuTableTests, Fill1) 123 { 124 KukuTable ct(1 << 10, 0, 2, make_zero_item(), 100, make_random_item()); 125 vector<item_type> inserted_items; 126 for (int i = 0; i < 100; i++) 127 { 128 inserted_items.emplace_back(make_random_item()); 129 ASSERT_TRUE(ct.insert(inserted_items.back())); 130 } 131 for (auto b : inserted_items) 132 { 133 ASSERT_TRUE(ct.query(b)); 134 } 135 ASSERT_FALSE(ct.query(make_random_item())); 136 } 137 TEST(KukuTableTests,Fill2)138 TEST(KukuTableTests, Fill2) 139 { 140 KukuTable ct((1 << 10) - 1, 0, 4, make_zero_item(), 100, make_random_item()); 141 vector<item_type> inserted_items; 142 for (int i = 0; i < 600; i++) 143 { 144 inserted_items.emplace_back(make_random_item()); 145 ASSERT_TRUE(ct.insert(inserted_items.back())); 146 } 147 for (auto b : inserted_items) 148 { 149 ASSERT_TRUE(ct.query(b)); 150 } 151 ASSERT_FALSE(ct.query(make_random_item())); 152 } 153 TEST(KukuTableTests,Fill3)154 TEST(KukuTableTests, Fill3) 155 { 156 KukuTable ct((1 << 10) + 1, 4, 2, make_zero_item(), 100, make_random_item()); 157 vector<item_type> inserted_items; 158 for (int i = 0; i < 950; i++) 159 { 160 inserted_items.emplace_back(make_random_item()); 161 if (!ct.insert(inserted_items.back())) 162 { 163 auto it = find_if(inserted_items.cbegin(), inserted_items.cend(), [&](const item_type &item) { 164 return are_equal_item(ct.leftover_item(), item); 165 }); 166 ASSERT_TRUE(it != inserted_items.cend()); 167 ASSERT_FALSE(ct.query(ct.leftover_item())); 168 inserted_items.erase(it); 169 } 170 } 171 for (auto b : inserted_items) 172 { 173 ASSERT_TRUE(ct.query(b)); 174 } 175 } 176 TEST(KukuTableTests,Locations)177 TEST(KukuTableTests, Locations) 178 { 179 uint8_t lfc = 2; 180 KukuTable ct(1 << 10, 4, lfc, make_random_item(), 100, make_all_ones_item()); 181 for (int k = 0; k < 20; k++) 182 { 183 auto it = make_random_item(); 184 auto all_locs = ct.all_locations(it); 185 186 bool collision_found = false; 187 for (uint8_t i = 0; i < lfc; i++) 188 { 189 for (uint8_t j = 0; j < i; j++) 190 { 191 collision_found = collision_found || (ct.location(it, i) == ct.location(it, j)); 192 } 193 } 194 195 ASSERT_EQ(all_locs.size() < lfc, collision_found); 196 } 197 } 198 TEST(KukuTableTests,RepeatedInsert)199 TEST(KukuTableTests, RepeatedInsert) 200 { 201 KukuTable ct(1 << 10, 0, 4, make_zero_item(), 10, make_zero_item()); 202 ASSERT_TRUE(ct.insert(make_item(1, 0))); 203 ASSERT_TRUE(ct.insert(make_item(0, 1))); 204 ASSERT_TRUE(ct.insert(make_item(1, 1))); 205 ASSERT_TRUE(ct.insert(make_item(2, 2))); 206 207 ASSERT_FALSE(ct.insert(make_item(1, 0))); 208 ASSERT_FALSE(ct.insert(make_item(0, 1))); 209 ASSERT_FALSE(ct.insert(make_item(1, 1))); 210 ASSERT_FALSE(ct.insert(make_item(2, 2))); 211 } 212 } // namespace kuku_tests 213