1de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi/* 2de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * Copyright (C) 2014 The Android Open Source Project 3de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * 4de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * Licensed under the Apache License, Version 2.0 (the "License"); 5de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * you may not use this file except in compliance with the License. 6de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * You may obtain a copy of the License at 7de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * 8de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * http://www.apache.org/licenses/LICENSE-2.0 9de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * 10de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * Unless required by applicable law or agreed to in writing, software 11de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * distributed under the License is distributed on an "AS IS" BASIS, 12de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * See the License for the specific language governing permissions and 14de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * limitations under the License. 15de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi */ 16de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 1788bc312ad34321fb3e81be2dc939a889d065f4a7Keisuke Kuroyanagi#include "dictionary/utils/trie_map.h" 18de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 19de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi#include <gtest/gtest.h> 20de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 21de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi#include <algorithm> 22de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi#include <cstdlib> 23de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi#include <functional> 24de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi#include <map> 25de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi#include <random> 26de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi#include <unordered_map> 27de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 28de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanaginamespace latinime { 29de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanaginamespace { 30de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 31de3121dead395d32760379c03938faef6eac2f98Keisuke KuroyanagiTEST(TrieMapTest, TestSetAndGet) { 32de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi TrieMap trieMap; 33de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi trieMap.putRoot(10, 10); 34de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi EXPECT_EQ(10ull, trieMap.getRoot(10).mValue); 35de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi trieMap.putRoot(0x10A, 10); 36de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi EXPECT_EQ(10ull, trieMap.getRoot(10).mValue); 37de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi EXPECT_EQ(10ull, trieMap.getRoot(0x10A).mValue); 38de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi trieMap.putRoot(10, 1000); 39de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi EXPECT_EQ(1000ull, trieMap.getRoot(10).mValue); 40de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi trieMap.putRoot(11, 1000); 41de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi EXPECT_EQ(1000ull, trieMap.getRoot(11).mValue); 42de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const int next = trieMap.getNextLevelBitmapEntryIndex(10); 439c9f2d06bcb80da64968c7a48907da241fa86f1fKeisuke Kuroyanagi EXPECT_EQ(1000ull, trieMap.getRoot(10).mValue); 44de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi trieMap.put(9, 9, next); 45de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi EXPECT_EQ(9ull, trieMap.get(9, next).mValue); 46de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi EXPECT_FALSE(trieMap.get(11, next).mIsValid); 47de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi trieMap.putRoot(0, 0xFFFFFFFFFull); 48de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi EXPECT_EQ(0xFFFFFFFFFull, trieMap.getRoot(0).mValue); 49de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi} 50de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 515fe1bed2e47bb44a6219f87888c40473eb30dec3Keisuke KuroyanagiTEST(TrieMapTest, TestRemove) { 525fe1bed2e47bb44a6219f87888c40473eb30dec3Keisuke Kuroyanagi TrieMap trieMap; 535fe1bed2e47bb44a6219f87888c40473eb30dec3Keisuke Kuroyanagi trieMap.putRoot(10, 10); 545fe1bed2e47bb44a6219f87888c40473eb30dec3Keisuke Kuroyanagi EXPECT_EQ(10ull, trieMap.getRoot(10).mValue); 555fe1bed2e47bb44a6219f87888c40473eb30dec3Keisuke Kuroyanagi EXPECT_TRUE(trieMap.remove(10, trieMap.getRootBitmapEntryIndex())); 565fe1bed2e47bb44a6219f87888c40473eb30dec3Keisuke Kuroyanagi EXPECT_FALSE(trieMap.getRoot(10).mIsValid); 575fe1bed2e47bb44a6219f87888c40473eb30dec3Keisuke Kuroyanagi for (const auto &element : trieMap.getEntriesInRootLevel()) { 585fe1bed2e47bb44a6219f87888c40473eb30dec3Keisuke Kuroyanagi EXPECT_TRUE(false); 595fe1bed2e47bb44a6219f87888c40473eb30dec3Keisuke Kuroyanagi } 605fe1bed2e47bb44a6219f87888c40473eb30dec3Keisuke Kuroyanagi EXPECT_TRUE(trieMap.putRoot(10, 0x3FFFFF)); 615fe1bed2e47bb44a6219f87888c40473eb30dec3Keisuke Kuroyanagi EXPECT_FALSE(trieMap.remove(11, trieMap.getRootBitmapEntryIndex())) 625fe1bed2e47bb44a6219f87888c40473eb30dec3Keisuke Kuroyanagi << "Should fail if the key does not exist."; 635fe1bed2e47bb44a6219f87888c40473eb30dec3Keisuke Kuroyanagi EXPECT_EQ(0x3FFFFFull, trieMap.getRoot(10).mValue); 645fe1bed2e47bb44a6219f87888c40473eb30dec3Keisuke Kuroyanagi trieMap.putRoot(12, 11); 655fe1bed2e47bb44a6219f87888c40473eb30dec3Keisuke Kuroyanagi const int nextLevel = trieMap.getNextLevelBitmapEntryIndex(10); 665fe1bed2e47bb44a6219f87888c40473eb30dec3Keisuke Kuroyanagi trieMap.put(10, 10, nextLevel); 675fe1bed2e47bb44a6219f87888c40473eb30dec3Keisuke Kuroyanagi EXPECT_EQ(0x3FFFFFull, trieMap.getRoot(10).mValue); 685fe1bed2e47bb44a6219f87888c40473eb30dec3Keisuke Kuroyanagi EXPECT_EQ(10ull, trieMap.get(10, nextLevel).mValue); 695fe1bed2e47bb44a6219f87888c40473eb30dec3Keisuke Kuroyanagi EXPECT_TRUE(trieMap.remove(10, trieMap.getRootBitmapEntryIndex())); 705fe1bed2e47bb44a6219f87888c40473eb30dec3Keisuke Kuroyanagi const TrieMap::Result result = trieMap.getRoot(10); 715fe1bed2e47bb44a6219f87888c40473eb30dec3Keisuke Kuroyanagi EXPECT_FALSE(result.mIsValid); 725fe1bed2e47bb44a6219f87888c40473eb30dec3Keisuke Kuroyanagi EXPECT_EQ(TrieMap::INVALID_INDEX, result.mNextLevelBitmapEntryIndex); 735fe1bed2e47bb44a6219f87888c40473eb30dec3Keisuke Kuroyanagi EXPECT_EQ(11ull, trieMap.getRoot(12).mValue); 74b4531d861ea740f1bf8e718f312150eb682e3f7bKeisuke Kuroyanagi EXPECT_TRUE(trieMap.putRoot(S_INT_MAX, 0xFFFFFFFFFull)); 75b4531d861ea740f1bf8e718f312150eb682e3f7bKeisuke Kuroyanagi EXPECT_TRUE(trieMap.remove(S_INT_MAX, trieMap.getRootBitmapEntryIndex())); 765fe1bed2e47bb44a6219f87888c40473eb30dec3Keisuke Kuroyanagi} 775fe1bed2e47bb44a6219f87888c40473eb30dec3Keisuke Kuroyanagi 78de3121dead395d32760379c03938faef6eac2f98Keisuke KuroyanagiTEST(TrieMapTest, TestSetAndGetLarge) { 79de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi static const int ELEMENT_COUNT = 200000; 80de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi TrieMap trieMap; 81de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi for (int i = 0; i < ELEMENT_COUNT; ++i) { 82de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi EXPECT_TRUE(trieMap.putRoot(i, i)); 83de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 84de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi for (int i = 0; i < ELEMENT_COUNT; ++i) { 855c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi EXPECT_EQ(static_cast<uint64_t>(i), trieMap.getRoot(i).mValue); 86de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 87de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi} 88de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 89de3121dead395d32760379c03938faef6eac2f98Keisuke KuroyanagiTEST(TrieMapTest, TestRandSetAndGetLarge) { 90de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi static const int ELEMENT_COUNT = 100000; 91de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi TrieMap trieMap; 92de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi std::unordered_map<int, uint64_t> testKeyValuePairs; 93de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 94de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi // Use the uniform integer distribution [S_INT_MIN, S_INT_MAX]. 95de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi std::uniform_int_distribution<int> keyDistribution(S_INT_MIN, S_INT_MAX); 96de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi auto keyRandomNumberGenerator = std::bind(keyDistribution, std::mt19937()); 97de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 98de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi // Use the uniform distribution [0, TrieMap::MAX_VALUE]. 99de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi std::uniform_int_distribution<uint64_t> valueDistribution(0, TrieMap::MAX_VALUE); 100de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi auto valueRandomNumberGenerator = std::bind(valueDistribution, std::mt19937()); 101de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 102de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi for (int i = 0; i < ELEMENT_COUNT; ++i) { 103de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const int key = keyRandomNumberGenerator(); 104de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const uint64_t value = valueRandomNumberGenerator(); 105de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi EXPECT_TRUE(trieMap.putRoot(key, value)) << key << " " << value; 106de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi testKeyValuePairs[key] = value; 107de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 108de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi for (const auto &v : testKeyValuePairs) { 1095c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi EXPECT_EQ(v.second, trieMap.getRoot(v.first).mValue); 110de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 111de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi} 112de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 113de3121dead395d32760379c03938faef6eac2f98Keisuke KuroyanagiTEST(TrieMapTest, TestMultiLevel) { 114de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi static const int FIRST_LEVEL_ENTRY_COUNT = 10000; 115de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi static const int SECOND_LEVEL_ENTRY_COUNT = 20000; 116de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi static const int THIRD_LEVEL_ENTRY_COUNT = 40000; 117de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 118de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi TrieMap trieMap; 119de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi std::vector<int> firstLevelKeys; 120de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi std::map<int, uint64_t> firstLevelEntries; 121de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi std::vector<std::pair<int, int>> secondLevelKeys; 122de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi std::map<int, std::map<int, uint64_t>> twoLevelMap; 123de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi std::map<int, std::map<int, std::map<int, uint64_t>>> threeLevelMap; 124de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 125de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi // Use the uniform integer distribution [0, S_INT_MAX]. 126de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi std::uniform_int_distribution<int> distribution(0, S_INT_MAX); 127de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi auto keyRandomNumberGenerator = std::bind(distribution, std::mt19937()); 128de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi auto randomNumberGeneratorForKeySelection = std::bind(distribution, std::mt19937()); 129de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 130de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi // Use the uniform distribution [0, TrieMap::MAX_VALUE]. 131de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi std::uniform_int_distribution<uint64_t> valueDistribution(0, TrieMap::MAX_VALUE); 132de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi auto valueRandomNumberGenerator = std::bind(valueDistribution, std::mt19937()); 133de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 134de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi for (int i = 0; i < FIRST_LEVEL_ENTRY_COUNT; ++i) { 135de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const int key = keyRandomNumberGenerator(); 136de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const uint64_t value = valueRandomNumberGenerator(); 137de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi EXPECT_TRUE(trieMap.putRoot(key, value)); 138de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi firstLevelKeys.push_back(key); 139de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi firstLevelEntries[key] = value; 140de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 141de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 142de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi for (int i = 0; i < SECOND_LEVEL_ENTRY_COUNT; ++i) { 143de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const int key = keyRandomNumberGenerator(); 144de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const uint64_t value = valueRandomNumberGenerator(); 145de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const int firstLevelKey = 146de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi firstLevelKeys[randomNumberGeneratorForKeySelection() % FIRST_LEVEL_ENTRY_COUNT]; 147de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const int nextLevelBitmapEntryIndex = trieMap.getNextLevelBitmapEntryIndex(firstLevelKey); 148de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi EXPECT_NE(TrieMap::INVALID_INDEX, nextLevelBitmapEntryIndex); 149de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi EXPECT_TRUE(trieMap.put(key, value, nextLevelBitmapEntryIndex)); 150de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi secondLevelKeys.push_back(std::make_pair(firstLevelKey, key)); 151de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi twoLevelMap[firstLevelKey][key] = value; 152de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 153de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 154de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi for (int i = 0; i < THIRD_LEVEL_ENTRY_COUNT; ++i) { 155de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const int key = keyRandomNumberGenerator(); 156de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const uint64_t value = valueRandomNumberGenerator(); 157de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const std::pair<int, int> secondLevelKey = 158de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi secondLevelKeys[randomNumberGeneratorForKeySelection() % SECOND_LEVEL_ENTRY_COUNT]; 159de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const int secondLevel = trieMap.getNextLevelBitmapEntryIndex(secondLevelKey.first); 160de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi EXPECT_NE(TrieMap::INVALID_INDEX, secondLevel); 161de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const int thirdLevel = trieMap.getNextLevelBitmapEntryIndex( 162de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi secondLevelKey.second, secondLevel); 163de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi EXPECT_NE(TrieMap::INVALID_INDEX, thirdLevel); 164de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi EXPECT_TRUE(trieMap.put(key, value, thirdLevel)); 165de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi threeLevelMap[secondLevelKey.first][secondLevelKey.second][key] = value; 166de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 167de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 168de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi for (const auto &firstLevelEntry : firstLevelEntries) { 169de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi EXPECT_EQ(firstLevelEntry.second, trieMap.getRoot(firstLevelEntry.first).mValue); 170de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 171de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 172de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi for (const auto &firstLevelEntry : twoLevelMap) { 173de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const int secondLevel = trieMap.getNextLevelBitmapEntryIndex(firstLevelEntry.first); 174de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi EXPECT_NE(TrieMap::INVALID_INDEX, secondLevel); 175de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi for (const auto &secondLevelEntry : firstLevelEntry.second) { 176de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi EXPECT_EQ(secondLevelEntry.second, 177de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi trieMap.get(secondLevelEntry.first, secondLevel).mValue); 178de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 179de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 180de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 181de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi for (const auto &firstLevelEntry : threeLevelMap) { 182de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const int secondLevel = trieMap.getNextLevelBitmapEntryIndex(firstLevelEntry.first); 183de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi EXPECT_NE(TrieMap::INVALID_INDEX, secondLevel); 184de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi for (const auto &secondLevelEntry : firstLevelEntry.second) { 185de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const int thirdLevel = 186de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi trieMap.getNextLevelBitmapEntryIndex(secondLevelEntry.first, secondLevel); 187de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi EXPECT_NE(TrieMap::INVALID_INDEX, thirdLevel); 188de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi for (const auto &thirdLevelEntry : secondLevelEntry.second) { 189de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi EXPECT_EQ(thirdLevelEntry.second, 190de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi trieMap.get(thirdLevelEntry.first, thirdLevel).mValue); 191de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 192de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 193de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 1945c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi 1955c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi // Iteration 1965c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi for (const auto &firstLevelEntry : trieMap.getEntriesInRootLevel()) { 1975c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi EXPECT_EQ(trieMap.getRoot(firstLevelEntry.key()).mValue, firstLevelEntry.value()); 1985c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi EXPECT_EQ(firstLevelEntries[firstLevelEntry.key()], firstLevelEntry.value()); 1995c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi firstLevelEntries.erase(firstLevelEntry.key()); 2005c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi for (const auto &secondLevelEntry : firstLevelEntry.getEntriesInNextLevel()) { 2015c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi EXPECT_EQ(twoLevelMap[firstLevelEntry.key()][secondLevelEntry.key()], 2025c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi secondLevelEntry.value()); 2035c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi twoLevelMap[firstLevelEntry.key()].erase(secondLevelEntry.key()); 2045c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi for (const auto &thirdLevelEntry : secondLevelEntry.getEntriesInNextLevel()) { 2055c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi EXPECT_EQ(threeLevelMap[firstLevelEntry.key()][secondLevelEntry.key()] 2065c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi [thirdLevelEntry.key()], thirdLevelEntry.value()); 2075c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi threeLevelMap[firstLevelEntry.key()][secondLevelEntry.key()].erase( 2085c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi thirdLevelEntry.key()); 2095c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi } 2105c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi } 2115c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi } 2125c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi 2135c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi // Ensure all entries have been traversed. 2145c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi EXPECT_TRUE(firstLevelEntries.empty()); 2155c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi for (const auto &secondLevelEntry : twoLevelMap) { 2165c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi EXPECT_TRUE(secondLevelEntry.second.empty()); 2175c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi } 2185c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi for (const auto &secondLevelEntry : threeLevelMap) { 2195c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi for (const auto &thirdLevelEntry : secondLevelEntry.second) { 2205c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi EXPECT_TRUE(thirdLevelEntry.second.empty()); 2215c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi } 2225c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi } 2235c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi} 2245c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi 2255c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke KuroyanagiTEST(TrieMapTest, TestIteration) { 2265c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi static const int ELEMENT_COUNT = 200000; 2275c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi TrieMap trieMap; 2285c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi std::unordered_map<int, uint64_t> testKeyValuePairs; 2295c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi 2305c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi // Use the uniform integer distribution [S_INT_MIN, S_INT_MAX]. 2315c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi std::uniform_int_distribution<int> keyDistribution(S_INT_MIN, S_INT_MAX); 2325c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi auto keyRandomNumberGenerator = std::bind(keyDistribution, std::mt19937()); 2335c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi 2345c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi // Use the uniform distribution [0, TrieMap::MAX_VALUE]. 2355c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi std::uniform_int_distribution<uint64_t> valueDistribution(0, TrieMap::MAX_VALUE); 2365c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi auto valueRandomNumberGenerator = std::bind(valueDistribution, std::mt19937()); 2375c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi for (int i = 0; i < ELEMENT_COUNT; ++i) { 2385c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi const int key = keyRandomNumberGenerator(); 2395c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi const uint64_t value = valueRandomNumberGenerator(); 2405c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi EXPECT_TRUE(trieMap.putRoot(key, value)); 2415c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi testKeyValuePairs[key] = value; 2425c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi } 2435c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi for (const auto &entry : trieMap.getEntriesInRootLevel()) { 2445c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi EXPECT_EQ(trieMap.getRoot(entry.key()).mValue, entry.value()); 2455c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi EXPECT_EQ(testKeyValuePairs[entry.key()], entry.value()); 2465c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi testKeyValuePairs.erase(entry.key()); 2475c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi } 2485c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi EXPECT_TRUE(testKeyValuePairs.empty()); 249de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi} 250de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 251de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi} // namespace 252de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi} // namespace latinime 253