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