Home | History | Annotate | Download | only in utils
      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