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         (void)element; // not used
59         EXPECT_TRUE(false);
60     }
61     EXPECT_TRUE(trieMap.putRoot(10, 0x3FFFFF));
62     EXPECT_FALSE(trieMap.remove(11, trieMap.getRootBitmapEntryIndex()))
63             << "Should fail if the key does not exist.";
64     EXPECT_EQ(0x3FFFFFull, trieMap.getRoot(10).mValue);
65     trieMap.putRoot(12, 11);
66     const int nextLevel = trieMap.getNextLevelBitmapEntryIndex(10);
67     trieMap.put(10, 10, nextLevel);
68     EXPECT_EQ(0x3FFFFFull, trieMap.getRoot(10).mValue);
69     EXPECT_EQ(10ull, trieMap.get(10, nextLevel).mValue);
70     EXPECT_TRUE(trieMap.remove(10, trieMap.getRootBitmapEntryIndex()));
71     const TrieMap::Result result = trieMap.getRoot(10);
72     EXPECT_FALSE(result.mIsValid);
73     EXPECT_EQ(TrieMap::INVALID_INDEX, result.mNextLevelBitmapEntryIndex);
74     EXPECT_EQ(11ull, trieMap.getRoot(12).mValue);
75     EXPECT_TRUE(trieMap.putRoot(S_INT_MAX, 0xFFFFFFFFFull));
76     EXPECT_TRUE(trieMap.remove(S_INT_MAX, trieMap.getRootBitmapEntryIndex()));
77 }
78 
TEST(TrieMapTest,TestSetAndGetLarge)79 TEST(TrieMapTest, TestSetAndGetLarge) {
80     static const int ELEMENT_COUNT = 200000;
81     TrieMap trieMap;
82     for (int i = 0; i < ELEMENT_COUNT; ++i) {
83         EXPECT_TRUE(trieMap.putRoot(i, i));
84     }
85     for (int i = 0; i < ELEMENT_COUNT; ++i) {
86         EXPECT_EQ(static_cast<uint64_t>(i), trieMap.getRoot(i).mValue);
87     }
88 }
89 
TEST(TrieMapTest,TestRandSetAndGetLarge)90 TEST(TrieMapTest, TestRandSetAndGetLarge) {
91     static const int ELEMENT_COUNT = 100000;
92     TrieMap trieMap;
93     std::unordered_map<int, uint64_t> testKeyValuePairs;
94 
95     // Use the uniform integer distribution [S_INT_MIN, S_INT_MAX].
96     std::uniform_int_distribution<int> keyDistribution(S_INT_MIN, S_INT_MAX);
97     auto keyRandomNumberGenerator = std::bind(keyDistribution, std::mt19937());
98 
99     // Use the uniform distribution [0, TrieMap::MAX_VALUE].
100     std::uniform_int_distribution<uint64_t> valueDistribution(0, TrieMap::MAX_VALUE);
101     auto valueRandomNumberGenerator = std::bind(valueDistribution, std::mt19937());
102 
103     for (int i = 0; i < ELEMENT_COUNT; ++i) {
104         const int key = keyRandomNumberGenerator();
105         const uint64_t value = valueRandomNumberGenerator();
106         EXPECT_TRUE(trieMap.putRoot(key, value)) << key << " " << value;
107         testKeyValuePairs[key] = value;
108     }
109     for (const auto &v : testKeyValuePairs) {
110         EXPECT_EQ(v.second, trieMap.getRoot(v.first).mValue);
111     }
112 }
113 
TEST(TrieMapTest,TestMultiLevel)114 TEST(TrieMapTest, TestMultiLevel) {
115     static const int FIRST_LEVEL_ENTRY_COUNT = 10000;
116     static const int SECOND_LEVEL_ENTRY_COUNT = 20000;
117     static const int THIRD_LEVEL_ENTRY_COUNT = 40000;
118 
119     TrieMap trieMap;
120     std::vector<int> firstLevelKeys;
121     std::map<int, uint64_t> firstLevelEntries;
122     std::vector<std::pair<int, int>> secondLevelKeys;
123     std::map<int, std::map<int, uint64_t>> twoLevelMap;
124     std::map<int, std::map<int, std::map<int, uint64_t>>> threeLevelMap;
125 
126     // Use the uniform integer distribution [0, S_INT_MAX].
127     std::uniform_int_distribution<int> distribution(0, S_INT_MAX);
128     auto keyRandomNumberGenerator = std::bind(distribution, std::mt19937());
129     auto randomNumberGeneratorForKeySelection = std::bind(distribution, std::mt19937());
130 
131     // Use the uniform distribution [0, TrieMap::MAX_VALUE].
132     std::uniform_int_distribution<uint64_t> valueDistribution(0, TrieMap::MAX_VALUE);
133     auto valueRandomNumberGenerator = std::bind(valueDistribution, std::mt19937());
134 
135     for (int i = 0; i < FIRST_LEVEL_ENTRY_COUNT; ++i) {
136         const int key = keyRandomNumberGenerator();
137         const uint64_t value = valueRandomNumberGenerator();
138         EXPECT_TRUE(trieMap.putRoot(key, value));
139         firstLevelKeys.push_back(key);
140         firstLevelEntries[key] = value;
141     }
142 
143     for (int i = 0; i < SECOND_LEVEL_ENTRY_COUNT; ++i) {
144         const int key = keyRandomNumberGenerator();
145         const uint64_t value = valueRandomNumberGenerator();
146         const int firstLevelKey =
147                 firstLevelKeys[randomNumberGeneratorForKeySelection() % FIRST_LEVEL_ENTRY_COUNT];
148         const int nextLevelBitmapEntryIndex = trieMap.getNextLevelBitmapEntryIndex(firstLevelKey);
149         EXPECT_NE(TrieMap::INVALID_INDEX, nextLevelBitmapEntryIndex);
150         EXPECT_TRUE(trieMap.put(key, value, nextLevelBitmapEntryIndex));
151         secondLevelKeys.push_back(std::make_pair(firstLevelKey, key));
152         twoLevelMap[firstLevelKey][key] = value;
153     }
154 
155     for (int i = 0; i < THIRD_LEVEL_ENTRY_COUNT; ++i) {
156         const int key = keyRandomNumberGenerator();
157         const uint64_t value = valueRandomNumberGenerator();
158         const std::pair<int, int> secondLevelKey =
159                 secondLevelKeys[randomNumberGeneratorForKeySelection() % SECOND_LEVEL_ENTRY_COUNT];
160         const int secondLevel = trieMap.getNextLevelBitmapEntryIndex(secondLevelKey.first);
161         EXPECT_NE(TrieMap::INVALID_INDEX, secondLevel);
162         const int thirdLevel = trieMap.getNextLevelBitmapEntryIndex(
163                 secondLevelKey.second, secondLevel);
164         EXPECT_NE(TrieMap::INVALID_INDEX, thirdLevel);
165         EXPECT_TRUE(trieMap.put(key, value, thirdLevel));
166         threeLevelMap[secondLevelKey.first][secondLevelKey.second][key] = value;
167     }
168 
169     for (const auto &firstLevelEntry : firstLevelEntries) {
170         EXPECT_EQ(firstLevelEntry.second, trieMap.getRoot(firstLevelEntry.first).mValue);
171     }
172 
173     for (const auto &firstLevelEntry : twoLevelMap) {
174         const int secondLevel = trieMap.getNextLevelBitmapEntryIndex(firstLevelEntry.first);
175         EXPECT_NE(TrieMap::INVALID_INDEX, secondLevel);
176         for (const auto &secondLevelEntry : firstLevelEntry.second) {
177             EXPECT_EQ(secondLevelEntry.second,
178                     trieMap.get(secondLevelEntry.first, secondLevel).mValue);
179         }
180     }
181 
182     for (const auto &firstLevelEntry : threeLevelMap) {
183         const int secondLevel = trieMap.getNextLevelBitmapEntryIndex(firstLevelEntry.first);
184         EXPECT_NE(TrieMap::INVALID_INDEX, secondLevel);
185         for (const auto &secondLevelEntry : firstLevelEntry.second) {
186             const int thirdLevel =
187                     trieMap.getNextLevelBitmapEntryIndex(secondLevelEntry.first, secondLevel);
188             EXPECT_NE(TrieMap::INVALID_INDEX, thirdLevel);
189             for (const auto &thirdLevelEntry : secondLevelEntry.second) {
190                 EXPECT_EQ(thirdLevelEntry.second,
191                         trieMap.get(thirdLevelEntry.first, thirdLevel).mValue);
192             }
193         }
194     }
195 
196     // Iteration
197     for (const auto &firstLevelEntry : trieMap.getEntriesInRootLevel()) {
198         EXPECT_EQ(trieMap.getRoot(firstLevelEntry.key()).mValue, firstLevelEntry.value());
199         EXPECT_EQ(firstLevelEntries[firstLevelEntry.key()], firstLevelEntry.value());
200         firstLevelEntries.erase(firstLevelEntry.key());
201         for (const auto &secondLevelEntry : firstLevelEntry.getEntriesInNextLevel()) {
202             EXPECT_EQ(twoLevelMap[firstLevelEntry.key()][secondLevelEntry.key()],
203                     secondLevelEntry.value());
204             twoLevelMap[firstLevelEntry.key()].erase(secondLevelEntry.key());
205             for (const auto &thirdLevelEntry : secondLevelEntry.getEntriesInNextLevel()) {
206                 EXPECT_EQ(threeLevelMap[firstLevelEntry.key()][secondLevelEntry.key()]
207                         [thirdLevelEntry.key()], thirdLevelEntry.value());
208                 threeLevelMap[firstLevelEntry.key()][secondLevelEntry.key()].erase(
209                         thirdLevelEntry.key());
210             }
211         }
212     }
213 
214     // Ensure all entries have been traversed.
215     EXPECT_TRUE(firstLevelEntries.empty());
216     for (const auto &secondLevelEntry : twoLevelMap) {
217         EXPECT_TRUE(secondLevelEntry.second.empty());
218     }
219     for (const auto &secondLevelEntry : threeLevelMap) {
220         for (const auto &thirdLevelEntry : secondLevelEntry.second) {
221             EXPECT_TRUE(thirdLevelEntry.second.empty());
222         }
223     }
224 }
225 
TEST(TrieMapTest,TestIteration)226 TEST(TrieMapTest, TestIteration) {
227     static const int ELEMENT_COUNT = 200000;
228     TrieMap trieMap;
229     std::unordered_map<int, uint64_t> testKeyValuePairs;
230 
231     // Use the uniform integer distribution [S_INT_MIN, S_INT_MAX].
232     std::uniform_int_distribution<int> keyDistribution(S_INT_MIN, S_INT_MAX);
233     auto keyRandomNumberGenerator = std::bind(keyDistribution, std::mt19937());
234 
235     // Use the uniform distribution [0, TrieMap::MAX_VALUE].
236     std::uniform_int_distribution<uint64_t> valueDistribution(0, TrieMap::MAX_VALUE);
237     auto valueRandomNumberGenerator = std::bind(valueDistribution, std::mt19937());
238     for (int i = 0; i < ELEMENT_COUNT; ++i) {
239         const int key = keyRandomNumberGenerator();
240         const uint64_t value = valueRandomNumberGenerator();
241         EXPECT_TRUE(trieMap.putRoot(key, value));
242         testKeyValuePairs[key] = value;
243     }
244     for (const auto &entry : trieMap.getEntriesInRootLevel()) {
245         EXPECT_EQ(trieMap.getRoot(entry.key()).mValue, entry.value());
246         EXPECT_EQ(testKeyValuePairs[entry.key()], entry.value());
247         testKeyValuePairs.erase(entry.key());
248     }
249     EXPECT_TRUE(testKeyValuePairs.empty());
250 }
251 
252 }  // namespace
253 }  // namespace latinime
254