android-12.0.0_r34/s

/*
 * 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, TranscodingSessionTest) {
    // Test data structure that mimics the Transcoding session.
    struct TranscodingSession {
        int32_t priority;
        int64_t createTimeUs;
    };

    // The session is arranging according to priority with highest priority comes first.
    // For the session with the same priority, the session with early createTime will come first.
    class TranscodingSessionComp {
    public:
        bool operator()(const std::unique_ptr<TranscodingSession>& lhs,
                        const std::unique_ptr<TranscodingSession>& 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, TranscodingSession*> sessionIdToSessionMap;

    TranscodingSession testSessions[] = {
            {1 /*priority*/, 66 /*createTimeUs*/},  // First session,
            {2 /*priority*/, 67 /*createTimeUs*/},  // Second session,
            {2 /*priority*/, 66 /*createTimeUs*/},  // Third session,
            {3 /*priority*/, 68 /*createTimeUs*/},  // Fourth session.
    };

    AdjustableMaxPriorityQueue<std::unique_ptr<TranscodingSession>, TranscodingSessionComp>
            sessionQueue;

    // Pushes all the sessions into the heap.
    for (int sessionId = 0; sessionId < 4; ++sessionId) {
        auto newSession = std::make_unique<TranscodingSession>(testSessions[sessionId]);
        sessionIdToSessionMap[sessionId] = newSession.get();
        EXPECT_TRUE(sessionQueue.push(std::move(newSession)));
    }

    // Check the session queue size.
    EXPECT_EQ(4, sessionQueue.size());

    // Check the top and it should be Forth session: (3, 68)
    const std::unique_ptr<TranscodingSession>& topSession = sessionQueue.top();
    EXPECT_EQ(3, topSession->priority);
    EXPECT_EQ(68, topSession->createTimeUs);

    // Consume the top.
    std::unique_ptr<TranscodingSession> consumeSession = sessionQueue.consume_top();

    // Check the top and it should be Third Session (2, 66)
    const std::unique_ptr<TranscodingSession>& topSession2 = sessionQueue.top();
    EXPECT_EQ(2, topSession2->priority);
    EXPECT_EQ(66, topSession2->createTimeUs);

    // Change the Second session's priority to 4 from (2, 67) -> (4, 67). It should becomes
    // top of the queue.
    sessionIdToSessionMap[1]->priority = 4;
    sessionQueue.rebuild();
    const std::unique_ptr<TranscodingSession>& topSession3 = sessionQueue.top();
    EXPECT_EQ(4, topSession3->priority);
    EXPECT_EQ(67, topSession3->createTimeUs);
}
}  // namespace android