MediaTranscodingService: Add AdjustableMaxPriorityQueue.
AdjustableMaxPriorityQueue is a custom max priority queue that helps managing jobs for MediaTranscodingService.
AdjustableMaxPriorityQueue is a wrapper template around the STL's *_heap() functions.
- Internally, it uses a std::vector<T> to store elements in a heap order.
- Support adjusting item's priority while maintaining the heap property.
- Support removing any item in the heap while maintaining the heap property.
- AdjustableMaxPriorityQueue needs T::operator<() at instantiation time
Bug: 145233472
Test: Unit test.
Change-Id: Ic43eee817877dfbf8b38919ce03d40d8763c493c
diff --git a/media/libmediatranscoding/tests/AdjustableMaxPriorityQueue_tests.cpp b/media/libmediatranscoding/tests/AdjustableMaxPriorityQueue_tests.cpp
new file mode 100644
index 0000000..d58af4e
--- /dev/null
+++ b/media/libmediatranscoding/tests/AdjustableMaxPriorityQueue_tests.cpp
@@ -0,0 +1,289 @@
+/*
+ * Copyright (C) 2020 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+// Unit Test for AdjustableMaxPriorityQueue
+
+#define LOG_NDEBUG 0
+#define LOG_TAG "AdjustableMaxPriorityQueueTest"
+
+#include <android-base/logging.h>
+#include <android/binder_manager.h>
+#include <android/binder_process.h>
+#include <gtest/gtest.h>
+#include <media/AdjustableMaxPriorityQueue.h>
+#include <utils/Log.h>
+
+#include <algorithm>
+#include <functional>
+#include <iterator>
+#include <list>
+#include <queue>
+#include <unordered_map>
+
+namespace android {
+
+class IntUniquePtrComp {
+ public:
+ bool operator()(const std::unique_ptr<int>& lhs, const std::unique_ptr<int>& rhs) const {
+ return *lhs < *rhs;
+ }
+};
+
+// Test the heap property and make sure it is the same as std::priority_queue.
+TEST(AdjustableMaxPriorityQueueTest, BasicAPIS) {
+ AdjustableMaxPriorityQueue<std::pair<float, char*>> heap;
+ std::priority_queue<std::pair<float, char*>> pq;
+ AdjustableMaxPriorityQueue<std::pair<float, char*>> remove_queue;
+
+ // Push a set of values onto both AdjustableMaxPriorityQueue and priority_queue
+ // Also compute the sum of those values
+ double sum = 0;
+ for (int i = 0; i < 10; ++i) {
+ float value = 2.1 * i;
+ sum += value;
+ heap.push(std::pair<float, char*>(value, nullptr));
+ pq.push(std::pair<float, char*>(value, nullptr));
+ remove_queue.push(std::pair<float, char*>(value, nullptr));
+ }
+
+ // Test the iterator by using it to subtract all values from earlier sum
+ AdjustableMaxPriorityQueue<std::pair<float, char*>>::iterator it;
+ for (it = heap.begin(); it != heap.end(); ++it) {
+ sum -= it->first;
+ }
+ EXPECT_EQ(0, sum);
+
+ // Test the size();
+ EXPECT_EQ(10, heap.size());
+
+ // Testing pop() by popping values from both queues and compare if they are the same.
+ // Also check each pop is smaller than the previous pop max value.
+ float max = 1000;
+ while (!heap.empty()) {
+ float value = heap.top().first;
+ ALOGD("Value is %f ", value);
+ EXPECT_EQ(value, pq.top().first);
+ EXPECT_LE(value, max);
+ max = value;
+ heap.pop();
+ pq.pop();
+ }
+
+ // Test erase() by removing values and ensuring the heap
+ // condition is still met as miscellaneous elements are
+ // removed from the heap.
+ int iteration_mixer = 0;
+ float previous_value = remove_queue.top().first;
+
+ while (!remove_queue.empty()) {
+ int iteration_count = iteration_mixer % remove_queue.size();
+
+ AdjustableMaxPriorityQueue<std::pair<float, char*>>::iterator iterator =
+ remove_queue.begin();
+
+ // Empty loop as we just want to advance the iterator.
+ for (int i = 0; i < iteration_count; ++i, ++iterator) {
+ }
+
+ remove_queue.erase(iterator);
+ float value = remove_queue.top().first;
+ remove_queue.pop();
+
+ EXPECT_GE(previous_value, value);
+
+ ++iteration_mixer;
+ previous_value = value;
+ }
+}
+
+TEST(AdjustableMaxPriorityQueueTest, BasicWithMoveOnly) {
+ AdjustableMaxPriorityQueue<std::unique_ptr<int>, IntUniquePtrComp> heap;
+
+ auto smaller = std::make_unique<int>(1);
+ EXPECT_TRUE(heap.push(std::move(smaller)));
+ EXPECT_EQ(1, *heap.top());
+ EXPECT_EQ(1, heap.size());
+
+ auto bigger = std::make_unique<int>(2);
+ heap.push(std::move(bigger));
+ EXPECT_EQ(2, *heap.top());
+
+ auto biggest = std::make_unique<int>(3);
+ EXPECT_TRUE(heap.push(std::move(biggest)));
+
+ EXPECT_EQ(3, heap.size());
+ // Biggest should be on top.
+ EXPECT_EQ(3, *heap.top());
+
+ biggest = heap.consume_top();
+ EXPECT_EQ(3, *biggest);
+
+ bigger = heap.consume_top();
+ EXPECT_EQ(2, *bigger);
+
+ smaller = heap.consume_top();
+ EXPECT_EQ(1, *smaller);
+
+ EXPECT_TRUE(heap.empty());
+}
+
+TEST(AdjustableMaxPriorityQueueTest, TestChangingItem) {
+ AdjustableMaxPriorityQueue<std::unique_ptr<int>, IntUniquePtrComp> heap;
+ using HeapIterator =
+ AdjustableMaxPriorityQueue<std::unique_ptr<int>, IntUniquePtrComp>::iterator;
+
+ int testValues[] = {1, 2, 3};
+ // Map to save each value's position in the heap.
+ std::unordered_map<int, HeapIterator> itemToIterratorMap;
+
+ // Insert the test values into the heap.
+ for (auto value : testValues) {
+ auto item = std::make_unique<int>(value);
+ EXPECT_TRUE(heap.push(std::move(item)));
+ }
+
+ // Save each value and its pos in the heap into the map.
+ for (HeapIterator iter = heap.begin(); iter != heap.end(); iter++) {
+ itemToIterratorMap[*iter->get()] = iter;
+ }
+
+ // Change the item with value 1 -> 4. And expects the 4 to be the top of the HEAP after that.
+ // After changing, the heap should contain [2,3,4].
+ auto newValue = std::make_unique<int>(4);
+ itemToIterratorMap[1]->swap(newValue);
+ heap.rebuild();
+ EXPECT_EQ(4, *heap.top());
+
+ // Change the item with value 2 -> 5. And expects the 5 to be the top of the HEAP after that.
+ auto newValue2 = std::make_unique<int>(5);
+ itemToIterratorMap[2]->swap(newValue2);
+ heap.rebuild();
+ EXPECT_EQ(5, *heap.top());
+}
+
+TEST(AdjustableMaxPriorityQueueTest, TestErasingItem) {
+ AdjustableMaxPriorityQueue<std::unique_ptr<int>, IntUniquePtrComp> heap;
+ using HeapIterator =
+ AdjustableMaxPriorityQueue<std::unique_ptr<int>, IntUniquePtrComp>::iterator;
+
+ int testValues[] = {1, 2, 3};
+ // Map to save each value's position in the heap.
+ std::unordered_map<int, HeapIterator> itemToIterratorMap;
+
+ // Insert the test values into the heap.
+ for (auto value : testValues) {
+ auto item = std::make_unique<int>(value);
+ EXPECT_TRUE(heap.push(std::move(item)));
+ }
+
+ // Save each value and its pos in the heap into the map.
+ for (HeapIterator iter = heap.begin(); iter != heap.end(); iter++) {
+ itemToIterratorMap[*iter->get()] = iter;
+ }
+
+ // The top of the heap must be 3.
+ EXPECT_EQ(3, *heap.top());
+
+ // Remove 3 and the top of the heap should be 2.
+ heap.erase(itemToIterratorMap[3]);
+ EXPECT_EQ(2, *heap.top());
+
+ // Reset the iter pos in the heap.
+ itemToIterratorMap.clear();
+ for (HeapIterator iter = heap.begin(); iter != heap.end(); iter++) {
+ itemToIterratorMap[*iter->get()] = iter;
+ }
+
+ // Remove 2 and the top of the heap should be 1.
+ heap.erase(itemToIterratorMap[2]);
+ EXPECT_EQ(1, *heap.top());
+
+ // Reset the iter pos in the heap as iterator pos changed after
+ itemToIterratorMap.clear();
+ for (HeapIterator iter = heap.begin(); iter != heap.end(); iter++) {
+ itemToIterratorMap[*iter->get()] = iter;
+ }
+
+ // Remove 1 and the heap should be empty.
+ heap.erase(itemToIterratorMap[1]);
+ EXPECT_TRUE(heap.empty());
+}
+
+// Test the heap property and make sure it is the same as std::priority_queue.
+TEST(AdjustableMaxPriorityQueueTest, TranscodingJobTest) {
+ // Test data structure that mimics the Transcoding job.
+ struct TranscodingJob {
+ int32_t priority;
+ int64_t createTimeUs;
+ };
+
+ // The job is arranging according to priority with highest priority comes first.
+ // For the job with the same priority, the job with early createTime will come first.
+ class TranscodingJobComp {
+ public:
+ bool operator()(const std::unique_ptr<TranscodingJob>& lhs,
+ const std::unique_ptr<TranscodingJob>& rhs) const {
+ if (lhs->priority != rhs->priority) {
+ return lhs->priority < rhs->priority;
+ }
+ return lhs->createTimeUs > rhs->createTimeUs;
+ }
+ };
+
+ // Map to save each value's position in the heap.
+ std::unordered_map<int, TranscodingJob*> jobIdToJobMap;
+
+ TranscodingJob testJobs[] = {
+ {1 /*priority*/, 66 /*createTimeUs*/}, // First job,
+ {2 /*priority*/, 67 /*createTimeUs*/}, // Second job,
+ {2 /*priority*/, 66 /*createTimeUs*/}, // Third job,
+ {3 /*priority*/, 68 /*createTimeUs*/}, // Fourth job.
+ };
+
+ AdjustableMaxPriorityQueue<std::unique_ptr<TranscodingJob>, TranscodingJobComp> jobQueue;
+
+ // Pushes all the jobs into the heap.
+ for (int jobId = 0; jobId < 4; ++jobId) {
+ auto newJob = std::make_unique<TranscodingJob>(testJobs[jobId]);
+ jobIdToJobMap[jobId] = newJob.get();
+ EXPECT_TRUE(jobQueue.push(std::move(newJob)));
+ }
+
+ // Check the job queue size.
+ EXPECT_EQ(4, jobQueue.size());
+
+ // Check the top and it should be Forth job: (3, 68)
+ const std::unique_ptr<TranscodingJob>& topJob = jobQueue.top();
+ EXPECT_EQ(3, topJob->priority);
+ EXPECT_EQ(68, topJob->createTimeUs);
+
+ // Consume the top.
+ std::unique_ptr<TranscodingJob> consumeJob = jobQueue.consume_top();
+
+ // Check the top and it should be Third Job (2, 66)
+ const std::unique_ptr<TranscodingJob>& topJob2 = jobQueue.top();
+ EXPECT_EQ(2, topJob2->priority);
+ EXPECT_EQ(66, topJob2->createTimeUs);
+
+ // Change the Second job's priority to 4 from (2, 67) -> (4, 67). It should becomes top of the
+ // queue.
+ jobIdToJobMap[1]->priority = 4;
+ jobQueue.rebuild();
+ const std::unique_ptr<TranscodingJob>& topJob3 = jobQueue.top();
+ EXPECT_EQ(4, topJob3->priority);
+ EXPECT_EQ(67, topJob3->createTimeUs);
+}
+} // namespace android
\ No newline at end of file
diff --git a/media/libmediatranscoding/tests/Android.bp b/media/libmediatranscoding/tests/Android.bp
index f3cc4c5..8191b00 100644
--- a/media/libmediatranscoding/tests/Android.bp
+++ b/media/libmediatranscoding/tests/Android.bp
@@ -35,4 +35,14 @@
defaults: ["libmediatranscoding_test_defaults"],
srcs: ["TranscodingClientManager_tests.cpp"],
+}
+
+//
+// AdjustableMaxPriorityQueue unit test
+//
+cc_test {
+ name: "AdjustableMaxPriorityQueue_tests",
+ defaults: ["libmediatranscoding_test_defaults"],
+
+ srcs: ["AdjustableMaxPriorityQueue_tests.cpp"],
}
\ No newline at end of file
diff --git a/media/libmediatranscoding/tests/build_and_run_all_unit_tests.sh b/media/libmediatranscoding/tests/build_and_run_all_unit_tests.sh
index 9832696..d8e4830 100644
--- a/media/libmediatranscoding/tests/build_and_run_all_unit_tests.sh
+++ b/media/libmediatranscoding/tests/build_and_run_all_unit_tests.sh
@@ -21,3 +21,6 @@
echo "testing TranscodingClientManager"
adb shell /data/nativetest64/TranscodingClientManager_tests/TranscodingClientManager_tests
+
+echo "testing AdjustableMaxPriorityQueue"
+adb shell /data/nativetest64/AdjustableMaxPriorityQueue_tests/AdjustableMaxPriorityQueue_tests