xpcom/tests/gtest/TestHashtables.cpp

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
   3 /* This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #include "nsTHashtable.h"
   8 #include "nsBaseHashtable.h"
   9 #include "nsTHashMap.h"
  10 #include "nsInterfaceHashtable.h"
  11 #include "nsClassHashtable.h"
  12 #include "nsRefCountedHashtable.h"
  13
  14 #include "nsCOMPtr.h"
  15 #include "nsIMemoryReporter.h"
  16 #include "nsISupports.h"
  17 #include "nsCOMArray.h"
  18 #include "mozilla/Attributes.h"
  19 #include "mozilla/Unused.h"
  20
  21 #include "gtest/gtest.h"
  22
  23 #include <numeric>
  24
  25 using mozilla::MakeRefPtr;
  26 using mozilla::MakeUnique;
  27 using mozilla::UniquePtr;
  28
  29 namespace TestHashtables {
  30
  31 class TestUniChar  // for nsClassHashtable
  32 {
  33  public:
  34   explicit TestUniChar(uint32_t aWord) { mWord = aWord; }
  35
  36   ~TestUniChar() = default;
  37
  38   uint32_t GetChar() const { return mWord; }
  39
  40  private:
  41   uint32_t mWord;
  42 };
  43
  44 class TestUniCharDerived : public TestUniChar {
  45   using TestUniChar::TestUniChar;
  46 };
  47
  48 class TestUniCharRefCounted  // for nsRefPtrHashtable
  49 {
  50  public:
  51   explicit TestUniCharRefCounted(uint32_t aWord,
  52                                  uint32_t aExpectedAddRefCnt = 0)
  53       : mExpectedAddRefCnt(aExpectedAddRefCnt),
  54         mAddRefCnt(0),
  55         mRefCnt(0),
  56         mWord(aWord) {}
  57
  58   uint32_t AddRef() {
  59     mRefCnt++;
  60     mAddRefCnt++;
  61     return mRefCnt;
  62   }
  63
  64   uint32_t Release() {
  65     EXPECT_TRUE(mRefCnt > 0);
  66     mRefCnt--;
  67     if (mRefCnt == 0) {
  68       delete this;
  69       return 0;
  70     }
  71     return mRefCnt;
  72   }
  73
  74   uint32_t GetChar() const { return mWord; }
  75
  76  private:
  77   ~TestUniCharRefCounted() {
  78     if (mExpectedAddRefCnt > 0) {
  79       EXPECT_EQ(mAddRefCnt, mExpectedAddRefCnt);
  80     }
  81   }
  82
  83   uint32_t mExpectedAddRefCnt;
  84   uint32_t mAddRefCnt;
  85   uint32_t mRefCnt;
  86   uint32_t mWord;
  87 };
  88
  89 struct EntityNode {
  90   const char* mStr;  // never owns buffer
  91   uint32_t mUnicode;
  92
  93   bool operator<(const EntityNode& aOther) const {
  94     return mUnicode < aOther.mUnicode ||
  95            (mUnicode == aOther.mUnicode && strcmp(mStr, aOther.mStr) < 0);
  96   }
  97 };
  98
  99 static const EntityNode gEntities[] = {
 100     {"nbsp", 160},   {"iexcl", 161}, {"cent", 162},   {"pound", 163},
 101     {"curren", 164}, {"yen", 165},   {"brvbar", 166}, {"sect", 167},
 102     {"uml", 168},    {"copy", 169},  {"ordf", 170},   {"laquo", 171},
 103     {"not", 172},    {"shy", 173},   {"reg", 174},    {"macr", 175}};
 104
 105 #define ENTITY_COUNT (unsigned(sizeof(gEntities) / sizeof(EntityNode)))
 106
 107 class EntityToUnicodeEntry : public PLDHashEntryHdr {
 108  public:
 109   typedef const char* KeyType;
 110   typedef const char* KeyTypePointer;
 111
 112   explicit EntityToUnicodeEntry(const char* aKey) { mNode = nullptr; }
 113   EntityToUnicodeEntry(const EntityToUnicodeEntry& aEntry) {
 114     mNode = aEntry.mNode;
 115   }
 116   ~EntityToUnicodeEntry() = default;
 117
 118   bool KeyEquals(const char* aEntity) const {
 119     return !strcmp(mNode->mStr, aEntity);
 120   }
 121   static const char* KeyToPointer(const char* aEntity) { return aEntity; }
 122   static PLDHashNumber HashKey(const char* aEntity) {
 123     return mozilla::HashString(aEntity);
 124   }
 125   enum { ALLOW_MEMMOVE = true };
 126
 127   const EntityNode* mNode;
 128 };
 129
 130 static uint32_t nsTIterPrint(nsTHashtable<EntityToUnicodeEntry>& hash) {
 131   uint32_t n = 0;
 132   for (auto iter = hash.Iter(); !iter.Done(); iter.Next()) {
 133     n++;
 134   }
 135   return n;
 136 }
 137
 138 static uint32_t nsTIterPrintRemove(nsTHashtable<EntityToUnicodeEntry>& hash) {
 139   uint32_t n = 0;
 140   for (auto iter = hash.Iter(); !iter.Done(); iter.Next()) {
 141     iter.Remove();
 142     n++;
 143   }
 144   return n;
 145 }
 146
 147 static void testTHashtable(nsTHashtable<EntityToUnicodeEntry>& hash,
 148                            uint32_t numEntries) {
 149   uint32_t i;
 150   for (i = 0; i < numEntries; ++i) {
 151     EntityToUnicodeEntry* entry = hash.PutEntry(gEntities[i].mStr);
 152
 153     EXPECT_TRUE(entry);
 154
 155     EXPECT_FALSE(entry->mNode);
 156     entry->mNode = &gEntities[i];
 157   }
 158
 159   for (i = 0; i < numEntries; ++i) {
 160     EntityToUnicodeEntry* entry = hash.GetEntry(gEntities[i].mStr);
 161
 162     EXPECT_TRUE(entry);
 163   }
 164
 165   EntityToUnicodeEntry* entry = hash.GetEntry("xxxy");
 166
 167   EXPECT_FALSE(entry);
 168
 169   uint32_t count = nsTIterPrint(hash);
 170   EXPECT_EQ(count, numEntries);
 171
 172   for (const auto& entry :
 173        const_cast<const nsTHashtable<EntityToUnicodeEntry>&>(hash)) {
 174     static_assert(std::is_same_v<decltype(entry), const EntityToUnicodeEntry&>);
 175   }
 176   for (auto& entry : hash) {
 177     static_assert(std::is_same_v<decltype(entry), EntityToUnicodeEntry&>);
 178   }
 179
 180   EXPECT_EQ(numEntries == ENTITY_COUNT ? 6 : 0,
 181             std::count_if(hash.cbegin(), hash.cend(), [](const auto& entry) {
 182               return entry.mNode->mUnicode >= 170;
 183             }));
 184 }
 185
 186 //
 187 // all this nsIFoo stuff was copied wholesale from TestCOMPtr.cpp
 188 //
 189
 190 #define NS_IFOO_IID                                  \
 191   {                                                  \
 192     0x6f7652e0, 0xee43, 0x11d1, {                    \
 193       0x9c, 0xc3, 0x00, 0x60, 0x08, 0x8c, 0xa6, 0xb3 \
 194     }                                                \
 195   }
 196
 197 class IFoo final : public nsISupports {
 198  public:
 199   NS_DECLARE_STATIC_IID_ACCESSOR(NS_IFOO_IID)
 200
 201   IFoo();
 202
 203   NS_IMETHOD_(MozExternalRefCountType) AddRef() override;
 204   NS_IMETHOD_(MozExternalRefCountType) Release() override;
 205   NS_IMETHOD QueryInterface(const nsIID&, void**) override;
 206
 207   NS_IMETHOD SetString(const nsACString& /*in*/ aString);
 208   NS_IMETHOD GetString(nsACString& /*out*/ aString);
 209
 210   static void print_totals();
 211
 212  private:
 213   ~IFoo();
 214
 215   unsigned int refcount_;
 216
 217   static unsigned int total_constructions_;
 218   static unsigned int total_destructions_;
 219   nsCString mString;
 220 };
 221
 222 NS_DEFINE_STATIC_IID_ACCESSOR(IFoo, NS_IFOO_IID)
 223
 224 unsigned int IFoo::total_constructions_;
 225 unsigned int IFoo::total_destructions_;
 226
 227 void IFoo::print_totals() {}
 228
 229 IFoo::IFoo() : refcount_(0) { ++total_constructions_; }
 230
 231 IFoo::~IFoo() { ++total_destructions_; }
 232
 233 MozExternalRefCountType IFoo::AddRef() {
 234   ++refcount_;
 235   return refcount_;
 236 }
 237
 238 MozExternalRefCountType IFoo::Release() {
 239   int newcount = --refcount_;
 240   if (newcount == 0) {
 241     delete this;
 242   }
 243
 244   return newcount;
 245 }
 246
 247 nsresult IFoo::QueryInterface(const nsIID& aIID, void** aResult) {
 248   nsISupports* rawPtr = 0;
 249   nsresult status = NS_OK;
 250
 251   if (aIID.Equals(NS_GET_IID(IFoo)))
 252     rawPtr = this;
 253   else {
 254     nsID iid_of_ISupports = NS_ISUPPORTS_IID;
 255     if (aIID.Equals(iid_of_ISupports))
 256       rawPtr = static_cast<nsISupports*>(this);
 257     else
 258       status = NS_ERROR_NO_INTERFACE;
 259   }
 260
 261   NS_IF_ADDREF(rawPtr);
 262   *aResult = rawPtr;
 263
 264   return status;
 265 }
 266
 267 nsresult IFoo::SetString(const nsACString& aString) {
 268   mString = aString;
 269   return NS_OK;
 270 }
 271
 272 nsresult IFoo::GetString(nsACString& aString) {
 273   aString = mString;
 274   return NS_OK;
 275 }
 276
 277 static nsresult CreateIFoo(IFoo** result)
 278 // a typical factory function (that calls AddRef)
 279 {
 280   auto* foop = new IFoo();
 281
 282   foop->AddRef();
 283   *result = foop;
 284
 285   return NS_OK;
 286 }
 287
 288 class DefaultConstructible {
 289  public:
 290   // Allow default construction.
 291   DefaultConstructible() = default;
 292
 293   // Construct/assign from a ref counted char.
 294   explicit DefaultConstructible(RefPtr<TestUniCharRefCounted> aChar)
 295       : mChar(std::move(aChar)) {}
 296
 297   const RefPtr<TestUniCharRefCounted>& CharRef() const { return mChar; }
 298
 299   // DefaultConstructible can be copied and moved.
 300   DefaultConstructible(const DefaultConstructible&) = default;
 301   DefaultConstructible& operator=(const DefaultConstructible&) = default;
 302   DefaultConstructible(DefaultConstructible&&) = default;
 303   DefaultConstructible& operator=(DefaultConstructible&&) = default;
 304
 305  private:
 306   RefPtr<TestUniCharRefCounted> mChar;
 307 };
 308
 309 class MovingNonDefaultConstructible;
 310
 311 class NonDefaultConstructible {
 312  public:
 313   // Construct/assign from a ref counted char.
 314   explicit NonDefaultConstructible(RefPtr<TestUniCharRefCounted> aChar)
 315       : mChar(std::move(aChar)) {}
 316
 317   // Disallow default construction.
 318   NonDefaultConstructible() = delete;
 319
 320   MOZ_IMPLICIT NonDefaultConstructible(MovingNonDefaultConstructible&& aOther);
 321
 322   const RefPtr<TestUniCharRefCounted>& CharRef() const { return mChar; }
 323
 324   // NonDefaultConstructible can be copied, but not trivially (efficiently)
 325   // moved.
 326   NonDefaultConstructible(const NonDefaultConstructible&) = default;
 327   NonDefaultConstructible& operator=(const NonDefaultConstructible&) = default;
 328
 329  private:
 330   RefPtr<TestUniCharRefCounted> mChar;
 331 };
 332
 333 class MovingNonDefaultConstructible {
 334  public:
 335   // Construct/assign from a ref counted char.
 336   explicit MovingNonDefaultConstructible(RefPtr<TestUniCharRefCounted> aChar)
 337       : mChar(std::move(aChar)) {}
 338
 339   MovingNonDefaultConstructible() = delete;
 340
 341   MOZ_IMPLICIT MovingNonDefaultConstructible(
 342       const NonDefaultConstructible& aSrc)
 343       : mChar(aSrc.CharRef()) {}
 344
 345   RefPtr<TestUniCharRefCounted> unwrapChar() && { return std::move(mChar); }
 346
 347   // MovingNonDefaultConstructible can be moved, but not copied.
 348   MovingNonDefaultConstructible(const MovingNonDefaultConstructible&) = delete;
 349   MovingNonDefaultConstructible& operator=(
 350       const MovingNonDefaultConstructible&) = delete;
 351   MovingNonDefaultConstructible(MovingNonDefaultConstructible&&) = default;
 352   MovingNonDefaultConstructible& operator=(MovingNonDefaultConstructible&&) =
 353       default;
 354
 355  private:
 356   RefPtr<TestUniCharRefCounted> mChar;
 357 };
 358
 359 NonDefaultConstructible::NonDefaultConstructible(
 360     MovingNonDefaultConstructible&& aOther)
 361     : mChar(std::move(aOther).unwrapChar()) {}
 362
 363 struct DefaultConstructible_DefaultConstructible {
 364   using DataType = DefaultConstructible;
 365   using UserDataType = DefaultConstructible;
 366
 367   static constexpr uint32_t kExpectedAddRefCnt_Contains = 1;
 368   static constexpr uint32_t kExpectedAddRefCnt_GetGeneration = 1;
 369   static constexpr uint32_t kExpectedAddRefCnt_SizeOfExcludingThis = 1;
 370   static constexpr uint32_t kExpectedAddRefCnt_SizeOfIncludingThis = 1;
 371   static constexpr uint32_t kExpectedAddRefCnt_Count = 1;
 372   static constexpr uint32_t kExpectedAddRefCnt_IsEmpty = 1;
 373   static constexpr uint32_t kExpectedAddRefCnt_Get_OutputParam = 3;
 374   static constexpr uint32_t kExpectedAddRefCnt_Get = 3;
 375   static constexpr uint32_t kExpectedAddRefCnt_MaybeGet = 3;
 376   static constexpr uint32_t kExpectedAddRefCnt_LookupOrInsert = 1;
 377   static constexpr uint32_t kExpectedAddRefCnt_InsertOrUpdate = 1;
 378   static constexpr uint32_t kExpectedAddRefCnt_InsertOrUpdate_Fallible = 1;
 379   static constexpr uint32_t kExpectedAddRefCnt_InsertOrUpdate_Rvalue = 1;
 380   static constexpr uint32_t kExpectedAddRefCnt_InsertOrUpdate_Rvalue_Fallible =
 381       1;
 382   static constexpr uint32_t kExpectedAddRefCnt_Remove_OutputParam = 1;
 383   static constexpr uint32_t kExpectedAddRefCnt_Remove = 1;
 384   static constexpr uint32_t kExpectedAddRefCnt_Extract = 1;
 385   static constexpr uint32_t kExpectedAddRefCnt_RemoveIf = 1;
 386   static constexpr uint32_t kExpectedAddRefCnt_Lookup = 1;
 387   static constexpr uint32_t kExpectedAddRefCnt_Lookup_Remove = 1;
 388   static constexpr uint32_t kExpectedAddRefCnt_LookupForAdd = 1;
 389   static constexpr uint32_t kExpectedAddRefCnt_LookupForAdd_OrInsert = 1;
 390   static constexpr uint32_t kExpectedAddRefCnt_LookupForAdd_OrRemove = 1;
 391   static constexpr uint32_t kExpectedAddRefCnt_Iter = 1;
 392   static constexpr uint32_t kExpectedAddRefCnt_ConstIter = 1;
 393   static constexpr uint32_t kExpectedAddRefCnt_begin_end = 1;
 394   static constexpr uint32_t kExpectedAddRefCnt_cbegin_cend = 1;
 395   static constexpr uint32_t kExpectedAddRefCnt_Clear = 1;
 396   static constexpr uint32_t kExpectedAddRefCnt_ShallowSizeOfExcludingThis = 1;
 397   static constexpr uint32_t kExpectedAddRefCnt_ShallowSizeOfIncludingThis = 1;
 398   static constexpr uint32_t kExpectedAddRefCnt_SwapElements = 1;
 399   static constexpr uint32_t kExpectedAddRefCnt_MarkImmutable = 1;
 400 };
 401
 402 struct NonDefaultConstructible_NonDefaultConstructible {
 403   using DataType = NonDefaultConstructible;
 404   using UserDataType = NonDefaultConstructible;
 405
 406   static constexpr uint32_t kExpectedAddRefCnt_Contains = 2;
 407   static constexpr uint32_t kExpectedAddRefCnt_GetGeneration = 2;
 408   static constexpr uint32_t kExpectedAddRefCnt_SizeOfExcludingThis = 3;
 409   static constexpr uint32_t kExpectedAddRefCnt_SizeOfIncludingThis = 3;
 410   static constexpr uint32_t kExpectedAddRefCnt_Count = 2;
 411   static constexpr uint32_t kExpectedAddRefCnt_IsEmpty = 2;
 412   static constexpr uint32_t kExpectedAddRefCnt_Get_OutputParam = 5;
 413   static constexpr uint32_t kExpectedAddRefCnt_MaybeGet = 5;
 414   static constexpr uint32_t kExpectedAddRefCnt_InsertOrUpdate = 2;
 415   static constexpr uint32_t kExpectedAddRefCnt_InsertOrUpdate_Fallible = 2;
 416   static constexpr uint32_t kExpectedAddRefCnt_InsertOrUpdate_Rvalue = 2;
 417   static constexpr uint32_t kExpectedAddRefCnt_InsertOrUpdate_Rvalue_Fallible =
 418       2;
 419   static constexpr uint32_t kExpectedAddRefCnt_Remove = 2;
 420   static constexpr uint32_t kExpectedAddRefCnt_Extract = 3;
 421   static constexpr uint32_t kExpectedAddRefCnt_RemoveIf = 2;
 422   static constexpr uint32_t kExpectedAddRefCnt_Lookup = 2;
 423   static constexpr uint32_t kExpectedAddRefCnt_Lookup_Remove = 2;
 424   static constexpr uint32_t kExpectedAddRefCnt_Iter = 2;
 425   static constexpr uint32_t kExpectedAddRefCnt_ConstIter = 2;
 426   static constexpr uint32_t kExpectedAddRefCnt_begin_end = 2;
 427   static constexpr uint32_t kExpectedAddRefCnt_cbegin_cend = 2;
 428   static constexpr uint32_t kExpectedAddRefCnt_Clear = 2;
 429   static constexpr uint32_t kExpectedAddRefCnt_ShallowSizeOfExcludingThis = 2;
 430   static constexpr uint32_t kExpectedAddRefCnt_ShallowSizeOfIncludingThis = 2;
 431   static constexpr uint32_t kExpectedAddRefCnt_SwapElements = 2;
 432   static constexpr uint32_t kExpectedAddRefCnt_MarkImmutable = 2;
 433 };
 434
 435 struct NonDefaultConstructible_MovingNonDefaultConstructible {
 436   using DataType = NonDefaultConstructible;
 437   using UserDataType = MovingNonDefaultConstructible;
 438
 439   static constexpr uint32_t kExpectedAddRefCnt_Contains = 1;
 440   static constexpr uint32_t kExpectedAddRefCnt_GetGeneration = 1;
 441   static constexpr uint32_t kExpectedAddRefCnt_SizeOfExcludingThis = 1;
 442   static constexpr uint32_t kExpectedAddRefCnt_SizeOfIncludingThis = 1;
 443   static constexpr uint32_t kExpectedAddRefCnt_Count = 1;
 444   static constexpr uint32_t kExpectedAddRefCnt_IsEmpty = 1;
 445   static constexpr uint32_t kExpectedAddRefCnt_Get_OutputParam = 2;
 446   static constexpr uint32_t kExpectedAddRefCnt_MaybeGet = 2;
 447   static constexpr uint32_t kExpectedAddRefCnt_InsertOrUpdate = 1;
 448   static constexpr uint32_t kExpectedAddRefCnt_InsertOrUpdate_Fallible = 1;
 449   static constexpr uint32_t kExpectedAddRefCnt_InsertOrUpdate_Rvalue = 1;
 450   static constexpr uint32_t kExpectedAddRefCnt_InsertOrUpdate_Rvalue_Fallible =
 451       1;
 452   static constexpr uint32_t kExpectedAddRefCnt_Remove = 1;
 453   static constexpr uint32_t kExpectedAddRefCnt_Extract = 2;
 454   static constexpr uint32_t kExpectedAddRefCnt_RemoveIf = 1;
 455   static constexpr uint32_t kExpectedAddRefCnt_Lookup = 1;
 456   static constexpr uint32_t kExpectedAddRefCnt_Lookup_Remove = 1;
 457   static constexpr uint32_t kExpectedAddRefCnt_Iter = 1;
 458   static constexpr uint32_t kExpectedAddRefCnt_ConstIter = 1;
 459   static constexpr uint32_t kExpectedAddRefCnt_begin_end = 1;
 460   static constexpr uint32_t kExpectedAddRefCnt_cbegin_cend = 1;
 461   static constexpr uint32_t kExpectedAddRefCnt_Clear = 1;
 462   static constexpr uint32_t kExpectedAddRefCnt_ShallowSizeOfExcludingThis = 1;
 463   static constexpr uint32_t kExpectedAddRefCnt_ShallowSizeOfIncludingThis = 1;
 464   static constexpr uint32_t kExpectedAddRefCnt_SwapElements = 1;
 465   static constexpr uint32_t kExpectedAddRefCnt_MarkImmutable = 1;
 466 };
 467
 468 template <bool flag = false>
 469 void UnsupportedType() {
 470   static_assert(flag, "Unsupported type!");
 471 }
 472
 473 class TypeNames {
 474  public:
 475   template <typename T>
 476   static std::string GetName(int) {
 477     if constexpr (std::is_same<T,
 478                                DefaultConstructible_DefaultConstructible>()) {
 479       return "DefaultConstructible_DefaultConstructible";
 480     } else if constexpr (
 481         std::is_same<T, NonDefaultConstructible_NonDefaultConstructible>()) {
 482       return "NonDefaultConstructible_NonDefaultConstructible";
 483     } else if constexpr (
 484         std::is_same<T,
 485                      NonDefaultConstructible_MovingNonDefaultConstructible>()) {
 486       return "NonDefaultConstructible_MovingNonDefaultConstructible";
 487     } else {
 488       UnsupportedType();
 489     }
 490   }
 491 };
 492
 493 template <typename TypeParam>
 494 auto MakeEmptyBaseHashtable() {
 495   nsBaseHashtable<nsUint64HashKey, typename TypeParam::DataType,
 496                   typename TypeParam::UserDataType>
 497       table;
 498
 499   return table;
 500 }
 501
 502 template <typename TypeParam>
 503 auto MakeBaseHashtable(const uint32_t aExpectedAddRefCnt) {
 504   auto table = MakeEmptyBaseHashtable<TypeParam>();
 505
 506   auto myChar = MakeRefPtr<TestUniCharRefCounted>(42, aExpectedAddRefCnt);
 507
 508   table.InsertOrUpdate(1, typename TypeParam::UserDataType(std::move(myChar)));
 509
 510   return table;
 511 }
 512
 513 template <typename TypeParam>
 514 typename TypeParam::DataType GetDataFrom(
 515     typename TypeParam::UserDataType& aUserData) {
 516   if constexpr (std::is_same_v<TypeParam,
 517                                DefaultConstructible_DefaultConstructible> ||
 518                 std::is_same_v<
 519                     TypeParam,
 520                     NonDefaultConstructible_NonDefaultConstructible>) {
 521     return aUserData;
 522   } else if constexpr (
 523       std::is_same_v<TypeParam,
 524                      NonDefaultConstructible_MovingNonDefaultConstructible>) {
 525     return std::move(aUserData);
 526   } else {
 527     UnsupportedType();
 528   }
 529 }
 530
 531 template <typename TypeParam>
 532 typename TypeParam::DataType GetDataFrom(
 533     mozilla::Maybe<typename TypeParam::UserDataType>& aMaybeUserData) {
 534   return GetDataFrom<TypeParam>(*aMaybeUserData);
 535 }
 536
 537 }  // namespace TestHashtables
 538
 539 using namespace TestHashtables;
 540
 541 TEST(Hashtable, THashtable)
 542 {
 543   // check an nsTHashtable
 544   nsTHashtable<EntityToUnicodeEntry> EntityToUnicode(ENTITY_COUNT);
 545
 546   testTHashtable(EntityToUnicode, 5);
 547
 548   uint32_t count = nsTIterPrintRemove(EntityToUnicode);
 549   ASSERT_EQ(count, uint32_t(5));
 550
 551   count = nsTIterPrint(EntityToUnicode);
 552   ASSERT_EQ(count, uint32_t(0));
 553
 554   testTHashtable(EntityToUnicode, ENTITY_COUNT);
 555
 556   EntityToUnicode.Clear();
 557
 558   count = nsTIterPrint(EntityToUnicode);
 559   ASSERT_EQ(count, uint32_t(0));
 560 }
 561
 562 TEST(Hashtable, PtrHashtable)
 563 {
 564   nsTHashtable<nsPtrHashKey<int>> hash;
 565
 566   for (const auto& entry :
 567        const_cast<const nsTHashtable<nsPtrHashKey<int>>&>(hash)) {
 568     static_assert(std::is_same_v<decltype(entry), const nsPtrHashKey<int>&>);
 569   }
 570   for (auto& entry : hash) {
 571     static_assert(std::is_same_v<decltype(entry), nsPtrHashKey<int>&>);
 572   }
 573 }
 574
 575 TEST(Hashtable, Move)
 576 {
 577   const void* kPtr = reinterpret_cast<void*>(static_cast<uintptr_t>(0xbadc0de));
 578
 579   nsTHashtable<nsPtrHashKey<const void>> table;
 580   table.PutEntry(kPtr);
 581
 582   nsTHashtable<nsPtrHashKey<const void>> moved = std::move(table);
 583   ASSERT_EQ(table.Count(), 0u);
 584   ASSERT_EQ(moved.Count(), 1u);
 585
 586   EXPECT_TRUE(moved.Contains(kPtr));
 587   EXPECT_FALSE(table.Contains(kPtr));
 588 }
 589
 590 TEST(Hashtable, Keys)
 591 {
 592   static constexpr uint64_t count = 10;
 593
 594   nsTHashtable<nsUint64HashKey> table;
 595   for (uint64_t i = 0; i < count; i++) {
 596     table.PutEntry(i);
 597   }
 598
 599   nsTArray<uint64_t> keys;
 600   for (const uint64_t& key : table.Keys()) {
 601     keys.AppendElement(key);
 602   }
 603   keys.Sort();
 604
 605   EXPECT_EQ((nsTArray<uint64_t>{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}), keys);
 606 }
 607
 608 template <typename TypeParam>
 609 class BaseHashtableTest : public ::testing::Test {};
 610
 611 TYPED_TEST_SUITE_P(BaseHashtableTest);
 612
 613 TYPED_TEST_P(BaseHashtableTest, Contains) {
 614   auto table =
 615       MakeBaseHashtable<TypeParam>(TypeParam::kExpectedAddRefCnt_Contains);
 616
 617   auto res = table.Contains(1);
 618   EXPECT_TRUE(res);
 619 }
 620
 621 TYPED_TEST_P(BaseHashtableTest, GetGeneration) {
 622   auto table =
 623       MakeBaseHashtable<TypeParam>(TypeParam::kExpectedAddRefCnt_GetGeneration);
 624
 625   auto res = table.GetGeneration();
 626   EXPECT_GT(res, 0u);
 627 }
 628
 629 MOZ_DEFINE_MALLOC_SIZE_OF(MallocSizeOf);
 630
 631 TYPED_TEST_P(BaseHashtableTest, SizeOfExcludingThis) {
 632   // This doesn't compile at the moment, since nsBaseHashtableET lacks
 633   // SizeOfExcludingThis implementation. Bug 1689214.
 634 #if 0
 635   auto table = MakeBaseHashtable<TypeParam>(
 636       TypeParam::kExpectedAddRefCnt_SizeOfExcludingThis);
 637
 638   auto res = table.SizeOfExcludingThis(MallocSizeOf);
 639   EXPECT_GT(res, 0u);
 640 #endif
 641 }
 642
 643 TYPED_TEST_P(BaseHashtableTest, SizeOfIncludingThis) {
 644   // This doesn't compile at the moment, since nsBaseHashtableET lacks
 645   // SizeOfIncludingThis implementation. Bug 1689214.
 646 #if 0
 647   auto table = MakeBaseHashtable<TypeParam>(
 648       TypeParam::kExpectedAddRefCnt_SizeOfIncludingThis);
 649
 650   auto res = table.SizeOfIncludingThis(MallocSizeOf);
 651   EXPECT_GT(res, 0u);
 652 #endif
 653 }
 654
 655 TYPED_TEST_P(BaseHashtableTest, Count) {
 656   auto table =
 657       MakeBaseHashtable<TypeParam>(TypeParam::kExpectedAddRefCnt_Count);
 658
 659   auto res = table.Count();
 660   EXPECT_EQ(res, 1u);
 661 }
 662
 663 TYPED_TEST_P(BaseHashtableTest, IsEmpty) {
 664   auto table =
 665       MakeBaseHashtable<TypeParam>(TypeParam::kExpectedAddRefCnt_IsEmpty);
 666
 667   auto res = table.IsEmpty();
 668   EXPECT_EQ(res, false);
 669 }
 670
 671 TYPED_TEST_P(BaseHashtableTest, Get_OutputParam) {
 672   auto table = MakeBaseHashtable<TypeParam>(
 673       TypeParam::kExpectedAddRefCnt_Get_OutputParam);
 674
 675   typename TypeParam::UserDataType userData(nullptr);
 676   auto res = table.Get(1, &userData);
 677   EXPECT_TRUE(res);
 678
 679   auto data = GetDataFrom<TypeParam>(userData);
 680   EXPECT_EQ(data.CharRef()->GetChar(), 42u);
 681 }
 682
 683 TYPED_TEST_P(BaseHashtableTest, Get) {
 684   // The Get overload can't support non-default-constructible UserDataType.
 685   if constexpr (std::is_default_constructible_v<
 686                     typename TypeParam::UserDataType>) {
 687     auto table =
 688         MakeBaseHashtable<TypeParam>(TypeParam::kExpectedAddRefCnt_Get);
 689
 690     auto userData = table.Get(1);
 691
 692     auto data = GetDataFrom<TypeParam>(userData);
 693     EXPECT_EQ(data.CharRef()->GetChar(), 42u);
 694   }
 695 }
 696
 697 TYPED_TEST_P(BaseHashtableTest, MaybeGet) {
 698   auto table =
 699       MakeBaseHashtable<TypeParam>(TypeParam::kExpectedAddRefCnt_MaybeGet);
 700
 701   auto maybeUserData = table.MaybeGet(1);
 702   EXPECT_TRUE(maybeUserData);
 703
 704   auto data = GetDataFrom<TypeParam>(maybeUserData);
 705   EXPECT_EQ(data.CharRef()->GetChar(), 42u);
 706 }
 707
 708 TYPED_TEST_P(BaseHashtableTest, LookupOrInsert_Default) {
 709   if constexpr (std::is_default_constructible_v<typename TypeParam::DataType>) {
 710     auto table = MakeEmptyBaseHashtable<TypeParam>();
 711
 712     typename TypeParam::DataType& data = table.LookupOrInsert(1);
 713     EXPECT_EQ(data.CharRef(), nullptr);
 714
 715     data = typename TypeParam::DataType(MakeRefPtr<TestUniCharRefCounted>(
 716         42, TypeParam::kExpectedAddRefCnt_LookupOrInsert));
 717   }
 718 }
 719
 720 TYPED_TEST_P(BaseHashtableTest, LookupOrInsert_NonDefault) {
 721   auto table = MakeEmptyBaseHashtable<TypeParam>();
 722
 723   typename TypeParam::DataType& data = table.LookupOrInsert(
 724       1, typename TypeParam::DataType{MakeRefPtr<TestUniCharRefCounted>(42)});
 725   EXPECT_NE(data.CharRef(), nullptr);
 726 }
 727
 728 TYPED_TEST_P(BaseHashtableTest, LookupOrInsert_NonDefault_AlreadyPresent) {
 729   auto table = MakeEmptyBaseHashtable<TypeParam>();
 730
 731   typename TypeParam::DataType& data1 = table.LookupOrInsert(
 732       1, typename TypeParam::DataType{MakeRefPtr<TestUniCharRefCounted>(42)});
 733   TestUniCharRefCounted* const address = data1.CharRef();
 734   typename TypeParam::DataType& data2 = table.LookupOrInsert(
 735       1,
 736       typename TypeParam::DataType{MakeRefPtr<TestUniCharRefCounted>(42, 1)});
 737   EXPECT_EQ(&data1, &data2);
 738   EXPECT_EQ(address, data2.CharRef());
 739 }
 740
 741 TYPED_TEST_P(BaseHashtableTest, LookupOrInsertWith) {
 742   auto table = MakeEmptyBaseHashtable<TypeParam>();
 743
 744   typename TypeParam::DataType& data = table.LookupOrInsertWith(1, [] {
 745     return typename TypeParam::DataType{MakeRefPtr<TestUniCharRefCounted>(42)};
 746   });
 747   EXPECT_NE(data.CharRef(), nullptr);
 748 }
 749
 750 TYPED_TEST_P(BaseHashtableTest, LookupOrInsertWith_AlreadyPresent) {
 751   auto table = MakeEmptyBaseHashtable<TypeParam>();
 752
 753   table.LookupOrInsertWith(1, [] {
 754     return typename TypeParam::DataType{MakeRefPtr<TestUniCharRefCounted>(42)};
 755   });
 756   table.LookupOrInsertWith(1, [] {
 757     ADD_FAILURE();
 758     return typename TypeParam::DataType{MakeRefPtr<TestUniCharRefCounted>(42)};
 759   });
 760 }
 761
 762 TYPED_TEST_P(BaseHashtableTest, InsertOrUpdate) {
 763   auto table = MakeEmptyBaseHashtable<TypeParam>();
 764
 765   auto myChar = MakeRefPtr<TestUniCharRefCounted>(
 766       42, TypeParam::kExpectedAddRefCnt_InsertOrUpdate);
 767
 768   table.InsertOrUpdate(1, typename TypeParam::UserDataType(std::move(myChar)));
 769 }
 770
 771 TYPED_TEST_P(BaseHashtableTest, InsertOrUpdate_Fallible) {
 772   auto table = MakeEmptyBaseHashtable<TypeParam>();
 773
 774   auto myChar = MakeRefPtr<TestUniCharRefCounted>(
 775       42, TypeParam::kExpectedAddRefCnt_InsertOrUpdate_Fallible);
 776
 777   auto res = table.InsertOrUpdate(
 778       1, typename TypeParam::UserDataType(std::move(myChar)),
 779       mozilla::fallible);
 780   EXPECT_TRUE(res);
 781 }
 782
 783 TYPED_TEST_P(BaseHashtableTest, InsertOrUpdate_Rvalue) {
 784   auto table = MakeEmptyBaseHashtable<TypeParam>();
 785
 786   auto myChar = MakeRefPtr<TestUniCharRefCounted>(
 787       42, TypeParam::kExpectedAddRefCnt_InsertOrUpdate_Rvalue);
 788
 789   table.InsertOrUpdate(
 790       1, std::move(typename TypeParam::UserDataType(std::move(myChar))));
 791 }
 792
 793 TYPED_TEST_P(BaseHashtableTest, InsertOrUpdate_Rvalue_Fallible) {
 794   auto table = MakeEmptyBaseHashtable<TypeParam>();
 795
 796   auto myChar = MakeRefPtr<TestUniCharRefCounted>(
 797       42, TypeParam::kExpectedAddRefCnt_InsertOrUpdate_Rvalue_Fallible);
 798
 799   auto res = table.InsertOrUpdate(
 800       1, std::move(typename TypeParam::UserDataType(std::move(myChar))),
 801       mozilla::fallible);
 802   EXPECT_TRUE(res);
 803 }
 804
 805 TYPED_TEST_P(BaseHashtableTest, Remove_OutputParam) {
 806   // The Remove overload can't support non-default-constructible DataType.
 807   if constexpr (std::is_default_constructible_v<typename TypeParam::DataType>) {
 808     auto table = MakeBaseHashtable<TypeParam>(
 809         TypeParam::kExpectedAddRefCnt_Remove_OutputParam);
 810
 811     typename TypeParam::DataType data;
 812     auto res = table.Remove(1, &data);
 813     EXPECT_TRUE(res);
 814     EXPECT_EQ(data.CharRef()->GetChar(), 42u);
 815   }
 816 }
 817
 818 TYPED_TEST_P(BaseHashtableTest, Remove) {
 819   auto table =
 820       MakeBaseHashtable<TypeParam>(TypeParam::kExpectedAddRefCnt_Remove);
 821
 822   auto res = table.Remove(1);
 823   EXPECT_TRUE(res);
 824 }
 825
 826 TYPED_TEST_P(BaseHashtableTest, Extract) {
 827   auto table =
 828       MakeBaseHashtable<TypeParam>(TypeParam::kExpectedAddRefCnt_Extract);
 829
 830   auto maybeData = table.Extract(1);
 831   EXPECT_TRUE(maybeData);
 832   EXPECT_EQ(maybeData->CharRef()->GetChar(), 42u);
 833 }
 834
 835 TYPED_TEST_P(BaseHashtableTest, RemoveIf) {
 836   auto table =
 837       MakeBaseHashtable<TypeParam>(TypeParam::kExpectedAddRefCnt_RemoveIf);
 838
 839   table.RemoveIf([](const auto&) { return true; });
 840 }
 841
 842 TYPED_TEST_P(BaseHashtableTest, Lookup) {
 843   auto table =
 844       MakeBaseHashtable<TypeParam>(TypeParam::kExpectedAddRefCnt_Lookup);
 845
 846   auto res = table.Lookup(1);
 847   EXPECT_TRUE(res);
 848   EXPECT_EQ(res.Data().CharRef()->GetChar(), 42u);
 849 }
 850
 851 TYPED_TEST_P(BaseHashtableTest, Lookup_Remove) {
 852   auto table =
 853       MakeBaseHashtable<TypeParam>(TypeParam::kExpectedAddRefCnt_Lookup_Remove);
 854
 855   auto res = table.Lookup(1);
 856   EXPECT_TRUE(res);
 857   EXPECT_EQ(res.Data().CharRef()->GetChar(), 42u);
 858
 859   res.Remove();
 860 }
 861
 862 TYPED_TEST_P(BaseHashtableTest, WithEntryHandle_NoOp) {
 863   auto table = MakeEmptyBaseHashtable<TypeParam>();
 864
 865   table.WithEntryHandle(1, [](auto&&) {});
 866
 867   EXPECT_FALSE(table.Contains(1));
 868 }
 869
 870 TYPED_TEST_P(BaseHashtableTest, WithEntryHandle_NotFound_OrInsert) {
 871   auto table = MakeEmptyBaseHashtable<TypeParam>();
 872
 873   table.WithEntryHandle(1, [](auto&& entry) {
 874     entry.OrInsert(typename TypeParam::UserDataType(
 875         MakeRefPtr<TestUniCharRefCounted>(42)));
 876   });
 877
 878   EXPECT_TRUE(table.Contains(1));
 879 }
 880
 881 TYPED_TEST_P(BaseHashtableTest, WithEntryHandle_NotFound_OrInsertFrom) {
 882   auto table = MakeEmptyBaseHashtable<TypeParam>();
 883
 884   table.WithEntryHandle(1, [](auto&& entry) {
 885     entry.OrInsertWith([] {
 886       return typename TypeParam::UserDataType(
 887           MakeRefPtr<TestUniCharRefCounted>(42));
 888     });
 889   });
 890
 891   EXPECT_TRUE(table.Contains(1));
 892 }
 893
 894 TYPED_TEST_P(BaseHashtableTest, WithEntryHandle_NotFound_OrInsertFrom_Exists) {
 895   auto table = MakeEmptyBaseHashtable<TypeParam>();
 896
 897   table.WithEntryHandle(1, [](auto&& entry) {
 898     entry.OrInsertWith([] {
 899       return typename TypeParam::UserDataType(
 900           MakeRefPtr<TestUniCharRefCounted>(42));
 901     });
 902   });
 903   table.WithEntryHandle(1, [](auto&& entry) {
 904     entry.OrInsertWith([]() -> typename TypeParam::UserDataType {
 905       ADD_FAILURE();
 906       return typename TypeParam::UserDataType(
 907           MakeRefPtr<TestUniCharRefCounted>(42));
 908     });
 909   });
 910
 911   EXPECT_TRUE(table.Contains(1));
 912 }
 913
 914 TYPED_TEST_P(BaseHashtableTest, WithEntryHandle_NotFound_OrRemove) {
 915   auto table = MakeEmptyBaseHashtable<TypeParam>();
 916
 917   table.WithEntryHandle(1, [](auto&& entry) { entry.OrRemove(); });
 918
 919   EXPECT_FALSE(table.Contains(1));
 920 }
 921
 922 TYPED_TEST_P(BaseHashtableTest, WithEntryHandle_NotFound_OrRemove_Exists) {
 923   auto table = MakeEmptyBaseHashtable<TypeParam>();
 924
 925   table.WithEntryHandle(1, [](auto&& entry) {
 926     entry.OrInsertWith([] {
 927       return typename TypeParam::UserDataType(
 928           MakeRefPtr<TestUniCharRefCounted>(42));
 929     });
 930   });
 931   table.WithEntryHandle(1, [](auto&& entry) { entry.OrRemove(); });
 932
 933   EXPECT_FALSE(table.Contains(1));
 934 }
 935
 936 TYPED_TEST_P(BaseHashtableTest, Iter) {
 937   auto table = MakeBaseHashtable<TypeParam>(TypeParam::kExpectedAddRefCnt_Iter);
 938
 939   for (auto iter = table.Iter(); !iter.Done(); iter.Next()) {
 940     EXPECT_EQ(iter.Data().CharRef()->GetChar(), 42u);
 941   }
 942 }
 943
 944 TYPED_TEST_P(BaseHashtableTest, ConstIter) {
 945   auto table =
 946       MakeBaseHashtable<TypeParam>(TypeParam::kExpectedAddRefCnt_ConstIter);
 947
 948   for (auto iter = table.ConstIter(); !iter.Done(); iter.Next()) {
 949     EXPECT_EQ(iter.Data().CharRef()->GetChar(), 42u);
 950   }
 951 }
 952
 953 TYPED_TEST_P(BaseHashtableTest, begin_end) {
 954   auto table =
 955       MakeBaseHashtable<TypeParam>(TypeParam::kExpectedAddRefCnt_begin_end);
 956
 957   auto res = std::count_if(table.begin(), table.end(), [](const auto& entry) {
 958     return entry.GetData().CharRef()->GetChar() == 42;
 959   });
 960   EXPECT_EQ(res, 1);
 961 }
 962
 963 TYPED_TEST_P(BaseHashtableTest, cbegin_cend) {
 964   auto table =
 965       MakeBaseHashtable<TypeParam>(TypeParam::kExpectedAddRefCnt_cbegin_cend);
 966
 967   auto res = std::count_if(table.cbegin(), table.cend(), [](const auto& entry) {
 968     return entry.GetData().CharRef()->GetChar() == 42;
 969   });
 970   EXPECT_EQ(res, 1);
 971 }
 972
 973 TYPED_TEST_P(BaseHashtableTest, Clear) {
 974   auto table =
 975       MakeBaseHashtable<TypeParam>(TypeParam::kExpectedAddRefCnt_Clear);
 976
 977   table.Clear();
 978 }
 979
 980 TYPED_TEST_P(BaseHashtableTest, ShallowSizeOfExcludingThis) {
 981   auto table = MakeBaseHashtable<TypeParam>(
 982       TypeParam::kExpectedAddRefCnt_ShallowSizeOfExcludingThis);
 983
 984   auto res = table.ShallowSizeOfExcludingThis(MallocSizeOf);
 985   EXPECT_GT(res, 0u);
 986 }
 987
 988 TYPED_TEST_P(BaseHashtableTest, ShallowSizeOfIncludingThis) {
 989   // Make this work with ASAN builds, bug 1689549.
 990 #if !defined(MOZ_ASAN)
 991   auto table = MakeBaseHashtable<TypeParam>(
 992       TypeParam::kExpectedAddRefCnt_ShallowSizeOfIncludingThis);
 993
 994   auto res = table.ShallowSizeOfIncludingThis(MallocSizeOf);
 995   EXPECT_GT(res, 0u);
 996 #endif
 997 }
 998
 999 TYPED_TEST_P(BaseHashtableTest, SwapElements) {
1000   auto table =
1001       MakeBaseHashtable<TypeParam>(TypeParam::kExpectedAddRefCnt_SwapElements);
1002
1003   auto table2 = MakeEmptyBaseHashtable<TypeParam>();
1004
1005   table.SwapElements(table2);
1006 }
1007
1008 TYPED_TEST_P(BaseHashtableTest, MarkImmutable) {
1009   auto table =
1010       MakeBaseHashtable<TypeParam>(TypeParam::kExpectedAddRefCnt_MarkImmutable);
1011
1012   table.MarkImmutable();
1013 }
1014
1015 REGISTER_TYPED_TEST_SUITE_P(
1016     BaseHashtableTest, Contains, GetGeneration, SizeOfExcludingThis,
1017     SizeOfIncludingThis, Count, IsEmpty, Get_OutputParam, Get, MaybeGet,
1018     LookupOrInsert_Default, LookupOrInsert_NonDefault,
1019     LookupOrInsert_NonDefault_AlreadyPresent, LookupOrInsertWith,
1020     LookupOrInsertWith_AlreadyPresent, InsertOrUpdate, InsertOrUpdate_Fallible,
1021     InsertOrUpdate_Rvalue, InsertOrUpdate_Rvalue_Fallible, Remove_OutputParam,
1022     Remove, Extract, RemoveIf, Lookup, Lookup_Remove, WithEntryHandle_NoOp,
1023     WithEntryHandle_NotFound_OrInsert, WithEntryHandle_NotFound_OrInsertFrom,
1024     WithEntryHandle_NotFound_OrInsertFrom_Exists,
1025     WithEntryHandle_NotFound_OrRemove, WithEntryHandle_NotFound_OrRemove_Exists,
1026     Iter, ConstIter, begin_end, cbegin_cend, Clear, ShallowSizeOfExcludingThis,
1027     ShallowSizeOfIncludingThis, SwapElements, MarkImmutable);
1028
1029 using BaseHashtableTestTypes =
1030     ::testing::Types<DefaultConstructible_DefaultConstructible,
1031                      NonDefaultConstructible_NonDefaultConstructible,
1032                      NonDefaultConstructible_MovingNonDefaultConstructible>;
1033
1034 INSTANTIATE_TYPED_TEST_SUITE_P(Hashtables, BaseHashtableTest,
1035                                BaseHashtableTestTypes, TypeNames);
1036
1037 TEST(Hashtables, DataHashtable)
1038 {
1039   // check a data-hashtable
1040   nsTHashMap<nsUint32HashKey, const char*> UniToEntity(ENTITY_COUNT);
1041
1042   for (auto& entity : gEntities) {
1043     UniToEntity.InsertOrUpdate(entity.mUnicode, entity.mStr);
1044   }
1045
1046   const char* str;
1047
1048   for (auto& entity : gEntities) {
1049     ASSERT_TRUE(UniToEntity.Get(entity.mUnicode, &str));
1050   }
1051
1052   ASSERT_FALSE(UniToEntity.Get(99446, &str));
1053
1054   uint32_t count = 0;
1055   for (auto iter = UniToEntity.Iter(); !iter.Done(); iter.Next()) {
1056     count++;
1057   }
1058   ASSERT_EQ(count, ENTITY_COUNT);
1059
1060   UniToEntity.Clear();
1061
1062   count = 0;
1063   for (auto iter = UniToEntity.Iter(); !iter.Done(); iter.Next()) {
1064     printf("  enumerated %u = \"%s\"\n", iter.Key(), iter.Data());
1065     count++;
1066   }
1067   ASSERT_EQ(count, uint32_t(0));
1068 }
1069
1070 TEST(Hashtables, DataHashtable_STLIterators)
1071 {
1072   using mozilla::Unused;
1073
1074   nsTHashMap<nsUint32HashKey, const char*> UniToEntity(ENTITY_COUNT);
1075
1076   for (auto& entity : gEntities) {
1077     UniToEntity.InsertOrUpdate(entity.mUnicode, entity.mStr);
1078   }
1079
1080   // operators, including conversion from iterator to const_iterator
1081   nsTHashMap<nsUint32HashKey, const char*>::const_iterator ci =
1082       UniToEntity.begin();
1083   ++ci;
1084   ASSERT_EQ(1, std::distance(UniToEntity.cbegin(), ci++));
1085   ASSERT_EQ(2, std::distance(UniToEntity.cbegin(), ci));
1086   ASSERT_TRUE(ci == ci);
1087   auto otherCi = ci;
1088   ++otherCi;
1089   ++ci;
1090   ASSERT_TRUE(&*ci == &*otherCi);
1091
1092   // STL algorithms (just to check that the iterator sufficiently conforms
1093   // with the actual syntactical requirements of those algorithms).
1094   std::for_each(UniToEntity.cbegin(), UniToEntity.cend(),
1095                 [](const auto& entry) {});
1096   Unused << std::find_if(
1097       UniToEntity.cbegin(), UniToEntity.cend(),
1098       [](const auto& entry) { return entry.GetKey() == 42; });
1099   Unused << std::accumulate(
1100       UniToEntity.cbegin(), UniToEntity.cend(), 0u,
1101       [](size_t sum, const auto& entry) { return sum + entry.GetKey(); });
1102   Unused << std::any_of(UniToEntity.cbegin(), UniToEntity.cend(),
1103                         [](const auto& entry) { return entry.GetKey() == 42; });
1104   Unused << std::max_element(UniToEntity.cbegin(), UniToEntity.cend(),
1105                              [](const auto& lhs, const auto& rhs) {
1106                                return lhs.GetKey() > rhs.GetKey();
1107                              });
1108
1109   // const range-based for
1110   {
1111     std::set<EntityNode> entities(gEntities, gEntities + ENTITY_COUNT);
1112     for (const auto& entity :
1113          const_cast<const nsTHashMap<nsUint32HashKey, const char*>&>(
1114              UniToEntity)) {
1115       ASSERT_EQ(1u,
1116                 entities.erase(EntityNode{entity.GetData(), entity.GetKey()}));
1117     }
1118     ASSERT_TRUE(entities.empty());
1119   }
1120
1121   // non-const range-based for
1122   {
1123     std::set<EntityNode> entities(gEntities, gEntities + ENTITY_COUNT);
1124     for (auto& entity : UniToEntity) {
1125       ASSERT_EQ(1u,
1126                 entities.erase(EntityNode{entity.GetData(), entity.GetKey()}));
1127
1128       entity.SetData(nullptr);
1129       ASSERT_EQ(nullptr, entity.GetData());
1130     }
1131     ASSERT_TRUE(entities.empty());
1132   }
1133 }
1134
1135 TEST(Hashtables, DataHashtable_RemoveIf)
1136 {
1137   // check a data-hashtable
1138   nsTHashMap<nsUint32HashKey, const char*> UniToEntity(ENTITY_COUNT);
1139
1140   for (auto& entity : gEntities) {
1141     UniToEntity.InsertOrUpdate(entity.mUnicode, entity.mStr);
1142   }
1143
1144   UniToEntity.RemoveIf([](const auto& iter) { return iter.Key() >= 170; });
1145
1146   ASSERT_EQ(10u, UniToEntity.Count());
1147 }
1148
1149 TEST(Hashtables, ClassHashtable)
1150 {
1151   // check a class-hashtable
1152   nsClassHashtable<nsCStringHashKey, TestUniChar> EntToUniClass(ENTITY_COUNT);
1153
1154   for (auto& entity : gEntities) {
1155     // Insert a sub-class of TestUniChar to test if this is accepted by
1156     // InsertOrUpdate.
1157     EntToUniClass.InsertOrUpdate(
1158         nsDependentCString(entity.mStr),
1159         mozilla::MakeUnique<TestUniCharDerived>(entity.mUnicode));
1160   }
1161
1162   TestUniChar* myChar;
1163
1164   for (auto& entity : gEntities) {
1165     ASSERT_TRUE(EntToUniClass.Get(nsDependentCString(entity.mStr), &myChar));
1166   }
1167
1168   ASSERT_FALSE(EntToUniClass.Get("xxxx"_ns, &myChar));
1169
1170   uint32_t count = 0;
1171   for (auto iter = EntToUniClass.Iter(); !iter.Done(); iter.Next()) {
1172     count++;
1173   }
1174   ASSERT_EQ(count, ENTITY_COUNT);
1175
1176   EntToUniClass.Clear();
1177
1178   count = 0;
1179   for (auto iter = EntToUniClass.Iter(); !iter.Done(); iter.Next()) {
1180     count++;
1181   }
1182   ASSERT_EQ(count, uint32_t(0));
1183 }
1184
1185 TEST(Hashtables, ClassHashtable_RangeBasedFor)
1186 {
1187   // check a class-hashtable
1188   nsClassHashtable<nsCStringHashKey, TestUniChar> EntToUniClass(ENTITY_COUNT);
1189
1190   for (auto& entity : gEntities) {
1191     EntToUniClass.InsertOrUpdate(nsDependentCString(entity.mStr),
1192                                  MakeUnique<TestUniChar>(entity.mUnicode));
1193   }
1194
1195   // const range-based for
1196   {
1197     std::set<EntityNode> entities(gEntities, gEntities + ENTITY_COUNT);
1198     for (const auto& entity :
1199          const_cast<const nsClassHashtable<nsCStringHashKey, TestUniChar>&>(
1200              EntToUniClass)) {
1201       const char* str;
1202       entity.GetKey().GetData(&str);
1203       ASSERT_EQ(1u,
1204                 entities.erase(EntityNode{str, entity.GetData()->GetChar()}));
1205     }
1206     ASSERT_TRUE(entities.empty());
1207   }
1208
1209   // non-const range-based for
1210   {
1211     std::set<EntityNode> entities(gEntities, gEntities + ENTITY_COUNT);
1212     for (auto& entity : EntToUniClass) {
1213       const char* str;
1214       entity.GetKey().GetData(&str);
1215       ASSERT_EQ(1u,
1216                 entities.erase(EntityNode{str, entity.GetData()->GetChar()}));
1217
1218       entity.SetData(UniquePtr<TestUniChar>{});
1219       ASSERT_EQ(nullptr, entity.GetData());
1220     }
1221     ASSERT_TRUE(entities.empty());
1222   }
1223 }
1224
1225 TEST(Hashtables, DataHashtableWithInterfaceKey)
1226 {
1227   // check a data-hashtable with an interface key
1228   nsTHashMap<nsISupportsHashKey, uint32_t> EntToUniClass2(ENTITY_COUNT);
1229
1230   nsCOMArray<IFoo> fooArray;
1231
1232   for (uint32_t i = 0; i < ENTITY_COUNT; ++i) {
1233     nsCOMPtr<IFoo> foo;
1234     CreateIFoo(getter_AddRefs(foo));
1235     foo->SetString(nsDependentCString(gEntities[i].mStr));
1236
1237     fooArray.InsertObjectAt(foo, i);
1238
1239     EntToUniClass2.InsertOrUpdate(foo, gEntities[i].mUnicode);
1240   }
1241
1242   uint32_t myChar2;
1243
1244   for (uint32_t i = 0; i < ENTITY_COUNT; ++i) {
1245     ASSERT_TRUE(EntToUniClass2.Get(fooArray[i], &myChar2));
1246   }
1247
1248   ASSERT_FALSE(EntToUniClass2.Get((nsISupports*)0x55443316, &myChar2));
1249
1250   uint32_t count = 0;
1251   for (auto iter = EntToUniClass2.Iter(); !iter.Done(); iter.Next()) {
1252     nsAutoCString s;
1253     nsCOMPtr<IFoo> foo = do_QueryInterface(iter.Key());
1254     foo->GetString(s);
1255     count++;
1256   }
1257   ASSERT_EQ(count, ENTITY_COUNT);
1258
1259   EntToUniClass2.Clear();
1260
1261   count = 0;
1262   for (auto iter = EntToUniClass2.Iter(); !iter.Done(); iter.Next()) {
1263     nsAutoCString s;
1264     nsCOMPtr<IFoo> foo = do_QueryInterface(iter.Key());
1265     foo->GetString(s);
1266     count++;
1267   }
1268   ASSERT_EQ(count, uint32_t(0));
1269 }
1270
1271 TEST(Hashtables, InterfaceHashtable)
1272 {
1273   // check an interface-hashtable with an uint32_t key
1274   nsInterfaceHashtable<nsUint32HashKey, IFoo> UniToEntClass2(ENTITY_COUNT);
1275
1276   for (auto& entity : gEntities) {
1277     nsCOMPtr<IFoo> foo;
1278     CreateIFoo(getter_AddRefs(foo));
1279     foo->SetString(nsDependentCString(entity.mStr));
1280
1281     UniToEntClass2.InsertOrUpdate(entity.mUnicode, foo);
1282   }
1283
1284   for (auto& entity : gEntities) {
1285     nsCOMPtr<IFoo> myEnt;
1286     ASSERT_TRUE(UniToEntClass2.Get(entity.mUnicode, getter_AddRefs(myEnt)));
1287
1288     nsAutoCString myEntStr;
1289     myEnt->GetString(myEntStr);
1290   }
1291
1292   nsCOMPtr<IFoo> myEnt;
1293   ASSERT_FALSE(UniToEntClass2.Get(9462, getter_AddRefs(myEnt)));
1294
1295   uint32_t count = 0;
1296   for (auto iter = UniToEntClass2.Iter(); !iter.Done(); iter.Next()) {
1297     nsAutoCString s;
1298     iter.UserData()->GetString(s);
1299     count++;
1300   }
1301   ASSERT_EQ(count, ENTITY_COUNT);
1302
1303   UniToEntClass2.Clear();
1304
1305   count = 0;
1306   for (auto iter = UniToEntClass2.Iter(); !iter.Done(); iter.Next()) {
1307     nsAutoCString s;
1308     iter.Data()->GetString(s);
1309     count++;
1310   }
1311   ASSERT_EQ(count, uint32_t(0));
1312 }
1313
1314 TEST(Hashtables, DataHashtable_WithEntryHandle)
1315 {
1316   // check WithEntryHandle/OrInsertWith
1317   nsTHashMap<nsUint32HashKey, const char*> UniToEntity(ENTITY_COUNT);
1318
1319   for (auto& entity : gEntities) {
1320     UniToEntity.WithEntryHandle(entity.mUnicode, [&entity](auto&& entry) {
1321       EXPECT_FALSE(entry);
1322       const char* const val =
1323           entry.OrInsertWith([&entity]() { return entity.mStr; });
1324       EXPECT_TRUE(entry);
1325       EXPECT_TRUE(val == entity.mStr);
1326       EXPECT_TRUE(entry.Data() == entity.mStr);
1327     });
1328   }
1329
1330   for (auto& entity : gEntities) {
1331     UniToEntity.WithEntryHandle(entity.mUnicode,
1332                                 [](auto&& entry) { EXPECT_TRUE(entry); });
1333   }
1334
1335   // 0 should not be found
1336   size_t count = UniToEntity.Count();
1337   UniToEntity.Lookup(0U).Remove();
1338   ASSERT_TRUE(count == UniToEntity.Count());
1339
1340   // Lookup should find all entries
1341   count = 0;
1342   for (auto& entity : gEntities) {
1343     if (UniToEntity.Lookup(entity.mUnicode)) {
1344       count++;
1345     }
1346   }
1347   ASSERT_TRUE(count == UniToEntity.Count());
1348
1349   for (auto& entity : gEntities) {
1350     UniToEntity.WithEntryHandle(entity.mUnicode,
1351                                 [](auto&& entry) { EXPECT_TRUE(entry); });
1352   }
1353
1354   // Lookup().Remove() should remove all entries.
1355   for (auto& entity : gEntities) {
1356     if (auto entry = UniToEntity.Lookup(entity.mUnicode)) {
1357       entry.Remove();
1358     }
1359   }
1360   ASSERT_TRUE(0 == UniToEntity.Count());
1361
1362   // Remove newly added entries via OrRemove.
1363   for (auto& entity : gEntities) {
1364     UniToEntity.WithEntryHandle(entity.mUnicode, [](auto&& entry) {
1365       EXPECT_FALSE(entry);
1366       entry.OrRemove();
1367     });
1368   }
1369   ASSERT_TRUE(0 == UniToEntity.Count());
1370
1371   // Remove existing entries via OrRemove.
1372   for (auto& entity : gEntities) {
1373     UniToEntity.WithEntryHandle(entity.mUnicode, [&entity](auto&& entry) {
1374       EXPECT_FALSE(entry);
1375       const char* const val = entry.OrInsert(entity.mStr);
1376       EXPECT_TRUE(entry);
1377       EXPECT_TRUE(val == entity.mStr);
1378       EXPECT_TRUE(entry.Data() == entity.mStr);
1379     });
1380
1381     UniToEntity.WithEntryHandle(entity.mUnicode, [](auto&& entry) {
1382       EXPECT_TRUE(entry);
1383       entry.OrRemove();
1384     });
1385   }
1386   ASSERT_TRUE(0 == UniToEntity.Count());
1387 }
1388
1389 TEST(Hashtables, ClassHashtable_WithEntryHandle)
1390 {
1391   // check a class-hashtable WithEntryHandle with null values
1392   nsClassHashtable<nsCStringHashKey, TestUniChar> EntToUniClass(ENTITY_COUNT);
1393
1394   for (auto& entity : gEntities) {
1395     EntToUniClass.WithEntryHandle(
1396         nsDependentCString(entity.mStr), [](auto&& entry) {
1397           EXPECT_FALSE(entry);
1398           const TestUniChar* val = entry.OrInsert(nullptr).get();
1399           EXPECT_TRUE(entry);
1400           EXPECT_TRUE(val == nullptr);
1401           EXPECT_TRUE(entry.Data() == nullptr);
1402         });
1403   }
1404
1405   for (auto& entity : gEntities) {
1406     EntToUniClass.WithEntryHandle(nsDependentCString(entity.mStr),
1407                                   [](auto&& entry) { EXPECT_TRUE(entry); });
1408     EntToUniClass.WithEntryHandle(
1409         nsDependentCString(entity.mStr),
1410         [](auto&& entry) { EXPECT_TRUE(entry.Data() == nullptr); });
1411   }
1412
1413   // "" should not be found
1414   size_t count = EntToUniClass.Count();
1415   EntToUniClass.Lookup(nsDependentCString("")).Remove();
1416   ASSERT_TRUE(count == EntToUniClass.Count());
1417
1418   // Lookup should find all entries.
1419   count = 0;
1420   for (auto& entity : gEntities) {
1421     if (EntToUniClass.Lookup(nsDependentCString(entity.mStr))) {
1422       count++;
1423     }
1424   }
1425   ASSERT_TRUE(count == EntToUniClass.Count());
1426
1427   for (auto& entity : gEntities) {
1428     EntToUniClass.WithEntryHandle(nsDependentCString(entity.mStr),
1429                                   [](auto&& entry) { EXPECT_TRUE(entry); });
1430   }
1431
1432   // Lookup().Remove() should remove all entries.
1433   for (auto& entity : gEntities) {
1434     if (auto entry = EntToUniClass.Lookup(nsDependentCString(entity.mStr))) {
1435       entry.Remove();
1436     }
1437   }
1438   ASSERT_TRUE(0 == EntToUniClass.Count());
1439
1440   // Remove newly added entries via OrRemove.
1441   for (auto& entity : gEntities) {
1442     EntToUniClass.WithEntryHandle(nsDependentCString(entity.mStr),
1443                                   [](auto&& entry) {
1444                                     EXPECT_FALSE(entry);
1445                                     entry.OrRemove();
1446                                   });
1447   }
1448   ASSERT_TRUE(0 == EntToUniClass.Count());
1449
1450   // Remove existing entries via OrRemove.
1451   for (auto& entity : gEntities) {
1452     EntToUniClass.WithEntryHandle(
1453         nsDependentCString(entity.mStr), [](auto&& entry) {
1454           EXPECT_FALSE(entry);
1455           const TestUniChar* val = entry.OrInsert(nullptr).get();
1456           EXPECT_TRUE(entry);
1457           EXPECT_TRUE(val == nullptr);
1458           EXPECT_TRUE(entry.Data() == nullptr);
1459         });
1460
1461     EntToUniClass.WithEntryHandle(nsDependentCString(entity.mStr),
1462                                   [](auto&& entry) {
1463                                     EXPECT_TRUE(entry);
1464                                     entry.OrRemove();
1465                                   });
1466   }
1467   ASSERT_TRUE(0 == EntToUniClass.Count());
1468 }
1469
1470 TEST(Hashtables, ClassHashtable_GetOrInsertNew_Present)
1471 {
1472   nsClassHashtable<nsCStringHashKey, TestUniChar> EntToUniClass(ENTITY_COUNT);
1473
1474   for (const auto& entity : gEntities) {
1475     EntToUniClass.InsertOrUpdate(
1476         nsDependentCString(entity.mStr),
1477         mozilla::MakeUnique<TestUniCharDerived>(entity.mUnicode));
1478   }
1479
1480   auto* entry = EntToUniClass.GetOrInsertNew("uml"_ns, 42);
1481   EXPECT_EQ(168u, entry->GetChar());
1482 }
1483
1484 TEST(Hashtables, ClassHashtable_GetOrInsertNew_NotPresent)
1485 {
1486   nsClassHashtable<nsCStringHashKey, TestUniChar> EntToUniClass(ENTITY_COUNT);
1487
1488   // This is going to insert a TestUniChar.
1489   auto* entry = EntToUniClass.GetOrInsertNew("uml"_ns, 42);
1490   EXPECT_EQ(42u, entry->GetChar());
1491 }
1492
1493 TEST(Hashtables, ClassHashtable_LookupOrInsertWith_Present)
1494 {
1495   nsClassHashtable<nsCStringHashKey, TestUniChar> EntToUniClass(ENTITY_COUNT);
1496
1497   for (const auto& entity : gEntities) {
1498     EntToUniClass.InsertOrUpdate(
1499         nsDependentCString(entity.mStr),
1500         mozilla::MakeUnique<TestUniCharDerived>(entity.mUnicode));
1501   }
1502
1503   const auto& entry = EntToUniClass.LookupOrInsertWith(
1504       "uml"_ns, [] { return mozilla::MakeUnique<TestUniCharDerived>(42); });
1505   EXPECT_EQ(168u, entry->GetChar());
1506 }
1507
1508 TEST(Hashtables, ClassHashtable_LookupOrInsertWith_NotPresent)
1509 {
1510   nsClassHashtable<nsCStringHashKey, TestUniChar> EntToUniClass(ENTITY_COUNT);
1511
1512   // This is going to insert a TestUniCharDerived.
1513   const auto& entry = EntToUniClass.LookupOrInsertWith(
1514       "uml"_ns, [] { return mozilla::MakeUnique<TestUniCharDerived>(42); });
1515   EXPECT_EQ(42u, entry->GetChar());
1516 }
1517
1518 TEST(Hashtables, RefPtrHashtable)
1519 {
1520   // check a RefPtr-hashtable
1521   nsRefPtrHashtable<nsCStringHashKey, TestUniCharRefCounted> EntToUniClass(
1522       ENTITY_COUNT);
1523
1524   for (auto& entity : gEntities) {
1525     EntToUniClass.InsertOrUpdate(
1526         nsDependentCString(entity.mStr),
1527         MakeRefPtr<TestUniCharRefCounted>(entity.mUnicode));
1528   }
1529
1530   TestUniCharRefCounted* myChar;
1531
1532   for (auto& entity : gEntities) {
1533     ASSERT_TRUE(EntToUniClass.Get(nsDependentCString(entity.mStr), &myChar));
1534   }
1535
1536   ASSERT_FALSE(EntToUniClass.Get("xxxx"_ns, &myChar));
1537
1538   uint32_t count = 0;
1539   for (auto iter = EntToUniClass.Iter(); !iter.Done(); iter.Next()) {
1540     count++;
1541   }
1542   ASSERT_EQ(count, ENTITY_COUNT);
1543
1544   EntToUniClass.Clear();
1545
1546   count = 0;
1547   for (auto iter = EntToUniClass.Iter(); !iter.Done(); iter.Next()) {
1548     count++;
1549   }
1550   ASSERT_EQ(count, uint32_t(0));
1551 }
1552
1553 TEST(Hashtables, RefPtrHashtable_Clone)
1554 {
1555   // check a RefPtr-hashtable
1556   nsRefPtrHashtable<nsCStringHashKey, TestUniCharRefCounted> EntToUniClass(
1557       ENTITY_COUNT);
1558
1559   for (auto& entity : gEntities) {
1560     EntToUniClass.InsertOrUpdate(
1561         nsDependentCString(entity.mStr),
1562         MakeRefPtr<TestUniCharRefCounted>(entity.mUnicode));
1563   }
1564
1565   auto clone = EntToUniClass.Clone();
1566   static_assert(std::is_same_v<decltype(clone), decltype(EntToUniClass)>);
1567
1568   EXPECT_EQ(clone.Count(), EntToUniClass.Count());
1569
1570   for (const auto& entry : EntToUniClass) {
1571     auto cloneEntry = clone.Lookup(entry.GetKey());
1572
1573     EXPECT_TRUE(cloneEntry);
1574     EXPECT_EQ(cloneEntry.Data(), entry.GetWeak());
1575   }
1576 }
1577
1578 TEST(Hashtables, Clone)
1579 {
1580   static constexpr uint64_t count = 10;
1581
1582   nsTHashMap<nsUint64HashKey, uint64_t> table;
1583   for (uint64_t i = 0; i < count; i++) {
1584     table.InsertOrUpdate(42 + i, i);
1585   }
1586
1587   auto clone = table.Clone();
1588
1589   static_assert(std::is_same_v<decltype(clone), decltype(table)>);
1590
1591   EXPECT_EQ(clone.Count(), table.Count());
1592
1593   for (const auto& entry : table) {
1594     auto cloneEntry = clone.Lookup(entry.GetKey());
1595
1596     EXPECT_TRUE(cloneEntry);
1597     EXPECT_EQ(cloneEntry.Data(), entry.GetData());
1598   }
1599 }
1600
1601 TEST(Hashtables, Values)
1602 {
1603   static constexpr uint64_t count = 10;
1604
1605   nsTHashMap<nsUint64HashKey, uint64_t> table;
1606   for (uint64_t i = 0; i < count; i++) {
1607     table.InsertOrUpdate(42 + i, i);
1608   }
1609
1610   nsTArray<uint64_t> values;
1611   for (const uint64_t& value : table.Values()) {
1612     values.AppendElement(value);
1613   }
1614   values.Sort();
1615
1616   EXPECT_EQ((nsTArray<uint64_t>{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}), values);
1617 }