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 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 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 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 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 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 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