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" 2688bc312ad34321fb3e81be2dc939a889d065f4a7Keisuke Kuroyanagi#include "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 879aa6699107de4da356b8eb89fb3ca38100e19c9dKeisuke Kuroyanagi AK_FORCE_INLINE int getNextLevelBitmapEntryIndex() const { 889aa6699107de4da356b8eb89fb3ca38100e19c9dKeisuke Kuroyanagi return mNextLevelBitmapEntryIndex; 899aa6699107de4da356b8eb89fb3ca38100e19c9dKeisuke Kuroyanagi } 909aa6699107de4da356b8eb89fb3ca38100e19c9dKeisuke Kuroyanagi 915c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi private: 925c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi const TrieMap *const mTrieMap; 935c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi const int mKey; 945c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi const uint64_t mValue; 955c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi const int mNextLevelBitmapEntryIndex; 965c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi }; 975c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi 985c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi TrieMapIterator(const TrieMap *const trieMap, const int bitmapEntryIndex) 995c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi : mTrieMap(trieMap), mStateStack(), mBaseBitmapEntryIndex(bitmapEntryIndex), 1005c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi mKey(0), mValue(0), mIsValid(false), mNextLevelBitmapEntryIndex(INVALID_INDEX) { 10107b3b41c25e000615396399e484a041df9301449Keisuke Kuroyanagi if (!trieMap || mBaseBitmapEntryIndex == INVALID_INDEX) { 1025c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi return; 1035c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi } 1045c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi const Entry bitmapEntry = mTrieMap->readEntry(mBaseBitmapEntryIndex); 1055c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi mStateStack.emplace_back( 1065c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi mTrieMap->popCount(bitmapEntry.getBitmap()), bitmapEntry.getTableIndex()); 1075c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi this->operator++(); 1085c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi } 1095c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi 1105c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi const IterationResult operator*() const { 1115c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi return IterationResult(mTrieMap, mKey, mValue, mNextLevelBitmapEntryIndex); 1125c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi } 1135c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi 1145c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi bool operator!=(const TrieMapIterator &other) const { 1155c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi // Caveat: This works only for for loops. 1165c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi return mIsValid || other.mIsValid; 1175c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi } 1185c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi 1195c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi const TrieMapIterator &operator++() { 1205c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi const Result result = mTrieMap->iterateNext(&mStateStack, &mKey); 1215c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi mValue = result.mValue; 1225c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi mIsValid = result.mIsValid; 1235c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi mNextLevelBitmapEntryIndex = result.mNextLevelBitmapEntryIndex; 1245c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi return *this; 1255c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi } 1265c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi 1275c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi private: 1285c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi DISALLOW_DEFAULT_CONSTRUCTOR(TrieMapIterator); 1295c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi DISALLOW_ASSIGNMENT_OPERATOR(TrieMapIterator); 1305c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi 1315c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi const TrieMap *const mTrieMap; 1325c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi std::vector<TrieMap::TableIterationState> mStateStack; 1335c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi const int mBaseBitmapEntryIndex; 1345c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi int mKey; 1355c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi uint64_t mValue; 1365c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi bool mIsValid; 1375c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi int mNextLevelBitmapEntryIndex; 1385c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi }; 1395c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi 1405c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi /** 1415c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi * Class to support iterating entries in TrieMap by range base for loops. 1425c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi */ 1435c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi class TrieMapRange { 1445c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi public: 1455c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi TrieMapRange(const TrieMap *const trieMap, const int bitmapEntryIndex) 1465c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi : mTrieMap(trieMap), mBaseBitmapEntryIndex(bitmapEntryIndex) {}; 1475c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi 1485c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi TrieMapIterator begin() const { 1495c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi return TrieMapIterator(mTrieMap, mBaseBitmapEntryIndex); 1505c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi } 1515c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi 1525c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi const TrieMapIterator end() const { 1535c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi return TrieMapIterator(nullptr, INVALID_INDEX); 1545c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi } 1555c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi 1565c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi private: 1575c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi DISALLOW_DEFAULT_CONSTRUCTOR(TrieMapRange); 1585c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi DISALLOW_ASSIGNMENT_OPERATOR(TrieMapRange); 1595c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi 1605c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi const TrieMap *const mTrieMap; 1615c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi const int mBaseBitmapEntryIndex; 1625c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi }; 1635c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi 164de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi static const int INVALID_INDEX; 165de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi static const uint64_t MAX_VALUE; 166de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 167de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi TrieMap(); 168de5c3a2562bbddc0f3d95619a1b3b1318b9598fdKeisuke Kuroyanagi // Construct TrieMap using existing data in the memory region written by save(). 169c0c674cdc0721a374e140ad5ee1409c0498b3262Keisuke Kuroyanagi TrieMap(const ReadWriteByteArrayView buffer); 170de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi void dump(const int from = 0, const int to = 0) const; 171de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 172de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi bool isNearSizeLimit() const { 173de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return mBuffer.isNearSizeLimit(); 174de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 175de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 17603dc44f543795040a092723085fac1209103b7bdKeisuke Kuroyanagi int getRootBitmapEntryIndex() const { 17703dc44f543795040a092723085fac1209103b7bdKeisuke Kuroyanagi return ROOT_BITMAP_ENTRY_INDEX; 17803dc44f543795040a092723085fac1209103b7bdKeisuke Kuroyanagi } 17903dc44f543795040a092723085fac1209103b7bdKeisuke Kuroyanagi 180de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi // Returns bitmapEntryIndex. Create the next level map if it doesn't exist. 181de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi int getNextLevelBitmapEntryIndex(const int key) { 182de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return getNextLevelBitmapEntryIndex(key, ROOT_BITMAP_ENTRY_INDEX); 183de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 184de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 185de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi int getNextLevelBitmapEntryIndex(const int key, const int bitmapEntryIndex); 186de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 187de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const Result getRoot(const int key) const { 188de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return get(key, ROOT_BITMAP_ENTRY_INDEX); 189de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 190de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 191de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const Result get(const int key, const int bitmapEntryIndex) const; 192de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 193de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi bool putRoot(const int key, const uint64_t value) { 194de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return put(key, value, ROOT_BITMAP_ENTRY_INDEX); 195de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 196de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 197de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi bool put(const int key, const uint64_t value, const int bitmapEntryIndex); 198de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 1995c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi const TrieMapRange getEntriesInRootLevel() const { 2005c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi return getEntriesInSpecifiedLevel(ROOT_BITMAP_ENTRY_INDEX); 2015c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi } 2025c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi 2035c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi const TrieMapRange getEntriesInSpecifiedLevel(const int bitmapEntryIndex) const { 2045c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi return TrieMapRange(this, bitmapEntryIndex); 2055c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi } 2065c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi 20760ae3e0be5374478183362005f7c48809924ef01Keisuke Kuroyanagi bool save(FILE *const file) const; 20860ae3e0be5374478183362005f7c48809924ef01Keisuke Kuroyanagi 2095fe1bed2e47bb44a6219f87888c40473eb30dec3Keisuke Kuroyanagi bool remove(const int key, const int bitmapEntryIndex); 2105fe1bed2e47bb44a6219f87888c40473eb30dec3Keisuke Kuroyanagi 211de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi private: 212de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi DISALLOW_COPY_AND_ASSIGN(TrieMap); 213de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 214de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi /** 215de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * Struct represents an entry. 216de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * 217de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * Entry is one of these entry types. All entries are fixed size and have 2 fields FIELD_0 and 218de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * FIELD_1. 219de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * 1. bitmap entry. bitmap entry contains bitmap and the link to hash table. 220de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * FIELD_0(bitmap) FIELD_1(LINK_TO_HASH_TABLE) 221de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * 2. terminal entry. terminal entry contains hashed key and value or terminal link. terminal 222de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * entry have terminal link when the value is not fit to FIELD_1 or there is a next level map 223de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * for the key. 224de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * FIELD_0(hashed key) (FIELD_1(VALUE_FLAG VALUE) | FIELD_1(TERMINAL_LINK_FLAG TERMINAL_LINK)) 225de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * 3. value entry. value entry represents a value. Upper order bytes are stored in FIELD_0 and 226de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * lower order bytes are stored in FIELD_1. 227de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi * FIELD_0(value (upper order bytes)) FIELD_1(value (lower order bytes)) 228de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi */ 229de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi struct Entry { 230de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const uint32_t mData0; 231de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const uint32_t mData1; 232de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 233de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi Entry(const uint32_t data0, const uint32_t data1) : mData0(data0), mData1(data1) {} 234de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 235de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE bool isBitmapEntry() const { 236de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return (mData1 & VALUE_FLAG) == 0 && (mData1 & TERMINAL_LINK_FLAG) == 0; 237de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 238de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 239de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE bool hasTerminalLink() const { 240de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return (mData1 & TERMINAL_LINK_FLAG) != 0; 241de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 242de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 243de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi // For terminal entry. 244de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE uint32_t getKey() const { 245de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return mData0; 246de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 247de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 248de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi // For terminal entry. 249de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE uint32_t getValue() const { 250de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return mData1 & VALUE_MASK; 251de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 252de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 253de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi // For terminal entry. 2545fe1bed2e47bb44a6219f87888c40473eb30dec3Keisuke Kuroyanagi AK_FORCE_INLINE bool isValidTerminalEntry() const { 2555fe1bed2e47bb44a6219f87888c40473eb30dec3Keisuke Kuroyanagi return hasTerminalLink() || ((mData1 & VALUE_MASK) != INVALID_VALUE_IN_KEY_VALUE_ENTRY); 2565fe1bed2e47bb44a6219f87888c40473eb30dec3Keisuke Kuroyanagi } 2575fe1bed2e47bb44a6219f87888c40473eb30dec3Keisuke Kuroyanagi 2585fe1bed2e47bb44a6219f87888c40473eb30dec3Keisuke Kuroyanagi // For terminal entry. 259de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE uint32_t getValueEntryIndex() const { 260de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return mData1 & TERMINAL_LINK_MASK; 261de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 262de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 263de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi // For bitmap entry. 264de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE uint32_t getBitmap() const { 265de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return mData0; 266de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 267de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 268de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi // For bitmap entry. 269de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE int getTableIndex() const { 270de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return static_cast<int>(mData1); 271de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 272de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 273de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi // For value entry. 274de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE uint64_t getValueOfValueEntry() const { 275de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return ((static_cast<uint64_t>(mData0) << (FIELD1_SIZE * CHAR_BIT)) ^ mData1); 276de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 277de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi }; 278de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 279de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi BufferWithExtendableBuffer mBuffer; 280de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 281de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi static const int FIELD0_SIZE; 282de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi static const int FIELD1_SIZE; 283de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi static const int ENTRY_SIZE; 284de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi static const uint32_t VALUE_FLAG; 285de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi static const uint32_t VALUE_MASK; 2865fe1bed2e47bb44a6219f87888c40473eb30dec3Keisuke Kuroyanagi static const uint32_t INVALID_VALUE_IN_KEY_VALUE_ENTRY; 287de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi static const uint32_t TERMINAL_LINK_FLAG; 288de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi static const uint32_t TERMINAL_LINK_MASK; 289de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi static const int NUM_OF_BITS_USED_FOR_ONE_LEVEL; 290de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi static const uint32_t LABEL_MASK; 291de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi static const int MAX_NUM_OF_ENTRIES_IN_ONE_LEVEL; 292de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi static const int ROOT_BITMAP_ENTRY_INDEX; 293de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi static const int ROOT_BITMAP_ENTRY_POS; 294de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi static const Entry EMPTY_BITMAP_ENTRY; 2955fe1bed2e47bb44a6219f87888c40473eb30dec3Keisuke Kuroyanagi static const int TERMINAL_LINKED_ENTRY_COUNT; 296de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi static const int MAX_BUFFER_SIZE; 297de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 298de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi uint32_t getBitShuffledKey(const uint32_t key) const; 299de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi bool writeValue(const uint64_t value, const int terminalEntryIndex); 300de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi bool updateValue(const Entry &terminalEntry, const uint64_t value, 301de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const int terminalEntryIndex); 302de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi bool freeTable(const int tableIndex, const int entryCount); 303de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi int allocateTable(const int entryCount); 304de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi int getTerminalEntryIndex(const uint32_t key, const uint32_t hashedKey, 305de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const Entry &bitmapEntry, const int level) const; 306de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const Result getInternal(const uint32_t key, const uint32_t hashedKey, 307de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const int bitmapEntryIndex, const int level) const; 308de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi bool putInternal(const uint32_t key, const uint64_t value, const uint32_t hashedKey, 309de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const int bitmapEntryIndex, const Entry &bitmapEntry, const int level); 310de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi bool addNewEntryByResolvingConflict(const uint32_t key, const uint64_t value, 311de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const uint32_t hashedKey, const Entry &conflictedEntry, const int conflictedEntryIndex, 312de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const int level); 313de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi bool addNewEntryByExpandingTable(const uint32_t key, const uint64_t value, 314de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const int tableIndex, const uint32_t bitmap, const int bitmapEntryIndex, 315de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const int label); 3165c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi const Result iterateNext(std::vector<TableIterationState> *const iterationState, 3175c1decfbb91dbc3fd1b9b0a2058fcc38d99f48b5Keisuke Kuroyanagi int *const outKey) const; 318de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 319de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE const Entry readEntry(const int entryIndex) const { 320de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return Entry(readField0(entryIndex), readField1(entryIndex)); 321de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 322de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 323de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi // Returns whether an entry for the index is existing by testing if the index-th bit in the 324de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi // bitmap is set or not. 325de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE bool exists(const uint32_t bitmap, const int index) const { 326de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return (bitmap & (1 << index)) != 0; 327de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 328de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 329de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi // Set index-th bit in the bitmap. 330de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE uint32_t setExist(const uint32_t bitmap, const int index) const { 331de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return bitmap | (1 << index); 332de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 333de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 334de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi // Count set bits before index in the bitmap. 335de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE int popCount(const uint32_t bitmap, const int index) const { 336de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return popCount(bitmap & ((1 << index) - 1)); 337de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 338de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 339de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi // Count set bits in the bitmap. 340de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE int popCount(const uint32_t bitmap) const { 341de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return __builtin_popcount(bitmap); 342de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi // int v = bitmap - ((bitmap >> 1) & 0x55555555); 343de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi // v = (v & 0x33333333) + ((v >> 2) & 0x33333333); 344de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi // return (((v + (v >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24; 345de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 346de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 347de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE int getLabel(const uint32_t hashedKey, const int level) const { 348de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return (hashedKey >> (level * NUM_OF_BITS_USED_FOR_ONE_LEVEL)) & LABEL_MASK; 349de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 350de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 351de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE uint32_t readField0(const int entryIndex) const { 352de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return mBuffer.readUint(FIELD0_SIZE, ROOT_BITMAP_ENTRY_POS + entryIndex * ENTRY_SIZE); 353de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 354de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 355de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE uint32_t readField1(const int entryIndex) const { 356de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return mBuffer.readUint(FIELD1_SIZE, 357de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi ROOT_BITMAP_ENTRY_POS + entryIndex * ENTRY_SIZE + FIELD0_SIZE); 358de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 359de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 360de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE int readEmptyTableLink(const int entryCount) const { 361de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return mBuffer.readUint(FIELD1_SIZE, (entryCount - 1) * FIELD1_SIZE); 362de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 363de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 364de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE bool writeEmptyTableLink(const int tableIndex, const int entryCount) { 365de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return mBuffer.writeUint(tableIndex, FIELD1_SIZE, (entryCount - 1) * FIELD1_SIZE); 366de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 367de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 368de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE bool writeField0(const uint32_t data, const int entryIndex) { 369de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return mBuffer.writeUint(data, FIELD0_SIZE, 370de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi ROOT_BITMAP_ENTRY_POS + entryIndex * ENTRY_SIZE); 371de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 372de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 373de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE bool writeField1(const uint32_t data, const int entryIndex) { 374de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return mBuffer.writeUint(data, FIELD1_SIZE, 375de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi ROOT_BITMAP_ENTRY_POS + entryIndex * ENTRY_SIZE + FIELD0_SIZE); 376de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 377de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 378de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE bool writeEntry(const Entry &entry, const int entryIndex) { 379de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return writeField0(entry.mData0, entryIndex) && writeField1(entry.mData1, entryIndex); 380de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 381de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 382de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE bool writeTerminalEntry(const uint32_t key, const uint64_t value, 383de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi const int entryIndex) { 384de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return writeField0(key, entryIndex) && writeValue(value, entryIndex); 385de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 386de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 387de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE bool copyEntry(const int originalEntryIndex, const int newEntryIndex) { 388de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return writeEntry(readEntry(originalEntryIndex), newEntryIndex); 389de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 390de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 391de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi AK_FORCE_INLINE int getTailEntryIndex() const { 392de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi return (mBuffer.getTailPosition() - ROOT_BITMAP_ENTRY_POS) / ENTRY_SIZE; 393de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi } 3945fe1bed2e47bb44a6219f87888c40473eb30dec3Keisuke Kuroyanagi 3955fe1bed2e47bb44a6219f87888c40473eb30dec3Keisuke Kuroyanagi bool removeInner(const Entry &bitmapEntry); 396de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi}; 397de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi 398de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi} // namespace latinime 399de3121dead395d32760379c03938faef6eac2f98Keisuke Kuroyanagi#endif /* LATINIME_TRIE_MAP_H */ 400