Add spellcheck and word suggestion to the prediction service

third_party/prediction/suggest/policyimpl/dictionary/utils/trie_map.cpp

+/*
+ * Copyright (C) 2014, The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "third_party/prediction/suggest/policyimpl/dictionary/utils/trie_map.h"
+
+#include "third_party/prediction/suggest/policyimpl/dictionary/utils/dict_file_writing_utils.h"
+
+namespace latinime {
+
+const int TrieMap::INVALID_INDEX = -1;
+const int TrieMap::FIELD0_SIZE = 4;
+const int TrieMap::FIELD1_SIZE = 3;
+const int TrieMap::ENTRY_SIZE = FIELD0_SIZE + FIELD1_SIZE;
+const uint32_t TrieMap::VALUE_FLAG = 0x400000;
+const uint32_t TrieMap::VALUE_MASK = 0x3FFFFF;
+const uint32_t TrieMap::TERMINAL_LINK_FLAG = 0x800000;
+const uint32_t TrieMap::TERMINAL_LINK_MASK = 0x7FFFFF;
+const int TrieMap::NUM_OF_BITS_USED_FOR_ONE_LEVEL = 5;
+const uint32_t TrieMap::LABEL_MASK = 0x1F;
+const int TrieMap::MAX_NUM_OF_ENTRIES_IN_ONE_LEVEL =
+    1 << NUM_OF_BITS_USED_FOR_ONE_LEVEL;
+const int TrieMap::ROOT_BITMAP_ENTRY_INDEX = 0;
+const int TrieMap::ROOT_BITMAP_ENTRY_POS =
+    MAX_NUM_OF_ENTRIES_IN_ONE_LEVEL * FIELD0_SIZE;
+const TrieMap::Entry TrieMap::EMPTY_BITMAP_ENTRY = TrieMap::Entry(0, 0);
+const uint64_t TrieMap::MAX_VALUE =
+    (static_cast<uint64_t>(1) << ((FIELD0_SIZE + FIELD1_SIZE) * CHAR_BIT)) - 1;
+const int TrieMap::MAX_BUFFER_SIZE = TERMINAL_LINK_MASK * ENTRY_SIZE;
+
+TrieMap::TrieMap() : mBuffer(MAX_BUFFER_SIZE) {
+  mBuffer.extend(ROOT_BITMAP_ENTRY_POS);
+  writeEntry(EMPTY_BITMAP_ENTRY, ROOT_BITMAP_ENTRY_INDEX);
+}
+
+TrieMap::TrieMap(const ReadWriteByteArrayView buffer)
+    : mBuffer(buffer,
+              BufferWithExtendableBuffer::DEFAULT_MAX_ADDITIONAL_BUFFER_SIZE) {
+}
+
+void TrieMap::dump(const int from, const int to) const {
+  AKLOGI("BufSize: %d", mBuffer.getTailPosition());
+  for (int i = from; i < to; ++i) {
+    AKLOGI("Entry[%d]: %x, %x", i, readField0(i), readField1(i));
+  }
+  int unusedRegionSize = 0;
+  for (int i = 1; i <= MAX_NUM_OF_ENTRIES_IN_ONE_LEVEL; ++i) {
+    int index = readEmptyTableLink(i);
+    while (index != ROOT_BITMAP_ENTRY_INDEX) {
+      index = readField0(index);
+      unusedRegionSize += i;
+    }
+  }
+  AKLOGI("Unused Size: %d", unusedRegionSize);
+}
+
+int TrieMap::getNextLevelBitmapEntryIndex(const int key,
+                                          const int bitmapEntryIndex) {
+  const Entry bitmapEntry = readEntry(bitmapEntryIndex);
+  const uint32_t unsignedKey = static_cast<uint32_t>(key);
+  const int terminalEntryIndex = getTerminalEntryIndex(
+      unsignedKey, getBitShuffledKey(unsignedKey), bitmapEntry, 0 /* level */);
+  if (terminalEntryIndex == INVALID_INDEX) {
+    // Not found.
+    return INVALID_INDEX;
+  }
+  const Entry terminalEntry = readEntry(terminalEntryIndex);
+  if (terminalEntry.hasTerminalLink()) {
+    return terminalEntry.getValueEntryIndex() + 1;
+  }
+  // Create a value entry and a bitmap entry.
+  const int valueEntryIndex = allocateTable(2 /* entryCount */);
+  if (!writeEntry(Entry(0, terminalEntry.getValue()), valueEntryIndex)) {
+    return INVALID_INDEX;
+  }
+  if (!writeEntry(EMPTY_BITMAP_ENTRY, valueEntryIndex + 1)) {
+    return INVALID_INDEX;
+  }
+  if (!writeField1(valueEntryIndex | TERMINAL_LINK_FLAG, valueEntryIndex)) {
+    return INVALID_INDEX;
+  }
+  return valueEntryIndex + 1;
+}
+
+const TrieMap::Result TrieMap::get(const int key,
+                                   const int bitmapEntryIndex) const {
+  const uint32_t unsignedKey = static_cast<uint32_t>(key);
+  return getInternal(unsignedKey, getBitShuffledKey(unsignedKey),
+                     bitmapEntryIndex, 0 /* level */);
+}
+
+bool TrieMap::put(const int key,
+                  const uint64_t value,
+                  const int bitmapEntryIndex) {
+  if (value > MAX_VALUE) {
+    return false;
+  }
+  const uint32_t unsignedKey = static_cast<uint32_t>(key);
+  return putInternal(unsignedKey, value, getBitShuffledKey(unsignedKey),
+                     bitmapEntryIndex, readEntry(bitmapEntryIndex),
+                     0 /* level */);
+}
+
+bool TrieMap::save(FILE* const file) const {
+  return DictFileWritingUtils::writeBufferToFileTail(file, &mBuffer);
+}
+
+/**
+ * Iterate next entry in a certain level.
+ *
+ * @param iterationState the iteration state that will be read and updated in
+ *this method.
+ * @param outKey the output key
+ * @return Result instance. mIsValid is false when all entries are iterated.
+ */
+const TrieMap::Result TrieMap::iterateNext(
+    std::vector<TableIterationState>* const iterationState,
+    int* const outKey) const {
+  while (!iterationState->empty()) {
+    TableIterationState& state = iterationState->back();
+    if (state.mTableSize <= state.mCurrentIndex) {
+      // Move to parent.
+      iterationState->pop_back();
+    } else {
+      const int entryIndex = state.mTableIndex + state.mCurrentIndex;
+      state.mCurrentIndex += 1;
+      const Entry entry = readEntry(entryIndex);
+      if (entry.isBitmapEntry()) {
+        // Move to child.
+        iterationState->emplace_back(popCount(entry.getBitmap()),
+                                     entry.getTableIndex());
+      } else {
+        if (outKey) {
+          *outKey = entry.getKey();
+        }
+        if (!entry.hasTerminalLink()) {
+          return Result(entry.getValue(), true, INVALID_INDEX);
+        }
+        const int valueEntryIndex = entry.getValueEntryIndex();
+        const Entry valueEntry = readEntry(valueEntryIndex);
+        return Result(valueEntry.getValueOfValueEntry(), true,
+                      valueEntryIndex + 1);
+      }
+    }
+  }
+  // Visited all entries.
+  return Result(0, false, INVALID_INDEX);
+}
+
+/**
+ * Shuffle bits of the key in the fixed order.
+ *
+ * This method is used as a hash function. This returns different values for
+ *different inputs.
+ */
+uint32_t TrieMap::getBitShuffledKey(const uint32_t key) const {
+  uint32_t shuffledKey = 0;
+  for (int i = 0; i < 4; ++i) {
+    const uint32_t keyPiece = (key >> (i * 8)) & 0xFF;
+    shuffledKey ^=
+        ((keyPiece ^ (keyPiece << 7) ^ (keyPiece << 14) ^ (keyPiece << 21)) &
+         0x11111111)
+        << i;
+  }
+  return shuffledKey;
+}
+
+bool TrieMap::writeValue(const uint64_t value, const int terminalEntryIndex) {
+  if (value <= VALUE_MASK) {
+    // Write value into the terminal entry.
+    return writeField1(value | VALUE_FLAG, terminalEntryIndex);
+  }
+  // Create value entry and write value.
+  const int valueEntryIndex = allocateTable(2 /* entryCount */);
+  if (!writeEntry(Entry(value >> (FIELD1_SIZE * CHAR_BIT), value),
+                  valueEntryIndex)) {
+    return false;
+  }
+  if (!writeEntry(EMPTY_BITMAP_ENTRY, valueEntryIndex + 1)) {
+    return false;
+  }
+  return writeField1(valueEntryIndex | TERMINAL_LINK_FLAG, terminalEntryIndex);
+}
+
+bool TrieMap::updateValue(const Entry& terminalEntry,
+                          const uint64_t value,
+                          const int terminalEntryIndex) {
+  if (!terminalEntry.hasTerminalLink()) {
+    return writeValue(value, terminalEntryIndex);
+  }
+  const int valueEntryIndex = terminalEntry.getValueEntryIndex();
+  return writeEntry(Entry(value >> (FIELD1_SIZE * CHAR_BIT), value),
+                    valueEntryIndex);
+}
+
+bool TrieMap::freeTable(const int tableIndex, const int entryCount) {
+  if (!writeField0(readEmptyTableLink(entryCount), tableIndex)) {
+    return false;
+  }
+  return writeEmptyTableLink(tableIndex, entryCount);
+}
+
+/**
+ * Allocate table with entryCount-entries. Reuse freed table if possible.
+ */
+int TrieMap::allocateTable(const int entryCount) {
+  if (entryCount > 0 && entryCount <= MAX_NUM_OF_ENTRIES_IN_ONE_LEVEL) {
+    const int tableIndex = readEmptyTableLink(entryCount);
+    if (tableIndex > 0) {
+      if (!writeEmptyTableLink(readField0(tableIndex), entryCount)) {
+        return INVALID_INDEX;
+      }
+      // Reuse the table.
+      return tableIndex;
+    }
+  }
+  // Allocate memory space at tail position of the buffer.
+  const int mapIndex = getTailEntryIndex();
+  if (!mBuffer.extend(entryCount * ENTRY_SIZE)) {
+    return INVALID_INDEX;
+  }
+  return mapIndex;
+}
+
+int TrieMap::getTerminalEntryIndex(const uint32_t key,
+                                   const uint32_t hashedKey,
+                                   const Entry& bitmapEntry,
+                                   const int level) const {
+  const int label = getLabel(hashedKey, level);
+  if (!exists(bitmapEntry.getBitmap(), label)) {
+    return INVALID_INDEX;
+  }
+  const int entryIndex =
+      bitmapEntry.getTableIndex() + popCount(bitmapEntry.getBitmap(), label);
+  const Entry entry = readEntry(entryIndex);
+  if (entry.isBitmapEntry()) {
+    // Move to the next level.
+    return getTerminalEntryIndex(key, hashedKey, entry, level + 1);
+  }
+  if (entry.getKey() == key) {
+    // Terminal entry is found.
+    return entryIndex;
+  }
+  return INVALID_INDEX;
+}
+
+/**
+ * Get Result corresponding to the key.
+ *
+ * @param key the key.
+ * @param hashedKey the hashed key.
+ * @param bitmapEntryIndex the index of bitmap entry
+ * @param level current level
+ * @return Result instance corresponding to the key. mIsValid indicates whether
+ *the key is in the
+ * map.
+ */
+const TrieMap::Result TrieMap::getInternal(const uint32_t key,
+                                           const uint32_t hashedKey,
+                                           const int bitmapEntryIndex,
+                                           const int level) const {
+  const int terminalEntryIndex =
+      getTerminalEntryIndex(key, hashedKey, readEntry(bitmapEntryIndex), level);
+  if (terminalEntryIndex == INVALID_INDEX) {
+    // Not found.
+    return Result(0, false, INVALID_INDEX);
+  }
+  const Entry terminalEntry = readEntry(terminalEntryIndex);
+  if (!terminalEntry.hasTerminalLink()) {
+    return Result(terminalEntry.getValue(), true, INVALID_INDEX);
+  }
+  const int valueEntryIndex = terminalEntry.getValueEntryIndex();
+  const Entry valueEntry = readEntry(valueEntryIndex);
+  return Result(valueEntry.getValueOfValueEntry(), true, valueEntryIndex + 1);
+}
+
+/**
+ * Put key to value mapping to the map.
+ *
+ * @param key the key.
+ * @param value the value
+ * @param hashedKey the hashed key.
+ * @param bitmapEntryIndex the index of bitmap entry
+ * @param bitmapEntry the bitmap entry
+ * @param level current level
+ * @return whether the key-value has been correctly inserted to the map or not.
+ */
+bool TrieMap::putInternal(const uint32_t key,
+                          const uint64_t value,
+                          const uint32_t hashedKey,
+                          const int bitmapEntryIndex,
+                          const Entry& bitmapEntry,
+                          const int level) {
+  const int label = getLabel(hashedKey, level);
+  const uint32_t bitmap = bitmapEntry.getBitmap();
+  const int mapIndex = bitmapEntry.getTableIndex();
+  if (!exists(bitmap, label)) {
+    // Current map doesn't contain the label.
+    return addNewEntryByExpandingTable(key, value, mapIndex, bitmap,
+                                       bitmapEntryIndex, label);
+  }
+  const int entryIndex = mapIndex + popCount(bitmap, label);
+  const Entry entry = readEntry(entryIndex);
+  if (entry.isBitmapEntry()) {
+    // Bitmap entry is found. Go to the next level.
+    return putInternal(key, value, hashedKey, entryIndex, entry, level + 1);
+  }
+  if (entry.getKey() == key) {
+    // Terminal entry for the key is found. Update the value.
+    return updateValue(entry, value, entryIndex);
+  }
+  // Conflict with the existing key.
+  return addNewEntryByResolvingConflict(key, value, hashedKey, entry,
+                                        entryIndex, level);
+}
+
+/**
+ * Resolve a conflict in the current level and add new entry.
+ *
+ * @param key the key
+ * @param value the value
+ * @param hashedKey the hashed key
+ * @param conflictedEntry the existing conflicted entry
+ * @param conflictedEntryIndex the index of existing conflicted entry
+ * @param level current level
+ * @return whether the key-value has been correctly inserted to the map or not.
+ */
+bool TrieMap::addNewEntryByResolvingConflict(const uint32_t key,
+                                             const uint64_t value,
+                                             const uint32_t hashedKey,
+                                             const Entry& conflictedEntry,
+                                             const int conflictedEntryIndex,
+                                             const int level) {
+  const int conflictedKeyNextLabel =
+      getLabel(getBitShuffledKey(conflictedEntry.getKey()), level + 1);
+  const int nextLabel = getLabel(hashedKey, level + 1);
+  if (conflictedKeyNextLabel == nextLabel) {
+    // Conflicted again in the next level.
+    const int newTableIndex = allocateTable(1 /* entryCount */);
+    if (newTableIndex == INVALID_INDEX) {
+      return false;
+    }
+    if (!writeEntry(conflictedEntry, newTableIndex)) {
+      return false;
+    }
+    const Entry newBitmapEntry(setExist(0 /* bitmap */, nextLabel),
+                               newTableIndex);
+    if (!writeEntry(newBitmapEntry, conflictedEntryIndex)) {
+      return false;
+    }
+    return putInternal(key, value, hashedKey, conflictedEntryIndex,
+                       newBitmapEntry, level + 1);
+  }
+  // The conflict has been resolved. Create a table that contains 2 entries.
+  const int newTableIndex = allocateTable(2 /* entryCount */);
+  if (newTableIndex == INVALID_INDEX) {
+    return false;
+  }
+  if (nextLabel < conflictedKeyNextLabel) {
+    if (!writeTerminalEntry(key, value, newTableIndex)) {
+      return false;
+    }
+    if (!writeEntry(conflictedEntry, newTableIndex + 1)) {
+      return false;
+    }
+  } else {  // nextLabel > conflictedKeyNextLabel
+    if (!writeEntry(conflictedEntry, newTableIndex)) {
+      return false;
+    }
+    if (!writeTerminalEntry(key, value, newTableIndex + 1)) {
+      return false;
+    }
+  }
+  const uint32_t updatedBitmap =
+      setExist(setExist(0 /* bitmap */, nextLabel), conflictedKeyNextLabel);
+  return writeEntry(Entry(updatedBitmap, newTableIndex), conflictedEntryIndex);
+}
+
+/**
+ * Add new entry to the existing table.
+ */
+bool TrieMap::addNewEntryByExpandingTable(const uint32_t key,
+                                          const uint64_t value,
+                                          const int tableIndex,
+                                          const uint32_t bitmap,
+                                          const int bitmapEntryIndex,
+                                          const int label) {
+  // Current map doesn't contain the label.
+  const int entryCount = popCount(bitmap);
+  const int newTableIndex = allocateTable(entryCount + 1);
+  if (newTableIndex == INVALID_INDEX) {
+    return false;
+  }
+  const int newEntryIndexInTable = popCount(bitmap, label);
+  // Copy from existing table to the new table.
+  for (int i = 0; i < entryCount; ++i) {
+    if (!copyEntry(tableIndex + i,
+                   newTableIndex + i + (i >= newEntryIndexInTable ? 1 : 0))) {
+      return false;
+    }
+  }
+  // Write new terminal entry.
+  if (!writeTerminalEntry(key, value, newTableIndex + newEntryIndexInTable)) {
+    return false;
+  }
+  // Update bitmap.
+  if (!writeEntry(Entry(setExist(bitmap, label), newTableIndex),
+                  bitmapEntryIndex)) {
+    return false;
+  }
+  if (entryCount > 0) {
+    return freeTable(tableIndex, entryCount);
+  }
+  return true;
+}
+
+}  // namespace latinime