test/core/gprpp/map_test.cc

   1 /*
   2  *
   3  * Copyright 2017 gRPC authors.
   4  *
   5  * Licensed under the Apache License, Version 2.0 (the "License");
   6  * you may not use this file except in compliance with the License.
   7  * You may obtain a copy of the License at
   8  *
   9  *     http://www.apache.org/licenses/LICENSE-2.0
  10  *
  11  * Unless required by applicable law or agreed to in writing, software
  12  * distributed under the License is distributed on an "AS IS" BASIS,
  13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14  * See the License for the specific language governing permissions and
  15  * limitations under the License.
  16  *
  17  */
  18
  19 #include "src/core/lib/gprpp/map.h"
  20
  21 #include <gtest/gtest.h>
  22
  23 #include "include/grpc/support/string_util.h"
  24 #include "src/core/lib/gprpp/inlined_vector.h"
  25 #include "src/core/lib/gprpp/memory.h"
  26 #include "src/core/lib/gprpp/orphanable.h"
  27 #include "src/core/lib/gprpp/ref_counted_ptr.h"
  28 #include "test/core/util/test_config.h"
  29
  30 namespace grpc_core {
  31 namespace testing {
  32 class Payload {
  33  public:
  34   Payload() : data_(-1) {}
  35   explicit Payload(int data) : data_(data) {}
  36   Payload(const Payload& other) : data_(other.data_) {}
  37   Payload& operator=(const Payload& other) {
  38     if (this != &other) {
  39       data_ = other.data_;
  40     }
  41     return *this;
  42   }
  43   int data() { return data_; }
  44
  45  private:
  46   int data_;
  47 };
  48
  49 inline UniquePtr<char> CopyString(const char* string) {
  50   return UniquePtr<char>(gpr_strdup(string));
  51 }
  52
  53 static constexpr char kKeys[][4] = {"abc", "efg", "hij", "klm", "xyz"};
  54
  55 class MapTest : public ::testing::Test {
  56  public:
  57   template <class Key, class T, class Compare>
  58   typename ::grpc_core::Map<Key, T, Compare>::Entry* Root(
  59       typename ::grpc_core::Map<Key, T, Compare>* map) {
  60     return map->root_;
  61   }
  62 };
  63
  64 // Test insertion of Payload
  65 TEST_F(MapTest, EmplaceAndFind) {
  66   Map<const char*, Payload, StringLess> test_map;
  67   for (int i = 0; i < 5; i++) {
  68     test_map.emplace(kKeys[i], Payload(i));
  69   }
  70   for (int i = 0; i < 5; i++) {
  71     EXPECT_EQ(i, test_map.find(kKeys[i])->second.data());
  72   }
  73 }
  74
  75 // Test insertion of Payload Unique Ptrs
  76 TEST_F(MapTest, EmplaceAndFindWithUniquePtrValue) {
  77   Map<const char*, UniquePtr<Payload>, StringLess> test_map;
  78   for (int i = 0; i < 5; i++) {
  79     test_map.emplace(kKeys[i], MakeUnique<Payload>(i));
  80   }
  81   for (int i = 0; i < 5; i++) {
  82     EXPECT_EQ(i, test_map.find(kKeys[i])->second->data());
  83   }
  84 }
  85
  86 // Test insertion of Unique Ptr kKeys and Payload
  87 TEST_F(MapTest, EmplaceAndFindWithUniquePtrKey) {
  88   Map<UniquePtr<char>, Payload, StringLess> test_map;
  89   for (int i = 0; i < 5; i++) {
  90     test_map.emplace(CopyString(kKeys[i]), Payload(i));
  91   }
  92   for (int i = 0; i < 5; i++) {
  93     EXPECT_EQ(i, test_map.find(CopyString(kKeys[i]))->second.data());
  94   }
  95 }
  96
  97 // Test insertion of Payload
  98 TEST_F(MapTest, InsertAndFind) {
  99   Map<const char*, Payload, StringLess> test_map;
 100   for (int i = 0; i < 5; i++) {
 101     test_map.insert(MakePair(kKeys[i], Payload(i)));
 102   }
 103   for (int i = 0; i < 5; i++) {
 104     EXPECT_EQ(i, test_map.find(kKeys[i])->second.data());
 105   }
 106 }
 107
 108 // Test insertion of Payload Unique Ptrs
 109 TEST_F(MapTest, InsertAndFindWithUniquePtrValue) {
 110   Map<const char*, UniquePtr<Payload>, StringLess> test_map;
 111   for (int i = 0; i < 5; i++) {
 112     test_map.insert(MakePair(kKeys[i], MakeUnique<Payload>(i)));
 113   }
 114   for (int i = 0; i < 5; i++) {
 115     EXPECT_EQ(i, test_map.find(kKeys[i])->second->data());
 116   }
 117 }
 118
 119 // Test insertion of Unique Ptr kKeys and Payload
 120 TEST_F(MapTest, InsertAndFindWithUniquePtrKey) {
 121   Map<UniquePtr<char>, Payload, StringLess> test_map;
 122   for (int i = 0; i < 5; i++) {
 123     test_map.insert(MakePair(CopyString(kKeys[i]), Payload(i)));
 124   }
 125   for (int i = 0; i < 5; i++) {
 126     EXPECT_EQ(i, test_map.find(CopyString(kKeys[i]))->second.data());
 127   }
 128 }
 129
 130 // Test bracket operators
 131 TEST_F(MapTest, BracketOperator) {
 132   Map<const char*, Payload, StringLess> test_map;
 133   for (int i = 0; i < 5; i++) {
 134     test_map[kKeys[i]] = Payload(i);
 135   }
 136   for (int i = 0; i < 5; i++) {
 137     EXPECT_EQ(i, test_map[kKeys[i]].data());
 138   }
 139 }
 140
 141 // Test bracket operators with unique pointer to payload
 142 TEST_F(MapTest, BracketOperatorWithUniquePtrValue) {
 143   Map<const char*, UniquePtr<Payload>, StringLess> test_map;
 144   for (int i = 0; i < 5; i++) {
 145     test_map[kKeys[i]] = MakeUnique<Payload>(i);
 146   }
 147   for (int i = 0; i < 5; i++) {
 148     EXPECT_EQ(i, test_map[kKeys[i]]->data());
 149   }
 150 }
 151
 152 // Test bracket operators with unique pointer to payload
 153 TEST_F(MapTest, BracketOperatorWithUniquePtrKey) {
 154   Map<UniquePtr<char>, Payload, StringLess> test_map;
 155   for (int i = 0; i < 5; i++) {
 156     test_map[CopyString(kKeys[i])] = Payload(i);
 157   }
 158   for (int i = 0; i < 5; i++) {
 159     EXPECT_EQ(i, test_map[CopyString(kKeys[i])].data());
 160   }
 161 }
 162
 163 // Test removal of a single value
 164 TEST_F(MapTest, Erase) {
 165   Map<const char*, Payload, StringLess> test_map;
 166   for (int i = 0; i < 5; i++) {
 167     test_map.emplace(kKeys[i], Payload(i));
 168   }
 169   EXPECT_EQ(test_map.size(), 5UL);
 170   EXPECT_EQ(test_map.erase(kKeys[3]), 1UL);  // Remove "hij"
 171   for (int i = 0; i < 5; i++) {
 172     if (i == 3) {  // "hij" should not be present
 173       EXPECT_TRUE(test_map.find(kKeys[i]) == test_map.end());
 174     } else {
 175       EXPECT_EQ(i, test_map.find(kKeys[i])->second.data());
 176     }
 177   }
 178   EXPECT_EQ(test_map.size(), 4UL);
 179 }
 180
 181 // Test removal of a single value with unique ptr to payload
 182 TEST_F(MapTest, EraseWithUniquePtrValue) {
 183   Map<const char*, UniquePtr<Payload>, StringLess> test_map;
 184   for (int i = 0; i < 5; i++) {
 185     test_map.emplace(kKeys[i], MakeUnique<Payload>(i));
 186   }
 187   EXPECT_EQ(test_map.size(), 5UL);
 188   test_map.erase(kKeys[3]);  // Remove "hij"
 189   for (int i = 0; i < 5; i++) {
 190     if (i == 3) {  // "hij" should not be present
 191       EXPECT_TRUE(test_map.find(kKeys[i]) == test_map.end());
 192     } else {
 193       EXPECT_EQ(i, test_map.find(kKeys[i])->second->data());
 194     }
 195   }
 196   EXPECT_EQ(test_map.size(), 4UL);
 197 }
 198
 199 // Test removal of a single value
 200 TEST_F(MapTest, EraseWithUniquePtrKey) {
 201   Map<UniquePtr<char>, Payload, StringLess> test_map;
 202   for (int i = 0; i < 5; i++) {
 203     test_map.emplace(CopyString(kKeys[i]), Payload(i));
 204   }
 205   EXPECT_EQ(test_map.size(), 5UL);
 206   test_map.erase(CopyString(kKeys[3]));  // Remove "hij"
 207   for (int i = 0; i < 5; i++) {
 208     if (i == 3) {  // "hij" should not be present
 209       EXPECT_TRUE(test_map.find(CopyString(kKeys[i])) == test_map.end());
 210     } else {
 211       EXPECT_EQ(i, test_map.find(CopyString(kKeys[i]))->second.data());
 212     }
 213   }
 214   EXPECT_EQ(test_map.size(), 4UL);
 215 }
 216
 217 // Test clear
 218 TEST_F(MapTest, SizeAndClear) {
 219   Map<const char*, Payload, StringLess> test_map;
 220   for (int i = 0; i < 5; i++) {
 221     test_map.emplace(kKeys[i], Payload(i));
 222   }
 223   EXPECT_EQ(test_map.size(), 5UL);
 224   EXPECT_FALSE(test_map.empty());
 225   test_map.clear();
 226   EXPECT_EQ(test_map.size(), 0UL);
 227   EXPECT_TRUE(test_map.empty());
 228 }
 229
 230 // Test clear with unique ptr payload
 231 TEST_F(MapTest, SizeAndClearWithUniquePtrValue) {
 232   Map<const char*, UniquePtr<Payload>, StringLess> test_map;
 233   for (int i = 0; i < 5; i++) {
 234     test_map.emplace(kKeys[i], MakeUnique<Payload>(i));
 235   }
 236   EXPECT_EQ(test_map.size(), 5UL);
 237   EXPECT_FALSE(test_map.empty());
 238   test_map.clear();
 239   EXPECT_EQ(test_map.size(), 0UL);
 240   EXPECT_TRUE(test_map.empty());
 241 }
 242
 243 // Test clear with unique ptr char key
 244 TEST_F(MapTest, SizeAndClearWithUniquePtrKey) {
 245   Map<UniquePtr<char>, Payload, StringLess> test_map;
 246   for (int i = 0; i < 5; i++) {
 247     test_map.emplace(CopyString(kKeys[i]), Payload(i));
 248   }
 249   EXPECT_EQ(test_map.size(), 5UL);
 250   EXPECT_FALSE(test_map.empty());
 251   test_map.clear();
 252   EXPECT_EQ(test_map.size(), 0UL);
 253   EXPECT_TRUE(test_map.empty());
 254 }
 255
 256 // Test correction of Left-Left Tree imbalance
 257 TEST_F(MapTest, MapLL) {
 258   Map<const char*, Payload, StringLess> test_map;
 259   for (int i = 2; i >= 0; i--) {
 260     test_map.emplace(kKeys[i], Payload(i));
 261   }
 262   EXPECT_EQ(strcmp(Root(&test_map)->pair.first, kKeys[1]), 0);
 263   EXPECT_EQ(strcmp(Root(&test_map)->left->pair.first, kKeys[0]), 0);
 264   EXPECT_EQ(strcmp(Root(&test_map)->right->pair.first, kKeys[2]), 0);
 265 }
 266
 267 // Test correction of Left-Right tree imbalance
 268 TEST_F(MapTest, MapLR) {
 269   Map<const char*, Payload, StringLess> test_map;
 270   int insertion_key_index[] = {2, 0, 1};
 271   for (int i = 0; i < 3; i++) {
 272     int key_index = insertion_key_index[i];
 273     test_map.emplace(kKeys[key_index], Payload(key_index));
 274   }
 275   EXPECT_EQ(strcmp(Root(&test_map)->pair.first, kKeys[1]), 0);
 276   EXPECT_EQ(strcmp(Root(&test_map)->left->pair.first, kKeys[0]), 0);
 277   EXPECT_EQ(strcmp(Root(&test_map)->right->pair.first, kKeys[2]), 0);
 278 }
 279
 280 // Test correction of Right-Left tree imbalance
 281 TEST_F(MapTest, MapRL) {
 282   Map<const char*, Payload, StringLess> test_map;
 283   int insertion_key_index[] = {0, 2, 1};
 284   for (int i = 0; i < 3; i++) {
 285     int key_index = insertion_key_index[i];
 286     test_map.emplace(kKeys[key_index], Payload(key_index));
 287   }
 288   EXPECT_EQ(strcmp(Root(&test_map)->pair.first, kKeys[1]), 0);
 289   EXPECT_EQ(strcmp(Root(&test_map)->left->pair.first, kKeys[0]), 0);
 290   EXPECT_EQ(strcmp(Root(&test_map)->right->pair.first, kKeys[2]), 0);
 291 }
 292
 293 // Test correction of Right-Right tree imbalance
 294 TEST_F(MapTest, MapRR) {
 295   Map<const char*, Payload, StringLess> test_map;
 296   for (int i = 0; i < 5; i++) {
 297     test_map.emplace(kKeys[i], Payload(i));
 298   }
 299   EXPECT_EQ(strcmp(Root(&test_map)->pair.first, kKeys[1]), 0);
 300   EXPECT_EQ(strcmp(Root(&test_map)->left->pair.first, kKeys[0]), 0);
 301   EXPECT_EQ(strcmp(Root(&test_map)->right->pair.first, kKeys[3]), 0);
 302   EXPECT_EQ(strcmp(Root(&test_map)->right->left->pair.first, kKeys[2]), 0);
 303   EXPECT_EQ(strcmp(Root(&test_map)->right->right->pair.first, kKeys[4]), 0);
 304 }
 305
 306 // Test correction after random insertion
 307 TEST_F(MapTest, MapRandomInsertions) {
 308   Map<const char*, Payload, StringLess> test_map;
 309   int insertion_key_index[] = {1, 4, 3, 0, 2};
 310   for (int i = 0; i < 5; i++) {
 311     int key_index = insertion_key_index[i];
 312     test_map.emplace(kKeys[key_index], Payload(key_index));
 313   }
 314   EXPECT_EQ(strcmp(Root(&test_map)->pair.first, kKeys[3]), 0);
 315   EXPECT_EQ(strcmp(Root(&test_map)->left->pair.first, kKeys[1]), 0);
 316   EXPECT_EQ(strcmp(Root(&test_map)->right->pair.first, kKeys[4]), 0);
 317   EXPECT_EQ(strcmp(Root(&test_map)->left->right->pair.first, kKeys[2]), 0);
 318   EXPECT_EQ(strcmp(Root(&test_map)->left->left->pair.first, kKeys[0]), 0);
 319 }
 320
 321 // Test Map iterator
 322 TEST_F(MapTest, Iteration) {
 323   Map<const char*, Payload, StringLess> test_map;
 324   for (int i = 4; i >= 0; --i) {
 325     test_map.emplace(kKeys[i], Payload(i));
 326   }
 327   auto it = test_map.begin();
 328   for (int i = 0; i < 5; ++i) {
 329     ASSERT_NE(it, test_map.end());
 330     EXPECT_STREQ(kKeys[i], it->first);
 331     EXPECT_EQ(i, it->second.data());
 332     ++it;
 333   }
 334   EXPECT_EQ(it, test_map.end());
 335 }
 336
 337 // Test Map iterator with unique ptr payload
 338 TEST_F(MapTest, IterationWithUniquePtrValue) {
 339   Map<const char*, UniquePtr<Payload>, StringLess> test_map;
 340   for (int i = 4; i >= 0; --i) {
 341     test_map.emplace(kKeys[i], MakeUnique<Payload>(i));
 342   }
 343   auto it = test_map.begin();
 344   for (int i = 0; i < 5; ++i) {
 345     ASSERT_NE(it, test_map.end());
 346     EXPECT_STREQ(kKeys[i], it->first);
 347     EXPECT_EQ(i, it->second->data());
 348     ++it;
 349   }
 350   EXPECT_EQ(it, test_map.end());
 351 }
 352
 353 // Test Map iterator with unique ptr to char key
 354 TEST_F(MapTest, IterationWithUniquePtrKey) {
 355   Map<UniquePtr<char>, Payload, StringLess> test_map;
 356   for (int i = 4; i >= 0; --i) {
 357     test_map.emplace(CopyString(kKeys[i]), Payload(i));
 358   }
 359   auto it = test_map.begin();
 360   for (int i = 0; i < 5; ++i) {
 361     ASSERT_NE(it, test_map.end());
 362     EXPECT_STREQ(kKeys[i], it->first.get());
 363     EXPECT_EQ(i, it->second.data());
 364     ++it;
 365   }
 366   EXPECT_EQ(it, test_map.end());
 367 }
 368
 369 // Test removing entries while iterating the map
 370 TEST_F(MapTest, EraseUsingIterator) {
 371   Map<const char*, Payload, StringLess> test_map;
 372   for (int i = 0; i < 5; i++) {
 373     test_map.emplace(kKeys[i], Payload(i));
 374   }
 375   int count = 0;
 376   for (auto iter = test_map.begin(); iter != test_map.end();) {
 377     EXPECT_EQ(iter->second.data(), count);
 378     if (count % 2 == 1) {
 379       iter = test_map.erase(iter);
 380     } else {
 381       ++iter;
 382     }
 383     ++count;
 384   }
 385   EXPECT_EQ(count, 5);
 386   auto it = test_map.begin();
 387   for (int i = 0; i < 5; ++i) {
 388     if (i % 2 == 0) {
 389       EXPECT_STREQ(kKeys[i], it->first);
 390       EXPECT_EQ(i, it->second.data());
 391       ++it;
 392     }
 393   }
 394   EXPECT_EQ(it, test_map.end());
 395 }
 396
 397 // Random ops on a Map with Integer key of Payload value,
 398 // tests default comparator
 399 TEST_F(MapTest, RandomOpsWithIntKey) {
 400   Map<int, Payload> test_map;
 401   for (int i = 0; i < 5; i++) {
 402     test_map.emplace(i, Payload(i));
 403   }
 404   for (int i = 0; i < 5; i++) {
 405     EXPECT_EQ(i, test_map.find(i)->second.data());
 406   }
 407   for (int i = 0; i < 5; i++) {
 408     test_map[i] = Payload(i + 10);
 409   }
 410   for (int i = 0; i < 5; i++) {
 411     EXPECT_EQ(i + 10, test_map[i].data());
 412   }
 413   EXPECT_EQ(test_map.erase(3), 1UL);
 414   EXPECT_TRUE(test_map.find(3) == test_map.end());
 415   EXPECT_FALSE(test_map.empty());
 416   EXPECT_EQ(test_map.size(), 4UL);
 417   test_map.clear();
 418   EXPECT_EQ(test_map.size(), 0UL);
 419   EXPECT_TRUE(test_map.empty());
 420 }
 421
 422 // Tests lower_bound().
 423 TEST_F(MapTest, LowerBound) {
 424   Map<int, Payload> test_map;
 425   for (int i = 0; i < 10; i += 2) {
 426     test_map.emplace(i, Payload(i));
 427   }
 428   auto it = test_map.lower_bound(-1);
 429   EXPECT_EQ(it, test_map.begin());
 430   it = test_map.lower_bound(0);
 431   EXPECT_EQ(it, test_map.begin());
 432   it = test_map.lower_bound(2);
 433   EXPECT_EQ(it->first, 2);
 434   it = test_map.lower_bound(3);
 435   EXPECT_EQ(it->first, 4);
 436   it = test_map.lower_bound(9);
 437   EXPECT_EQ(it, test_map.end());
 438 }
 439
 440 }  // namespace testing
 441 }  // namespace grpc_core
 442
 443 int main(int argc, char** argv) {
 444   grpc::testing::TestEnvironment env(argc, argv);
 445   ::testing::InitGoogleTest(&argc, argv);
 446   return RUN_ALL_TESTS();
 447 }