trie_map.cpp revision 60ae3e0be5374478183362005f7c48809924ef01
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 "suggest/policyimpl/dictionary/utils/trie_map.h" 18 19#include "suggest/policyimpl/dictionary/utils/dict_file_writing_utils.h" 20 21namespace latinime { 22 23const int TrieMap::INVALID_INDEX = -1; 24const int TrieMap::FIELD0_SIZE = 4; 25const int TrieMap::FIELD1_SIZE = 3; 26const int TrieMap::ENTRY_SIZE = FIELD0_SIZE + FIELD1_SIZE; 27const uint32_t TrieMap::VALUE_FLAG = 0x400000; 28const uint32_t TrieMap::VALUE_MASK = 0x3FFFFF; 29const uint32_t TrieMap::TERMINAL_LINK_FLAG = 0x800000; 30const uint32_t TrieMap::TERMINAL_LINK_MASK = 0x7FFFFF; 31const int TrieMap::NUM_OF_BITS_USED_FOR_ONE_LEVEL = 5; 32const uint32_t TrieMap::LABEL_MASK = 0x1F; 33const int TrieMap::MAX_NUM_OF_ENTRIES_IN_ONE_LEVEL = 1 << NUM_OF_BITS_USED_FOR_ONE_LEVEL; 34const int TrieMap::ROOT_BITMAP_ENTRY_INDEX = 0; 35const int TrieMap::ROOT_BITMAP_ENTRY_POS = MAX_NUM_OF_ENTRIES_IN_ONE_LEVEL * FIELD0_SIZE; 36const TrieMap::Entry TrieMap::EMPTY_BITMAP_ENTRY = TrieMap::Entry(0, 0); 37const uint64_t TrieMap::MAX_VALUE = 38 (static_cast<uint64_t>(1) << ((FIELD0_SIZE + FIELD1_SIZE) * CHAR_BIT)) - 1; 39const int TrieMap::MAX_BUFFER_SIZE = TERMINAL_LINK_MASK * ENTRY_SIZE; 40 41TrieMap::TrieMap() : mBuffer(MAX_BUFFER_SIZE) { 42 mBuffer.extend(ROOT_BITMAP_ENTRY_POS); 43 writeEntry(EMPTY_BITMAP_ENTRY, ROOT_BITMAP_ENTRY_INDEX); 44} 45 46void TrieMap::dump(const int from, const int to) const { 47 AKLOGI("BufSize: %d", mBuffer.getTailPosition()); 48 for (int i = from; i < to; ++i) { 49 AKLOGI("Entry[%d]: %x, %x", i, readField0(i), readField1(i)); 50 } 51 int unusedRegionSize = 0; 52 for (int i = 1; i <= MAX_NUM_OF_ENTRIES_IN_ONE_LEVEL; ++i) { 53 int index = readEmptyTableLink(i); 54 while (index != ROOT_BITMAP_ENTRY_INDEX) { 55 index = readField0(index); 56 unusedRegionSize += i; 57 } 58 } 59 AKLOGI("Unused Size: %d", unusedRegionSize); 60} 61 62int TrieMap::getNextLevelBitmapEntryIndex(const int key, const int bitmapEntryIndex) { 63 const Entry bitmapEntry = readEntry(bitmapEntryIndex); 64 const uint32_t unsignedKey = static_cast<uint32_t>(key); 65 const int terminalEntryIndex = getTerminalEntryIndex( 66 unsignedKey, getBitShuffledKey(unsignedKey), bitmapEntry, 0 /* level */); 67 if (terminalEntryIndex == INVALID_INDEX) { 68 // Not found. 69 return INVALID_INDEX; 70 } 71 const Entry terminalEntry = readEntry(terminalEntryIndex); 72 if (terminalEntry.hasTerminalLink()) { 73 return terminalEntry.getValueEntryIndex() + 1; 74 } 75 // Create a value entry and a bitmap entry. 76 const int valueEntryIndex = allocateTable(2 /* entryCount */); 77 if (!writeEntry(Entry(0, terminalEntry.getValue()), valueEntryIndex)) { 78 return INVALID_INDEX; 79 } 80 if (!writeEntry(EMPTY_BITMAP_ENTRY, valueEntryIndex + 1)) { 81 return INVALID_INDEX; 82 } 83 if (!writeField1(valueEntryIndex | TERMINAL_LINK_FLAG, valueEntryIndex)) { 84 return INVALID_INDEX; 85 } 86 return valueEntryIndex + 1; 87} 88 89const TrieMap::Result TrieMap::get(const int key, const int bitmapEntryIndex) const { 90 const uint32_t unsignedKey = static_cast<uint32_t>(key); 91 return getInternal(unsignedKey, getBitShuffledKey(unsignedKey), bitmapEntryIndex, 92 0 /* level */); 93} 94 95bool TrieMap::put(const int key, const uint64_t value, const int bitmapEntryIndex) { 96 if (value > MAX_VALUE) { 97 return false; 98 } 99 const uint32_t unsignedKey = static_cast<uint32_t>(key); 100 return putInternal(unsignedKey, value, getBitShuffledKey(unsignedKey), bitmapEntryIndex, 101 readEntry(bitmapEntryIndex), 0 /* level */); 102} 103 104bool TrieMap::save(FILE *const file) const { 105 return DictFileWritingUtils::writeBufferToFileTail(file, &mBuffer); 106} 107 108/** 109 * Iterate next entry in a certain level. 110 * 111 * @param iterationState the iteration state that will be read and updated in this method. 112 * @param outKey the output key 113 * @return Result instance. mIsValid is false when all entries are iterated. 114 */ 115const TrieMap::Result TrieMap::iterateNext(std::vector<TableIterationState> *const iterationState, 116 int *const outKey) const { 117 while (!iterationState->empty()) { 118 TableIterationState &state = iterationState->back(); 119 if (state.mTableSize <= state.mCurrentIndex) { 120 // Move to parent. 121 iterationState->pop_back(); 122 } else { 123 const int entryIndex = state.mTableIndex + state.mCurrentIndex; 124 state.mCurrentIndex += 1; 125 const Entry entry = readEntry(entryIndex); 126 if (entry.isBitmapEntry()) { 127 // Move to child. 128 iterationState->emplace_back(popCount(entry.getBitmap()), entry.getTableIndex()); 129 } else { 130 if (outKey) { 131 *outKey = entry.getKey(); 132 } 133 if (!entry.hasTerminalLink()) { 134 return Result(entry.getValue(), true, INVALID_INDEX); 135 } 136 const int valueEntryIndex = entry.getValueEntryIndex(); 137 const Entry valueEntry = readEntry(valueEntryIndex); 138 return Result(valueEntry.getValueOfValueEntry(), true, valueEntryIndex + 1); 139 } 140 } 141 } 142 // Visited all entries. 143 return Result(0, false, INVALID_INDEX); 144} 145 146/** 147 * Shuffle bits of the key in the fixed order. 148 * 149 * This method is used as a hash function. This returns different values for different inputs. 150 */ 151uint32_t TrieMap::getBitShuffledKey(const uint32_t key) const { 152 uint32_t shuffledKey = 0; 153 for (int i = 0; i < 4; ++i) { 154 const uint32_t keyPiece = (key >> (i * 8)) & 0xFF; 155 shuffledKey ^= ((keyPiece ^ (keyPiece << 7) ^ (keyPiece << 14) ^ (keyPiece << 21)) 156 & 0x11111111) << i; 157 } 158 return shuffledKey; 159} 160 161bool TrieMap::writeValue(const uint64_t value, const int terminalEntryIndex) { 162 if (value <= VALUE_MASK) { 163 // Write value into the terminal entry. 164 return writeField1(value | VALUE_FLAG, terminalEntryIndex); 165 } 166 // Create value entry and write value. 167 const int valueEntryIndex = allocateTable(2 /* entryCount */); 168 if (!writeEntry(Entry(value >> (FIELD1_SIZE * CHAR_BIT), value), valueEntryIndex)) { 169 return false; 170 } 171 if (!writeEntry(EMPTY_BITMAP_ENTRY, valueEntryIndex + 1)) { 172 return false; 173 } 174 return writeField1(valueEntryIndex | TERMINAL_LINK_FLAG, terminalEntryIndex); 175} 176 177bool TrieMap::updateValue(const Entry &terminalEntry, const uint64_t value, 178 const int terminalEntryIndex) { 179 if (!terminalEntry.hasTerminalLink()) { 180 return writeValue(value, terminalEntryIndex); 181 } 182 const int valueEntryIndex = terminalEntry.getValueEntryIndex(); 183 return writeEntry(Entry(value >> (FIELD1_SIZE * CHAR_BIT), value), valueEntryIndex); 184} 185 186bool TrieMap::freeTable(const int tableIndex, const int entryCount) { 187 if (!writeField0(readEmptyTableLink(entryCount), tableIndex)) { 188 return false; 189 } 190 return writeEmptyTableLink(tableIndex, entryCount); 191} 192 193/** 194 * Allocate table with entryCount-entries. Reuse freed table if possible. 195 */ 196int TrieMap::allocateTable(const int entryCount) { 197 if (entryCount > 0 && entryCount <= MAX_NUM_OF_ENTRIES_IN_ONE_LEVEL) { 198 const int tableIndex = readEmptyTableLink(entryCount); 199 if (tableIndex > 0) { 200 if (!writeEmptyTableLink(readField0(tableIndex), entryCount)) { 201 return INVALID_INDEX; 202 } 203 // Reuse the table. 204 return tableIndex; 205 } 206 } 207 // Allocate memory space at tail position of the buffer. 208 const int mapIndex = getTailEntryIndex(); 209 if (!mBuffer.extend(entryCount * ENTRY_SIZE)) { 210 return INVALID_INDEX; 211 } 212 return mapIndex; 213} 214 215int TrieMap::getTerminalEntryIndex(const uint32_t key, const uint32_t hashedKey, 216 const Entry &bitmapEntry, const int level) const { 217 const int label = getLabel(hashedKey, level); 218 if (!exists(bitmapEntry.getBitmap(), label)) { 219 return INVALID_INDEX; 220 } 221 const int entryIndex = bitmapEntry.getTableIndex() + popCount(bitmapEntry.getBitmap(), label); 222 const Entry entry = readEntry(entryIndex); 223 if (entry.isBitmapEntry()) { 224 // Move to the next level. 225 return getTerminalEntryIndex(key, hashedKey, entry, level + 1); 226 } 227 if (entry.getKey() == key) { 228 // Terminal entry is found. 229 return entryIndex; 230 } 231 return INVALID_INDEX; 232} 233 234/** 235 * Get Result corresponding to the key. 236 * 237 * @param key the key. 238 * @param hashedKey the hashed key. 239 * @param bitmapEntryIndex the index of bitmap entry 240 * @param level current level 241 * @return Result instance corresponding to the key. mIsValid indicates whether the key is in the 242 * map. 243 */ 244const TrieMap::Result TrieMap::getInternal(const uint32_t key, const uint32_t hashedKey, 245 const int bitmapEntryIndex, const int level) const { 246 const int terminalEntryIndex = getTerminalEntryIndex(key, hashedKey, 247 readEntry(bitmapEntryIndex), level); 248 if (terminalEntryIndex == INVALID_INDEX) { 249 // Not found. 250 return Result(0, false, INVALID_INDEX); 251 } 252 const Entry terminalEntry = readEntry(terminalEntryIndex); 253 if (!terminalEntry.hasTerminalLink()) { 254 return Result(terminalEntry.getValue(), true, INVALID_INDEX); 255 } 256 const int valueEntryIndex = terminalEntry.getValueEntryIndex(); 257 const Entry valueEntry = readEntry(valueEntryIndex); 258 return Result(valueEntry.getValueOfValueEntry(), true, valueEntryIndex + 1); 259} 260 261/** 262 * Put key to value mapping to the map. 263 * 264 * @param key the key. 265 * @param value the value 266 * @param hashedKey the hashed key. 267 * @param bitmapEntryIndex the index of bitmap entry 268 * @param bitmapEntry the bitmap entry 269 * @param level current level 270 * @return whether the key-value has been correctly inserted to the map or not. 271 */ 272bool TrieMap::putInternal(const uint32_t key, const uint64_t value, const uint32_t hashedKey, 273 const int bitmapEntryIndex, const Entry &bitmapEntry, const int level) { 274 const int label = getLabel(hashedKey, level); 275 const uint32_t bitmap = bitmapEntry.getBitmap(); 276 const int mapIndex = bitmapEntry.getTableIndex(); 277 if (!exists(bitmap, label)) { 278 // Current map doesn't contain the label. 279 return addNewEntryByExpandingTable(key, value, mapIndex, bitmap, bitmapEntryIndex, label); 280 } 281 const int entryIndex = mapIndex + popCount(bitmap, label); 282 const Entry entry = readEntry(entryIndex); 283 if (entry.isBitmapEntry()) { 284 // Bitmap entry is found. Go to the next level. 285 return putInternal(key, value, hashedKey, entryIndex, entry, level + 1); 286 } 287 if (entry.getKey() == key) { 288 // Terminal entry for the key is found. Update the value. 289 return updateValue(entry, value, entryIndex); 290 } 291 // Conflict with the existing key. 292 return addNewEntryByResolvingConflict(key, value, hashedKey, entry, entryIndex, level); 293} 294 295/** 296 * Resolve a conflict in the current level and add new entry. 297 * 298 * @param key the key 299 * @param value the value 300 * @param hashedKey the hashed key 301 * @param conflictedEntry the existing conflicted entry 302 * @param conflictedEntryIndex the index of existing conflicted entry 303 * @param level current level 304 * @return whether the key-value has been correctly inserted to the map or not. 305 */ 306bool TrieMap::addNewEntryByResolvingConflict(const uint32_t key, const uint64_t value, 307 const uint32_t hashedKey, const Entry &conflictedEntry, const int conflictedEntryIndex, 308 const int level) { 309 const int conflictedKeyNextLabel = 310 getLabel(getBitShuffledKey(conflictedEntry.getKey()), level + 1); 311 const int nextLabel = getLabel(hashedKey, level + 1); 312 if (conflictedKeyNextLabel == nextLabel) { 313 // Conflicted again in the next level. 314 const int newTableIndex = allocateTable(1 /* entryCount */); 315 if (newTableIndex == INVALID_INDEX) { 316 return false; 317 } 318 if (!writeEntry(conflictedEntry, newTableIndex)) { 319 return false; 320 } 321 const Entry newBitmapEntry(setExist(0 /* bitmap */, nextLabel), newTableIndex); 322 if (!writeEntry(newBitmapEntry, conflictedEntryIndex)) { 323 return false; 324 } 325 return putInternal(key, value, hashedKey, conflictedEntryIndex, newBitmapEntry, level + 1); 326 } 327 // The conflict has been resolved. Create a table that contains 2 entries. 328 const int newTableIndex = allocateTable(2 /* entryCount */); 329 if (newTableIndex == INVALID_INDEX) { 330 return false; 331 } 332 if (nextLabel < conflictedKeyNextLabel) { 333 if (!writeTerminalEntry(key, value, newTableIndex)) { 334 return false; 335 } 336 if (!writeEntry(conflictedEntry, newTableIndex + 1)) { 337 return false; 338 } 339 } else { // nextLabel > conflictedKeyNextLabel 340 if (!writeEntry(conflictedEntry, newTableIndex)) { 341 return false; 342 } 343 if (!writeTerminalEntry(key, value, newTableIndex + 1)) { 344 return false; 345 } 346 } 347 const uint32_t updatedBitmap = 348 setExist(setExist(0 /* bitmap */, nextLabel), conflictedKeyNextLabel); 349 return writeEntry(Entry(updatedBitmap, newTableIndex), conflictedEntryIndex); 350} 351 352/** 353 * Add new entry to the existing table. 354 */ 355bool TrieMap::addNewEntryByExpandingTable(const uint32_t key, const uint64_t value, 356 const int tableIndex, const uint32_t bitmap, const int bitmapEntryIndex, const int label) { 357 // Current map doesn't contain the label. 358 const int entryCount = popCount(bitmap); 359 const int newTableIndex = allocateTable(entryCount + 1); 360 if (newTableIndex == INVALID_INDEX) { 361 return false; 362 } 363 const int newEntryIndexInTable = popCount(bitmap, label); 364 // Copy from existing table to the new table. 365 for (int i = 0; i < entryCount; ++i) { 366 if (!copyEntry(tableIndex + i, newTableIndex + i + (i >= newEntryIndexInTable ? 1 : 0))) { 367 return false; 368 } 369 } 370 // Write new terminal entry. 371 if (!writeTerminalEntry(key, value, newTableIndex + newEntryIndexInTable)) { 372 return false; 373 } 374 // Update bitmap. 375 if (!writeEntry(Entry(setExist(bitmap, label), newTableIndex), bitmapEntryIndex)) { 376 return false; 377 } 378 if (entryCount > 0) { 379 return freeTable(tableIndex, entryCount); 380 } 381 return true; 382} 383 384} // namespace latinime 385