xref: /aosp_15_r20/system/chre/util/tests/segmented_queue_test.cc (revision 84e339476a462649f82315436d70fd732297a399)

/*
 * Copyright (C) 2022 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.
 */

#include "chre/util/segmented_queue.h"

#include <cstdlib>
#include <deque>
#include <vector>

#include "chre/util/enum.h"
#include "chre/util/nested_data_ptr.h"
#include "chre/util/non_copyable.h"
#include "gtest/gtest.h"

using ::chre::NestedDataPtr;
using ::chre::SegmentedQueue;
using ::std::deque;
using ::std::vector;

namespace {

class ConstructorCount {
 public:
  ConstructorCount() = default;
  ConstructorCount(int value_, ssize_t *constructedCount)
      : sConstructedCounter(constructedCount), value(value_) {
    (*sConstructedCounter)++;
  }
  ~ConstructorCount() {
    (*sConstructedCounter)--;
  }
  int getValue() {
    return value;
  }

  ssize_t *sConstructedCounter;

 private:
  int value;
};

constexpr int kConstructedMagic = 0xdeadbeef;
class CopyableButNonMovable {
 public:
  CopyableButNonMovable(int value) : mValue(value) {}

  CopyableButNonMovable(const CopyableButNonMovable &other) {
    mValue = other.mValue;
  }

  CopyableButNonMovable &operator=(const CopyableButNonMovable &other) {
    CHRE_ASSERT(mMagic == kConstructedMagic);
    mValue = other.mValue;
    return *this;
  }

  CopyableButNonMovable(CopyableButNonMovable &&other) = delete;
  CopyableButNonMovable &operator=(CopyableButNonMovable &&other) = delete;

  int getValue() const {
    return mValue;
  }

 private:
  int mMagic = kConstructedMagic;
  int mValue;
};

class MovableButNonCopyable : public chre::NonCopyable {
 public:
  MovableButNonCopyable(int value) : mValue(value) {}

  MovableButNonCopyable(MovableButNonCopyable &&other) {
    mValue = other.mValue;
    other.mValue = -1;
  }

  MovableButNonCopyable &operator=(MovableButNonCopyable &&other) {
    CHRE_ASSERT(mMagic == kConstructedMagic);
    mValue = other.mValue;
    other.mValue = -1;
    return *this;
  }

  int getValue() const {
    return mValue;
  }

 private:
  int mMagic = kConstructedMagic;
  int mValue;
};

enum class OperationType : uint8_t {
  EMPLACE_BACK = 0,
  PUSH_BACK,
  POP_FRONT,
  REMOVE,
  BATCH_REMOVE,

  OPERATION_TYPE_COUNT,  // Must be at the end.
};

}  // namespace

TEST(SegmentedQueue, InitialzedState) {
  constexpr uint8_t blockSize = 5;
  constexpr uint8_t maxBlockCount = 3;
  constexpr uint8_t staticBlockCount = 2;
  SegmentedQueue<int, blockSize> segmentedQueue(maxBlockCount,
                                                staticBlockCount);

  EXPECT_EQ(segmentedQueue.block_count(), staticBlockCount);
  EXPECT_EQ(segmentedQueue.capacity(), staticBlockCount * blockSize);
  EXPECT_EQ(segmentedQueue.size(), 0);
}

TEST(SegmentedQueue, PushAndRead) {
  constexpr uint8_t blockSize = 5;
  constexpr uint8_t maxBlockCount = 3;
  SegmentedQueue<int, blockSize> segmentedQueue(maxBlockCount);

  for (uint32_t queueSize = 0; queueSize < blockSize * maxBlockCount;
       queueSize++) {
    EXPECT_TRUE(segmentedQueue.push_back(queueSize));
    EXPECT_EQ(segmentedQueue.size(), queueSize + 1);
    EXPECT_EQ(segmentedQueue[queueSize], queueSize);
    EXPECT_EQ(segmentedQueue.back(), queueSize);
  }

  EXPECT_FALSE(segmentedQueue.push_back(10000));
  EXPECT_EQ(segmentedQueue.size(), maxBlockCount * blockSize);
  EXPECT_TRUE(segmentedQueue.full());
}

TEST(SegmentedQueue, EmplaceAndRead) {
  constexpr uint8_t blockSize = 5;
  constexpr uint8_t maxBlockCount = 3;
  ssize_t constructorCount = 0;
  SegmentedQueue<ConstructorCount, blockSize> segmentedQueue(maxBlockCount);

  for (uint32_t queueSize = 0; queueSize < blockSize * maxBlockCount;
       queueSize++) {
    ssize_t oldConstructedCounter = constructorCount;
    EXPECT_TRUE(segmentedQueue.emplace_back(queueSize, &constructorCount));
    EXPECT_EQ(segmentedQueue.size(), queueSize + 1);
    EXPECT_EQ(segmentedQueue[queueSize].getValue(), queueSize);
    EXPECT_EQ(segmentedQueue.back().getValue(), queueSize);
    EXPECT_EQ(constructorCount, oldConstructedCounter + 1);
  }

  EXPECT_FALSE(segmentedQueue.emplace_back(10000, &constructorCount));
  EXPECT_EQ(segmentedQueue.size(), maxBlockCount * blockSize);
  EXPECT_TRUE(segmentedQueue.full());
}

TEST(SegmentedQueue, PushAndReadCopyableButNonMovable) {
  constexpr uint8_t blockSize = 5;
  constexpr uint8_t maxBlockCount = 3;
  SegmentedQueue<CopyableButNonMovable, blockSize> segmentedQueue(
      maxBlockCount);

  for (uint32_t queueSize = 0; queueSize < blockSize * maxBlockCount;
       queueSize++) {
    CopyableButNonMovable cbnm(queueSize);
    EXPECT_TRUE(segmentedQueue.push_back(cbnm));
    EXPECT_EQ(segmentedQueue.size(), queueSize + 1);
    EXPECT_EQ(segmentedQueue[queueSize].getValue(), queueSize);
    EXPECT_EQ(segmentedQueue.back().getValue(), queueSize);
  }
}

TEST(SegmentedQueue, PushAndReadMovableButNonCopyable) {
  constexpr uint8_t blockSize = 5;
  constexpr uint8_t maxBlockCount = 3;
  SegmentedQueue<MovableButNonCopyable, blockSize> segmentedQueue(
      maxBlockCount);

  for (uint8_t blockIndex = 0; blockIndex < maxBlockCount; blockIndex++) {
    for (uint8_t index = 0; index < blockSize; index++) {
      int value = segmentedQueue.size();
      EXPECT_TRUE(segmentedQueue.emplace_back(value));
      EXPECT_EQ(segmentedQueue.size(), value + 1);
      EXPECT_EQ(segmentedQueue[value].getValue(), value);
      EXPECT_EQ(segmentedQueue.back().getValue(), value);
    }
  }
}

TEST(SegmentedQueue, ReadAndPop) {
  constexpr uint8_t blockSize = 5;
  constexpr uint8_t maxBlockCount = 3;
  SegmentedQueue<ConstructorCount, blockSize> segmentedQueue(maxBlockCount);
  ssize_t constructedCounter = 0;

  for (uint32_t index = 0; index < blockSize * maxBlockCount; index++) {
    EXPECT_TRUE(segmentedQueue.emplace_back(index, &constructedCounter));
  }

  uint8_t originalQueueSize = segmentedQueue.size();
  for (uint8_t index = 0; index < originalQueueSize; index++) {
    EXPECT_EQ(segmentedQueue[index].getValue(), index);
  }

  size_t capacityBeforePop = segmentedQueue.capacity();
  while (!segmentedQueue.empty()) {
    ASSERT_EQ(segmentedQueue.front().getValue(),
              originalQueueSize - segmentedQueue.size());
    ssize_t oldConstructedCounter = constructedCounter;
    segmentedQueue.pop_front();
    EXPECT_EQ(oldConstructedCounter - 1, constructedCounter);
  }

  EXPECT_EQ(segmentedQueue.size(), 0);
  EXPECT_TRUE(segmentedQueue.empty());
  EXPECT_LT(segmentedQueue.capacity(), capacityBeforePop);
  EXPECT_GT(segmentedQueue.capacity(), 0);
}

TEST(SegmentedQueue, RemoveTest) {
  constexpr uint8_t blockSize = 2;
  constexpr uint8_t maxBlockCount = 3;
  SegmentedQueue<int, blockSize> segmentedQueue(maxBlockCount);

  for (uint32_t index = 0; index < blockSize * maxBlockCount; index++) {
    EXPECT_TRUE(segmentedQueue.push_back(index));
  }

  // segmentedQueue = [[0, 1], [2, 3], [4, 5]]
  EXPECT_FALSE(segmentedQueue.remove(segmentedQueue.size()));

  EXPECT_TRUE(segmentedQueue.remove(4));
  EXPECT_EQ(segmentedQueue[4], 5);
  EXPECT_EQ(segmentedQueue[3], 3);
  EXPECT_EQ(segmentedQueue.size(), 5);

  EXPECT_TRUE(segmentedQueue.remove(1));
  EXPECT_EQ(segmentedQueue[3], 5);
  EXPECT_EQ(segmentedQueue[1], 2);
  EXPECT_EQ(segmentedQueue[0], 0);
  EXPECT_EQ(segmentedQueue.size(), 4);

  size_t currentSize = segmentedQueue.size();
  size_t capacityBeforeRemove = segmentedQueue.capacity();
  while (currentSize--) {
    EXPECT_TRUE(segmentedQueue.remove(0));
  }

  EXPECT_EQ(segmentedQueue.size(), 0);
  EXPECT_TRUE(segmentedQueue.empty());
  EXPECT_LT(segmentedQueue.capacity(), capacityBeforeRemove);
  EXPECT_GT(segmentedQueue.capacity(), 0);
}

TEST(SegmentedQueue, MiddleBlockTest) {
  // This test tests that the SegmentedQueue will behave correctly when
  // the reference of front() and back() are not aligned to the head/back
  // of a block.

  constexpr uint8_t blockSize = 3;
  constexpr uint8_t maxBlockCount = 3;
  SegmentedQueue<int, blockSize> segmentedQueue(maxBlockCount);

  for (uint32_t index = 0; index < blockSize * (maxBlockCount - 1); index++) {
    EXPECT_TRUE(segmentedQueue.push_back(index));
  }

  segmentedQueue.pop_front();
  segmentedQueue.pop_front();
  EXPECT_TRUE(segmentedQueue.push_back(6));
  EXPECT_TRUE(segmentedQueue.push_back(7));

  // segmentedQueue = [[6, 7, 2], [3, 4, 5], [X]]
  EXPECT_EQ(segmentedQueue.front(), 2);
  EXPECT_EQ(segmentedQueue.back(), 7);

  EXPECT_TRUE(segmentedQueue.push_back(8));
  EXPECT_EQ(segmentedQueue.back(), 8);

  // segmentedQueue = [[x, x, 2], [3, 4, 5], [6, 7, 8]]
  EXPECT_TRUE(segmentedQueue.push_back(9));
  EXPECT_TRUE(segmentedQueue.push_back(10));

  for (int i = 0; i < segmentedQueue.size(); i++) {
    EXPECT_EQ(segmentedQueue[i], i + 2);
  }
}

TEST(SegmentedQueue, RemoveMatchesEnoughItem) {
  constexpr uint8_t blockSize = 3;
  constexpr uint8_t maxBlockCount = 2;
  ssize_t constCounter = 0;
  SegmentedQueue<ConstructorCount, blockSize> segmentedQueue(maxBlockCount);

  for (uint32_t index = 0; index < blockSize * maxBlockCount; index++) {
    EXPECT_TRUE(segmentedQueue.emplace_back(index, &constCounter));
  }

  EXPECT_EQ(3, segmentedQueue.removeMatchedFromBack(
                   [](ConstructorCount &element, void *data, void *extraData) {
                     NestedDataPtr<int> targetValue(data);
                     NestedDataPtr<int> targetValue2(extraData);
                     return element.getValue() <= targetValue + targetValue2;
                   },
                   /* data= */ NestedDataPtr<int>(2),
                   /* extraData= */ NestedDataPtr<int>(2), 3));

  EXPECT_EQ(segmentedQueue[0].getValue(), 0);
  EXPECT_EQ(segmentedQueue[1].getValue(), 1);
  EXPECT_EQ(segmentedQueue[2].getValue(), 5);
  EXPECT_EQ(segmentedQueue.size(), blockSize * maxBlockCount - 3);
  EXPECT_EQ(segmentedQueue.front().getValue(), 0);
  EXPECT_EQ(segmentedQueue.back().getValue(), 5);
  EXPECT_EQ(constCounter, 3);
}

TEST(SegmentedQueue, RemoveMatchesEmptyQueue) {
  constexpr uint8_t blockSize = 5;
  constexpr uint8_t maxBlockCount = 2;
  SegmentedQueue<int, blockSize> segmentedQueue(maxBlockCount);

  EXPECT_EQ(0, segmentedQueue.removeMatchedFromBack(
                   [](int element, void * /* data */, void * /* extraData */) {
                     return element >= 5;
                   },
                   /* data= */ nullptr, /* extraData= */ nullptr, 3));
  EXPECT_EQ(segmentedQueue.size(), 0);
}

TEST(SegmentedQueue, RemoveMatchesSingleElementQueue) {
  constexpr uint8_t blockSize = 5;
  constexpr uint8_t maxBlockCount = 2;
  SegmentedQueue<int, blockSize> segmentedQueue(maxBlockCount);

  EXPECT_TRUE(segmentedQueue.push_back(1));

  EXPECT_EQ(1, segmentedQueue.removeMatchedFromBack(
                   [](int element, void * /* data */, void * /* extraData */) {
                     return element == 1;
                   },
                   /* data= */ nullptr, /* extraData= */ nullptr, 3));
  EXPECT_EQ(segmentedQueue.size(), 0);
}

TEST(SegmentedQueue, RemoveMatchesTemp) {
  constexpr uint8_t blockSize = 5;
  constexpr uint8_t maxBlockCount = 2;
  SegmentedQueue<int, blockSize> segmentedQueue(maxBlockCount);

  EXPECT_TRUE(segmentedQueue.push_back(1));

  EXPECT_EQ(1, segmentedQueue.removeMatchedFromBack(
                   [](int element, void * /* data */, void * /* extraData */) {
                     return element == 1;
                   },
                   /* data= */ nullptr, /* extraData= */ nullptr, 3));
  EXPECT_EQ(segmentedQueue.size(), 0);
}

TEST(SegmentedQueue, RemoveMatchesTailInMiddle) {
  constexpr uint8_t blockSize = 5;
  constexpr uint8_t maxBlockCount = 2;
  SegmentedQueue<int, blockSize> segmentedQueue(maxBlockCount);

  for (uint32_t index = 0; index < blockSize * maxBlockCount; index++) {
    EXPECT_TRUE(segmentedQueue.emplace_back(index));
  }

  segmentedQueue.pop();
  segmentedQueue.pop();
  segmentedQueue.push_back(blockSize * maxBlockCount);
  segmentedQueue.push_back(blockSize * maxBlockCount + 1);

  EXPECT_EQ(5, segmentedQueue.removeMatchedFromBack(
                   [](int item, void * /* data */, void * /* extraData */) {
                     return item % 2 == 0;
                   },
                   /* data= */ nullptr, /* extraData= */ nullptr, 10));
  EXPECT_EQ(segmentedQueue.size(), 5);

  EXPECT_EQ(segmentedQueue[0], 3);
  EXPECT_EQ(segmentedQueue[1], 5);
  EXPECT_EQ(segmentedQueue[2], 7);
  EXPECT_EQ(segmentedQueue[3], 9);
  EXPECT_EQ(segmentedQueue[4], 11);

  EXPECT_EQ(segmentedQueue.front(), 3);
  EXPECT_EQ(segmentedQueue.back(), 11);
}

TEST(SegmentedQueue, RemoveMatchesWithFreeCallback) {
  constexpr uint8_t blockSize = 3;
  constexpr uint8_t maxBlockCount = 2;
  int8_t counter = 0;
  SegmentedQueue<uint8_t, blockSize> segmentedQueue(maxBlockCount);

  for (uint8_t index = 0; index < blockSize * maxBlockCount; ++index) {
    EXPECT_TRUE(segmentedQueue.push_back(index));
  }

  EXPECT_EQ(3, segmentedQueue.removeMatchedFromBack(
                   [](uint8_t item, void * /* data */, void * /* extraData */) {
                     return item % 2 == 0;
                   },
                   /* data= */ nullptr, /* extraData= */ nullptr, 3,
                   [](uint8_t item, void *counter) {
                     *static_cast<int8_t *>(counter) -= item;
                   },
                   &counter));

  EXPECT_EQ(counter, -6);  // item 0, 2, 4 is removed.
  EXPECT_EQ(segmentedQueue.size(), 3);
  EXPECT_EQ(segmentedQueue.back(), 5);
  EXPECT_EQ(segmentedQueue.front(), 1);
}

TEST(SegmentedQueue, RemoveALotOFMatchItems) {
  constexpr uint8_t kBlockSize = 10;
  constexpr uint8_t kMaxBlockCount = 3;
  constexpr uint8_t kTargetRemoveNumber = 13;
  SegmentedQueue<uint8_t, kBlockSize> segmentedQueue(kMaxBlockCount);

  for (uint32_t index = 0; index < kBlockSize * kMaxBlockCount; index++) {
    EXPECT_TRUE(segmentedQueue.push_back(index));
  }

  EXPECT_EQ(13, segmentedQueue.removeMatchedFromBack(
                    [](uint8_t element, void * /*data*/, void * /*extraData*/) {
                      return element % 2 == 0;
                    },
                    /* data= */ nullptr,
                    /* extraData= */ nullptr, kTargetRemoveNumber));

  EXPECT_EQ(segmentedQueue.size(),
            kBlockSize * kMaxBlockCount - kTargetRemoveNumber);
  for (size_t i = 0; i < segmentedQueue.size(); ++i) {
    if (i <= 3) {
      // Special case since this part of the queue should be untouched.
      EXPECT_EQ(segmentedQueue[i], i);
    } else {
      EXPECT_EQ(segmentedQueue[i], 2 * (i - 4) + 5);
    }
  }
}

TEST(SegmentedQueue, PseudoRandomStressTest) {
  // This test uses std::deque as reference implementation to make sure
  // that chre::SegmentedQueue is functioning correctly.

  constexpr uint32_t maxIteration = 200;

  constexpr uint32_t totalSize = 1024;
  constexpr uint32_t blockSize = 16;

  ssize_t referenceQueueConstructedCounter = 0;
  ssize_t segmentedQueueConstructedCounter = 0;

  std::srand(0xbeef);

  deque<ConstructorCount> referenceDeque;
  SegmentedQueue<ConstructorCount, blockSize> testSegmentedQueue(totalSize /
                                                                 blockSize);

  for (uint32_t currentIteration = 0; currentIteration < maxIteration;
       currentIteration++) {
    OperationType operationType = static_cast<OperationType>(
        std::rand() % chre::asBaseType(OperationType::OPERATION_TYPE_COUNT));
    int temp = std::rand();
    switch (operationType) {
      case OperationType::PUSH_BACK:
        if (referenceDeque.size() < totalSize) {
          ASSERT_TRUE(testSegmentedQueue.push_back(
              ConstructorCount(temp, &segmentedQueueConstructedCounter)));
          referenceDeque.push_back(
              ConstructorCount(temp, &referenceQueueConstructedCounter));
        } else {
          ASSERT_FALSE(testSegmentedQueue.push_back(
              ConstructorCount(temp, &segmentedQueueConstructedCounter)));
        }
        break;

      case OperationType::EMPLACE_BACK:
        if (referenceDeque.size() < totalSize) {
          ASSERT_TRUE(testSegmentedQueue.emplace_back(
              temp, &segmentedQueueConstructedCounter));
          referenceDeque.emplace_back(temp, &referenceQueueConstructedCounter);
        } else {
          ASSERT_FALSE(testSegmentedQueue.emplace_back(
              temp, &segmentedQueueConstructedCounter));
        }
        break;

      case OperationType::POP_FRONT:
        ASSERT_EQ(testSegmentedQueue.empty(), referenceDeque.empty());
        if (!testSegmentedQueue.empty()) {
          testSegmentedQueue.pop_front();
          referenceDeque.pop_front();
        }
        break;

      case OperationType::REMOVE: {
        ASSERT_EQ(testSegmentedQueue.size(), referenceDeque.size());
        if (!testSegmentedQueue.empty()) {
          // Creates 50% chance for removing index that is out of bound
          size_t index = std::rand() % (testSegmentedQueue.size() * 2);
          if (index >= referenceDeque.size()) {
            ASSERT_FALSE(testSegmentedQueue.remove(index));
          } else {
            ASSERT_TRUE(testSegmentedQueue.remove(index));
            referenceDeque.erase(referenceDeque.begin() + index);
          }
        }
      } break;

      case OperationType::BATCH_REMOVE: {
        ASSERT_EQ(testSegmentedQueue.size(), referenceDeque.size());
        // Always try to remove a quarter of elements
        size_t targetRemoveElement = referenceDeque.size() * 0.25;
        vector<size_t> removedIndex;
        for (int i = referenceDeque.size() - 1; i >= 0; i--) {
          if (removedIndex.size() == targetRemoveElement) {
            break;
          } else if (referenceDeque[i].getValue() % 2 == 0) {
            removedIndex.push_back(i);
          }
        }
        for (auto idx : removedIndex) {
          referenceDeque.erase(referenceDeque.begin() + idx);
        }

        ASSERT_EQ(
            removedIndex.size(),
            testSegmentedQueue.removeMatchedFromBack(
                [](ConstructorCount &item, void * /* data */,
                   void * /* extraData */) { return item.getValue() % 2 == 0; },
                /* data= */ nullptr, /* extraData= */ nullptr,
                targetRemoveElement));
      } break;

      case OperationType::OPERATION_TYPE_COUNT:
        // Should not be here, create this to prevent compiler error from
        // -Wswitch.
        FAIL();
        break;
    }

    // Complete check
    ASSERT_EQ(segmentedQueueConstructedCounter,
              referenceQueueConstructedCounter);
    ASSERT_EQ(testSegmentedQueue.size(), referenceDeque.size());
    ASSERT_EQ(testSegmentedQueue.empty(), referenceDeque.empty());
    if (!testSegmentedQueue.empty()) {
      ASSERT_EQ(testSegmentedQueue.back().getValue(),
                referenceDeque.back().getValue());
      ASSERT_EQ(testSegmentedQueue.front().getValue(),
                referenceDeque.front().getValue());
    }
    for (size_t idx = 0; idx < testSegmentedQueue.size(); idx++) {
      ASSERT_EQ(testSegmentedQueue[idx].getValue(),
                referenceDeque[idx].getValue());
    }
  }
}