trie_map.h revision c0c674cdc0721a374e140ad5ee1409c0498b3262
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 17de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi#ifndef LATINIME_TRIE_MAP_H 18de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi#define LATINIME_TRIE_MAP_H 19de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 20de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi#include <climits> 21de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi#include <cstdint> 2260ae3e0be5374478183362005f7c48809924ef01Keisuke Kuroyanagi#include <cstdio> 23de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi#include <vector> 24de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 25de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi#include "defines.h" 26de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi#include "suggest/policyimpl/dictionary/utils/buffer_with_extendable_buffer.h" 27c0c674cdc0721a374e140ad5ee1409c0498b3262Keisuke Kuroyanagi#include "utils/byte_array_view.h" 28de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 29de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanaginamespace latinime { 30de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 31de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi/** 32de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * Trie map derived from Phil Bagwell's Hash Array Mapped Trie. 33de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * key is int and value is uint64_t. 34de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * This supports multiple level map. Terminal entries can have a bitmap for the next level map. 35de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * This doesn't support root map resizing. 36de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi */ 37de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagiclass TrieMap { 38de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi public: 39de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi struct Result { 40de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const uint64_t mValue; 41de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const bool mIsValid; 42de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const int mNextLevelBitmapEntryIndex; 43de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 44de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi Result(const uint64_t value, const bool isValid, const int nextLevelBitmapEntryIndex) 45de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi : mValue(value), mIsValid(isValid), 46de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi mNextLevelBitmapEntryIndex(nextLevelBitmapEntryIndex) {} 47de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi }; 48de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 495c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi /** 505c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi * Struct to record iteration state in a table. 515c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi */ 525c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi struct TableIterationState { 535c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi int mTableSize; 545c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi int mTableIndex; 555c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi int mCurrentIndex; 565c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi 575c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi TableIterationState(const int tableSize, const int tableIndex) 585c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi : mTableSize(tableSize), mTableIndex(tableIndex), mCurrentIndex(0) {} 595c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi }; 605c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi 615c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi class TrieMapRange; 625c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi class TrieMapIterator { 635c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi public: 645c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi class IterationResult { 655c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi public: 665c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi IterationResult(const TrieMap *const trieMap, const int key, const uint64_t value, 675c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi const int nextLeveBitmapEntryIndex) 685c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi : mTrieMap(trieMap), mKey(key), mValue(value), 695c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi mNextLevelBitmapEntryIndex(nextLeveBitmapEntryIndex) {} 705c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi 715c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi const TrieMapRange getEntriesInNextLevel() const { 725c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi return TrieMapRange(mTrieMap, mNextLevelBitmapEntryIndex); 735c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi } 745c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi 755c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi bool hasNextLevelMap() const { 765c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi return mNextLevelBitmapEntryIndex != INVALID_INDEX; 775c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi } 785c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi 795c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi AK_FORCE_INLINE int key() const { 805c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi return mKey; 815c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi } 825c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi 835c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi AK_FORCE_INLINE uint64_t value() const { 845c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi return mValue; 855c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi } 865c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi 875c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi private: 885c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi const TrieMap *const mTrieMap; 895c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi const int mKey; 905c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi const uint64_t mValue; 915c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi const int mNextLevelBitmapEntryIndex; 925c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi }; 935c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi 945c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi TrieMapIterator(const TrieMap *const trieMap, const int bitmapEntryIndex) 955c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi : mTrieMap(trieMap), mStateStack(), mBaseBitmapEntryIndex(bitmapEntryIndex), 965c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi mKey(0), mValue(0), mIsValid(false), mNextLevelBitmapEntryIndex(INVALID_INDEX) { 975c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi if (!trieMap) { 985c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi return; 995c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi } 1005c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi const Entry bitmapEntry = mTrieMap->readEntry(mBaseBitmapEntryIndex); 1015c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi mStateStack.emplace_back( 1025c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi mTrieMap->popCount(bitmapEntry.getBitmap()), bitmapEntry.getTableIndex()); 1035c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi this->operator++(); 1045c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi } 1055c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi 1065c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi const IterationResult operator*() const { 1075c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi return IterationResult(mTrieMap, mKey, mValue, mNextLevelBitmapEntryIndex); 1085c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi } 1095c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi 1105c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi bool operator!=(const TrieMapIterator &other) const { 1115c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi // Caveat: This works only for for loops. 1125c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi return mIsValid || other.mIsValid; 1135c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi } 1145c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi 1155c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi const TrieMapIterator &operator++() { 1165c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi const Result result = mTrieMap->iterateNext(&mStateStack, &mKey); 1175c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi mValue = result.mValue; 1185c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi mIsValid = result.mIsValid; 1195c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi mNextLevelBitmapEntryIndex = result.mNextLevelBitmapEntryIndex; 1205c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi return *this; 1215c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi } 1225c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi 1235c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi private: 1245c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi DISALLOW_DEFAULT_CONSTRUCTOR(TrieMapIterator); 1255c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi DISALLOW_ASSIGNMENT_OPERATOR(TrieMapIterator); 1265c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi 1275c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi const TrieMap *const mTrieMap; 1285c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi std::vector<TrieMap::TableIterationState> mStateStack; 1295c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi const int mBaseBitmapEntryIndex; 1305c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi int mKey; 1315c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi uint64_t mValue; 1325c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi bool mIsValid; 1335c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi int mNextLevelBitmapEntryIndex; 1345c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi }; 1355c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi 1365c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi /** 1375c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi * Class to support iterating entries in TrieMap by range base for loops. 1385c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi */ 1395c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi class TrieMapRange { 1405c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi public: 1415c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi TrieMapRange(const TrieMap *const trieMap, const int bitmapEntryIndex) 1425c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi : mTrieMap(trieMap), mBaseBitmapEntryIndex(bitmapEntryIndex) {}; 1435c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi 1445c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi TrieMapIterator begin() const { 1455c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi return TrieMapIterator(mTrieMap, mBaseBitmapEntryIndex); 1465c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi } 1475c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi 1485c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi const TrieMapIterator end() const { 1495c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi return TrieMapIterator(nullptr, INVALID_INDEX); 1505c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi } 1515c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi 1525c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi private: 1535c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi DISALLOW_DEFAULT_CONSTRUCTOR(TrieMapRange); 1545c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi DISALLOW_ASSIGNMENT_OPERATOR(TrieMapRange); 1555c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi 1565c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi const TrieMap *const mTrieMap; 1575c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi const int mBaseBitmapEntryIndex; 1585c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi }; 1595c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi 160de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi static const int INVALID_INDEX; 161de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi static const uint64_t MAX_VALUE; 162de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 163de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi TrieMap(); 164de5c3a2562bbddc0f3d95619a1b3b1318b9598fdKeisuke Kuroyanagi // Construct TrieMap using existing data in the memory region written by save(). 165c0c674cdc0721a374e140ad5ee1409c0498b3262Keisuke Kuroyanagi TrieMap(const ReadWriteByteArrayView buffer); 166de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi void dump(const int from = 0, const int to = 0) const; 167de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 168de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi bool isNearSizeLimit() const { 169de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return mBuffer.isNearSizeLimit(); 170de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 171de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 172de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi // Returns bitmapEntryIndex. Create the next level map if it doesn't exist. 173de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi int getNextLevelBitmapEntryIndex(const int key) { 174de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return getNextLevelBitmapEntryIndex(key, ROOT_BITMAP_ENTRY_INDEX); 175de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 176de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 177de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi int getNextLevelBitmapEntryIndex(const int key, const int bitmapEntryIndex); 178de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 179de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const Result getRoot(const int key) const { 180de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return get(key, ROOT_BITMAP_ENTRY_INDEX); 181de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 182de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 183de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const Result get(const int key, const int bitmapEntryIndex) const; 184de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 185de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi bool putRoot(const int key, const uint64_t value) { 186de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return put(key, value, ROOT_BITMAP_ENTRY_INDEX); 187de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 188de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 189de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi bool put(const int key, const uint64_t value, const int bitmapEntryIndex); 190de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 1915c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi const TrieMapRange getEntriesInRootLevel() const { 1925c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi return getEntriesInSpecifiedLevel(ROOT_BITMAP_ENTRY_INDEX); 1935c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi } 1945c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi 1955c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi const TrieMapRange getEntriesInSpecifiedLevel(const int bitmapEntryIndex) const { 1965c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi return TrieMapRange(this, bitmapEntryIndex); 1975c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi } 1985c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi 19960ae3e0be5374478183362005f7c48809924ef01Keisuke Kuroyanagi bool save(FILE *const file) const; 20060ae3e0be5374478183362005f7c48809924ef01Keisuke Kuroyanagi 201de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi private: 202de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi DISALLOW_COPY_AND_ASSIGN(TrieMap); 203de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 204de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi /** 205de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * Struct represents an entry. 206de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * 207de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * Entry is one of these entry types. All entries are fixed size and have 2 fields FIELD_0 and 208de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * FIELD_1. 209de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * 1. bitmap entry. bitmap entry contains bitmap and the link to hash table. 210de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * FIELD_0(bitmap) FIELD_1(LINK_TO_HASH_TABLE) 211de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * 2. terminal entry. terminal entry contains hashed key and value or terminal link. terminal 212de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * entry have terminal link when the value is not fit to FIELD_1 or there is a next level map 213de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * for the key. 214de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * FIELD_0(hashed key) (FIELD_1(VALUE_FLAG VALUE) | FIELD_1(TERMINAL_LINK_FLAG TERMINAL_LINK)) 215de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * 3. value entry. value entry represents a value. Upper order bytes are stored in FIELD_0 and 216de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * lower order bytes are stored in FIELD_1. 217de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * FIELD_0(value (upper order bytes)) FIELD_1(value (lower order bytes)) 218de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi */ 219de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi struct Entry { 220de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const uint32_t mData0; 221de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const uint32_t mData1; 222de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 223de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi Entry(const uint32_t data0, const uint32_t data1) : mData0(data0), mData1(data1) {} 224de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 225de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE bool isBitmapEntry() const { 226de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return (mData1 & VALUE_FLAG) == 0 && (mData1 & TERMINAL_LINK_FLAG) == 0; 227de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 228de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 229de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE bool hasTerminalLink() const { 230de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return (mData1 & TERMINAL_LINK_FLAG) != 0; 231de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 232de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 233de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi // For terminal entry. 234de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE uint32_t getKey() const { 235de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return mData0; 236de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 237de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 238de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi // For terminal entry. 239de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE uint32_t getValue() const { 240de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return mData1 & VALUE_MASK; 241de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 242de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 243de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi // For terminal entry. 244de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE uint32_t getValueEntryIndex() const { 245de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return mData1 & TERMINAL_LINK_MASK; 246de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 247de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 248de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi // For bitmap entry. 249de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE uint32_t getBitmap() const { 250de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return mData0; 251de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 252de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 253de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi // For bitmap entry. 254de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE int getTableIndex() const { 255de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return static_cast<int>(mData1); 256de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 257de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 258de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi // For value entry. 259de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE uint64_t getValueOfValueEntry() const { 260de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return ((static_cast<uint64_t>(mData0) << (FIELD1_SIZE * CHAR_BIT)) ^ mData1); 261de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 262de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi }; 263de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 264de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi BufferWithExtendableBuffer mBuffer; 265de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 266de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi static const int FIELD0_SIZE; 267de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi static const int FIELD1_SIZE; 268de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi static const int ENTRY_SIZE; 269de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi static const uint32_t VALUE_FLAG; 270de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi static const uint32_t VALUE_MASK; 271de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi static const uint32_t TERMINAL_LINK_FLAG; 272de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi static const uint32_t TERMINAL_LINK_MASK; 273de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi static const int NUM_OF_BITS_USED_FOR_ONE_LEVEL; 274de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi static const uint32_t LABEL_MASK; 275de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi static const int MAX_NUM_OF_ENTRIES_IN_ONE_LEVEL; 276de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi static const int ROOT_BITMAP_ENTRY_INDEX; 277de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi static const int ROOT_BITMAP_ENTRY_POS; 278de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi static const Entry EMPTY_BITMAP_ENTRY; 279de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi static const int MAX_BUFFER_SIZE; 280de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 281de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi uint32_t getBitShuffledKey(const uint32_t key) const; 282de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi bool writeValue(const uint64_t value, const int terminalEntryIndex); 283de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi bool updateValue(const Entry &terminalEntry, const uint64_t value, 284de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const int terminalEntryIndex); 285de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi bool freeTable(const int tableIndex, const int entryCount); 286de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi int allocateTable(const int entryCount); 287de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi int getTerminalEntryIndex(const uint32_t key, const uint32_t hashedKey, 288de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const Entry &bitmapEntry, const int level) const; 289de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const Result getInternal(const uint32_t key, const uint32_t hashedKey, 290de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const int bitmapEntryIndex, const int level) const; 291de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi bool putInternal(const uint32_t key, const uint64_t value, const uint32_t hashedKey, 292de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const int bitmapEntryIndex, const Entry &bitmapEntry, const int level); 293de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi bool addNewEntryByResolvingConflict(const uint32_t key, const uint64_t value, 294de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const uint32_t hashedKey, const Entry &conflictedEntry, const int conflictedEntryIndex, 295de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const int level); 296de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi bool addNewEntryByExpandingTable(const uint32_t key, const uint64_t value, 297de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const int tableIndex, const uint32_t bitmap, const int bitmapEntryIndex, 298de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const int label); 2995c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi const Result iterateNext(std::vector<TableIterationState> *const iterationState, 3005c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi int *const outKey) const; 301de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 302de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE const Entry readEntry(const int entryIndex) const { 303de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return Entry(readField0(entryIndex), readField1(entryIndex)); 304de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 305de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 306de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi // Returns whether an entry for the index is existing by testing if the index-th bit in the 307de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi // bitmap is set or not. 308de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE bool exists(const uint32_t bitmap, const int index) const { 309de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return (bitmap & (1 << index)) != 0; 310de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 311de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 312de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi // Set index-th bit in the bitmap. 313de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE uint32_t setExist(const uint32_t bitmap, const int index) const { 314de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return bitmap | (1 << index); 315de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 316de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 317de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi // Count set bits before index in the bitmap. 318de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE int popCount(const uint32_t bitmap, const int index) const { 319de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return popCount(bitmap & ((1 << index) - 1)); 320de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 321de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 322de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi // Count set bits in the bitmap. 323de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE int popCount(const uint32_t bitmap) const { 324de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return __builtin_popcount(bitmap); 325de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi // int v = bitmap - ((bitmap >> 1) & 0x55555555); 326de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi // v = (v & 0x33333333) + ((v >> 2) & 0x33333333); 327de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi // return (((v + (v >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24; 328de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 329de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 330de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE int getLabel(const uint32_t hashedKey, const int level) const { 331de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return (hashedKey >> (level * NUM_OF_BITS_USED_FOR_ONE_LEVEL)) & LABEL_MASK; 332de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 333de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 334de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE uint32_t readField0(const int entryIndex) const { 335de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return mBuffer.readUint(FIELD0_SIZE, ROOT_BITMAP_ENTRY_POS + entryIndex * ENTRY_SIZE); 336de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 337de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 338de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE uint32_t readField1(const int entryIndex) const { 339de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return mBuffer.readUint(FIELD1_SIZE, 340de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi ROOT_BITMAP_ENTRY_POS + entryIndex * ENTRY_SIZE + FIELD0_SIZE); 341de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 342de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 343de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE int readEmptyTableLink(const int entryCount) const { 344de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return mBuffer.readUint(FIELD1_SIZE, (entryCount - 1) * FIELD1_SIZE); 345de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 346de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 347de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE bool writeEmptyTableLink(const int tableIndex, const int entryCount) { 348de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return mBuffer.writeUint(tableIndex, FIELD1_SIZE, (entryCount - 1) * FIELD1_SIZE); 349de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 350de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 351de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE bool writeField0(const uint32_t data, const int entryIndex) { 352de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return mBuffer.writeUint(data, FIELD0_SIZE, 353de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi ROOT_BITMAP_ENTRY_POS + entryIndex * ENTRY_SIZE); 354de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 355de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 356de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE bool writeField1(const uint32_t data, const int entryIndex) { 357de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return mBuffer.writeUint(data, FIELD1_SIZE, 358de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi ROOT_BITMAP_ENTRY_POS + entryIndex * ENTRY_SIZE + FIELD0_SIZE); 359de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 360de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 361de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE bool writeEntry(const Entry &entry, const int entryIndex) { 362de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return writeField0(entry.mData0, entryIndex) && writeField1(entry.mData1, entryIndex); 363de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 364de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 365de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE bool writeTerminalEntry(const uint32_t key, const uint64_t value, 366de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const int entryIndex) { 367de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return writeField0(key, entryIndex) && writeValue(value, entryIndex); 368de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 369de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 370de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE bool copyEntry(const int originalEntryIndex, const int newEntryIndex) { 371de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return writeEntry(readEntry(originalEntryIndex), newEntryIndex); 372de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 373de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 374de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE int getTailEntryIndex() const { 375de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return (mBuffer.getTailPosition() - ROOT_BITMAP_ENTRY_POS) / ENTRY_SIZE; 376de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 377de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi}; 378de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 379de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi} // namespace latinime 380de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi#endif /* LATINIME_TRIE_MAP_H */ 381