pw_containers/variable_length_entry_queue_test.cc

// Copyright 2023 The Pigweed Authors
//
// 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
//
//     https://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 "pw_containers/variable_length_entry_queue.h"

#include <cstring>
#include <string_view>
#include <variant>

#include "gtest/gtest.h"
#include "pw_containers_private/variable_length_entry_queue_test_oracle.h"

namespace {

struct PushOverwrite {
  std::string_view data;
};
struct Push {
  std::string_view data;
};
struct Pop {};
struct Clear {};
struct SizeEquals {
  size_t expected;
};

using TestStep = std::variant<PushOverwrite, Push, Pop, Clear, SizeEquals>;

// Copies an entry, which might be wrapped, to a single std::vector.
std::vector<std::byte> ReadEntry(
    const pw_VariableLengthEntryQueue_Iterator& it) {
  auto entry = pw_VariableLengthEntryQueue_GetEntry(&it);
  std::vector<std::byte> value(entry.size_1 + entry.size_2);
  EXPECT_EQ(value.size(),
            pw_VariableLengthEntryQueue_Entry_Copy(
                &entry, value.data(), entry.size_1 + entry.size_2));
  return value;
}

#define ASSERT_CONTENTS_EQ(oracle, queue)                                      \
  auto oracle_it = oracle.begin();                                             \
  auto queue_it = pw_VariableLengthEntryQueue_Begin(queue);                    \
  const auto queue_end = pw_VariableLengthEntryQueue_End(queue);               \
  uint32_t entries_compared = 0;                                               \
  while (oracle_it != oracle.end() &&                                          \
         !pw_VariableLengthEntryQueue_Iterator_Equal(&queue_it, &queue_end)) { \
    ASSERT_EQ(*oracle_it++, ReadEntry(queue_it));                              \
    pw_VariableLengthEntryQueue_Iterator_Advance(&queue_it);                   \
    entries_compared += 1;                                                     \
  }                                                                            \
  ASSERT_EQ(entries_compared, oracle.size())

// Declares a test that performs a series of operations on a
// VariableLengthEntryQueue and the "oracle" class, and checks that they match
// after every step.
#define DATA_DRIVEN_TEST(program, max_entry_size)                              \
  TEST(VariableLengthEntryQueue,                                               \
       DataDrivenTest_##program##_MaxSizeBytes##max_entry_size) {              \
    pw::containers::VariableLengthEntryQueueTestOracle oracle(max_entry_size); \
    PW_VARIABLE_LENGTH_ENTRY_QUEUE_DECLARE(c_queue, max_entry_size);           \
                                                                               \
    for (const TestStep& step : program) {                                     \
      /* Take the action */                                                    \
      if (auto ow = std::get_if<PushOverwrite>(&step); ow != nullptr) {        \
        pw_VariableLengthEntryQueue_PushOverwrite(                             \
            c_queue, ow->data.data(), static_cast<uint32_t>(ow->data.size())); \
        oracle.push_overwrite(pw::as_bytes(pw::span(ow->data)));               \
      } else if (auto push = std::get_if<Push>(&step); push != nullptr) {      \
        pw_VariableLengthEntryQueue_Push(                                      \
            c_queue,                                                           \
            push->data.data(),                                                 \
            static_cast<uint32_t>(push->data.size()));                         \
        oracle.push(pw::as_bytes(pw::span(push->data)));                       \
      } else if (std::holds_alternative<Pop>(step)) {                          \
        pw_VariableLengthEntryQueue_Pop(c_queue);                              \
        oracle.pop();                                                          \
      } else if (auto size = std::get_if<SizeEquals>(&step);                   \
                 size != nullptr) {                                            \
        size_t actual = pw_VariableLengthEntryQueue_Size(c_queue);             \
        ASSERT_EQ(oracle.size(), actual);                                      \
        ASSERT_EQ(size->expected, actual);                                     \
      } else if (std::holds_alternative<Clear>(step)) {                        \
        pw_VariableLengthEntryQueue_Clear(c_queue);                            \
        oracle.clear();                                                        \
      } else {                                                                 \
        FAIL() << "Unhandled case";                                            \
      }                                                                        \
      /* Check size and other functions */                                     \
      ASSERT_EQ(pw_VariableLengthEntryQueue_Size(c_queue), oracle.size());     \
      ASSERT_EQ(pw_VariableLengthEntryQueue_SizeBytes(c_queue),                \
                oracle.size_bytes());                                          \
      ASSERT_EQ(pw_VariableLengthEntryQueue_MaxSizeBytes(c_queue),             \
                oracle.max_size_bytes());                                      \
      ASSERT_CONTENTS_EQ(oracle, c_queue);                                     \
    }                                                                          \
  }                                                                            \
  static_assert(true, "use a semicolon")

constexpr TestStep kPop[] = {
    SizeEquals{0},
    PushOverwrite{""},
    SizeEquals{1},
    Pop{},
    SizeEquals{0},
};

DATA_DRIVEN_TEST(kPop, 0);  // Only holds one empty entry.
DATA_DRIVEN_TEST(kPop, 1);
DATA_DRIVEN_TEST(kPop, 6);

constexpr TestStep kOverwriteLargeEntriesWithSmall[] = {
    PushOverwrite{"12345"},
    PushOverwrite{"abcde"},
    PushOverwrite{""},
    PushOverwrite{""},
    PushOverwrite{""},
    PushOverwrite{""},
    PushOverwrite{""},
    PushOverwrite{""},
    SizeEquals{6},
    Pop{},
    Pop{},
    Pop{},
    Pop{},
    Pop{},
    Pop{},
    SizeEquals{0},
};
DATA_DRIVEN_TEST(kOverwriteLargeEntriesWithSmall, 5);
DATA_DRIVEN_TEST(kOverwriteLargeEntriesWithSmall, 6);
DATA_DRIVEN_TEST(kOverwriteLargeEntriesWithSmall, 7);

constexpr TestStep kOverwriteVaryingSizes012[] = {
    PushOverwrite{""},   PushOverwrite{""},   PushOverwrite{""},
    PushOverwrite{""},   PushOverwrite{""},   PushOverwrite{"1"},
    PushOverwrite{"2"},  PushOverwrite{""},   PushOverwrite{"3"},
    PushOverwrite{"4"},  PushOverwrite{""},   PushOverwrite{"5"},
    PushOverwrite{"6"},  PushOverwrite{"ab"}, PushOverwrite{"cd"},
    PushOverwrite{""},   PushOverwrite{"ef"}, PushOverwrite{"gh"},
    PushOverwrite{"ij"},
};
DATA_DRIVEN_TEST(kOverwriteVaryingSizes012, 2);
DATA_DRIVEN_TEST(kOverwriteVaryingSizes012, 3);

constexpr TestStep kOverwriteVaryingSizesUpTo4[] = {
    PushOverwrite{""},
    PushOverwrite{""},
    PushOverwrite{""},
    PushOverwrite{"1"},
    PushOverwrite{"2"},
    PushOverwrite{"3"},
    PushOverwrite{"ab"},
    PushOverwrite{"cd"},
    PushOverwrite{"ef"},
    PushOverwrite{"123"},
    PushOverwrite{"456"},
    PushOverwrite{"789"},
    PushOverwrite{"abcd"},
    PushOverwrite{"efgh"},
    PushOverwrite{"ijkl"},
    Pop{},
    SizeEquals{0},
};
DATA_DRIVEN_TEST(kOverwriteVaryingSizesUpTo4, 4);
DATA_DRIVEN_TEST(kOverwriteVaryingSizesUpTo4, 5);
DATA_DRIVEN_TEST(kOverwriteVaryingSizesUpTo4, 6);

constexpr char kBigEntryBytes[196]{};

constexpr TestStep kTwoBytePrefix[] = {
    PushOverwrite{std::string_view(kBigEntryBytes, 128)},
    PushOverwrite{std::string_view(kBigEntryBytes, 128)},
    PushOverwrite{std::string_view(kBigEntryBytes, 127)},
    PushOverwrite{std::string_view(kBigEntryBytes, 128)},
    PushOverwrite{std::string_view(kBigEntryBytes, 127)},
    SizeEquals{1},
    Pop{},
    SizeEquals{0},
};
DATA_DRIVEN_TEST(kTwoBytePrefix, 128);
DATA_DRIVEN_TEST(kTwoBytePrefix, 129);

constexpr TestStep kClear[] = {
    Push{"abcdefg"},
    PushOverwrite{""},
    PushOverwrite{""},
    PushOverwrite{"a"},
    PushOverwrite{"b"},
    Clear{},
    SizeEquals{0},
    Clear{},
};
DATA_DRIVEN_TEST(kClear, 7);
DATA_DRIVEN_TEST(kClear, 100);

TEST(VariableLengthEntryQueue, DeclareMacro) {
  PW_VARIABLE_LENGTH_ENTRY_QUEUE_DECLARE(queue, 123);

  constexpr size_t kArraySizeBytes =
      123 + 1 /*prefix*/ + 1 /* end */ + 3 /* round up */ +
      PW_VARIABLE_LENGTH_ENTRY_QUEUE_HEADER_SIZE_UINT32 * 4;
  static_assert(sizeof(queue) == kArraySizeBytes);
  EXPECT_EQ(pw_VariableLengthEntryQueue_RawStorageSizeBytes(queue),
            kArraySizeBytes - 3 /* padding isn't included */);

  EXPECT_EQ(pw_VariableLengthEntryQueue_MaxSizeBytes(queue), 123u);
  EXPECT_EQ(pw_VariableLengthEntryQueue_SizeBytes(queue), 0u);
  EXPECT_TRUE(pw_VariableLengthEntryQueue_Empty(queue));
}

TEST(VariableLengthEntryQueue, InitializeExistingBuffer) {
  constexpr size_t kArraySize =
      10 + PW_VARIABLE_LENGTH_ENTRY_QUEUE_HEADER_SIZE_UINT32;
  uint32_t queue[kArraySize];
  pw_VariableLengthEntryQueue_Init(queue, kArraySize);

  EXPECT_EQ(pw_VariableLengthEntryQueue_RawStorageSizeBytes(queue),
            sizeof(queue));
  EXPECT_EQ(pw_VariableLengthEntryQueue_MaxSizeBytes(queue),
            sizeof(uint32_t) * 10u - 1 /*prefix*/ - 1 /*end*/);
  EXPECT_EQ(pw_VariableLengthEntryQueue_SizeBytes(queue), 0u);
  EXPECT_EQ(pw_VariableLengthEntryQueue_Size(queue), 0u);
  EXPECT_TRUE(pw_VariableLengthEntryQueue_Empty(queue));
}

TEST(VariableLengthEntryQueue, MaxSizeElement) {
  // Test max size elements for a few sizes. Commented out statements fail an
  // assert because the elements are too large.
  PW_VARIABLE_LENGTH_ENTRY_QUEUE_DECLARE(q16, 126);
  PW_VARIABLE_LENGTH_ENTRY_QUEUE_DECLARE(q17, 127);
  PW_VARIABLE_LENGTH_ENTRY_QUEUE_DECLARE(q18, 128);
  PW_VARIABLE_LENGTH_ENTRY_QUEUE_DECLARE(q19, 129);

  pw_VariableLengthEntryQueue_PushOverwrite(q16, kBigEntryBytes, 126);
  pw_VariableLengthEntryQueue_PushOverwrite(q17, kBigEntryBytes, 126);
  pw_VariableLengthEntryQueue_PushOverwrite(q18, kBigEntryBytes, 126);
  pw_VariableLengthEntryQueue_PushOverwrite(q19, kBigEntryBytes, 126);

  // pw_VariableLengthEntryQueue_PushOverwrite(q16, kBigEntryBytes, 127);
  pw_VariableLengthEntryQueue_PushOverwrite(q17, kBigEntryBytes, 127);
  pw_VariableLengthEntryQueue_PushOverwrite(q18, kBigEntryBytes, 127);
  pw_VariableLengthEntryQueue_PushOverwrite(q19, kBigEntryBytes, 127);

  // pw_VariableLengthEntryQueue_PushOverwrite(q16, kBigEntryBytes, 128);
  // pw_VariableLengthEntryQueue_PushOverwrite(q17, kBigEntryBytes, 128);
  pw_VariableLengthEntryQueue_PushOverwrite(q18, kBigEntryBytes, 128);
  pw_VariableLengthEntryQueue_PushOverwrite(q19, kBigEntryBytes, 128);

  // pw_VariableLengthEntryQueue_PushOverwrite(q16, kBigEntryBytes, 129);
  // pw_VariableLengthEntryQueue_PushOverwrite(q17, kBigEntryBytes, 129);
  // pw_VariableLengthEntryQueue_PushOverwrite(q18, kBigEntryBytes, 129);
  pw_VariableLengthEntryQueue_PushOverwrite(q19, kBigEntryBytes, 129);

  EXPECT_EQ(pw_VariableLengthEntryQueue_Size(q16), 1u);
  EXPECT_EQ(pw_VariableLengthEntryQueue_Size(q17), 1u);
  EXPECT_EQ(pw_VariableLengthEntryQueue_Size(q18), 1u);
  EXPECT_EQ(pw_VariableLengthEntryQueue_Size(q19), 1u);
}

}  // namespace