legacy-libs/grpc/deps/grpc/src/core/lib/gprpp/map.h

   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 #ifndef GRPC_CORE_LIB_GPRPP_MAP_H
  20 #define GRPC_CORE_LIB_GPRPP_MAP_H
  21
  22 #include <grpc/support/port_platform.h>
  23
  24 #include <string.h>
  25
  26 #include <algorithm>
  27 #include <functional>
  28 #include <iterator>
  29
  30 #if GRPC_USE_CPP_STD_LIB
  31 #include <map>
  32 #endif
  33
  34 #include "src/core/lib/gpr/useful.h"
  35 #include "src/core/lib/gprpp/memory.h"
  36 #include "src/core/lib/gprpp/pair.h"
  37 #include "src/core/lib/gprpp/ref_counted_ptr.h"
  38 #include "src/core/lib/gprpp/string_view.h"
  39
  40 namespace grpc_core {
  41
  42 struct StringLess {
  43   bool operator()(const char* a, const char* b) const {
  44     return strcmp(a, b) < 0;
  45   }
  46   bool operator()(const UniquePtr<char>& a, const UniquePtr<char>& b) const {
  47     return strcmp(a.get(), b.get()) < 0;
  48   }
  49   bool operator()(const StringView& a, const StringView& b) const {
  50     const size_t min_size = std::min(a.size(), b.size());
  51     int c = strncmp(a.data(), b.data(), min_size);
  52     if (c != 0) return c < 0;
  53     return a.size() < b.size();
  54   }
  55 };
  56
  57 template <typename T>
  58 struct RefCountedPtrLess {
  59   bool operator()(const RefCountedPtr<T>& p1,
  60                   const RefCountedPtr<T>& p2) const {
  61     return p1.get() < p2.get();
  62   }
  63 };
  64
  65 #if GRPC_USE_CPP_STD_LIB
  66
  67 template <class Key, class T, class Compare = std::less<Key>>
  68 using Map = std::map<Key, T, Compare>;
  69
  70 #else  // GRPC_USE_CPP_STD_LIB
  71
  72 namespace testing {
  73 class MapTest;
  74 }
  75
  76 // Alternative map implementation for grpc_core
  77 template <class Key, class T, class Compare = std::less<Key>>
  78 class Map {
  79  public:
  80   typedef Key key_type;
  81   typedef T mapped_type;
  82   typedef Pair<key_type, mapped_type> value_type;
  83   typedef Compare key_compare;
  84   class iterator;
  85   class const_iterator;
  86
  87   Map() = default;
  88   ~Map() { clear(); }
  89
  90   // Movable.
  91   Map(Map&& other) : root_(other.root_), size_(other.size_) {
  92     other.root_ = nullptr;
  93     other.size_ = 0;
  94   }
  95   Map& operator=(Map&& other) {
  96     if (this != &other) {
  97       clear();
  98       root_ = other.root_;
  99       size_ = other.size_;
 100       other.root_ = nullptr;
 101       other.size_ = 0;
 102     }
 103     return *this;
 104   }
 105
 106   // Copyable.
 107   Map(const Map& other) {
 108     for (const auto& p : other) {
 109       emplace(p);
 110     }
 111   }
 112   Map& operator=(const Map& other) {
 113     if (this != &other) {
 114       clear();
 115       for (const auto& p : other) {
 116         emplace(p);
 117       }
 118     }
 119     return *this;
 120   }
 121
 122   T& operator[](key_type&& key);
 123   T& operator[](const key_type& key);
 124   iterator find(const key_type& k);
 125   size_t erase(const key_type& key);
 126   // Removes the current entry and points to the next one
 127   iterator erase(iterator iter);
 128
 129   size_t size() const { return size_; }
 130
 131   template <class... Args>
 132   Pair<iterator, bool> emplace(Args&&... args);
 133
 134   Pair<iterator, bool> insert(value_type&& pair) {
 135     return emplace(std::move(pair));
 136   }
 137
 138   Pair<iterator, bool> insert(const value_type& pair) { return emplace(pair); }
 139
 140   bool empty() const { return root_ == nullptr; }
 141
 142   void clear() {
 143     auto iter = begin();
 144     while (!empty()) {
 145       iter = erase(iter);
 146     }
 147   }
 148
 149   iterator begin() {
 150     Entry* curr = GetMinEntry(root_);
 151     return iterator(this, curr);
 152   }
 153
 154   iterator end() { return iterator(this, nullptr); }
 155
 156   const_iterator begin() const {
 157     Entry* curr = GetMinEntry(root_);
 158     return const_iterator(this, curr);
 159   }
 160
 161   const_iterator end() const { return const_iterator(this, nullptr); }
 162
 163   iterator lower_bound(const Key& k) {
 164     // This is a workaround for "const key_compare compare;"
 165     // because some versions of compilers cannot build this by requiring
 166     // a user-provided constructor. (ref: https://stackoverflow.com/q/7411515)
 167     key_compare compare_tmp;
 168     const key_compare& compare = compare_tmp;
 169     return std::find_if(begin(), end(), [&k, &compare](const value_type& v) {
 170       return !compare(v.first, k);
 171     });
 172   }
 173
 174  private:
 175   friend class testing::MapTest;
 176   struct Entry {
 177     explicit Entry(value_type&& pair) : pair(std::move(pair)) {}
 178     value_type pair;
 179     Entry* left = nullptr;
 180     Entry* right = nullptr;
 181     int32_t height = 1;
 182   };
 183
 184   static int32_t EntryHeight(const Entry* e) {
 185     return e == nullptr ? 0 : e->height;
 186   }
 187
 188   static Entry* GetMinEntry(Entry* e);
 189   Entry* InOrderSuccessor(const Entry* e) const;
 190   static Entry* RotateLeft(Entry* e);
 191   static Entry* RotateRight(Entry* e);
 192   static Entry* RebalanceTreeAfterInsertion(Entry* root, const key_type& k);
 193   static Entry* RebalanceTreeAfterDeletion(Entry* root);
 194   // Returns a pair with the first value being an iterator pointing to the
 195   // inserted entry and the second value being the new root of the subtree
 196   // after a rebalance
 197   Pair<iterator, Entry*> InsertRecursive(Entry* root, value_type&& p);
 198   // Returns a pair with the first value being an iterator pointing to the
 199   // successor of the deleted entry and the second value being the new root of
 200   // the subtree after a rebalance
 201   Pair<iterator, Entry*> RemoveRecursive(Entry* root, const key_type& k);
 202   // Return 0 if lhs = rhs
 203   //        1 if lhs > rhs
 204   //       -1 if lhs < rhs
 205   static int CompareKeys(const Key& lhs, const Key& rhs);
 206
 207   Entry* root_ = nullptr;
 208   size_t size_ = 0;
 209 };
 210
 211 template <class Key, class T, class Compare>
 212 class Map<Key, T, Compare>::iterator
 213     : public std::iterator<std::input_iterator_tag, Pair<Key, T>, int32_t,
 214                            Pair<Key, T>*, Pair<Key, T>&> {
 215  public:
 216   iterator(const iterator& iter) : curr_(iter.curr_), map_(iter.map_) {}
 217   bool operator==(const iterator& rhs) const { return (curr_ == rhs.curr_); }
 218   bool operator!=(const iterator& rhs) const { return (curr_ != rhs.curr_); }
 219
 220   iterator& operator++() {
 221     curr_ = map_->InOrderSuccessor(curr_);
 222     return *this;
 223   }
 224
 225   iterator operator++(int) {
 226     Entry* prev = curr_;
 227     curr_ = map_->InOrderSuccessor(curr_);
 228     return iterator(map_, prev);
 229   }
 230
 231   iterator& operator=(const iterator& other) {
 232     if (this != &other) {
 233       this->curr_ = other.curr_;
 234       this->map_ = other.map_;
 235     }
 236     return *this;
 237   }
 238
 239   // operator*()
 240   value_type& operator*() { return curr_->pair; }
 241   const value_type& operator*() const { return curr_->pair; }
 242
 243   // operator->()
 244   value_type* operator->() { return &curr_->pair; }
 245   value_type const* operator->() const { return &curr_->pair; }
 246
 247  private:
 248   friend class Map<key_type, mapped_type, key_compare>;
 249   using GrpcMap = typename ::grpc_core::Map<Key, T, Compare>;
 250   iterator(GrpcMap* map, Entry* curr) : curr_(curr), map_(map) {}
 251   Entry* curr_;
 252   GrpcMap* map_;
 253 };
 254
 255 template <class Key, class T, class Compare>
 256 class Map<Key, T, Compare>::const_iterator
 257     : public std::iterator<std::input_iterator_tag, Pair<Key, T>, int32_t,
 258                            Pair<Key, T>*, Pair<Key, T>&> {
 259  public:
 260   const_iterator(const const_iterator& iter)
 261       : curr_(iter.curr_), map_(iter.map_) {}
 262   bool operator==(const const_iterator& rhs) const {
 263     return (curr_ == rhs.curr_);
 264   }
 265   bool operator!=(const const_iterator& rhs) const {
 266     return (curr_ != rhs.curr_);
 267   }
 268
 269   const_iterator& operator++() {
 270     curr_ = map_->InOrderSuccessor(curr_);
 271     return *this;
 272   }
 273
 274   const_iterator operator++(int) {
 275     Entry* prev = curr_;
 276     curr_ = map_->InOrderSuccessor(curr_);
 277     return const_iterator(map_, prev);
 278   }
 279
 280   const_iterator& operator=(const const_iterator& other) {
 281     if (this != &other) {
 282       this->curr_ = other.curr_;
 283       this->map_ = other.map_;
 284     }
 285     return *this;
 286   }
 287
 288   // operator*()
 289   const value_type& operator*() const { return curr_->pair; }
 290
 291   // operator->()
 292   const value_type* operator->() const { return &curr_->pair; }
 293
 294  private:
 295   friend class Map<key_type, mapped_type, key_compare>;
 296   using GrpcMap = typename ::grpc_core::Map<Key, T, Compare>;
 297   const_iterator(const GrpcMap* map, Entry* curr) : curr_(curr), map_(map) {}
 298   Entry* curr_;
 299   const GrpcMap* map_;
 300 };
 301
 302 template <class Key, class T, class Compare>
 303 T& Map<Key, T, Compare>::operator[](key_type&& key) {
 304   auto iter = find(key);
 305   if (iter == end()) {
 306     return emplace(std::move(key), T()).first->second;
 307   }
 308   return iter->second;
 309 }
 310
 311 template <class Key, class T, class Compare>
 312 T& Map<Key, T, Compare>::operator[](const key_type& key) {
 313   auto iter = find(key);
 314   if (iter == end()) {
 315     return emplace(key, T()).first->second;
 316   }
 317   return iter->second;
 318 }
 319
 320 template <class Key, class T, class Compare>
 321 typename Map<Key, T, Compare>::iterator Map<Key, T, Compare>::find(
 322     const key_type& k) {
 323   Entry* iter = root_;
 324   while (iter != nullptr) {
 325     int comp = CompareKeys(iter->pair.first, k);
 326     if (comp == 0) {
 327       return iterator(this, iter);
 328     } else if (comp < 0) {
 329       iter = iter->right;
 330     } else {
 331       iter = iter->left;
 332     }
 333   }
 334   return end();
 335 }
 336
 337 template <class Key, class T, class Compare>
 338 template <class... Args>
 339 typename ::grpc_core::Pair<typename Map<Key, T, Compare>::iterator, bool>
 340 Map<Key, T, Compare>::emplace(Args&&... args) {
 341   Pair<key_type, mapped_type> pair(std::forward<Args>(args)...);
 342   iterator ret = find(pair.first);
 343   bool insertion = false;
 344   if (ret == end()) {
 345     Pair<iterator, Entry*> p = InsertRecursive(root_, std::move(pair));
 346     root_ = p.second;
 347     ret = p.first;
 348     insertion = true;
 349     size_++;
 350   }
 351   return MakePair(ret, insertion);
 352 }
 353
 354 template <class Key, class T, class Compare>
 355 size_t Map<Key, T, Compare>::erase(const key_type& key) {
 356   iterator it = find(key);
 357   if (it == end()) return 0;
 358   erase(it);
 359   return 1;
 360 }
 361
 362 // TODO(mhaidry): Modify erase to use the iterator location
 363 // to create an efficient erase method
 364 template <class Key, class T, class Compare>
 365 typename Map<Key, T, Compare>::iterator Map<Key, T, Compare>::erase(
 366     iterator iter) {
 367   if (iter == end()) return iter;
 368   key_type& del_key = iter->first;
 369   Pair<iterator, Entry*> ret = RemoveRecursive(root_, del_key);
 370   root_ = ret.second;
 371   size_--;
 372   return ret.first;
 373 }
 374
 375 template <class Key, class T, class Compare>
 376 typename Map<Key, T, Compare>::Entry* Map<Key, T, Compare>::InOrderSuccessor(
 377     const Entry* e) const {
 378   if (e->right != nullptr) {
 379     return GetMinEntry(e->right);
 380   }
 381   Entry* successor = nullptr;
 382   Entry* iter = root_;
 383   while (iter != nullptr) {
 384     int comp = CompareKeys(iter->pair.first, e->pair.first);
 385     if (comp > 0) {
 386       successor = iter;
 387       iter = iter->left;
 388     } else if (comp < 0) {
 389       iter = iter->right;
 390     } else
 391       break;
 392   }
 393   return successor;
 394 }
 395
 396 // Returns a pair with the first value being an iterator pointing to the
 397 // inserted entry and the second value being the new root of the subtree
 398 // after a rebalance
 399 template <class Key, class T, class Compare>
 400 typename ::grpc_core::Pair<typename Map<Key, T, Compare>::iterator,
 401                            typename Map<Key, T, Compare>::Entry*>
 402 Map<Key, T, Compare>::InsertRecursive(Entry* root, value_type&& p) {
 403   if (root == nullptr) {
 404     Entry* e = New<Entry>(std::move(p));
 405     return MakePair(iterator(this, e), e);
 406   }
 407   int comp = CompareKeys(root->pair.first, p.first);
 408   if (comp > 0) {
 409     Pair<iterator, Entry*> ret = InsertRecursive(root->left, std::move(p));
 410     root->left = ret.second;
 411     ret.second = RebalanceTreeAfterInsertion(root, ret.first->first);
 412     return ret;
 413   } else if (comp < 0) {
 414     Pair<iterator, Entry*> ret = InsertRecursive(root->right, std::move(p));
 415     root->right = ret.second;
 416     ret.second = RebalanceTreeAfterInsertion(root, ret.first->first);
 417     return ret;
 418   } else {
 419     root->pair = std::move(p);
 420     return MakePair(iterator(this, root), root);
 421   }
 422 }
 423
 424 template <class Key, class T, class Compare>
 425 typename Map<Key, T, Compare>::Entry* Map<Key, T, Compare>::GetMinEntry(
 426     Entry* e) {
 427   if (e != nullptr) {
 428     while (e->left != nullptr) {
 429       e = e->left;
 430     }
 431   }
 432   return e;
 433 }
 434
 435 template <class Key, class T, class Compare>
 436 typename Map<Key, T, Compare>::Entry* Map<Key, T, Compare>::RotateLeft(
 437     Entry* e) {
 438   Entry* rightChild = e->right;
 439   Entry* rightLeftChild = rightChild->left;
 440   rightChild->left = e;
 441   e->right = rightLeftChild;
 442   e->height = 1 + GPR_MAX(EntryHeight(e->left), EntryHeight(e->right));
 443   rightChild->height = 1 + GPR_MAX(EntryHeight(rightChild->left),
 444                                    EntryHeight(rightChild->right));
 445   return rightChild;
 446 }
 447
 448 template <class Key, class T, class Compare>
 449 typename Map<Key, T, Compare>::Entry* Map<Key, T, Compare>::RotateRight(
 450     Entry* e) {
 451   Entry* leftChild = e->left;
 452   Entry* leftRightChild = leftChild->right;
 453   leftChild->right = e;
 454   e->left = leftRightChild;
 455   e->height = 1 + GPR_MAX(EntryHeight(e->left), EntryHeight(e->right));
 456   leftChild->height =
 457       1 + GPR_MAX(EntryHeight(leftChild->left), EntryHeight(leftChild->right));
 458   return leftChild;
 459 }
 460
 461 template <class Key, class T, class Compare>
 462 typename Map<Key, T, Compare>::Entry*
 463 Map<Key, T, Compare>::RebalanceTreeAfterInsertion(Entry* root,
 464                                                   const key_type& k) {
 465   root->height = 1 + GPR_MAX(EntryHeight(root->left), EntryHeight(root->right));
 466   int32_t heightDifference = EntryHeight(root->left) - EntryHeight(root->right);
 467   if (heightDifference > 1 && CompareKeys(root->left->pair.first, k) > 0) {
 468     return RotateRight(root);
 469   }
 470   if (heightDifference < -1 && CompareKeys(root->right->pair.first, k) < 0) {
 471     return RotateLeft(root);
 472   }
 473   if (heightDifference > 1 && CompareKeys(root->left->pair.first, k) < 0) {
 474     root->left = RotateLeft(root->left);
 475     return RotateRight(root);
 476   }
 477   if (heightDifference < -1 && CompareKeys(root->right->pair.first, k) > 0) {
 478     root->right = RotateRight(root->right);
 479     return RotateLeft(root);
 480   }
 481   return root;
 482 }
 483
 484 template <class Key, class T, class Compare>
 485 typename Map<Key, T, Compare>::Entry*
 486 Map<Key, T, Compare>::RebalanceTreeAfterDeletion(Entry* root) {
 487   root->height = 1 + GPR_MAX(EntryHeight(root->left), EntryHeight(root->right));
 488   int32_t heightDifference = EntryHeight(root->left) - EntryHeight(root->right);
 489   if (heightDifference > 1) {
 490     int leftHeightDifference =
 491         EntryHeight(root->left->left) - EntryHeight(root->left->right);
 492     if (leftHeightDifference < 0) {
 493       root->left = RotateLeft(root->left);
 494     }
 495     return RotateRight(root);
 496   }
 497   if (heightDifference < -1) {
 498     int rightHeightDifference =
 499         EntryHeight(root->right->left) - EntryHeight(root->right->right);
 500     if (rightHeightDifference > 0) {
 501       root->right = RotateRight(root->right);
 502     }
 503     return RotateLeft(root);
 504   }
 505   return root;
 506 }
 507
 508 template <class Key, class T, class Compare>
 509 typename ::grpc_core::Pair<typename Map<Key, T, Compare>::iterator,
 510                            typename Map<Key, T, Compare>::Entry*>
 511 Map<Key, T, Compare>::RemoveRecursive(Entry* root, const key_type& k) {
 512   Pair<iterator, Entry*> ret = MakePair(end(), root);
 513   if (root == nullptr) return ret;
 514   int comp = CompareKeys(root->pair.first, k);
 515   if (comp > 0) {
 516     ret = RemoveRecursive(root->left, k);
 517     root->left = ret.second;
 518   } else if (comp < 0) {
 519     ret = RemoveRecursive(root->right, k);
 520     root->right = ret.second;
 521   } else {
 522     Entry* entry;
 523     Entry* successor = InOrderSuccessor(root);
 524     if (root->left == nullptr) {
 525       entry = root->right;
 526       Delete(root);
 527       return MakePair(iterator(this, successor), entry);
 528     } else if (root->right == nullptr) {
 529       entry = root->left;
 530       Delete(root);
 531       return MakePair(iterator(this, successor), entry);
 532     } else {
 533       entry = successor;
 534       root->pair.swap(entry->pair);
 535       ret = RemoveRecursive(root->right, entry->pair.first);
 536       root->right = ret.second;
 537       ret.first = iterator(this, root);
 538     }
 539   }
 540   return MakePair(ret.first, RebalanceTreeAfterDeletion(root));
 541 }
 542
 543 template <class Key, class T, class Compare>
 544 int Map<Key, T, Compare>::CompareKeys(const key_type& lhs,
 545                                       const key_type& rhs) {
 546   // This is a workaround for "const key_compare compare;"
 547   // because some versions of compilers cannot build this by requiring
 548   // a user-provided constructor. (ref: https://stackoverflow.com/q/7411515)
 549   key_compare compare_tmp;
 550   const key_compare& compare = compare_tmp;
 551   bool left_comparison = compare(lhs, rhs);
 552   bool right_comparison = compare(rhs, lhs);
 553   // Both values are equal
 554   if (!left_comparison && !right_comparison) {
 555     return 0;
 556   }
 557   return left_comparison ? -1 : 1;
 558 }
 559
 560 #endif  // GRPC_USE_CPP_STD_LIB
 561
 562 }  // namespace grpc_core
 563
 564 #endif /* GRPC_CORE_LIB_GPRPP_MAP_H */