| /* |
| * Copyright (C) 2012 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. |
| */ |
| |
| #ifndef LATINIME_DIC_NODE_PRIORITY_QUEUE_H |
| #define LATINIME_DIC_NODE_PRIORITY_QUEUE_H |
| |
| #include <queue> |
| #include <vector> |
| |
| #include "defines.h" |
| #include "dic_node.h" |
| #include "dic_node_release_listener.h" |
| |
| #define MAX_DIC_NODE_PRIORITY_QUEUE_CAPACITY 200 |
| |
| namespace latinime { |
| |
| class DicNodePriorityQueue : public DicNodeReleaseListener { |
| public: |
| AK_FORCE_INLINE DicNodePriorityQueue() |
| : MAX_CAPACITY(MAX_DIC_NODE_PRIORITY_QUEUE_CAPACITY), |
| mMaxSize(MAX_DIC_NODE_PRIORITY_QUEUE_CAPACITY), mDicNodesBuf(), mUnusedNodeIndices(), |
| mNextUnusedNodeId(0), mDicNodesQueue() { |
| mDicNodesBuf.resize(MAX_CAPACITY + 1); |
| mUnusedNodeIndices.resize(MAX_CAPACITY + 1); |
| reset(); |
| } |
| |
| // Non virtual inline destructor -- never inherit this class |
| AK_FORCE_INLINE ~DicNodePriorityQueue() {} |
| |
| int getSize() const { |
| return static_cast<int>(mDicNodesQueue.size()); |
| } |
| |
| int getMaxSize() const { |
| return mMaxSize; |
| } |
| |
| AK_FORCE_INLINE void setMaxSize(const int maxSize) { |
| mMaxSize = min(maxSize, MAX_CAPACITY); |
| } |
| |
| AK_FORCE_INLINE void reset() { |
| clearAndResize(MAX_CAPACITY); |
| } |
| |
| AK_FORCE_INLINE void clear() { |
| clearAndResize(mMaxSize); |
| } |
| |
| AK_FORCE_INLINE void clearAndResize(const int maxSize) { |
| while (!mDicNodesQueue.empty()) { |
| mDicNodesQueue.pop(); |
| } |
| setMaxSize(maxSize); |
| for (int i = 0; i < MAX_CAPACITY + 1; ++i) { |
| mDicNodesBuf[i].remove(); |
| mDicNodesBuf[i].setReleaseListener(this); |
| mUnusedNodeIndices[i] = i == MAX_CAPACITY ? NOT_A_NODE_ID : static_cast<int>(i) + 1; |
| } |
| mNextUnusedNodeId = 0; |
| } |
| |
| AK_FORCE_INLINE DicNode *newDicNode(DicNode *dicNode) { |
| DicNode *newNode = searchEmptyDicNode(); |
| if (newNode) { |
| DicNodeUtils::initByCopy(dicNode, newNode); |
| return newNode; |
| } |
| return 0; |
| } |
| |
| // Copy |
| AK_FORCE_INLINE DicNode *copyPush(DicNode *dicNode) { |
| return copyPush(dicNode, mMaxSize); |
| } |
| |
| AK_FORCE_INLINE void copyPop(DicNode *dest) { |
| if (mDicNodesQueue.empty()) { |
| ASSERT(false); |
| return; |
| } |
| DicNode *node = mDicNodesQueue.top(); |
| if (dest) { |
| DicNodeUtils::initByCopy(node, dest); |
| } |
| node->remove(); |
| mDicNodesQueue.pop(); |
| } |
| |
| void onReleased(DicNode *dicNode) { |
| const int index = static_cast<int>(dicNode - &mDicNodesBuf[0]); |
| if (mUnusedNodeIndices[index] != NOT_A_NODE_ID) { |
| // it's already released |
| return; |
| } |
| mUnusedNodeIndices[index] = mNextUnusedNodeId; |
| mNextUnusedNodeId = index; |
| ASSERT(index >= 0 && index < (MAX_CAPACITY + 1)); |
| } |
| |
| AK_FORCE_INLINE void dump() const { |
| AKLOGI("\n\n\n\n\n==========================="); |
| for (int i = 0; i < MAX_CAPACITY + 1; ++i) { |
| if (mDicNodesBuf[i].isUsed()) { |
| mDicNodesBuf[i].dump("QUEUE: "); |
| } |
| } |
| AKLOGI("===========================\n\n\n\n\n"); |
| } |
| |
| private: |
| DISALLOW_COPY_AND_ASSIGN(DicNodePriorityQueue); |
| static const int NOT_A_NODE_ID = -1; |
| |
| AK_FORCE_INLINE static bool compareDicNode(DicNode *left, DicNode *right) { |
| return left->compare(right); |
| } |
| |
| struct DicNodeComparator { |
| bool operator ()(DicNode *left, DicNode *right) { |
| return compareDicNode(left, right); |
| } |
| }; |
| |
| typedef std::priority_queue<DicNode *, std::vector<DicNode *>, DicNodeComparator> DicNodesQueue; |
| const int MAX_CAPACITY; |
| int mMaxSize; |
| std::vector<DicNode> mDicNodesBuf; // of each element of mDicNodesBuf respectively |
| std::vector<int> mUnusedNodeIndices; |
| int mNextUnusedNodeId; |
| DicNodesQueue mDicNodesQueue; |
| |
| inline bool isFull(const int maxSize) const { |
| return getSize() >= maxSize; |
| } |
| |
| AK_FORCE_INLINE void pop() { |
| copyPop(0); |
| } |
| |
| AK_FORCE_INLINE bool betterThanWorstDicNode(DicNode *dicNode) const { |
| DicNode *worstNode = mDicNodesQueue.top(); |
| if (!worstNode) { |
| return true; |
| } |
| return compareDicNode(dicNode, worstNode); |
| } |
| |
| AK_FORCE_INLINE DicNode *searchEmptyDicNode() { |
| // TODO: Currently O(n) but should be improved to O(1) |
| if (MAX_CAPACITY == 0) { |
| return 0; |
| } |
| if (mNextUnusedNodeId == NOT_A_NODE_ID) { |
| AKLOGI("No unused node found."); |
| for (int i = 0; i < MAX_CAPACITY + 1; ++i) { |
| AKLOGI("Dump node availability, %d, %d, %d", |
| i, mDicNodesBuf[i].isUsed(), mUnusedNodeIndices[i]); |
| } |
| ASSERT(false); |
| return 0; |
| } |
| DicNode *dicNode = &mDicNodesBuf[mNextUnusedNodeId]; |
| markNodeAsUsed(dicNode); |
| return dicNode; |
| } |
| |
| AK_FORCE_INLINE void markNodeAsUsed(DicNode *dicNode) { |
| const int index = static_cast<int>(dicNode - &mDicNodesBuf[0]); |
| mNextUnusedNodeId = mUnusedNodeIndices[index]; |
| mUnusedNodeIndices[index] = NOT_A_NODE_ID; |
| ASSERT(index >= 0 && index < (MAX_CAPACITY + 1)); |
| } |
| |
| AK_FORCE_INLINE DicNode *pushPoolNodeWithMaxSize(DicNode *dicNode, const int maxSize) { |
| if (!dicNode) { |
| return 0; |
| } |
| if (!isFull(maxSize)) { |
| mDicNodesQueue.push(dicNode); |
| return dicNode; |
| } |
| if (betterThanWorstDicNode(dicNode)) { |
| pop(); |
| mDicNodesQueue.push(dicNode); |
| return dicNode; |
| } |
| dicNode->remove(); |
| return 0; |
| } |
| |
| // Copy |
| AK_FORCE_INLINE DicNode *copyPush(DicNode *dicNode, const int maxSize) { |
| return pushPoolNodeWithMaxSize(newDicNode(dicNode), maxSize); |
| } |
| }; |
| } // namespace latinime |
| #endif // LATINIME_DIC_NODE_PRIORITY_QUEUE_H |