1 /*
2 * Copyright (C) 2020 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 // Unit Test for AdjustableMaxPriorityQueue
18
19 #define LOG_NDEBUG 0
20 #define LOG_TAG "AdjustableMaxPriorityQueueTest"
21
22 #include <android-base/logging.h>
23 #include <android/binder_manager.h>
24 #include <android/binder_process.h>
25 #include <gtest/gtest.h>
26 #include <media/AdjustableMaxPriorityQueue.h>
27 #include <utils/Log.h>
28
29 #include <algorithm>
30 #include <functional>
31 #include <iterator>
32 #include <list>
33 #include <queue>
34 #include <unordered_map>
35
36 namespace android {
37
38 class IntUniquePtrComp {
39 public:
operator ()(const std::unique_ptr<int> & lhs,const std::unique_ptr<int> & rhs) const40 bool operator()(const std::unique_ptr<int>& lhs, const std::unique_ptr<int>& rhs) const {
41 return *lhs < *rhs;
42 }
43 };
44
45 // Test the heap property and make sure it is the same as std::priority_queue.
TEST(AdjustableMaxPriorityQueueTest,BasicAPIS)46 TEST(AdjustableMaxPriorityQueueTest, BasicAPIS) {
47 AdjustableMaxPriorityQueue<std::pair<float, char*>> heap;
48 std::priority_queue<std::pair<float, char*>> pq;
49 AdjustableMaxPriorityQueue<std::pair<float, char*>> remove_queue;
50
51 // Push a set of values onto both AdjustableMaxPriorityQueue and priority_queue
52 // Also compute the sum of those values
53 double sum = 0;
54 for (int i = 0; i < 10; ++i) {
55 float value = 2.1 * i;
56 sum += value;
57 heap.push(std::pair<float, char*>(value, nullptr));
58 pq.push(std::pair<float, char*>(value, nullptr));
59 remove_queue.push(std::pair<float, char*>(value, nullptr));
60 }
61
62 // Test the iterator by using it to subtract all values from earlier sum
63 AdjustableMaxPriorityQueue<std::pair<float, char*>>::iterator it;
64 for (it = heap.begin(); it != heap.end(); ++it) {
65 sum -= it->first;
66 }
67 EXPECT_EQ(0, sum);
68
69 // Test the size();
70 EXPECT_EQ(10, heap.size());
71
72 // Testing pop() by popping values from both queues and compare if they are the same.
73 // Also check each pop is smaller than the previous pop max value.
74 float max = 1000;
75 while (!heap.empty()) {
76 float value = heap.top().first;
77 ALOGD("Value is %f ", value);
78 EXPECT_EQ(value, pq.top().first);
79 EXPECT_LE(value, max);
80 max = value;
81 heap.pop();
82 pq.pop();
83 }
84
85 // Test erase() by removing values and ensuring the heap
86 // condition is still met as miscellaneous elements are
87 // removed from the heap.
88 int iteration_mixer = 0;
89 float previous_value = remove_queue.top().first;
90
91 while (!remove_queue.empty()) {
92 int iteration_count = iteration_mixer % remove_queue.size();
93
94 AdjustableMaxPriorityQueue<std::pair<float, char*>>::iterator iterator =
95 remove_queue.begin();
96
97 // Empty loop as we just want to advance the iterator.
98 for (int i = 0; i < iteration_count; ++i, ++iterator) {
99 }
100
101 remove_queue.erase(iterator);
102 float value = remove_queue.top().first;
103 remove_queue.pop();
104
105 EXPECT_GE(previous_value, value);
106
107 ++iteration_mixer;
108 previous_value = value;
109 }
110 }
111
TEST(AdjustableMaxPriorityQueueTest,BasicWithMoveOnly)112 TEST(AdjustableMaxPriorityQueueTest, BasicWithMoveOnly) {
113 AdjustableMaxPriorityQueue<std::unique_ptr<int>, IntUniquePtrComp> heap;
114
115 auto smaller = std::make_unique<int>(1);
116 EXPECT_TRUE(heap.push(std::move(smaller)));
117 EXPECT_EQ(1, *heap.top());
118 EXPECT_EQ(1, heap.size());
119
120 auto bigger = std::make_unique<int>(2);
121 heap.push(std::move(bigger));
122 EXPECT_EQ(2, *heap.top());
123
124 auto biggest = std::make_unique<int>(3);
125 EXPECT_TRUE(heap.push(std::move(biggest)));
126
127 EXPECT_EQ(3, heap.size());
128 // Biggest should be on top.
129 EXPECT_EQ(3, *heap.top());
130
131 biggest = heap.consume_top();
132 EXPECT_EQ(3, *biggest);
133
134 bigger = heap.consume_top();
135 EXPECT_EQ(2, *bigger);
136
137 smaller = heap.consume_top();
138 EXPECT_EQ(1, *smaller);
139
140 EXPECT_TRUE(heap.empty());
141 }
142
TEST(AdjustableMaxPriorityQueueTest,TestChangingItem)143 TEST(AdjustableMaxPriorityQueueTest, TestChangingItem) {
144 AdjustableMaxPriorityQueue<std::unique_ptr<int>, IntUniquePtrComp> heap;
145 using HeapIterator =
146 AdjustableMaxPriorityQueue<std::unique_ptr<int>, IntUniquePtrComp>::iterator;
147
148 int testValues[] = {1, 2, 3};
149 // Map to save each value's position in the heap.
150 std::unordered_map<int, HeapIterator> itemToIterratorMap;
151
152 // Insert the test values into the heap.
153 for (auto value : testValues) {
154 auto item = std::make_unique<int>(value);
155 EXPECT_TRUE(heap.push(std::move(item)));
156 }
157
158 // Save each value and its pos in the heap into the map.
159 for (HeapIterator iter = heap.begin(); iter != heap.end(); iter++) {
160 itemToIterratorMap[*iter->get()] = iter;
161 }
162
163 // Change the item with value 1 -> 4. And expects the 4 to be the top of the HEAP after that.
164 // After changing, the heap should contain [2,3,4].
165 auto newValue = std::make_unique<int>(4);
166 itemToIterratorMap[1]->swap(newValue);
167 heap.rebuild();
168 EXPECT_EQ(4, *heap.top());
169
170 // Change the item with value 2 -> 5. And expects the 5 to be the top of the HEAP after that.
171 auto newValue2 = std::make_unique<int>(5);
172 itemToIterratorMap[2]->swap(newValue2);
173 heap.rebuild();
174 EXPECT_EQ(5, *heap.top());
175 }
176
TEST(AdjustableMaxPriorityQueueTest,TestErasingItem)177 TEST(AdjustableMaxPriorityQueueTest, TestErasingItem) {
178 AdjustableMaxPriorityQueue<std::unique_ptr<int>, IntUniquePtrComp> heap;
179 using HeapIterator =
180 AdjustableMaxPriorityQueue<std::unique_ptr<int>, IntUniquePtrComp>::iterator;
181
182 int testValues[] = {1, 2, 3};
183 // Map to save each value's position in the heap.
184 std::unordered_map<int, HeapIterator> itemToIterratorMap;
185
186 // Insert the test values into the heap.
187 for (auto value : testValues) {
188 auto item = std::make_unique<int>(value);
189 EXPECT_TRUE(heap.push(std::move(item)));
190 }
191
192 // Save each value and its pos in the heap into the map.
193 for (HeapIterator iter = heap.begin(); iter != heap.end(); iter++) {
194 itemToIterratorMap[*iter->get()] = iter;
195 }
196
197 // The top of the heap must be 3.
198 EXPECT_EQ(3, *heap.top());
199
200 // Remove 3 and the top of the heap should be 2.
201 heap.erase(itemToIterratorMap[3]);
202 EXPECT_EQ(2, *heap.top());
203
204 // Reset the iter pos in the heap.
205 itemToIterratorMap.clear();
206 for (HeapIterator iter = heap.begin(); iter != heap.end(); iter++) {
207 itemToIterratorMap[*iter->get()] = iter;
208 }
209
210 // Remove 2 and the top of the heap should be 1.
211 heap.erase(itemToIterratorMap[2]);
212 EXPECT_EQ(1, *heap.top());
213
214 // Reset the iter pos in the heap as iterator pos changed after
215 itemToIterratorMap.clear();
216 for (HeapIterator iter = heap.begin(); iter != heap.end(); iter++) {
217 itemToIterratorMap[*iter->get()] = iter;
218 }
219
220 // Remove 1 and the heap should be empty.
221 heap.erase(itemToIterratorMap[1]);
222 EXPECT_TRUE(heap.empty());
223 }
224
225 // Test the heap property and make sure it is the same as std::priority_queue.
TEST(AdjustableMaxPriorityQueueTest,TranscodingSessionTest)226 TEST(AdjustableMaxPriorityQueueTest, TranscodingSessionTest) {
227 // Test data structure that mimics the Transcoding session.
228 struct TranscodingSession {
229 int32_t priority;
230 int64_t createTimeUs;
231 };
232
233 // The session is arranging according to priority with highest priority comes first.
234 // For the session with the same priority, the session with early createTime will come first.
235 class TranscodingSessionComp {
236 public:
237 bool operator()(const std::unique_ptr<TranscodingSession>& lhs,
238 const std::unique_ptr<TranscodingSession>& rhs) const {
239 if (lhs->priority != rhs->priority) {
240 return lhs->priority < rhs->priority;
241 }
242 return lhs->createTimeUs > rhs->createTimeUs;
243 }
244 };
245
246 // Map to save each value's position in the heap.
247 std::unordered_map<int, TranscodingSession*> sessionIdToSessionMap;
248
249 TranscodingSession testSessions[] = {
250 {1 /*priority*/, 66 /*createTimeUs*/}, // First session,
251 {2 /*priority*/, 67 /*createTimeUs*/}, // Second session,
252 {2 /*priority*/, 66 /*createTimeUs*/}, // Third session,
253 {3 /*priority*/, 68 /*createTimeUs*/}, // Fourth session.
254 };
255
256 AdjustableMaxPriorityQueue<std::unique_ptr<TranscodingSession>, TranscodingSessionComp>
257 sessionQueue;
258
259 // Pushes all the sessions into the heap.
260 for (int sessionId = 0; sessionId < 4; ++sessionId) {
261 auto newSession = std::make_unique<TranscodingSession>(testSessions[sessionId]);
262 sessionIdToSessionMap[sessionId] = newSession.get();
263 EXPECT_TRUE(sessionQueue.push(std::move(newSession)));
264 }
265
266 // Check the session queue size.
267 EXPECT_EQ(4, sessionQueue.size());
268
269 // Check the top and it should be Forth session: (3, 68)
270 const std::unique_ptr<TranscodingSession>& topSession = sessionQueue.top();
271 EXPECT_EQ(3, topSession->priority);
272 EXPECT_EQ(68, topSession->createTimeUs);
273
274 // Consume the top.
275 std::unique_ptr<TranscodingSession> consumeSession = sessionQueue.consume_top();
276
277 // Check the top and it should be Third Session (2, 66)
278 const std::unique_ptr<TranscodingSession>& topSession2 = sessionQueue.top();
279 EXPECT_EQ(2, topSession2->priority);
280 EXPECT_EQ(66, topSession2->createTimeUs);
281
282 // Change the Second session's priority to 4 from (2, 67) -> (4, 67). It should becomes
283 // top of the queue.
284 sessionIdToSessionMap[1]->priority = 4;
285 sessionQueue.rebuild();
286 const std::unique_ptr<TranscodingSession>& topSession3 = sessionQueue.top();
287 EXPECT_EQ(4, topSession3->priority);
288 EXPECT_EQ(67, topSession3->createTimeUs);
289 }
290 } // namespace android