trie_map.cpp revision de3121dead395d32760379c03938faef6eac2f98
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/** 103 * Shuffle bits of the key in the fixed order. 104 * 105 * This method is used as a hash function. This returns different values for different inputs. 106 */ 107uint32_t TrieMap::getBitShuffledKey(const uint32_t key) const { 108 uint32_t shuffledKey = 0; 109 for (int i = 0; i < 4; ++i) { 110 const uint32_t keyPiece = (key >> (i * 8)) & 0xFF; 111 shuffledKey ^= ((keyPiece ^ (keyPiece << 7) ^ (keyPiece << 14) ^ (keyPiece << 21)) 112 & 0x11111111) << i; 113 } 114 return shuffledKey; 115} 116 117bool TrieMap::writeValue(const uint64_t value, const int terminalEntryIndex) { 118 if (value <= VALUE_MASK) { 119 // Write value into the terminal entry. 120 return writeField1(value | VALUE_FLAG, terminalEntryIndex); 121 } 122 // Create value entry and write value. 123 const int valueEntryIndex = allocateTable(2 /* entryCount */); 124 if (!writeEntry(Entry(value >> (FIELD1_SIZE * CHAR_BIT), value), valueEntryIndex)) { 125 return false; 126 } 127 if (!writeEntry(EMPTY_BITMAP_ENTRY, valueEntryIndex + 1)) { 128 return false; 129 } 130 return writeField1(valueEntryIndex | TERMINAL_LINK_FLAG, terminalEntryIndex); 131} 132 133bool TrieMap::updateValue(const Entry &terminalEntry, const uint64_t value, 134 const int terminalEntryIndex) { 135 if (!terminalEntry.hasTerminalLink()) { 136 return writeValue(value, terminalEntryIndex); 137 } 138 const int valueEntryIndex = terminalEntry.getValueEntryIndex(); 139 return writeEntry(Entry(value >> (FIELD1_SIZE * CHAR_BIT), value), valueEntryIndex); 140} 141 142bool TrieMap::freeTable(const int tableIndex, const int entryCount) { 143 if (!writeField0(readEmptyTableLink(entryCount), tableIndex)) { 144 return false; 145 } 146 return writeEmptyTableLink(tableIndex, entryCount); 147} 148 149/** 150 * Allocate table with entryCount-entries. Reuse freed table if possible. 151 */ 152int TrieMap::allocateTable(const int entryCount) { 153 if (entryCount > 0 && entryCount <= MAX_NUM_OF_ENTRIES_IN_ONE_LEVEL) { 154 const int tableIndex = readEmptyTableLink(entryCount); 155 if (tableIndex > 0) { 156 if (!writeEmptyTableLink(readField0(tableIndex), entryCount)) { 157 return INVALID_INDEX; 158 } 159 // Reuse the table. 160 return tableIndex; 161 } 162 } 163 // Allocate memory space at tail position of the buffer. 164 const int mapIndex = getTailEntryIndex(); 165 if (!mBuffer.extend(entryCount * ENTRY_SIZE)) { 166 return INVALID_INDEX; 167 } 168 return mapIndex; 169} 170 171int TrieMap::getTerminalEntryIndex(const uint32_t key, const uint32_t hashedKey, 172 const Entry &bitmapEntry, const int level) const { 173 const int label = getLabel(hashedKey, level); 174 if (!exists(bitmapEntry.getBitmap(), label)) { 175 return INVALID_INDEX; 176 } 177 const int entryIndex = bitmapEntry.getTableIndex() + popCount(bitmapEntry.getBitmap(), label); 178 const Entry entry = readEntry(entryIndex); 179 if (entry.isBitmapEntry()) { 180 // Move to the next level. 181 return getTerminalEntryIndex(key, hashedKey, entry, level + 1); 182 } 183 if (entry.getKey() == key) { 184 // Terminal entry is found. 185 return entryIndex; 186 } 187 return INVALID_INDEX; 188} 189 190/** 191 * Get Result corresponding to the key. 192 * 193 * @param key the key. 194 * @param hashedKey the hashed key. 195 * @param bitmapEntryIndex the index of bitmap entry 196 * @param level current level 197 * @return Result instance corresponding to the key. mIsValid indicates whether the key is in the 198 * map. 199 */ 200const TrieMap::Result TrieMap::getInternal(const uint32_t key, const uint32_t hashedKey, 201 const int bitmapEntryIndex, const int level) const { 202 const int terminalEntryIndex = getTerminalEntryIndex(key, hashedKey, 203 readEntry(bitmapEntryIndex), level); 204 if (terminalEntryIndex == INVALID_INDEX) { 205 // Not found. 206 return Result(0, false, INVALID_INDEX); 207 } 208 const Entry terminalEntry = readEntry(terminalEntryIndex); 209 if (!terminalEntry.hasTerminalLink()) { 210 return Result(terminalEntry.getValue(), true, INVALID_INDEX); 211 } 212 const int valueEntryIndex = terminalEntry.getValueEntryIndex(); 213 const Entry valueEntry = readEntry(valueEntryIndex); 214 return Result(valueEntry.getValueOfValueEntry(), true, valueEntryIndex + 1); 215} 216 217/** 218 * Put key to value mapping to the map. 219 * 220 * @param key the key. 221 * @param value the value 222 * @param hashedKey the hashed key. 223 * @param bitmapEntryIndex the index of bitmap entry 224 * @param bitmapEntry the bitmap entry 225 * @param level current level 226 * @return whether the key-value has been correctly inserted to the map or not. 227 */ 228bool TrieMap::putInternal(const uint32_t key, const uint64_t value, const uint32_t hashedKey, 229 const int bitmapEntryIndex, const Entry &bitmapEntry, const int level) { 230 const int label = getLabel(hashedKey, level); 231 const uint32_t bitmap = bitmapEntry.getBitmap(); 232 const int mapIndex = bitmapEntry.getTableIndex(); 233 if (!exists(bitmap, label)) { 234 // Current map doesn't contain the label. 235 return addNewEntryByExpandingTable(key, value, mapIndex, bitmap, bitmapEntryIndex, label); 236 } 237 const int entryIndex = mapIndex + popCount(bitmap, label); 238 const Entry entry = readEntry(entryIndex); 239 if (entry.isBitmapEntry()) { 240 // Bitmap entry is found. Go to the next level. 241 return putInternal(key, value, hashedKey, entryIndex, entry, level + 1); 242 } 243 if (entry.getKey() == key) { 244 // Terminal entry for the key is found. Update the value. 245 return updateValue(entry, value, entryIndex); 246 } 247 // Conflict with the existing key. 248 return addNewEntryByResolvingConflict(key, value, hashedKey, entry, entryIndex, level); 249} 250 251/** 252 * Resolve a conflict in the current level and add new entry. 253 * 254 * @param key the key 255 * @param value the value 256 * @param hashedKey the hashed key 257 * @param conflictedEntry the existing conflicted entry 258 * @param conflictedEntryIndex the index of existing conflicted entry 259 * @param level current level 260 * @return whether the key-value has been correctly inserted to the map or not. 261 */ 262bool TrieMap::addNewEntryByResolvingConflict(const uint32_t key, const uint64_t value, 263 const uint32_t hashedKey, const Entry &conflictedEntry, const int conflictedEntryIndex, 264 const int level) { 265 const int conflictedKeyNextLabel = 266 getLabel(getBitShuffledKey(conflictedEntry.getKey()), level + 1); 267 const int nextLabel = getLabel(hashedKey, level + 1); 268 if (conflictedKeyNextLabel == nextLabel) { 269 // Conflicted again in the next level. 270 const int newTableIndex = allocateTable(1 /* entryCount */); 271 if (newTableIndex == INVALID_INDEX) { 272 return false; 273 } 274 if (!writeEntry(conflictedEntry, newTableIndex)) { 275 return false; 276 } 277 const Entry newBitmapEntry(setExist(0 /* bitmap */, nextLabel), newTableIndex); 278 if (!writeEntry(newBitmapEntry, conflictedEntryIndex)) { 279 return false; 280 } 281 return putInternal(key, value, hashedKey, conflictedEntryIndex, newBitmapEntry, level + 1); 282 } 283 // The conflict has been resolved. Create a table that contains 2 entries. 284 const int newTableIndex = allocateTable(2 /* entryCount */); 285 if (newTableIndex == INVALID_INDEX) { 286 return false; 287 } 288 if (nextLabel < conflictedKeyNextLabel) { 289 if (!writeTerminalEntry(key, value, newTableIndex)) { 290 return false; 291 } 292 if (!writeEntry(conflictedEntry, newTableIndex + 1)) { 293 return false; 294 } 295 } else { // nextLabel > conflictedKeyNextLabel 296 if (!writeEntry(conflictedEntry, newTableIndex)) { 297 return false; 298 } 299 if (!writeTerminalEntry(key, value, newTableIndex + 1)) { 300 return false; 301 } 302 } 303 const uint32_t updatedBitmap = 304 setExist(setExist(0 /* bitmap */, nextLabel), conflictedKeyNextLabel); 305 return writeEntry(Entry(updatedBitmap, newTableIndex), conflictedEntryIndex); 306} 307 308/** 309 * Add new entry to the existing table. 310 */ 311bool TrieMap::addNewEntryByExpandingTable(const uint32_t key, const uint64_t value, 312 const int tableIndex, const uint32_t bitmap, const int bitmapEntryIndex, const int label) { 313 // Current map doesn't contain the label. 314 const int entryCount = popCount(bitmap); 315 const int newTableIndex = allocateTable(entryCount + 1); 316 if (newTableIndex == INVALID_INDEX) { 317 return false; 318 } 319 const int newEntryIndexInTable = popCount(bitmap, label); 320 // Copy from existing table to the new table. 321 for (int i = 0; i < entryCount; ++i) { 322 if (!copyEntry(tableIndex + i, newTableIndex + i + (i >= newEntryIndexInTable ? 1 : 0))) { 323 return false; 324 } 325 } 326 // Write new terminal entry. 327 if (!writeTerminalEntry(key, value, newTableIndex + newEntryIndexInTable)) { 328 return false; 329 } 330 // Update bitmap. 331 if (!writeEntry(Entry(setExist(bitmap, label), newTableIndex), bitmapEntryIndex)) { 332 return false; 333 } 334 if (entryCount > 0) { 335 return freeTable(tableIndex, entryCount); 336 } 337 return true; 338} 339 340} // namespace latinime 341