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