dic_node_priority_queue.h revision cf612a3abfd0cc244f8449db2cf11a0a7c680a2f
1/* 2 * Copyright (C) 2012 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#ifndef LATINIME_DIC_NODE_PRIORITY_QUEUE_H 18#define LATINIME_DIC_NODE_PRIORITY_QUEUE_H 19 20#include <algorithm> 21#include <queue> 22#include <vector> 23 24#include "defines.h" 25#include "suggest/core/dicnode/dic_node.h" 26#include "suggest/core/dicnode/dic_node_release_listener.h" 27 28namespace latinime { 29 30class DicNodePriorityQueue : public DicNodeReleaseListener { 31 public: 32 AK_FORCE_INLINE explicit DicNodePriorityQueue(const int capacity) 33 : mCapacity(capacity), mMaxSize(capacity), mDicNodesBuf(), 34 mUnusedNodeIndices(), mNextUnusedNodeId(0), mDicNodesQueue() { 35 mDicNodesBuf.resize(mCapacity + 1); 36 mUnusedNodeIndices.resize(mCapacity + 1); 37 clearAndResizeToCapacity(); 38 } 39 40 // Non virtual inline destructor -- never inherit this class 41 AK_FORCE_INLINE ~DicNodePriorityQueue() {} 42 43 int getSize() const { 44 return static_cast<int>(mDicNodesQueue.size()); 45 } 46 47 int getMaxSize() const { 48 return mMaxSize; 49 } 50 51 AK_FORCE_INLINE void setMaxSize(const int maxSize) { 52 ASSERT(maxSize <= mCapacity); 53 mMaxSize = std::min(maxSize, mCapacity); 54 } 55 56 AK_FORCE_INLINE void clearAndResizeToCapacity() { 57 clearAndResize(mCapacity); 58 } 59 60 AK_FORCE_INLINE void clear() { 61 clearAndResize(mMaxSize); 62 } 63 64 AK_FORCE_INLINE void clearAndResize(const int maxSize) { 65 ASSERT(maxSize <= mCapacity); 66 while (!mDicNodesQueue.empty()) { 67 mDicNodesQueue.pop(); 68 } 69 setMaxSize(maxSize); 70 for (int i = 0; i < mCapacity + 1; ++i) { 71 mDicNodesBuf[i].remove(); 72 mDicNodesBuf[i].setReleaseListener(this); 73 mUnusedNodeIndices[i] = i == mCapacity ? NOT_A_NODE_ID : static_cast<int>(i) + 1; 74 } 75 mNextUnusedNodeId = 0; 76 } 77 78 // Copy 79 AK_FORCE_INLINE DicNode *copyPush(DicNode *dicNode) { 80 return copyPush(dicNode, mMaxSize); 81 } 82 83 AK_FORCE_INLINE void copyPop(DicNode *dest) { 84 if (mDicNodesQueue.empty()) { 85 ASSERT(false); 86 return; 87 } 88 DicNode *node = mDicNodesQueue.top(); 89 if (dest) { 90 DicNodeUtils::initByCopy(node, dest); 91 } 92 node->remove(); 93 mDicNodesQueue.pop(); 94 } 95 96 void onReleased(DicNode *dicNode) { 97 const int index = static_cast<int>(dicNode - &mDicNodesBuf[0]); 98 if (mUnusedNodeIndices[index] != NOT_A_NODE_ID) { 99 // it's already released 100 return; 101 } 102 mUnusedNodeIndices[index] = mNextUnusedNodeId; 103 mNextUnusedNodeId = index; 104 ASSERT(index >= 0 && index < (mCapacity + 1)); 105 } 106 107 AK_FORCE_INLINE void dump() const { 108 AKLOGI("\n\n\n\n\n==========================="); 109 for (int i = 0; i < mCapacity + 1; ++i) { 110 if (mDicNodesBuf[i].isUsed()) { 111 mDicNodesBuf[i].dump("QUEUE: "); 112 } 113 } 114 AKLOGI("===========================\n\n\n\n\n"); 115 } 116 117 private: 118 DISALLOW_IMPLICIT_CONSTRUCTORS(DicNodePriorityQueue); 119 static const int NOT_A_NODE_ID = -1; 120 121 AK_FORCE_INLINE static bool compareDicNode(DicNode *left, DicNode *right) { 122 return left->compare(right); 123 } 124 125 struct DicNodeComparator { 126 bool operator ()(DicNode *left, DicNode *right) { 127 return compareDicNode(left, right); 128 } 129 }; 130 131 typedef std::priority_queue<DicNode *, std::vector<DicNode *>, DicNodeComparator> DicNodesQueue; 132 const int mCapacity; 133 int mMaxSize; 134 std::vector<DicNode> mDicNodesBuf; // of each element of mDicNodesBuf respectively 135 std::vector<int> mUnusedNodeIndices; 136 int mNextUnusedNodeId; 137 DicNodesQueue mDicNodesQueue; 138 139 inline bool isFull(const int maxSize) const { 140 return getSize() >= maxSize; 141 } 142 143 AK_FORCE_INLINE void pop() { 144 copyPop(0); 145 } 146 147 AK_FORCE_INLINE bool betterThanWorstDicNode(DicNode *dicNode) const { 148 DicNode *worstNode = mDicNodesQueue.top(); 149 if (!worstNode) { 150 return true; 151 } 152 return compareDicNode(dicNode, worstNode); 153 } 154 155 AK_FORCE_INLINE DicNode *searchEmptyDicNode() { 156 if (mCapacity == 0) { 157 return 0; 158 } 159 if (mNextUnusedNodeId == NOT_A_NODE_ID) { 160 AKLOGI("No unused node found."); 161 for (int i = 0; i < mCapacity + 1; ++i) { 162 AKLOGI("Dump node availability, %d, %d, %d", 163 i, mDicNodesBuf[i].isUsed(), mUnusedNodeIndices[i]); 164 } 165 ASSERT(false); 166 return 0; 167 } 168 DicNode *dicNode = &mDicNodesBuf[mNextUnusedNodeId]; 169 markNodeAsUsed(dicNode); 170 return dicNode; 171 } 172 173 AK_FORCE_INLINE void markNodeAsUsed(DicNode *dicNode) { 174 const int index = static_cast<int>(dicNode - &mDicNodesBuf[0]); 175 mNextUnusedNodeId = mUnusedNodeIndices[index]; 176 mUnusedNodeIndices[index] = NOT_A_NODE_ID; 177 ASSERT(index >= 0 && index < (mCapacity + 1)); 178 } 179 180 AK_FORCE_INLINE DicNode *pushPoolNodeWithMaxSize(DicNode *dicNode, const int maxSize) { 181 if (!dicNode) { 182 return 0; 183 } 184 if (!isFull(maxSize)) { 185 mDicNodesQueue.push(dicNode); 186 return dicNode; 187 } 188 if (betterThanWorstDicNode(dicNode)) { 189 pop(); 190 mDicNodesQueue.push(dicNode); 191 return dicNode; 192 } 193 dicNode->remove(); 194 return 0; 195 } 196 197 // Copy 198 AK_FORCE_INLINE DicNode *copyPush(DicNode *dicNode, const int maxSize) { 199 return pushPoolNodeWithMaxSize(newDicNode(dicNode), maxSize); 200 } 201 202 AK_FORCE_INLINE DicNode *newDicNode(DicNode *dicNode) { 203 DicNode *newNode = searchEmptyDicNode(); 204 if (newNode) { 205 DicNodeUtils::initByCopy(dicNode, newNode); 206 } 207 return newNode; 208 } 209 210}; 211} // namespace latinime 212#endif // LATINIME_DIC_NODE_PRIORITY_QUEUE_H 213