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