1 /*
2 * Copyright (C) 2014 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "dictionary/utils/trie_map.h"
18
19 #include <gtest/gtest.h>
20
21 #include <algorithm>
22 #include <cstdlib>
23 #include <functional>
24 #include <map>
25 #include <random>
26 #include <unordered_map>
27
28 namespace latinime {
29 namespace {
30
TEST(TrieMapTest,TestSetAndGet)31 TEST(TrieMapTest, TestSetAndGet) {
32 TrieMap trieMap;
33 trieMap.putRoot(10, 10);
34 EXPECT_EQ(10ull, trieMap.getRoot(10).mValue);
35 trieMap.putRoot(0x10A, 10);
36 EXPECT_EQ(10ull, trieMap.getRoot(10).mValue);
37 EXPECT_EQ(10ull, trieMap.getRoot(0x10A).mValue);
38 trieMap.putRoot(10, 1000);
39 EXPECT_EQ(1000ull, trieMap.getRoot(10).mValue);
40 trieMap.putRoot(11, 1000);
41 EXPECT_EQ(1000ull, trieMap.getRoot(11).mValue);
42 const int next = trieMap.getNextLevelBitmapEntryIndex(10);
43 EXPECT_EQ(1000ull, trieMap.getRoot(10).mValue);
44 trieMap.put(9, 9, next);
45 EXPECT_EQ(9ull, trieMap.get(9, next).mValue);
46 EXPECT_FALSE(trieMap.get(11, next).mIsValid);
47 trieMap.putRoot(0, 0xFFFFFFFFFull);
48 EXPECT_EQ(0xFFFFFFFFFull, trieMap.getRoot(0).mValue);
49 }
50
TEST(TrieMapTest,TestRemove)51 TEST(TrieMapTest, TestRemove) {
52 TrieMap trieMap;
53 trieMap.putRoot(10, 10);
54 EXPECT_EQ(10ull, trieMap.getRoot(10).mValue);
55 EXPECT_TRUE(trieMap.remove(10, trieMap.getRootBitmapEntryIndex()));
56 EXPECT_FALSE(trieMap.getRoot(10).mIsValid);
57 for (const auto &element : trieMap.getEntriesInRootLevel()) {
58 EXPECT_TRUE(false);
59 }
60 EXPECT_TRUE(trieMap.putRoot(10, 0x3FFFFF));
61 EXPECT_FALSE(trieMap.remove(11, trieMap.getRootBitmapEntryIndex()))
62 << "Should fail if the key does not exist.";
63 EXPECT_EQ(0x3FFFFFull, trieMap.getRoot(10).mValue);
64 trieMap.putRoot(12, 11);
65 const int nextLevel = trieMap.getNextLevelBitmapEntryIndex(10);
66 trieMap.put(10, 10, nextLevel);
67 EXPECT_EQ(0x3FFFFFull, trieMap.getRoot(10).mValue);
68 EXPECT_EQ(10ull, trieMap.get(10, nextLevel).mValue);
69 EXPECT_TRUE(trieMap.remove(10, trieMap.getRootBitmapEntryIndex()));
70 const TrieMap::Result result = trieMap.getRoot(10);
71 EXPECT_FALSE(result.mIsValid);
72 EXPECT_EQ(TrieMap::INVALID_INDEX, result.mNextLevelBitmapEntryIndex);
73 EXPECT_EQ(11ull, trieMap.getRoot(12).mValue);
74 EXPECT_TRUE(trieMap.putRoot(S_INT_MAX, 0xFFFFFFFFFull));
75 EXPECT_TRUE(trieMap.remove(S_INT_MAX, trieMap.getRootBitmapEntryIndex()));
76 }
77
TEST(TrieMapTest,TestSetAndGetLarge)78 TEST(TrieMapTest, TestSetAndGetLarge) {
79 static const int ELEMENT_COUNT = 200000;
80 TrieMap trieMap;
81 for (int i = 0; i < ELEMENT_COUNT; ++i) {
82 EXPECT_TRUE(trieMap.putRoot(i, i));
83 }
84 for (int i = 0; i < ELEMENT_COUNT; ++i) {
85 EXPECT_EQ(static_cast<uint64_t>(i), trieMap.getRoot(i).mValue);
86 }
87 }
88
TEST(TrieMapTest,TestRandSetAndGetLarge)89 TEST(TrieMapTest, TestRandSetAndGetLarge) {
90 static const int ELEMENT_COUNT = 100000;
91 TrieMap trieMap;
92 std::unordered_map<int, uint64_t> testKeyValuePairs;
93
94 // Use the uniform integer distribution [S_INT_MIN, S_INT_MAX].
95 std::uniform_int_distribution<int> keyDistribution(S_INT_MIN, S_INT_MAX);
96 auto keyRandomNumberGenerator = std::bind(keyDistribution, std::mt19937());
97
98 // Use the uniform distribution [0, TrieMap::MAX_VALUE].
99 std::uniform_int_distribution<uint64_t> valueDistribution(0, TrieMap::MAX_VALUE);
100 auto valueRandomNumberGenerator = std::bind(valueDistribution, std::mt19937());
101
102 for (int i = 0; i < ELEMENT_COUNT; ++i) {
103 const int key = keyRandomNumberGenerator();
104 const uint64_t value = valueRandomNumberGenerator();
105 EXPECT_TRUE(trieMap.putRoot(key, value)) << key << " " << value;
106 testKeyValuePairs[key] = value;
107 }
108 for (const auto &v : testKeyValuePairs) {
109 EXPECT_EQ(v.second, trieMap.getRoot(v.first).mValue);
110 }
111 }
112
TEST(TrieMapTest,TestMultiLevel)113 TEST(TrieMapTest, TestMultiLevel) {
114 static const int FIRST_LEVEL_ENTRY_COUNT = 10000;
115 static const int SECOND_LEVEL_ENTRY_COUNT = 20000;
116 static const int THIRD_LEVEL_ENTRY_COUNT = 40000;
117
118 TrieMap trieMap;
119 std::vector<int> firstLevelKeys;
120 std::map<int, uint64_t> firstLevelEntries;
121 std::vector<std::pair<int, int>> secondLevelKeys;
122 std::map<int, std::map<int, uint64_t>> twoLevelMap;
123 std::map<int, std::map<int, std::map<int, uint64_t>>> threeLevelMap;
124
125 // Use the uniform integer distribution [0, S_INT_MAX].
126 std::uniform_int_distribution<int> distribution(0, S_INT_MAX);
127 auto keyRandomNumberGenerator = std::bind(distribution, std::mt19937());
128 auto randomNumberGeneratorForKeySelection = std::bind(distribution, std::mt19937());
129
130 // Use the uniform distribution [0, TrieMap::MAX_VALUE].
131 std::uniform_int_distribution<uint64_t> valueDistribution(0, TrieMap::MAX_VALUE);
132 auto valueRandomNumberGenerator = std::bind(valueDistribution, std::mt19937());
133
134 for (int i = 0; i < FIRST_LEVEL_ENTRY_COUNT; ++i) {
135 const int key = keyRandomNumberGenerator();
136 const uint64_t value = valueRandomNumberGenerator();
137 EXPECT_TRUE(trieMap.putRoot(key, value));
138 firstLevelKeys.push_back(key);
139 firstLevelEntries[key] = value;
140 }
141
142 for (int i = 0; i < SECOND_LEVEL_ENTRY_COUNT; ++i) {
143 const int key = keyRandomNumberGenerator();
144 const uint64_t value = valueRandomNumberGenerator();
145 const int firstLevelKey =
146 firstLevelKeys[randomNumberGeneratorForKeySelection() % FIRST_LEVEL_ENTRY_COUNT];
147 const int nextLevelBitmapEntryIndex = trieMap.getNextLevelBitmapEntryIndex(firstLevelKey);
148 EXPECT_NE(TrieMap::INVALID_INDEX, nextLevelBitmapEntryIndex);
149 EXPECT_TRUE(trieMap.put(key, value, nextLevelBitmapEntryIndex));
150 secondLevelKeys.push_back(std::make_pair(firstLevelKey, key));
151 twoLevelMap[firstLevelKey][key] = value;
152 }
153
154 for (int i = 0; i < THIRD_LEVEL_ENTRY_COUNT; ++i) {
155 const int key = keyRandomNumberGenerator();
156 const uint64_t value = valueRandomNumberGenerator();
157 const std::pair<int, int> secondLevelKey =
158 secondLevelKeys[randomNumberGeneratorForKeySelection() % SECOND_LEVEL_ENTRY_COUNT];
159 const int secondLevel = trieMap.getNextLevelBitmapEntryIndex(secondLevelKey.first);
160 EXPECT_NE(TrieMap::INVALID_INDEX, secondLevel);
161 const int thirdLevel = trieMap.getNextLevelBitmapEntryIndex(
162 secondLevelKey.second, secondLevel);
163 EXPECT_NE(TrieMap::INVALID_INDEX, thirdLevel);
164 EXPECT_TRUE(trieMap.put(key, value, thirdLevel));
165 threeLevelMap[secondLevelKey.first][secondLevelKey.second][key] = value;
166 }
167
168 for (const auto &firstLevelEntry : firstLevelEntries) {
169 EXPECT_EQ(firstLevelEntry.second, trieMap.getRoot(firstLevelEntry.first).mValue);
170 }
171
172 for (const auto &firstLevelEntry : twoLevelMap) {
173 const int secondLevel = trieMap.getNextLevelBitmapEntryIndex(firstLevelEntry.first);
174 EXPECT_NE(TrieMap::INVALID_INDEX, secondLevel);
175 for (const auto &secondLevelEntry : firstLevelEntry.second) {
176 EXPECT_EQ(secondLevelEntry.second,
177 trieMap.get(secondLevelEntry.first, secondLevel).mValue);
178 }
179 }
180
181 for (const auto &firstLevelEntry : threeLevelMap) {
182 const int secondLevel = trieMap.getNextLevelBitmapEntryIndex(firstLevelEntry.first);
183 EXPECT_NE(TrieMap::INVALID_INDEX, secondLevel);
184 for (const auto &secondLevelEntry : firstLevelEntry.second) {
185 const int thirdLevel =
186 trieMap.getNextLevelBitmapEntryIndex(secondLevelEntry.first, secondLevel);
187 EXPECT_NE(TrieMap::INVALID_INDEX, thirdLevel);
188 for (const auto &thirdLevelEntry : secondLevelEntry.second) {
189 EXPECT_EQ(thirdLevelEntry.second,
190 trieMap.get(thirdLevelEntry.first, thirdLevel).mValue);
191 }
192 }
193 }
194
195 // Iteration
196 for (const auto &firstLevelEntry : trieMap.getEntriesInRootLevel()) {
197 EXPECT_EQ(trieMap.getRoot(firstLevelEntry.key()).mValue, firstLevelEntry.value());
198 EXPECT_EQ(firstLevelEntries[firstLevelEntry.key()], firstLevelEntry.value());
199 firstLevelEntries.erase(firstLevelEntry.key());
200 for (const auto &secondLevelEntry : firstLevelEntry.getEntriesInNextLevel()) {
201 EXPECT_EQ(twoLevelMap[firstLevelEntry.key()][secondLevelEntry.key()],
202 secondLevelEntry.value());
203 twoLevelMap[firstLevelEntry.key()].erase(secondLevelEntry.key());
204 for (const auto &thirdLevelEntry : secondLevelEntry.getEntriesInNextLevel()) {
205 EXPECT_EQ(threeLevelMap[firstLevelEntry.key()][secondLevelEntry.key()]
206 [thirdLevelEntry.key()], thirdLevelEntry.value());
207 threeLevelMap[firstLevelEntry.key()][secondLevelEntry.key()].erase(
208 thirdLevelEntry.key());
209 }
210 }
211 }
212
213 // Ensure all entries have been traversed.
214 EXPECT_TRUE(firstLevelEntries.empty());
215 for (const auto &secondLevelEntry : twoLevelMap) {
216 EXPECT_TRUE(secondLevelEntry.second.empty());
217 }
218 for (const auto &secondLevelEntry : threeLevelMap) {
219 for (const auto &thirdLevelEntry : secondLevelEntry.second) {
220 EXPECT_TRUE(thirdLevelEntry.second.empty());
221 }
222 }
223 }
224
TEST(TrieMapTest,TestIteration)225 TEST(TrieMapTest, TestIteration) {
226 static const int ELEMENT_COUNT = 200000;
227 TrieMap trieMap;
228 std::unordered_map<int, uint64_t> testKeyValuePairs;
229
230 // Use the uniform integer distribution [S_INT_MIN, S_INT_MAX].
231 std::uniform_int_distribution<int> keyDistribution(S_INT_MIN, S_INT_MAX);
232 auto keyRandomNumberGenerator = std::bind(keyDistribution, std::mt19937());
233
234 // Use the uniform distribution [0, TrieMap::MAX_VALUE].
235 std::uniform_int_distribution<uint64_t> valueDistribution(0, TrieMap::MAX_VALUE);
236 auto valueRandomNumberGenerator = std::bind(valueDistribution, std::mt19937());
237 for (int i = 0; i < ELEMENT_COUNT; ++i) {
238 const int key = keyRandomNumberGenerator();
239 const uint64_t value = valueRandomNumberGenerator();
240 EXPECT_TRUE(trieMap.putRoot(key, value));
241 testKeyValuePairs[key] = value;
242 }
243 for (const auto &entry : trieMap.getEntriesInRootLevel()) {
244 EXPECT_EQ(trieMap.getRoot(entry.key()).mValue, entry.value());
245 EXPECT_EQ(testKeyValuePairs[entry.key()], entry.value());
246 testKeyValuePairs.erase(entry.key());
247 }
248 EXPECT_TRUE(testKeyValuePairs.empty());
249 }
250
251 } // namespace
252 } // namespace latinime
253