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