Quelle TestHashtables.cpp Sprache: C

/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#include "nsTHashtable.h"
#include "nsBaseHashtable.h"
#include "nsTHashMap.h"
#include "nsInterfaceHashtable.h"
#include "nsClassHashtable.h"
#include "nsRefCountedHashtable.h"

#include "nsCOMPtr.h"
#include "nsIMemoryReporter.h"
#include "nsISupports.h"
#include "nsCOMArray.h"
#include "mozilla/Attributes.h"
#include "mozilla/Unused.h"

#include "gtest/gtest.h"

#include <numeric>

using mozilla::MakeRefPtr;
using mozilla::MakeUnique;
using mozilla::UniquePtr;

namespace TestHashtables {

class TestUniChar  // for nsClassHashtable
{
public:
  explicit TestUniChar(uint32_t aWord) { mWord = aWord; }

  ~TestUniChar() = default;

  uint32_t GetChar() const { return mWord; }

private:
  uint32_t mWord;
};

class TestUniCharDerived : public TestUniChar {
  using TestUniChar::TestUniChar;
};

class TestUniCharRefCounted  // for nsRefPtrHashtable
{
public:
  explicit TestUniCharRefCounted(uint32_t aWord,
                                 uint32_t aExpectedAddRefCnt = 0)
      : mExpectedAddRefCnt(aExpectedAddRefCnt),
        mAddRefCnt(0),
        mRefCnt(0),
        mWord(aWord) {}

  uint32_t AddRef() {
    mRefCnt++;
    mAddRefCnt++;
    return mRefCnt;
  }

  uint32_t Release() {
    EXPECT_TRUE(mRefCnt > 0);
    mRefCnt--;
    if (mRefCnt == 0) {
      delete this;
      return 0;
    }
    return mRefCnt;
  }

  uint32_t GetChar() const { return mWord; }

private:
  ~TestUniCharRefCounted() {
    if (mExpectedAddRefCnt > 0) {
      EXPECT_EQ(mAddRefCnt, mExpectedAddRefCnt);
    }
  }

  uint32_t mExpectedAddRefCnt;
  uint32_t mAddRefCnt;
  uint32_t mRefCnt;
  uint32_t mWord;
};

struct EntityNode {
  const char* mStr;  // never owns buffer
  uint32_t mUnicode;

  bool operator<(const EntityNode& aOther) const {
    return mUnicode < aOther.mUnicode ||
           (mUnicode == aOther.mUnicode && strcmp(mStr, aOther.mStr) < 0);
  }
};

static const EntityNode gEntities[] = {
    {"nbsp", 160},   {"iexcl", 161}, {"cent", 162},   {"pound", 163},
    {"curren", 164}, {"yen", 165},   {"brvbar", 166}, {"sect", 167},
    {"uml", 168},    {"copy", 169},  {"ordf", 170},   {"laquo", 171},
    {"not", 172},    {"shy", 173},   {"reg", 174},    {"macr", 175}};

#define ENTITY_COUNT (unsigned(sizeof(gEntities) / sizeof(EntityNode)))

class EntityToUnicodeEntry : public PLDHashEntryHdr {
public:
  typedef const char* KeyType;
  typedef const char* KeyTypePointer;

  explicit EntityToUnicodeEntry(const char* aKey) { mNode = nullptr; }
  EntityToUnicodeEntry(const EntityToUnicodeEntry& aEntry) {
    mNode = aEntry.mNode;
  }
  ~EntityToUnicodeEntry() = default;

  bool KeyEquals(const char* aEntity) const {
    return !strcmp(mNode->mStr, aEntity);
  }
  static const char* KeyToPointer(const char* aEntity) { return aEntity; }
  static PLDHashNumber HashKey(const char* aEntity) {
    return mozilla::HashString(aEntity);
  }
  enum { ALLOW_MEMMOVE = true };

  const EntityNode* mNode;
};

static uint32_t nsTIterPrint(nsTHashtable<EntityToUnicodeEntry>& hash) {
  uint32_t n = 0;
  for (auto iter = hash.Iter(); !iter.Done(); iter.Next()) {
    n++;
  }
  return n;
}

static uint32_t nsTIterPrintRemove(nsTHashtable<EntityToUnicodeEntry>& hash) {
  uint32_t n = 0;
  for (auto iter = hash.Iter(); !iter.Done(); iter.Next()) {
    iter.Remove();
    n++;
  }
  return n;
}

static void testTHashtable(nsTHashtable<EntityToUnicodeEntry>& hash,
                           uint32_t numEntries) {
  uint32_t i;
  for (i = 0; i < numEntries; ++i) {
    EntityToUnicodeEntry* entry = hash.PutEntry(gEntities[i].mStr);

    EXPECT_TRUE(entry);

    EXPECT_FALSE(entry->mNode);
    entry->mNode = &gEntities[i];
  }

  for (i = 0; i < numEntries; ++i) {
    EntityToUnicodeEntry* entry = hash.GetEntry(gEntities[i].mStr);

    EXPECT_TRUE(entry);
  }

  EntityToUnicodeEntry* entry = hash.GetEntry("xxxy");

  EXPECT_FALSE(entry);

  uint32_t count = nsTIterPrint(hash);
  EXPECT_EQ(count, numEntries);

  for (const auto& entry :
       const_cast<const nsTHashtable<EntityToUnicodeEntry>&>(hash)) {
    static_assert(std::is_same_v<decltype(entry), const EntityToUnicodeEntry&>);
  }
  for (auto& entry : hash) {
    static_assert(std::is_same_v<decltype(entry), EntityToUnicodeEntry&>);
  }

  EXPECT_EQ(numEntries == ENTITY_COUNT ? 6 : 0,
            std::count_if(hash.cbegin(), hash.cend(), [](const auto& entry) {
              return entry.mNode->mUnicode >= 170;
            }));
}

//
// all this nsIFoo stuff was copied wholesale from TestCOMPtr.cpp
//

#define NS_IFOO_IID                                  \
  {                                                  \
    0x6f7652e0, 0xee43, 0x11d1, {                    \
      0x9c, 0xc3, 0x00, 0x60, 0x08, 0x8c, 0xa6, 0xb3 \
    }                                                \
  }

class IFoo final : public nsISupports {
public:
  NS_DECLARE_STATIC_IID_ACCESSOR(NS_IFOO_IID)

  IFoo();

  NS_IMETHOD_(MozExternalRefCountType) AddRef() override;
  NS_IMETHOD_(MozExternalRefCountType) Release() override;
  NS_IMETHOD QueryInterface(const nsIID&, void**) override;

  NS_IMETHOD SetString(const nsACString& /*in*/ aString);
  NS_IMETHOD GetString(nsACString& /*out*/ aString);

  static void print_totals();

private:
  ~IFoo();

  unsigned int refcount_;

  static unsigned int total_constructions_;
  static unsigned int total_destructions_;
  nsCString mString;
};

NS_DEFINE_STATIC_IID_ACCESSOR(IFoo, NS_IFOO_IID)

unsigned int IFoo::total_constructions_;
unsigned int IFoo::total_destructions_;

void IFoo::print_totals() {}

IFoo::IFoo() : refcount_(0) { ++total_constructions_; }

IFoo::~IFoo() { ++total_destructions_; }

MozExternalRefCountType IFoo::AddRef() {
  ++refcount_;
  return refcount_;
}

MozExternalRefCountType IFoo::Release() {
  int newcount = --refcount_;
  if (newcount == 0) {
    delete this;
  }

  return newcount;
}

nsresult IFoo::QueryInterface(const nsIID& aIID, void** aResult) {
  nsISupports* rawPtr = 0;
  nsresult status = NS_OK;

  if (aIID.Equals(NS_GET_IID(IFoo)))
    rawPtr = this;
  else {
    nsID iid_of_ISupports = NS_ISUPPORTS_IID;
    if (aIID.Equals(iid_of_ISupports))
      rawPtr = static_cast<nsISupports*>(this);
    else
      status = NS_ERROR_NO_INTERFACE;
  }

  NS_IF_ADDREF(rawPtr);
  *aResult = rawPtr;

  return status;
}

nsresult IFoo::SetString(const nsACString& aString) {
  mString = aString;
  return NS_OK;
}

nsresult IFoo::GetString(nsACString& aString) {
  aString = mString;
  return NS_OK;
}

static nsresult CreateIFoo(IFoo** result)
// a typical factory function (that calls AddRef)
{
  auto* foop = new IFoo();

  foop->AddRef();
  *result = foop;

  return NS_OK;
}

class DefaultConstructible {
public:
  // Allow default construction.
  DefaultConstructible() = default;

  // Construct/assign from a ref counted char.
  explicit DefaultConstructible(RefPtr<TestUniCharRefCounted> aChar)
      : mChar(std::move(aChar)) {}

  const RefPtr<TestUniCharRefCounted>& CharRef() const { return mChar; }

  // DefaultConstructible can be copied and moved.
  DefaultConstructible(const DefaultConstructible&) = default;
  DefaultConstructible& operator=(const DefaultConstructible&) = default;
  DefaultConstructible(DefaultConstructible&&) = default;
  DefaultConstructible& operator=(DefaultConstructible&&) = default;

private:
  RefPtr<TestUniCharRefCounted> mChar;
};

class MovingNonDefaultConstructible;

class NonDefaultConstructible {
public:
  // Construct/assign from a ref counted char.
  explicit NonDefaultConstructible(RefPtr<TestUniCharRefCounted> aChar)
      : mChar(std::move(aChar)) {}

  // Disallow default construction.
  NonDefaultConstructible() = delete;

  MOZ_IMPLICIT NonDefaultConstructible(MovingNonDefaultConstructible&& aOther);

  const RefPtr<TestUniCharRefCounted>& CharRef() const { return mChar; }

  // NonDefaultConstructible can be copied, but not trivially (efficiently)
  // moved.
  NonDefaultConstructible(const NonDefaultConstructible&) = default;
  NonDefaultConstructible& operator=(const NonDefaultConstructible&) = default;

private:
  RefPtr<TestUniCharRefCounted> mChar;
};

class MovingNonDefaultConstructible {
public:
  // Construct/assign from a ref counted char.
  explicit MovingNonDefaultConstructible(RefPtr<TestUniCharRefCounted> aChar)
      : mChar(std::move(aChar)) {}

  MovingNonDefaultConstructible() = delete;

  MOZ_IMPLICIT MovingNonDefaultConstructible(
      const NonDefaultConstructible& aSrc)
      : mChar(aSrc.CharRef()) {}

  RefPtr<TestUniCharRefCounted> unwrapChar() && { return std::move(mChar); }

  // MovingNonDefaultConstructible can be moved, but not copied.
  MovingNonDefaultConstructible(const MovingNonDefaultConstructible&) = delete;
  MovingNonDefaultConstructible& operator=(
      const MovingNonDefaultConstructible&) = delete;
  MovingNonDefaultConstructible(MovingNonDefaultConstructible&&) = default;
  MovingNonDefaultConstructible& operator=(MovingNonDefaultConstructible&&) =
      default;

private:
  RefPtr<TestUniCharRefCounted> mChar;
};

NonDefaultConstructible::NonDefaultConstructible(
    MovingNonDefaultConstructible&& aOther)
    : mChar(std::move(aOther).unwrapChar()) {}

struct DefaultConstructible_DefaultConstructible {
  using DataType = DefaultConstructible;
  using UserDataType = DefaultConstructible;

  static constexpr uint32_t kExpectedAddRefCnt_Contains = 1;
  static constexpr uint32_t kExpectedAddRefCnt_GetGeneration = 1;
  static constexpr uint32_t kExpectedAddRefCnt_SizeOfExcludingThis = 1;
  static constexpr uint32_t kExpectedAddRefCnt_SizeOfIncludingThis = 1;
  static constexpr uint32_t kExpectedAddRefCnt_Count = 1;
  static constexpr uint32_t kExpectedAddRefCnt_IsEmpty = 1;
  static constexpr uint32_t kExpectedAddRefCnt_Get_OutputParam = 3;
  static constexpr uint32_t kExpectedAddRefCnt_Get = 3;
  static constexpr uint32_t kExpectedAddRefCnt_MaybeGet = 3;
  static constexpr uint32_t kExpectedAddRefCnt_LookupOrInsert = 1;
  static constexpr uint32_t kExpectedAddRefCnt_InsertOrUpdate = 1;
  static constexpr uint32_t kExpectedAddRefCnt_InsertOrUpdate_Fallible = 1;
  static constexpr uint32_t kExpectedAddRefCnt_InsertOrUpdate_Rvalue = 1;
  static constexpr uint32_t kExpectedAddRefCnt_InsertOrUpdate_Rvalue_Fallible =
      1;
  static constexpr uint32_t kExpectedAddRefCnt_Remove_OutputParam = 1;
  static constexpr uint32_t kExpectedAddRefCnt_Remove = 1;
  static constexpr uint32_t kExpectedAddRefCnt_Extract = 1;
  static constexpr uint32_t kExpectedAddRefCnt_RemoveIf = 1;
  static constexpr uint32_t kExpectedAddRefCnt_Lookup = 1;
  static constexpr uint32_t kExpectedAddRefCnt_Lookup_Remove = 1;
  static constexpr uint32_t kExpectedAddRefCnt_LookupForAdd = 1;
  static constexpr uint32_t kExpectedAddRefCnt_LookupForAdd_OrInsert = 1;
  static constexpr uint32_t kExpectedAddRefCnt_LookupForAdd_OrRemove = 1;
  static constexpr uint32_t kExpectedAddRefCnt_Iter = 1;
  static constexpr uint32_t kExpectedAddRefCnt_ConstIter = 1;
  static constexpr uint32_t kExpectedAddRefCnt_begin_end = 1;
  static constexpr uint32_t kExpectedAddRefCnt_cbegin_cend = 1;
  static constexpr uint32_t kExpectedAddRefCnt_Clear = 1;
  static constexpr uint32_t kExpectedAddRefCnt_ShallowSizeOfExcludingThis = 1;
  static constexpr uint32_t kExpectedAddRefCnt_ShallowSizeOfIncludingThis = 1;
  static constexpr uint32_t kExpectedAddRefCnt_SwapElements = 1;
  static constexpr uint32_t kExpectedAddRefCnt_MarkImmutable = 1;
};

struct NonDefaultConstructible_NonDefaultConstructible {
  using DataType = NonDefaultConstructible;
  using UserDataType = NonDefaultConstructible;

  static constexpr uint32_t kExpectedAddRefCnt_Contains = 2;
  static constexpr uint32_t kExpectedAddRefCnt_GetGeneration = 2;
  static constexpr uint32_t kExpectedAddRefCnt_SizeOfExcludingThis = 3;
  static constexpr uint32_t kExpectedAddRefCnt_SizeOfIncludingThis = 3;
  static constexpr uint32_t kExpectedAddRefCnt_Count = 2;
  static constexpr uint32_t kExpectedAddRefCnt_IsEmpty = 2;
  static constexpr uint32_t kExpectedAddRefCnt_Get_OutputParam = 5;
  static constexpr uint32_t kExpectedAddRefCnt_MaybeGet = 5;
  static constexpr uint32_t kExpectedAddRefCnt_InsertOrUpdate = 2;
  static constexpr uint32_t kExpectedAddRefCnt_InsertOrUpdate_Fallible = 2;
  static constexpr uint32_t kExpectedAddRefCnt_InsertOrUpdate_Rvalue = 2;
  static constexpr uint32_t kExpectedAddRefCnt_InsertOrUpdate_Rvalue_Fallible =
      2;
  static constexpr uint32_t kExpectedAddRefCnt_Remove = 2;
  static constexpr uint32_t kExpectedAddRefCnt_Extract = 3;
  static constexpr uint32_t kExpectedAddRefCnt_RemoveIf = 2;
  static constexpr uint32_t kExpectedAddRefCnt_Lookup = 2;
  static constexpr uint32_t kExpectedAddRefCnt_Lookup_Remove = 2;
  static constexpr uint32_t kExpectedAddRefCnt_Iter = 2;
  static constexpr uint32_t kExpectedAddRefCnt_ConstIter = 2;
  static constexpr uint32_t kExpectedAddRefCnt_begin_end = 2;
  static constexpr uint32_t kExpectedAddRefCnt_cbegin_cend = 2;
  static constexpr uint32_t kExpectedAddRefCnt_Clear = 2;
  static constexpr uint32_t kExpectedAddRefCnt_ShallowSizeOfExcludingThis = 2;
  static constexpr uint32_t kExpectedAddRefCnt_ShallowSizeOfIncludingThis = 2;
  static constexpr uint32_t kExpectedAddRefCnt_SwapElements = 2;
  static constexpr uint32_t kExpectedAddRefCnt_MarkImmutable = 2;
};

struct NonDefaultConstructible_MovingNonDefaultConstructible {
  using DataType = NonDefaultConstructible;
  using UserDataType = MovingNonDefaultConstructible;

  static constexpr uint32_t kExpectedAddRefCnt_Contains = 1;
  static constexpr uint32_t kExpectedAddRefCnt_GetGeneration = 1;
  static constexpr uint32_t kExpectedAddRefCnt_SizeOfExcludingThis = 1;
  static constexpr uint32_t kExpectedAddRefCnt_SizeOfIncludingThis = 1;
  static constexpr uint32_t kExpectedAddRefCnt_Count = 1;
  static constexpr uint32_t kExpectedAddRefCnt_IsEmpty = 1;
  static constexpr uint32_t kExpectedAddRefCnt_Get_OutputParam = 2;
  static constexpr uint32_t kExpectedAddRefCnt_MaybeGet = 2;
  static constexpr uint32_t kExpectedAddRefCnt_InsertOrUpdate = 1;
  static constexpr uint32_t kExpectedAddRefCnt_InsertOrUpdate_Fallible = 1;
  static constexpr uint32_t kExpectedAddRefCnt_InsertOrUpdate_Rvalue = 1;
  static constexpr uint32_t kExpectedAddRefCnt_InsertOrUpdate_Rvalue_Fallible =
      1;
  static constexpr uint32_t kExpectedAddRefCnt_Remove = 1;
  static constexpr uint32_t kExpectedAddRefCnt_Extract = 2;
  static constexpr uint32_t kExpectedAddRefCnt_RemoveIf = 1;
  static constexpr uint32_t kExpectedAddRefCnt_Lookup = 1;
  static constexpr uint32_t kExpectedAddRefCnt_Lookup_Remove = 1;
  static constexpr uint32_t kExpectedAddRefCnt_Iter = 1;
  static constexpr uint32_t kExpectedAddRefCnt_ConstIter = 1;
  static constexpr uint32_t kExpectedAddRefCnt_begin_end = 1;
  static constexpr uint32_t kExpectedAddRefCnt_cbegin_cend = 1;
  static constexpr uint32_t kExpectedAddRefCnt_Clear = 1;
  static constexpr uint32_t kExpectedAddRefCnt_ShallowSizeOfExcludingThis = 1;
  static constexpr uint32_t kExpectedAddRefCnt_ShallowSizeOfIncludingThis = 1;
  static constexpr uint32_t kExpectedAddRefCnt_SwapElements = 1;
  static constexpr uint32_t kExpectedAddRefCnt_MarkImmutable = 1;
};

template <bool flag = false>
void UnsupportedType() {
  static_assert(flag, "Unsupported type!");
}

class TypeNames {
public:
  template <typename T>
  static std::string GetName(int) {
    if constexpr (std::is_same<T,
                               DefaultConstructible_DefaultConstructible>()) {
      return "DefaultConstructible_DefaultConstructible";
    } else if constexpr (
        std::is_same<T, NonDefaultConstructible_NonDefaultConstructible>()) {
      return "NonDefaultConstructible_NonDefaultConstructible";
    } else if constexpr (
        std::is_same<T,
                     NonDefaultConstructible_MovingNonDefaultConstructible>()) {
      return "NonDefaultConstructible_MovingNonDefaultConstructible";
    } else {
      UnsupportedType();
    }
  }
};

template <typename TypeParam>
auto MakeEmptyBaseHashtable() {
  nsBaseHashtable<nsUint64HashKey, typename TypeParam::DataType,
                  typename TypeParam::UserDataType>
      table;

  return table;
}

template <typename TypeParam>
auto MakeUniqueEmptyBaseHashtable() {
  return MakeUnique<
      nsBaseHashtable<nsUint64HashKey, typename TypeParam::DataType,
                      typename TypeParam::UserDataType>>();
}

template <typename TypeParam>
auto MakeBaseHashtable(const uint32_t aExpectedAddRefCnt) {
  auto table = MakeEmptyBaseHashtable<TypeParam>();

  auto myChar = MakeRefPtr<TestUniCharRefCounted>(42, aExpectedAddRefCnt);

  table.InsertOrUpdate(1, typename TypeParam::UserDataType(std::move(myChar)));

  return table;
}

template <typename TypeParam>
auto MakeUniqueBaseHashtable(const uint32_t aExpectedAddRefCnt) {
  auto table = MakeUniqueEmptyBaseHashtable<TypeParam>();

  auto myChar = MakeRefPtr<TestUniCharRefCounted>(42, aExpectedAddRefCnt);

  table->InsertOrUpdate(1, typename TypeParam::UserDataType(std::move(myChar)));

  return table;
}

template <typename TypeParam>
typename TypeParam::DataType GetDataFrom(
    typename TypeParam::UserDataType& aUserData) {
  if constexpr (std::is_same_v<TypeParam,
                               DefaultConstructible_DefaultConstructible> ||
                std::is_same_v<
                    TypeParam,
                    NonDefaultConstructible_NonDefaultConstructible>) {
    return aUserData;
  } else if constexpr (
      std::is_same_v<TypeParam,
                     NonDefaultConstructible_MovingNonDefaultConstructible>) {
    return std::move(aUserData);
  } else {
    UnsupportedType();
  }
}

template <typename TypeParam>
typename TypeParam::DataType GetDataFrom(
    mozilla::Maybe<typename TypeParam::UserDataType>& aMaybeUserData) {
  return GetDataFrom<TypeParam>(*aMaybeUserData);
}

}  // namespace TestHashtables

using namespace TestHashtables;

TEST(Hashtable, THashtable)
{
  // check an nsTHashtable
  nsTHashtable<EntityToUnicodeEntry> EntityToUnicode(ENTITY_COUNT);

  testTHashtable(EntityToUnicode, 5);

  uint32_t count = nsTIterPrintRemove(EntityToUnicode);
  ASSERT_EQ(count, uint32_t(5));

  count = nsTIterPrint(EntityToUnicode);
  ASSERT_EQ(count, uint32_t(0));

  testTHashtable(EntityToUnicode, ENTITY_COUNT);

  EntityToUnicode.Clear();

  count = nsTIterPrint(EntityToUnicode);
  ASSERT_EQ(count, uint32_t(0));
}

TEST(Hashtable, PtrHashtable)
{
  nsTHashtable<nsPtrHashKey<int>> hash;

  for (const auto& entry :
       const_cast<const nsTHashtable<nsPtrHashKey<int>>&>(hash)) {
    static_assert(std::is_same_v<decltype(entry), const nsPtrHashKey<int>&>);
  }
  for (auto& entry : hash) {
    static_assert(std::is_same_v<decltype(entry), nsPtrHashKey<int>&>);
  }
}

TEST(Hashtable, Move)
{
  const void* kPtr = reinterpret_cast<void*>(static_cast<uintptr_t>(0xbadc0de));

  nsTHashtable<nsPtrHashKey<const void>> table;
  table.PutEntry(kPtr);

  nsTHashtable<nsPtrHashKey<const void>> moved = std::move(table);
  ASSERT_EQ(table.Count(), 0u);
  ASSERT_EQ(moved.Count(), 1u);

  EXPECT_TRUE(moved.Contains(kPtr));
  EXPECT_FALSE(table.Contains(kPtr));
}

TEST(Hashtable, Keys)
{
  static constexpr uint64_t count = 10;

  nsTHashtable<nsUint64HashKey> table;
  for (uint64_t i = 0; i < count; i++) {
    table.PutEntry(i);
  }

  nsTArray<uint64_t> keys;
  for (const uint64_t& key : table.Keys()) {
    keys.AppendElement(key);
  }
  keys.Sort();

  EXPECT_EQ((nsTArray<uint64_t>{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}), keys);
}

template <typename TypeParam>
class BaseHashtableTest : public ::testing::Test {};

TYPED_TEST_SUITE_P(BaseHashtableTest);

TYPED_TEST_P(BaseHashtableTest, Contains) {
  auto table =
      MakeBaseHashtable<TypeParam>(TypeParam::kExpectedAddRefCnt_Contains);

  auto res = table.Contains(1);
  EXPECT_TRUE(res);
}

TYPED_TEST_P(BaseHashtableTest, GetGeneration) {
  auto table =
      MakeBaseHashtable<TypeParam>(TypeParam::kExpectedAddRefCnt_GetGeneration);

  auto res = table.GetGeneration();
  EXPECT_GT(res, 0u);
}

MOZ_DEFINE_MALLOC_SIZE_OF(MallocSizeOf);

TYPED_TEST_P(BaseHashtableTest, SizeOfExcludingThis) {
  // This doesn't compile at the moment, since nsBaseHashtableET lacks
  // SizeOfExcludingThis implementation. Bug 1689214.
#if 0
  auto table = MakeBaseHashtable<TypeParam>(
      TypeParam::kExpectedAddRefCnt_SizeOfExcludingThis);

  auto res = table.SizeOfExcludingThis(MallocSizeOf);
  EXPECT_GT(res, 0u);
#endif
}

TYPED_TEST_P(BaseHashtableTest, SizeOfIncludingThis) {
  // This doesn't compile at the moment, since nsBaseHashtableET lacks
  // SizeOfIncludingThis implementation. Bug 1689214.
#if 0
  auto table = MakeUniqueBaseHashtable<TypeParam>(
      TypeParam::kExpectedAddRefCnt_SizeOfIncludingThis);

  auto res = table->SizeOfIncludingThis(MallocSizeOf);
  EXPECT_GT(res, 0u);
#endif
}

TYPED_TEST_P(BaseHashtableTest, Count) {
  auto table =
      MakeBaseHashtable<TypeParam>(TypeParam::kExpectedAddRefCnt_Count);

  auto res = table.Count();
  EXPECT_EQ(res, 1u);
}

TYPED_TEST_P(BaseHashtableTest, IsEmpty) {
  auto table =
      MakeBaseHashtable<TypeParam>(TypeParam::kExpectedAddRefCnt_IsEmpty);

  auto res = table.IsEmpty();
  EXPECT_EQ(res, false);
}

TYPED_TEST_P(BaseHashtableTest, Get_OutputParam) {
  auto table = MakeBaseHashtable<TypeParam>(
      TypeParam::kExpectedAddRefCnt_Get_OutputParam);

  typename TypeParam::UserDataType userData(nullptr);
  auto res = table.Get(1, &userData);
  EXPECT_TRUE(res);

  auto data = GetDataFrom<TypeParam>(userData);
  EXPECT_EQ(data.CharRef()->GetChar(), 42u);
}

TYPED_TEST_P(BaseHashtableTest, Get) {
  // The Get overload can't support non-default-constructible UserDataType.
  if constexpr (std::is_default_constructible_v<
                    typename TypeParam::UserDataType>) {
    auto table =
        MakeBaseHashtable<TypeParam>(TypeParam::kExpectedAddRefCnt_Get);

    auto userData = table.Get(1);

    auto data = GetDataFrom<TypeParam>(userData);
    EXPECT_EQ(data.CharRef()->GetChar(), 42u);
  }
}

TYPED_TEST_P(BaseHashtableTest, MaybeGet) {
  auto table =
      MakeBaseHashtable<TypeParam>(TypeParam::kExpectedAddRefCnt_MaybeGet);

  auto maybeUserData = table.MaybeGet(1);
  EXPECT_TRUE(maybeUserData);

  auto data = GetDataFrom<TypeParam>(maybeUserData);
  EXPECT_EQ(data.CharRef()->GetChar(), 42u);
}

TYPED_TEST_P(BaseHashtableTest, LookupOrInsert_Default) {
  if constexpr (std::is_default_constructible_v<typename TypeParam::DataType>) {
    auto table = MakeEmptyBaseHashtable<TypeParam>();

    typename TypeParam::DataType& data = table.LookupOrInsert(1);
    EXPECT_EQ(data.CharRef(), nullptr);

    data = typename TypeParam::DataType(MakeRefPtr<TestUniCharRefCounted>(
        42, TypeParam::kExpectedAddRefCnt_LookupOrInsert));
  }
}

TYPED_TEST_P(BaseHashtableTest, LookupOrInsert_NonDefault) {
  auto table = MakeEmptyBaseHashtable<TypeParam>();

  typename TypeParam::DataType& data = table.LookupOrInsert(
      1, typename TypeParam::DataType{MakeRefPtr<TestUniCharRefCounted>(42)});
  EXPECT_NE(data.CharRef(), nullptr);
}

TYPED_TEST_P(BaseHashtableTest, LookupOrInsert_NonDefault_AlreadyPresent) {
  auto table = MakeEmptyBaseHashtable<TypeParam>();

  typename TypeParam::DataType& data1 = table.LookupOrInsert(
      1, typename TypeParam::DataType{MakeRefPtr<TestUniCharRefCounted>(42)});
  TestUniCharRefCounted* const address = data1.CharRef();
  typename TypeParam::DataType& data2 = table.LookupOrInsert(
      1,
      typename TypeParam::DataType{MakeRefPtr<TestUniCharRefCounted>(42, 1)});
  EXPECT_EQ(&data1, &data2);
  EXPECT_EQ(address, data2.CharRef());
}

TYPED_TEST_P(BaseHashtableTest, LookupOrInsertWith) {
  auto table = MakeEmptyBaseHashtable<TypeParam>();

  typename TypeParam::DataType& data = table.LookupOrInsertWith(1, [] {
    return typename TypeParam::DataType{MakeRefPtr<TestUniCharRefCounted>(42)};
  });
  EXPECT_NE(data.CharRef(), nullptr);
}

TYPED_TEST_P(BaseHashtableTest, LookupOrInsertWith_AlreadyPresent) {
  auto table = MakeEmptyBaseHashtable<TypeParam>();

  table.LookupOrInsertWith(1, [] {
    return typename TypeParam::DataType{MakeRefPtr<TestUniCharRefCounted>(42)};
  });
  table.LookupOrInsertWith(1, [] {
    ADD_FAILURE();
    return typename TypeParam::DataType{MakeRefPtr<TestUniCharRefCounted>(42)};
  });
}

TYPED_TEST_P(BaseHashtableTest, InsertOrUpdate) {
  auto table = MakeEmptyBaseHashtable<TypeParam>();

  auto myChar = MakeRefPtr<TestUniCharRefCounted>(
      42, TypeParam::kExpectedAddRefCnt_InsertOrUpdate);

  table.InsertOrUpdate(1, typename TypeParam::UserDataType(std::move(myChar)));
}

TYPED_TEST_P(BaseHashtableTest, InsertOrUpdate_Fallible) {
  auto table = MakeEmptyBaseHashtable<TypeParam>();

  auto myChar = MakeRefPtr<TestUniCharRefCounted>(
      42, TypeParam::kExpectedAddRefCnt_InsertOrUpdate_Fallible);

  auto res = table.InsertOrUpdate(
      1, typename TypeParam::UserDataType(std::move(myChar)),
      mozilla::fallible);
  EXPECT_TRUE(res);
}

TYPED_TEST_P(BaseHashtableTest, InsertOrUpdate_Rvalue) {
  auto table = MakeEmptyBaseHashtable<TypeParam>();

  auto myChar = MakeRefPtr<TestUniCharRefCounted>(
      42, TypeParam::kExpectedAddRefCnt_InsertOrUpdate_Rvalue);

  table.InsertOrUpdate(
      1, std::move(typename TypeParam::UserDataType(std::move(myChar))));
}

TYPED_TEST_P(BaseHashtableTest, InsertOrUpdate_Rvalue_Fallible) {
  auto table = MakeEmptyBaseHashtable<TypeParam>();

  auto myChar = MakeRefPtr<TestUniCharRefCounted>(
      42, TypeParam::kExpectedAddRefCnt_InsertOrUpdate_Rvalue_Fallible);

  auto res = table.InsertOrUpdate(
      1, std::move(typename TypeParam::UserDataType(std::move(myChar))),
      mozilla::fallible);
  EXPECT_TRUE(res);
}

TYPED_TEST_P(BaseHashtableTest, Remove_OutputParam) {
  // The Remove overload can't support non-default-constructible DataType.
  if constexpr (std::is_default_constructible_v<typename TypeParam::DataType>) {
    auto table = MakeBaseHashtable<TypeParam>(
        TypeParam::kExpectedAddRefCnt_Remove_OutputParam);

    typename TypeParam::DataType data;
    auto res = table.Remove(1, &data);
    EXPECT_TRUE(res);
    EXPECT_EQ(data.CharRef()->GetChar(), 42u);
  }
}

TYPED_TEST_P(BaseHashtableTest, Remove) {
  auto table =
      MakeBaseHashtable<TypeParam>(TypeParam::kExpectedAddRefCnt_Remove);

  auto res = table.Remove(1);
  EXPECT_TRUE(res);
}

TYPED_TEST_P(BaseHashtableTest, Extract) {
  auto table =
      MakeBaseHashtable<TypeParam>(TypeParam::kExpectedAddRefCnt_Extract);

  auto maybeData = table.Extract(1);
  EXPECT_TRUE(maybeData);
  EXPECT_EQ(maybeData->CharRef()->GetChar(), 42u);
}

TYPED_TEST_P(BaseHashtableTest, RemoveIf) {
  auto table =
      MakeBaseHashtable<TypeParam>(TypeParam::kExpectedAddRefCnt_RemoveIf);

  table.RemoveIf([](const auto&) { return true; });
}

TYPED_TEST_P(BaseHashtableTest, Lookup) {
  auto table =
      MakeBaseHashtable<TypeParam>(TypeParam::kExpectedAddRefCnt_Lookup);

  auto res = table.Lookup(1);
  EXPECT_TRUE(res);
  EXPECT_EQ(res.Data().CharRef()->GetChar(), 42u);
}

TYPED_TEST_P(BaseHashtableTest, Lookup_Remove) {
  auto table =
      MakeBaseHashtable<TypeParam>(TypeParam::kExpectedAddRefCnt_Lookup_Remove);

  auto res = table.Lookup(1);
  EXPECT_TRUE(res);
  EXPECT_EQ(res.Data().CharRef()->GetChar(), 42u);

  res.Remove();
}

TYPED_TEST_P(BaseHashtableTest, WithEntryHandle_NoOp) {
  auto table = MakeEmptyBaseHashtable<TypeParam>();

  table.WithEntryHandle(1, [](auto&&) {});

  EXPECT_FALSE(table.Contains(1));
}

TYPED_TEST_P(BaseHashtableTest, WithEntryHandle_NotFound_OrInsert) {
  auto table = MakeEmptyBaseHashtable<TypeParam>();

  table.WithEntryHandle(1, [](auto&& entry) {
    entry.OrInsert(typename TypeParam::UserDataType(
        MakeRefPtr<TestUniCharRefCounted>(42)));
  });

  EXPECT_TRUE(table.Contains(1));
}

TYPED_TEST_P(BaseHashtableTest, WithEntryHandle_NotFound_OrInsertFrom) {
  auto table = MakeEmptyBaseHashtable<TypeParam>();

  table.WithEntryHandle(1, [](auto&& entry) {
    entry.OrInsertWith([] {
      return typename TypeParam::UserDataType(
          MakeRefPtr<TestUniCharRefCounted>(42));
    });
  });

  EXPECT_TRUE(table.Contains(1));
}

TYPED_TEST_P(BaseHashtableTest, WithEntryHandle_NotFound_OrInsertFrom_Exists) {
  auto table = MakeEmptyBaseHashtable<TypeParam>();

  table.WithEntryHandle(1, [](auto&& entry) {
    entry.OrInsertWith([] {
      return typename TypeParam::UserDataType(
          MakeRefPtr<TestUniCharRefCounted>(42));
    });
  });
  table.WithEntryHandle(1, [](auto&& entry) {
    entry.OrInsertWith([]() -> typename TypeParam::UserDataType {
      ADD_FAILURE();
      return typename TypeParam::UserDataType(
          MakeRefPtr<TestUniCharRefCounted>(42));
    });
  });

  EXPECT_TRUE(table.Contains(1));
}

TYPED_TEST_P(BaseHashtableTest, WithEntryHandle_NotFound_OrRemove) {
  auto table = MakeEmptyBaseHashtable<TypeParam>();

  table.WithEntryHandle(1, [](auto&& entry) { entry.OrRemove(); });

  EXPECT_FALSE(table.Contains(1));
}

TYPED_TEST_P(BaseHashtableTest, WithEntryHandle_NotFound_OrRemove_Exists) {
  auto table = MakeEmptyBaseHashtable<TypeParam>();

  table.WithEntryHandle(1, [](auto&& entry) {
    entry.OrInsertWith([] {
      return typename TypeParam::UserDataType(
          MakeRefPtr<TestUniCharRefCounted>(42));
    });
  });
  table.WithEntryHandle(1, [](auto&& entry) { entry.OrRemove(); });

  EXPECT_FALSE(table.Contains(1));
}

TYPED_TEST_P(BaseHashtableTest, Iter) {
  auto table = MakeBaseHashtable<TypeParam>(TypeParam::kExpectedAddRefCnt_Iter);

  for (auto iter = table.Iter(); !iter.Done(); iter.Next()) {
    EXPECT_EQ(iter.Data().CharRef()->GetChar(), 42u);
  }
}

TYPED_TEST_P(BaseHashtableTest, ConstIter) {
  auto table =
      MakeBaseHashtable<TypeParam>(TypeParam::kExpectedAddRefCnt_ConstIter);

  for (auto iter = table.ConstIter(); !iter.Done(); iter.Next()) {
    EXPECT_EQ(iter.Data().CharRef()->GetChar(), 42u);
  }
}

TYPED_TEST_P(BaseHashtableTest, begin_end) {
  auto table =
      MakeBaseHashtable<TypeParam>(TypeParam::kExpectedAddRefCnt_begin_end);

  auto res = std::count_if(table.begin(), table.end(), [](const auto& entry) {
    return entry.GetData().CharRef()->GetChar() == 42;
  });
  EXPECT_EQ(res, 1);
}

TYPED_TEST_P(BaseHashtableTest, cbegin_cend) {
  auto table =
      MakeBaseHashtable<TypeParam>(TypeParam::kExpectedAddRefCnt_cbegin_cend);

  auto res = std::count_if(table.cbegin(), table.cend(), [](const auto& entry) {
    return entry.GetData().CharRef()->GetChar() == 42;
  });
  EXPECT_EQ(res, 1);
}

TYPED_TEST_P(BaseHashtableTest, Clear) {
  auto table =
      MakeBaseHashtable<TypeParam>(TypeParam::kExpectedAddRefCnt_Clear);

  table.Clear();
}

TYPED_TEST_P(BaseHashtableTest, ShallowSizeOfExcludingThis) {
  auto table = MakeBaseHashtable<TypeParam>(
      TypeParam::kExpectedAddRefCnt_ShallowSizeOfExcludingThis);

  auto res = table.ShallowSizeOfExcludingThis(MallocSizeOf);
  EXPECT_GT(res, 0u);
}

TYPED_TEST_P(BaseHashtableTest, ShallowSizeOfIncludingThis) {
  auto table = MakeUniqueBaseHashtable<TypeParam>(
      TypeParam::kExpectedAddRefCnt_ShallowSizeOfIncludingThis);

  auto res = table->ShallowSizeOfIncludingThis(MallocSizeOf);
  EXPECT_GT(res, 0u);
}

TYPED_TEST_P(BaseHashtableTest, SwapElements) {
  auto table =
      MakeBaseHashtable<TypeParam>(TypeParam::kExpectedAddRefCnt_SwapElements);

  auto table2 = MakeEmptyBaseHashtable<TypeParam>();

  table.SwapElements(table2);
}

TYPED_TEST_P(BaseHashtableTest, MarkImmutable) {
  auto table =
      MakeBaseHashtable<TypeParam>(TypeParam::kExpectedAddRefCnt_MarkImmutable);

  table.MarkImmutable();
}

REGISTER_TYPED_TEST_SUITE_P(
    BaseHashtableTest, Contains, GetGeneration, SizeOfExcludingThis,
    SizeOfIncludingThis, Count, IsEmpty, Get_OutputParam, Get, MaybeGet,
    LookupOrInsert_Default, LookupOrInsert_NonDefault,
    LookupOrInsert_NonDefault_AlreadyPresent, LookupOrInsertWith,
    LookupOrInsertWith_AlreadyPresent, InsertOrUpdate, InsertOrUpdate_Fallible,
    InsertOrUpdate_Rvalue, InsertOrUpdate_Rvalue_Fallible, Remove_OutputParam,
    Remove, Extract, RemoveIf, Lookup, Lookup_Remove, WithEntryHandle_NoOp,
    WithEntryHandle_NotFound_OrInsert, WithEntryHandle_NotFound_OrInsertFrom,
    WithEntryHandle_NotFound_OrInsertFrom_Exists,
    WithEntryHandle_NotFound_OrRemove, WithEntryHandle_NotFound_OrRemove_Exists,
    Iter, ConstIter, begin_end, cbegin_cend, Clear, ShallowSizeOfExcludingThis,
    ShallowSizeOfIncludingThis, SwapElements, MarkImmutable);

using BaseHashtableTestTypes =
    ::testing::Types<DefaultConstructible_DefaultConstructible,
                     NonDefaultConstructible_NonDefaultConstructible,
                     NonDefaultConstructible_MovingNonDefaultConstructible>;

INSTANTIATE_TYPED_TEST_SUITE_P(Hashtables, BaseHashtableTest,
                               BaseHashtableTestTypes, TypeNames);

TEST(Hashtables, DataHashtable)
{
  // check a data-hashtable
  nsTHashMap<nsUint32HashKey, const char*> UniToEntity(ENTITY_COUNT);

  for (auto& entity : gEntities) {
    UniToEntity.InsertOrUpdate(entity.mUnicode, entity.mStr);
  }

  const char* str;

  for (auto& entity : gEntities) {
    ASSERT_TRUE(UniToEntity.Get(entity.mUnicode, &str));
  }

  ASSERT_FALSE(UniToEntity.Get(99446, &str));

  uint32_t count = 0;
  for (auto iter = UniToEntity.Iter(); !iter.Done(); iter.Next()) {
    count++;
  }
  ASSERT_EQ(count, ENTITY_COUNT);

  UniToEntity.Clear();

  count = 0;
  for (auto iter = UniToEntity.Iter(); !iter.Done(); iter.Next()) {
    printf(" enumerated %u = \"%s\"\n", iter.Key(), iter.Data());
    count++;
  }
  ASSERT_EQ(count, uint32_t(0));
}

TEST(Hashtables, DataHashtable_STLIterators)
{
  using mozilla::Unused;

  nsTHashMap<nsUint32HashKey, const char*> UniToEntity(ENTITY_COUNT);

  for (auto& entity : gEntities) {
    UniToEntity.InsertOrUpdate(entity.mUnicode, entity.mStr);
  }

  // operators, including conversion from iterator to const_iterator
  nsTHashMap<nsUint32HashKey, const char*>::const_iterator ci =
      UniToEntity.begin();
  ++ci;
  ASSERT_EQ(1, std::distance(UniToEntity.cbegin(), ci++));
  ASSERT_EQ(2, std::distance(UniToEntity.cbegin(), ci));
  ASSERT_TRUE(ci == ci);
  auto otherCi = ci;
  ++otherCi;
  ++ci;
  ASSERT_TRUE(&*ci == &*otherCi);

  // STL algorithms (just to check that the iterator sufficiently conforms
  // with the actual syntactical requirements of those algorithms).
  std::for_each(UniToEntity.cbegin(), UniToEntity.cend(),
                [](const auto& entry) {});
  Unused << std::find_if(
      UniToEntity.cbegin(), UniToEntity.cend(),
      [](const auto& entry) { return entry.GetKey() == 42; });
  Unused << std::accumulate(
      UniToEntity.cbegin(), UniToEntity.cend(), 0u,
      [](size_t sum, const auto& entry) { return sum + entry.GetKey(); });
  Unused << std::any_of(UniToEntity.cbegin(), UniToEntity.cend(),
                        [](const auto& entry) { return entry.GetKey() == 42; });
  Unused << std::max_element(UniToEntity.cbegin(), UniToEntity.cend(),
                             [](const auto& lhs, const auto& rhs) {
                               return lhs.GetKey() > rhs.GetKey();
                             });

  // const range-based for
  {
    std::set<EntityNode> entities(gEntities, gEntities + ENTITY_COUNT);
    for (const auto& entity :
         const_cast<const nsTHashMap<nsUint32HashKey, const char*>&>(
             UniToEntity)) {
      ASSERT_EQ(1u,
                entities.erase(EntityNode{entity.GetData(), entity.GetKey()}));
    }
    ASSERT_TRUE(entities.empty());
  }

  // non-const range-based for
  {
    std::set<EntityNode> entities(gEntities, gEntities + ENTITY_COUNT);
    for (auto& entity : UniToEntity) {
      ASSERT_EQ(1u,
                entities.erase(EntityNode{entity.GetData(), entity.GetKey()}));

      entity.SetData(nullptr);
      ASSERT_EQ(nullptr, entity.GetData());
    }
    ASSERT_TRUE(entities.empty());
  }
}

TEST(Hashtables, DataHashtable_RemoveIf)
{
  // check a data-hashtable
  nsTHashMap<nsUint32HashKey, const char*> UniToEntity(ENTITY_COUNT);

  for (auto& entity : gEntities) {
    UniToEntity.InsertOrUpdate(entity.mUnicode, entity.mStr);
  }

  UniToEntity.RemoveIf([](const auto& iter) { return iter.Key() >= 170; });

  ASSERT_EQ(10u, UniToEntity.Count());
}

TEST(Hashtables, ClassHashtable)
{
  // check a class-hashtable
  nsClassHashtable<nsCStringHashKey, TestUniChar> EntToUniClass(ENTITY_COUNT);

  for (auto& entity : gEntities) {
    // Insert a sub-class of TestUniChar to test if this is accepted by
    // InsertOrUpdate.
    EntToUniClass.InsertOrUpdate(
        nsDependentCString(entity.mStr),
        mozilla::MakeUnique<TestUniCharDerived>(entity.mUnicode));
  }

  TestUniChar* myChar;

  for (auto& entity : gEntities) {
    ASSERT_TRUE(EntToUniClass.Get(nsDependentCString(entity.mStr), &myChar));
  }

  ASSERT_FALSE(EntToUniClass.Get("xxxx"_ns, &myChar));

  uint32_t count = 0;
  for (auto iter = EntToUniClass.Iter(); !iter.Done(); iter.Next()) {
    count++;
  }
  ASSERT_EQ(count, ENTITY_COUNT);

  EntToUniClass.Clear();

  count = 0;
  for (auto iter = EntToUniClass.Iter(); !iter.Done(); iter.Next()) {
    count++;
  }
  ASSERT_EQ(count, uint32_t(0));
}

TEST(Hashtables, ClassHashtable_RangeBasedFor)
{
  // check a class-hashtable
  nsClassHashtable<nsCStringHashKey, TestUniChar> EntToUniClass(ENTITY_COUNT);

  for (auto& entity : gEntities) {
    EntToUniClass.InsertOrUpdate(nsDependentCString(entity.mStr),
                                 MakeUnique<TestUniChar>(entity.mUnicode));
  }

  // const range-based for
  {
    std::set<EntityNode> entities(gEntities, gEntities + ENTITY_COUNT);
    for (const auto& entity :
         const_cast<const nsClassHashtable<nsCStringHashKey, TestUniChar>&>(
             EntToUniClass)) {
      const char* str;
      entity.GetKey().GetData(&str);
      ASSERT_EQ(1u,
                entities.erase(EntityNode{str, entity.GetData()->GetChar()}));
    }
    ASSERT_TRUE(entities.empty());
  }

  // non-const range-based for
  {
    std::set<EntityNode> entities(gEntities, gEntities + ENTITY_COUNT);
    for (auto& entity : EntToUniClass) {
      const char* str;
      entity.GetKey().GetData(&str);
      ASSERT_EQ(1u,
                entities.erase(EntityNode{str, entity.GetData()->GetChar()}));

      entity.SetData(UniquePtr<TestUniChar>{});
      ASSERT_EQ(nullptr, entity.GetData());
    }
    ASSERT_TRUE(entities.empty());
  }
}

TEST(Hashtables, DataHashtableWithInterfaceKey)
{
  // check a data-hashtable with an interface key
  nsTHashMap<nsISupportsHashKey, uint32_t> EntToUniClass2(ENTITY_COUNT);

  nsCOMArray<IFoo> fooArray;

  for (uint32_t i = 0; i < ENTITY_COUNT; ++i) {
    nsCOMPtr<IFoo> foo;
    CreateIFoo(getter_AddRefs(foo));
    foo->SetString(nsDependentCString(gEntities[i].mStr));

    fooArray.InsertObjectAt(foo, i);

    EntToUniClass2.InsertOrUpdate(foo, gEntities[i].mUnicode);
  }

  uint32_t myChar2;

  for (uint32_t i = 0; i < ENTITY_COUNT; ++i) {
    ASSERT_TRUE(EntToUniClass2.Get(fooArray[i], &myChar2));
  }

  ASSERT_FALSE(EntToUniClass2.Get((nsISupports*)0x55443316, &myChar2));

  uint32_t count = 0;
  for (auto iter = EntToUniClass2.Iter(); !iter.Done(); iter.Next()) {
    nsAutoCString s;
    nsCOMPtr<IFoo> foo = do_QueryInterface(iter.Key());
    foo->GetString(s);
    count++;
  }
  ASSERT_EQ(count, ENTITY_COUNT);

  EntToUniClass2.Clear();

  count = 0;
  for (auto iter = EntToUniClass2.Iter(); !iter.Done(); iter.Next()) {
    nsAutoCString s;
    nsCOMPtr<IFoo> foo = do_QueryInterface(iter.Key());
    foo->GetString(s);
    count++;
  }
  ASSERT_EQ(count, uint32_t(0));
}

TEST(Hashtables, InterfaceHashtable)
{
  // check an interface-hashtable with an uint32_t key
  nsInterfaceHashtable<nsUint32HashKey, IFoo> UniToEntClass2(ENTITY_COUNT);

  for (auto& entity : gEntities) {
    nsCOMPtr<IFoo> foo;
    CreateIFoo(getter_AddRefs(foo));
    foo->SetString(nsDependentCString(entity.mStr));

    UniToEntClass2.InsertOrUpdate(entity.mUnicode, foo);
  }

  for (auto& entity : gEntities) {
    nsCOMPtr<IFoo> myEnt;
    ASSERT_TRUE(UniToEntClass2.Get(entity.mUnicode, getter_AddRefs(myEnt)));

    nsAutoCString myEntStr;
    myEnt->GetString(myEntStr);
  }

  nsCOMPtr<IFoo> myEnt;
  ASSERT_FALSE(UniToEntClass2.Get(9462, getter_AddRefs(myEnt)));

  uint32_t count = 0;
  for (auto iter = UniToEntClass2.Iter(); !iter.Done(); iter.Next()) {
    nsAutoCString s;
    iter.UserData()->GetString(s);
    count++;
  }
  ASSERT_EQ(count, ENTITY_COUNT);

  UniToEntClass2.Clear();

  count = 0;
  for (auto iter = UniToEntClass2.Iter(); !iter.Done(); iter.Next()) {
    nsAutoCString s;
    iter.Data()->GetString(s);
    count++;
  }
  ASSERT_EQ(count, uint32_t(0));
}

TEST(Hashtables, DataHashtable_WithEntryHandle)
{
  // check WithEntryHandle/OrInsertWith
  nsTHashMap<nsUint32HashKey, const char*> UniToEntity(ENTITY_COUNT);

  for (auto& entity : gEntities) {
    UniToEntity.WithEntryHandle(entity.mUnicode, [&entity](auto&& entry) {
      EXPECT_FALSE(entry);
      const char* const val =
          entry.OrInsertWith([&entity]() { return entity.mStr; });
      EXPECT_TRUE(entry);
      EXPECT_TRUE(val == entity.mStr);
      EXPECT_TRUE(entry.Data() == entity.mStr);
    });
  }

  for (auto& entity : gEntities) {
    UniToEntity.WithEntryHandle(entity.mUnicode,
                                [](auto&& entry) { EXPECT_TRUE(entry); });
  }

  // 0 should not be found
  size_t count = UniToEntity.Count();
  UniToEntity.Lookup(0U).Remove();
  ASSERT_TRUE(count == UniToEntity.Count());

  // Lookup should find all entries
  count = 0;
  for (auto& entity : gEntities) {
    if (UniToEntity.Lookup(entity.mUnicode)) {
      count++;
    }
  }
  ASSERT_TRUE(count == UniToEntity.Count());

  for (auto& entity : gEntities) {
    UniToEntity.WithEntryHandle(entity.mUnicode,
                                [](auto&& entry) { EXPECT_TRUE(entry); });
  }

  // Lookup().Remove() should remove all entries.
  for (auto& entity : gEntities) {
    if (auto entry = UniToEntity.Lookup(entity.mUnicode)) {
      entry.Remove();
    }
  }
  ASSERT_TRUE(0 == UniToEntity.Count());

  // Remove newly added entries via OrRemove.
  for (auto& entity : gEntities) {
    UniToEntity.WithEntryHandle(entity.mUnicode, [](auto&& entry) {
      EXPECT_FALSE(entry);
      entry.OrRemove();
    });
  }
  ASSERT_TRUE(0 == UniToEntity.Count());

  // Remove existing entries via OrRemove.
  for (auto& entity : gEntities) {
    UniToEntity.WithEntryHandle(entity.mUnicode, [&entity](auto&& entry) {
      EXPECT_FALSE(entry);
      const char* const val = entry.OrInsert(entity.mStr);
      EXPECT_TRUE(entry);
      EXPECT_TRUE(val == entity.mStr);
      EXPECT_TRUE(entry.Data() == entity.mStr);
    });

    UniToEntity.WithEntryHandle(entity.mUnicode, [](auto&& entry) {
      EXPECT_TRUE(entry);
      entry.OrRemove();
    });
  }
  ASSERT_TRUE(0 == UniToEntity.Count());
}

TEST(Hashtables, ClassHashtable_WithEntryHandle)
{
  // check a class-hashtable WithEntryHandle with null values
  nsClassHashtable<nsCStringHashKey, TestUniChar> EntToUniClass(ENTITY_COUNT);

  for (auto& entity : gEntities) {
    EntToUniClass.WithEntryHandle(
        nsDependentCString(entity.mStr), [](auto&& entry) {
          EXPECT_FALSE(entry);
          const TestUniChar* val = entry.OrInsert(nullptr).get();
          EXPECT_TRUE(entry);
          EXPECT_TRUE(val == nullptr);
          EXPECT_TRUE(entry.Data() == nullptr);
        });
  }

  for (auto& entity : gEntities) {
    EntToUniClass.WithEntryHandle(nsDependentCString(entity.mStr),
                                  [](auto&& entry) { EXPECT_TRUE(entry); });
    EntToUniClass.WithEntryHandle(
        nsDependentCString(entity.mStr),
        [](auto&& entry) { EXPECT_TRUE(entry.Data() == nullptr); });
  }

  // "" should not be found
  size_t count = EntToUniClass.Count();
  EntToUniClass.Lookup(nsDependentCString("")).Remove();
  ASSERT_TRUE(count == EntToUniClass.Count());

  // Lookup should find all entries.
  count = 0;
  for (auto& entity : gEntities) {
    if (EntToUniClass.Lookup(nsDependentCString(entity.mStr))) {
      count++;
    }
  }
  ASSERT_TRUE(count == EntToUniClass.Count());

  for (auto& entity : gEntities) {
    EntToUniClass.WithEntryHandle(nsDependentCString(entity.mStr),
                                  [](auto&& entry) { EXPECT_TRUE(entry); });
  }

  // Lookup().Remove() should remove all entries.
  for (auto& entity : gEntities) {
    if (auto entry = EntToUniClass.Lookup(nsDependentCString(entity.mStr))) {
      entry.Remove();
    }
  }
  ASSERT_TRUE(0 == EntToUniClass.Count());

  // Remove newly added entries via OrRemove.
  for (auto& entity : gEntities) {
    EntToUniClass.WithEntryHandle(nsDependentCString(entity.mStr),
                                  [](auto&& entry) {
                                    EXPECT_FALSE(entry);
                                    entry.OrRemove();
                                  });
  }
  ASSERT_TRUE(0 == EntToUniClass.Count());

  // Remove existing entries via OrRemove.
  for (auto& entity : gEntities) {
    EntToUniClass.WithEntryHandle(
        nsDependentCString(entity.mStr), [](auto&& entry) {
          EXPECT_FALSE(entry);
          const TestUniChar* val = entry.OrInsert(nullptr).get();
          EXPECT_TRUE(entry);
          EXPECT_TRUE(val == nullptr);
          EXPECT_TRUE(entry.Data() == nullptr);
        });

    EntToUniClass.WithEntryHandle(nsDependentCString(entity.mStr),
                                  [](auto&& entry) {
                                    EXPECT_TRUE(entry);
                                    entry.OrRemove();
                                  });
  }
  ASSERT_TRUE(0 == EntToUniClass.Count());
}

TEST(Hashtables, ClassHashtable_GetOrInsertNew_Present)
{
  nsClassHashtable<nsCStringHashKey, TestUniChar> EntToUniClass(ENTITY_COUNT);

  for (const auto& entity : gEntities) {
    EntToUniClass.InsertOrUpdate(
        nsDependentCString(entity.mStr),
        mozilla::MakeUnique<TestUniCharDerived>(entity.mUnicode));
  }

  auto* entry = EntToUniClass.GetOrInsertNew("uml"_ns, 42);
  EXPECT_EQ(168u, entry->GetChar());
}

TEST(Hashtables, ClassHashtable_GetOrInsertNew_NotPresent)
{
  nsClassHashtable<nsCStringHashKey, TestUniChar> EntToUniClass(ENTITY_COUNT);

  // This is going to insert a TestUniChar.
  auto* entry = EntToUniClass.GetOrInsertNew("uml"_ns, 42);
  EXPECT_EQ(42u, entry->GetChar());
}

TEST(Hashtables, ClassHashtable_LookupOrInsertWith_Present)
{
  nsClassHashtable<nsCStringHashKey, TestUniChar> EntToUniClass(ENTITY_COUNT);

  for (const auto& entity : gEntities) {
    EntToUniClass.InsertOrUpdate(
        nsDependentCString(entity.mStr),
        mozilla::MakeUnique<TestUniCharDerived>(entity.mUnicode));
  }

  const auto& entry = EntToUniClass.LookupOrInsertWith(
      "uml"_ns, [] { return mozilla::MakeUnique<TestUniCharDerived>(42); });
  EXPECT_EQ(168u, entry->GetChar());
}

TEST(Hashtables, ClassHashtable_LookupOrInsertWith_NotPresent)
{
  nsClassHashtable<nsCStringHashKey, TestUniChar> EntToUniClass(ENTITY_COUNT);

  // This is going to insert a TestUniCharDerived.
  const auto& entry = EntToUniClass.LookupOrInsertWith(
      "uml"_ns, [] { return mozilla::MakeUnique<TestUniCharDerived>(42); });
  EXPECT_EQ(42u, entry->GetChar());
}

TEST(Hashtables, RefPtrHashtable)
{
  // check a RefPtr-hashtable
  nsRefPtrHashtable<nsCStringHashKey, TestUniCharRefCounted> EntToUniClass(
      ENTITY_COUNT);

  for (auto& entity : gEntities) {
    EntToUniClass.InsertOrUpdate(
        nsDependentCString(entity.mStr),
        MakeRefPtr<TestUniCharRefCounted>(entity.mUnicode));
  }

  TestUniCharRefCounted* myChar;

  for (auto& entity : gEntities) {
    ASSERT_TRUE(EntToUniClass.Get(nsDependentCString(entity.mStr), &myChar));
  }

  ASSERT_FALSE(EntToUniClass.Get("xxxx"_ns, &myChar));

  uint32_t count = 0;
  for (auto iter = EntToUniClass.Iter(); !iter.Done(); iter.Next()) {
    count++;
  }
  ASSERT_EQ(count, ENTITY_COUNT);

  EntToUniClass.Clear();

  count = 0;
  for (auto iter = EntToUniClass.Iter(); !iter.Done(); iter.Next()) {
    count++;
  }
  ASSERT_EQ(count, uint32_t(0));
}

TEST(Hashtables, RefPtrHashtable_Clone)
{
  // check a RefPtr-hashtable
  nsRefPtrHashtable<nsCStringHashKey, TestUniCharRefCounted> EntToUniClass(
      ENTITY_COUNT);

  for (auto& entity : gEntities) {
    EntToUniClass.InsertOrUpdate(
        nsDependentCString(entity.mStr),
        MakeRefPtr<TestUniCharRefCounted>(entity.mUnicode));
  }

  auto clone = EntToUniClass.Clone();
  static_assert(std::is_same_v<decltype(clone), decltype(EntToUniClass)>);

  EXPECT_EQ(clone.Count(), EntToUniClass.Count());

  for (const auto& entry : EntToUniClass) {
    auto cloneEntry = clone.Lookup(entry.GetKey());

    EXPECT_TRUE(cloneEntry);
    EXPECT_EQ(cloneEntry.Data(), entry.GetWeak());
  }
}

TEST(Hashtables, Clone)
{
  static constexpr uint64_t count = 10;

  nsTHashMap<nsUint64HashKey, uint64_t> table;
  for (uint64_t i = 0; i < count; i++) {
    table.InsertOrUpdate(42 + i, i);
  }

  auto clone = table.Clone();

  static_assert(std::is_same_v<decltype(clone), decltype(table)>);

  EXPECT_EQ(clone.Count(), table.Count());

  for (const auto& entry : table) {
    auto cloneEntry = clone.Lookup(entry.GetKey());

    EXPECT_TRUE(cloneEntry);
    EXPECT_EQ(cloneEntry.Data(), entry.GetData());
  }
}

TEST(Hashtables, Values)
{
  static constexpr uint64_t count = 10;

  nsTHashMap<nsUint64HashKey, uint64_t> table;
  for (uint64_t i = 0; i < count; i++) {
    table.InsertOrUpdate(42 + i, i);
  }

  nsTArray<uint64_t> values;
  for (const uint64_t& value : table.Values()) {
    values.AppendElement(value);
  }
  values.Sort();

  EXPECT_EQ((nsTArray<uint64_t>{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}), values);
}

quality86%

¤ Dauer der Verarbeitung: 0.35 Sekunden ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.