Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

Rev

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

  1. //===- ContinuousRangeMap.h - Map with int range as key ---------*- 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. //  This file defines the ContinuousRangeMap class, which is a highly
  10. //  specialized container used by serialization.
  11. //
  12. //===----------------------------------------------------------------------===//
  13.  
  14. #ifndef LLVM_CLANG_SERIALIZATION_CONTINUOUSRANGEMAP_H
  15. #define LLVM_CLANG_SERIALIZATION_CONTINUOUSRANGEMAP_H
  16.  
  17. #include "clang/Basic/LLVM.h"
  18. #include "llvm/ADT/STLExtras.h"
  19. #include "llvm/ADT/SmallVector.h"
  20. #include <algorithm>
  21. #include <cassert>
  22. #include <utility>
  23.  
  24. namespace clang {
  25.  
  26. /// A map from continuous integer ranges to some value, with a very
  27. /// specialized interface.
  28. ///
  29. /// CRM maps from integer ranges to values. The ranges are continuous, i.e.
  30. /// where one ends, the next one begins. So if the map contains the stops I0-3,
  31. /// the first range is from I0 to I1, the second from I1 to I2, the third from
  32. /// I2 to I3 and the last from I3 to infinity.
  33. ///
  34. /// Ranges must be inserted in order. Inserting a new stop I4 into the map will
  35. /// shrink the fourth range to I3 to I4 and add the new range I4 to inf.
  36. template <typename Int, typename V, unsigned InitialCapacity>
  37. class ContinuousRangeMap {
  38. public:
  39.   using value_type = std::pair<Int, V>;
  40.   using reference = value_type &;
  41.   using const_reference = const value_type &;
  42.   using pointer = value_type *;
  43.   using const_pointer = const value_type *;
  44.  
  45. private:
  46.   using Representation = SmallVector<value_type, InitialCapacity>;
  47.  
  48.   Representation Rep;
  49.  
  50.   struct Compare {
  51.     bool operator ()(const_reference L, Int R) const {
  52.       return L.first < R;
  53.     }
  54.     bool operator ()(Int L, const_reference R) const {
  55.       return L < R.first;
  56.     }
  57.     bool operator ()(Int L, Int R) const {
  58.       return L < R;
  59.     }
  60.     bool operator ()(const_reference L, const_reference R) const {
  61.       return L.first < R.first;
  62.     }
  63.   };
  64.  
  65. public:
  66.   void insert(const value_type &Val) {
  67.     if (!Rep.empty() && Rep.back() == Val)
  68.       return;
  69.  
  70.     assert((Rep.empty() || Rep.back().first < Val.first) &&
  71.            "Must insert keys in order.");
  72.     Rep.push_back(Val);
  73.   }
  74.  
  75.   void insertOrReplace(const value_type &Val) {
  76.     iterator I = llvm::lower_bound(Rep, Val, Compare());
  77.     if (I != Rep.end() && I->first == Val.first) {
  78.       I->second = Val.second;
  79.       return;
  80.     }
  81.  
  82.     Rep.insert(I, Val);
  83.   }
  84.  
  85.   using iterator = typename Representation::iterator;
  86.   using const_iterator = typename Representation::const_iterator;
  87.  
  88.   iterator begin() { return Rep.begin(); }
  89.   iterator end() { return Rep.end(); }
  90.   const_iterator begin() const { return Rep.begin(); }
  91.   const_iterator end() const { return Rep.end(); }
  92.  
  93.   iterator find(Int K) {
  94.     iterator I = llvm::upper_bound(Rep, K, Compare());
  95.     // I points to the first entry with a key > K, which is the range that
  96.     // follows the one containing K.
  97.     if (I == Rep.begin())
  98.       return Rep.end();
  99.     --I;
  100.     return I;
  101.   }
  102.   const_iterator find(Int K) const {
  103.     return const_cast<ContinuousRangeMap*>(this)->find(K);
  104.   }
  105.  
  106.   reference back() { return Rep.back(); }
  107.   const_reference back() const { return Rep.back(); }
  108.  
  109.   /// An object that helps properly build a continuous range map
  110.   /// from a set of values.
  111.   class Builder {
  112.     ContinuousRangeMap &Self;
  113.  
  114.   public:
  115.     explicit Builder(ContinuousRangeMap &Self) : Self(Self) {}
  116.     Builder(const Builder&) = delete;
  117.     Builder &operator=(const Builder&) = delete;
  118.  
  119.     ~Builder() {
  120.       llvm::sort(Self.Rep, Compare());
  121.       Self.Rep.erase(
  122.           std::unique(
  123.               Self.Rep.begin(), Self.Rep.end(),
  124.               [](const_reference A, const_reference B) {
  125.                 // FIXME: we should not allow any duplicate keys, but there are
  126.                 // a lot of duplicate 0 -> 0 mappings to remove first.
  127.                 assert((A == B || A.first != B.first) &&
  128.                        "ContinuousRangeMap::Builder given non-unique keys");
  129.                 return A == B;
  130.               }),
  131.           Self.Rep.end());
  132.     }
  133.  
  134.     void insert(const value_type &Val) {
  135.       Self.Rep.push_back(Val);
  136.     }
  137.   };
  138.  
  139.   friend class Builder;
  140. };
  141.  
  142. } // namespace clang
  143.  
  144. #endif // LLVM_CLANG_SERIALIZATION_CONTINUOUSRANGEMAP_H
  145.