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