Home | History | Annotate | Download | only in dictionary 
      1 /*
      2  * Copyright (C) 2013, 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/dynamic_patricia_trie_writing_utils.h"
     18 
     19 #include <cstddef>
     20 #include <cstdlib>
     21 #include <stdint.h>
     22 
     23 #include "suggest/policyimpl/dictionary/utils/buffer_with_extendable_buffer.h"
     24 
     25 namespace latinime {
     26 
     27 const size_t DynamicPatriciaTrieWritingUtils::MAX_PTNODE_ARRAY_SIZE_TO_USE_SMALL_SIZE_FIELD = 0x7F;
     28 const size_t DynamicPatriciaTrieWritingUtils::MAX_PTNODE_ARRAY_SIZE = 0x7FFF;
     29 const int DynamicPatriciaTrieWritingUtils::SMALL_PTNODE_ARRAY_SIZE_FIELD_SIZE = 1;
     30 const int DynamicPatriciaTrieWritingUtils::LARGE_PTNODE_ARRAY_SIZE_FIELD_SIZE = 2;
     31 const int DynamicPatriciaTrieWritingUtils::LARGE_PTNODE_ARRAY_SIZE_FIELD_SIZE_FLAG = 0x8000;
     32 const int DynamicPatriciaTrieWritingUtils::DICT_OFFSET_FIELD_SIZE = 3;
     33 const int DynamicPatriciaTrieWritingUtils::MAX_DICT_OFFSET_VALUE = 0x7FFFFF;
     34 const int DynamicPatriciaTrieWritingUtils::MIN_DICT_OFFSET_VALUE = -0x7FFFFF;
     35 const int DynamicPatriciaTrieWritingUtils::DICT_OFFSET_NEGATIVE_FLAG = 0x800000;
     36 const int DynamicPatriciaTrieWritingUtils::PROBABILITY_FIELD_SIZE = 1;
     37 const int DynamicPatriciaTrieWritingUtils::NODE_FLAG_FIELD_SIZE = 1;
     38 
     39 /* static */ bool DynamicPatriciaTrieWritingUtils::writeEmptyDictionary(
     40         BufferWithExtendableBuffer *const buffer, const int rootPos) {
     41     int writingPos = rootPos;
     42     if (!writePtNodeArraySizeAndAdvancePosition(buffer, 0 /* arraySize */, &writingPos)) {
     43         return false;
     44     }
     45     return writeForwardLinkPositionAndAdvancePosition(buffer, NOT_A_DICT_POS /* forwardLinkPos */,
     46             &writingPos);
     47 }
     48 
     49 /* static */ bool DynamicPatriciaTrieWritingUtils::writeForwardLinkPositionAndAdvancePosition(
     50         BufferWithExtendableBuffer *const buffer, const int forwardLinkPos,
     51         int *const forwardLinkFieldPos) {
     52     return writeDictOffset(buffer, forwardLinkPos, (*forwardLinkFieldPos), forwardLinkFieldPos);
     53 }
     54 
     55 /* static */ bool DynamicPatriciaTrieWritingUtils::writePtNodeArraySizeAndAdvancePosition(
     56         BufferWithExtendableBuffer *const buffer, const size_t arraySize,
     57         int *const arraySizeFieldPos) {
     58     // Currently, all array size field to be created has LARGE_PTNODE_ARRAY_SIZE_FIELD_SIZE to
     59     // simplify updating process.
     60     // TODO: Use SMALL_PTNODE_ARRAY_SIZE_FIELD_SIZE for small arrays.
     61     /*if (arraySize <= MAX_PTNODE_ARRAY_SIZE_TO_USE_SMALL_SIZE_FIELD) {
     62         return buffer->writeUintAndAdvancePosition(arraySize, SMALL_PTNODE_ARRAY_SIZE_FIELD_SIZE,
     63                 arraySizeFieldPos);
     64     } else */
     65     if (arraySize <= MAX_PTNODE_ARRAY_SIZE) {
     66         uint32_t data = arraySize | LARGE_PTNODE_ARRAY_SIZE_FIELD_SIZE_FLAG;
     67         return buffer->writeUintAndAdvancePosition(data, LARGE_PTNODE_ARRAY_SIZE_FIELD_SIZE,
     68                 arraySizeFieldPos);
     69     } else {
     70         AKLOGI("PtNode array size cannot be written because arraySize is too large: %zd",
     71                 arraySize);
     72         ASSERT(false);
     73         return false;
     74     }
     75 }
     76 
     77 /* static */ bool DynamicPatriciaTrieWritingUtils::writeFlagsAndAdvancePosition(
     78         BufferWithExtendableBuffer *const buffer,
     79         const DynamicPatriciaTrieReadingUtils::NodeFlags nodeFlags, int *const nodeFlagsFieldPos) {
     80     return buffer->writeUintAndAdvancePosition(nodeFlags, NODE_FLAG_FIELD_SIZE, nodeFlagsFieldPos);
     81 }
     82 
     83 // Note that parentOffset is offset from node's head position.
     84 /* static */ bool DynamicPatriciaTrieWritingUtils::writeParentPosOffsetAndAdvancePosition(
     85         BufferWithExtendableBuffer *const buffer, const int parentPos, const int basePos,
     86         int *const parentPosFieldPos) {
     87     return writeDictOffset(buffer, parentPos, basePos, parentPosFieldPos);
     88 }
     89 
     90 /* static */ bool DynamicPatriciaTrieWritingUtils::writeCodePointsAndAdvancePosition(
     91         BufferWithExtendableBuffer *const buffer, const int *const codePoints,
     92         const int codePointCount, int *const codePointFieldPos) {
     93     if (codePointCount <= 0) {
     94         AKLOGI("code points cannot be written because codePointCount is invalid: %d",
     95                 codePointCount);
     96         ASSERT(false);
     97         return false;
     98     }
     99     const bool hasMultipleCodePoints = codePointCount > 1;
    100     return buffer->writeCodePointsAndAdvancePosition(codePoints, codePointCount,
    101             hasMultipleCodePoints, codePointFieldPos);
    102 }
    103 
    104 /* static */ bool DynamicPatriciaTrieWritingUtils::writeProbabilityAndAdvancePosition(
    105         BufferWithExtendableBuffer *const buffer, const int probability,
    106         int *const probabilityFieldPos) {
    107     if (probability < 0 || probability > MAX_PROBABILITY) {
    108         AKLOGI("probability cannot be written because the probability is invalid: %d",
    109                 probability);
    110         ASSERT(false);
    111         return false;
    112     }
    113     return buffer->writeUintAndAdvancePosition(probability, PROBABILITY_FIELD_SIZE,
    114             probabilityFieldPos);
    115 }
    116 
    117 /* static */ bool DynamicPatriciaTrieWritingUtils::writeChildrenPositionAndAdvancePosition(
    118         BufferWithExtendableBuffer *const buffer, const int childrenPosition,
    119         int *const childrenPositionFieldPos) {
    120     return writeDictOffset(buffer, childrenPosition, (*childrenPositionFieldPos),
    121             childrenPositionFieldPos);
    122 }
    123 
    124 /* static */ bool DynamicPatriciaTrieWritingUtils::writeDictOffset(
    125         BufferWithExtendableBuffer *const buffer, const int targetPos, const int basePos,
    126         int *const offsetFieldPos) {
    127     int offset = targetPos - basePos;
    128     if (targetPos == NOT_A_DICT_POS) {
    129         offset = DynamicPatriciaTrieReadingUtils::DICT_OFFSET_INVALID;
    130     } else if (offset == 0) {
    131         offset = DynamicPatriciaTrieReadingUtils::DICT_OFFSET_ZERO_OFFSET;
    132     }
    133     if (offset > MAX_DICT_OFFSET_VALUE || offset < MIN_DICT_OFFSET_VALUE) {
    134         AKLOGI("offset cannot be written because the offset is too large or too small: %d",
    135                 offset);
    136         ASSERT(false);
    137         return false;
    138     }
    139     uint32_t data = 0;
    140     if (offset >= 0) {
    141         data = offset;
    142     } else {
    143         data = abs(offset) | DICT_OFFSET_NEGATIVE_FLAG;
    144     }
    145     return buffer->writeUintAndAdvancePosition(data, DICT_OFFSET_FIELD_SIZE, offsetFieldPos);
    146 }
    147 }
    148