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