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