Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

Rev

Blame | Last modification | View Log | Download | RSS feed

  1. //===- llvm/ADT/MapVector.h - Map w/ deterministic value order --*- C++ -*-===//
  2. //
  3. // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
  4. // See https://llvm.org/LICENSE.txt for license information.
  5. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
  6. //
  7. //===----------------------------------------------------------------------===//
  8. ///
  9. /// \file
  10. /// This file implements a map that provides insertion order iteration. The
  11. /// interface is purposefully minimal. The key is assumed to be cheap to copy
  12. /// and 2 copies are kept, one for indexing in a DenseMap, one for iteration in
  13. /// a std::vector.
  14. ///
  15. //===----------------------------------------------------------------------===//
  16.  
  17. #ifndef LLVM_ADT_MAPVECTOR_H
  18. #define LLVM_ADT_MAPVECTOR_H
  19.  
  20. #include "llvm/ADT/DenseMap.h"
  21. #include "llvm/ADT/SmallVector.h"
  22. #include <cassert>
  23. #include <cstddef>
  24. #include <iterator>
  25. #include <type_traits>
  26. #include <utility>
  27. #include <vector>
  28.  
  29. namespace llvm {
  30.  
  31. /// This class implements a map that also provides access to all stored values
  32. /// in a deterministic order. The values are kept in a std::vector and the
  33. /// mapping is done with DenseMap from Keys to indexes in that vector.
  34. template<typename KeyT, typename ValueT,
  35.          typename MapType = DenseMap<KeyT, unsigned>,
  36.          typename VectorType = std::vector<std::pair<KeyT, ValueT>>>
  37. class MapVector {
  38.   MapType Map;
  39.   VectorType Vector;
  40.  
  41.   static_assert(
  42.       std::is_integral_v<typename MapType::mapped_type>,
  43.       "The mapped_type of the specified Map must be an integral type");
  44.  
  45. public:
  46.   using key_type = KeyT;
  47.   using value_type = typename VectorType::value_type;
  48.   using size_type = typename VectorType::size_type;
  49.  
  50.   using iterator = typename VectorType::iterator;
  51.   using const_iterator = typename VectorType::const_iterator;
  52.   using reverse_iterator = typename VectorType::reverse_iterator;
  53.   using const_reverse_iterator = typename VectorType::const_reverse_iterator;
  54.  
  55.   /// Clear the MapVector and return the underlying vector.
  56.   VectorType takeVector() {
  57.     Map.clear();
  58.     return std::move(Vector);
  59.   }
  60.  
  61.   size_type size() const { return Vector.size(); }
  62.  
  63.   /// Grow the MapVector so that it can contain at least \p NumEntries items
  64.   /// before resizing again.
  65.   void reserve(size_type NumEntries) {
  66.     Map.reserve(NumEntries);
  67.     Vector.reserve(NumEntries);
  68.   }
  69.  
  70.   iterator begin() { return Vector.begin(); }
  71.   const_iterator begin() const { return Vector.begin(); }
  72.   iterator end() { return Vector.end(); }
  73.   const_iterator end() const { return Vector.end(); }
  74.  
  75.   reverse_iterator rbegin() { return Vector.rbegin(); }
  76.   const_reverse_iterator rbegin() const { return Vector.rbegin(); }
  77.   reverse_iterator rend() { return Vector.rend(); }
  78.   const_reverse_iterator rend() const { return Vector.rend(); }
  79.  
  80.   bool empty() const {
  81.     return Vector.empty();
  82.   }
  83.  
  84.   std::pair<KeyT, ValueT>       &front()       { return Vector.front(); }
  85.   const std::pair<KeyT, ValueT> &front() const { return Vector.front(); }
  86.   std::pair<KeyT, ValueT>       &back()        { return Vector.back(); }
  87.   const std::pair<KeyT, ValueT> &back()  const { return Vector.back(); }
  88.  
  89.   void clear() {
  90.     Map.clear();
  91.     Vector.clear();
  92.   }
  93.  
  94.   void swap(MapVector &RHS) {
  95.     std::swap(Map, RHS.Map);
  96.     std::swap(Vector, RHS.Vector);
  97.   }
  98.  
  99.   ValueT &operator[](const KeyT &Key) {
  100.     std::pair<KeyT, typename MapType::mapped_type> Pair = std::make_pair(Key, 0);
  101.     std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
  102.     auto &I = Result.first->second;
  103.     if (Result.second) {
  104.       Vector.push_back(std::make_pair(Key, ValueT()));
  105.       I = Vector.size() - 1;
  106.     }
  107.     return Vector[I].second;
  108.   }
  109.  
  110.   // Returns a copy of the value.  Only allowed if ValueT is copyable.
  111.   ValueT lookup(const KeyT &Key) const {
  112.     static_assert(std::is_copy_constructible_v<ValueT>,
  113.                   "Cannot call lookup() if ValueT is not copyable.");
  114.     typename MapType::const_iterator Pos = Map.find(Key);
  115.     return Pos == Map.end()? ValueT() : Vector[Pos->second].second;
  116.   }
  117.  
  118.   std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {
  119.     std::pair<KeyT, typename MapType::mapped_type> Pair = std::make_pair(KV.first, 0);
  120.     std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
  121.     auto &I = Result.first->second;
  122.     if (Result.second) {
  123.       Vector.push_back(std::make_pair(KV.first, KV.second));
  124.       I = Vector.size() - 1;
  125.       return std::make_pair(std::prev(end()), true);
  126.     }
  127.     return std::make_pair(begin() + I, false);
  128.   }
  129.  
  130.   std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) {
  131.     // Copy KV.first into the map, then move it into the vector.
  132.     std::pair<KeyT, typename MapType::mapped_type> Pair = std::make_pair(KV.first, 0);
  133.     std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
  134.     auto &I = Result.first->second;
  135.     if (Result.second) {
  136.       Vector.push_back(std::move(KV));
  137.       I = Vector.size() - 1;
  138.       return std::make_pair(std::prev(end()), true);
  139.     }
  140.     return std::make_pair(begin() + I, false);
  141.   }
  142.  
  143.   size_type count(const KeyT &Key) const {
  144.     typename MapType::const_iterator Pos = Map.find(Key);
  145.     return Pos == Map.end()? 0 : 1;
  146.   }
  147.  
  148.   iterator find(const KeyT &Key) {
  149.     typename MapType::const_iterator Pos = Map.find(Key);
  150.     return Pos == Map.end()? Vector.end() :
  151.                             (Vector.begin() + Pos->second);
  152.   }
  153.  
  154.   const_iterator find(const KeyT &Key) const {
  155.     typename MapType::const_iterator Pos = Map.find(Key);
  156.     return Pos == Map.end()? Vector.end() :
  157.                             (Vector.begin() + Pos->second);
  158.   }
  159.  
  160.   /// Remove the last element from the vector.
  161.   void pop_back() {
  162.     typename MapType::iterator Pos = Map.find(Vector.back().first);
  163.     Map.erase(Pos);
  164.     Vector.pop_back();
  165.   }
  166.  
  167.   /// Remove the element given by Iterator.
  168.   ///
  169.   /// Returns an iterator to the element following the one which was removed,
  170.   /// which may be end().
  171.   ///
  172.   /// \note This is a deceivingly expensive operation (linear time).  It's
  173.   /// usually better to use \a remove_if() if possible.
  174.   typename VectorType::iterator erase(typename VectorType::iterator Iterator) {
  175.     Map.erase(Iterator->first);
  176.     auto Next = Vector.erase(Iterator);
  177.     if (Next == Vector.end())
  178.       return Next;
  179.  
  180.     // Update indices in the map.
  181.     size_t Index = Next - Vector.begin();
  182.     for (auto &I : Map) {
  183.       assert(I.second != Index && "Index was already erased!");
  184.       if (I.second > Index)
  185.         --I.second;
  186.     }
  187.     return Next;
  188.   }
  189.  
  190.   /// Remove all elements with the key value Key.
  191.   ///
  192.   /// Returns the number of elements removed.
  193.   size_type erase(const KeyT &Key) {
  194.     auto Iterator = find(Key);
  195.     if (Iterator == end())
  196.       return 0;
  197.     erase(Iterator);
  198.     return 1;
  199.   }
  200.  
  201.   /// Remove the elements that match the predicate.
  202.   ///
  203.   /// Erase all elements that match \c Pred in a single pass.  Takes linear
  204.   /// time.
  205.   template <class Predicate> void remove_if(Predicate Pred);
  206. };
  207.  
  208. template <typename KeyT, typename ValueT, typename MapType, typename VectorType>
  209. template <class Function>
  210. void MapVector<KeyT, ValueT, MapType, VectorType>::remove_if(Function Pred) {
  211.   auto O = Vector.begin();
  212.   for (auto I = O, E = Vector.end(); I != E; ++I) {
  213.     if (Pred(*I)) {
  214.       // Erase from the map.
  215.       Map.erase(I->first);
  216.       continue;
  217.     }
  218.  
  219.     if (I != O) {
  220.       // Move the value and update the index in the map.
  221.       *O = std::move(*I);
  222.       Map[O->first] = O - Vector.begin();
  223.     }
  224.     ++O;
  225.   }
  226.   // Erase trailing entries in the vector.
  227.   Vector.erase(O, Vector.end());
  228. }
  229.  
  230. /// A MapVector that performs no allocations if smaller than a certain
  231. /// size.
  232. template <typename KeyT, typename ValueT, unsigned N>
  233. struct SmallMapVector
  234.     : MapVector<KeyT, ValueT, SmallDenseMap<KeyT, unsigned, N>,
  235.                 SmallVector<std::pair<KeyT, ValueT>, N>> {
  236. };
  237.  
  238. } // end namespace llvm
  239.  
  240. #endif // LLVM_ADT_MAPVECTOR_H
  241.