Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

Rev

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

  1. //===--- ImmutableMap.h - Immutable (functional) map interface --*- 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 defines the ImmutableMap class.
  11. ///
  12. //===----------------------------------------------------------------------===//
  13.  
  14. #ifndef LLVM_ADT_IMMUTABLEMAP_H
  15. #define LLVM_ADT_IMMUTABLEMAP_H
  16.  
  17. #include "llvm/ADT/FoldingSet.h"
  18. #include "llvm/ADT/ImmutableSet.h"
  19. #include "llvm/Support/Allocator.h"
  20. #include <utility>
  21.  
  22. namespace llvm {
  23.  
  24. /// ImutKeyValueInfo -Traits class used by ImmutableMap.  While both the first
  25. /// and second elements in a pair are used to generate profile information,
  26. /// only the first element (the key) is used by isEqual and isLess.
  27. template <typename T, typename S>
  28. struct ImutKeyValueInfo {
  29.   using value_type = const std::pair<T,S>;
  30.   using value_type_ref = const value_type&;
  31.   using key_type = const T;
  32.   using key_type_ref = const T&;
  33.   using data_type = const S;
  34.   using data_type_ref = const S&;
  35.  
  36.   static inline key_type_ref KeyOfValue(value_type_ref V) {
  37.     return V.first;
  38.   }
  39.  
  40.   static inline data_type_ref DataOfValue(value_type_ref V) {
  41.     return V.second;
  42.   }
  43.  
  44.   static inline bool isEqual(key_type_ref L, key_type_ref R) {
  45.     return ImutContainerInfo<T>::isEqual(L,R);
  46.   }
  47.   static inline bool isLess(key_type_ref L, key_type_ref R) {
  48.     return ImutContainerInfo<T>::isLess(L,R);
  49.   }
  50.  
  51.   static inline bool isDataEqual(data_type_ref L, data_type_ref R) {
  52.     return ImutContainerInfo<S>::isEqual(L,R);
  53.   }
  54.  
  55.   static inline void Profile(FoldingSetNodeID& ID, value_type_ref V) {
  56.     ImutContainerInfo<T>::Profile(ID, V.first);
  57.     ImutContainerInfo<S>::Profile(ID, V.second);
  58.   }
  59. };
  60.  
  61. template <typename KeyT, typename ValT,
  62.           typename ValInfo = ImutKeyValueInfo<KeyT,ValT>>
  63. class ImmutableMap {
  64. public:
  65.   using value_type = typename ValInfo::value_type;
  66.   using value_type_ref = typename ValInfo::value_type_ref;
  67.   using key_type = typename ValInfo::key_type;
  68.   using key_type_ref = typename ValInfo::key_type_ref;
  69.   using data_type = typename ValInfo::data_type;
  70.   using data_type_ref = typename ValInfo::data_type_ref;
  71.   using TreeTy = ImutAVLTree<ValInfo>;
  72.  
  73. protected:
  74.   IntrusiveRefCntPtr<TreeTy> Root;
  75.  
  76. public:
  77.   /// Constructs a map from a pointer to a tree root.  In general one
  78.   /// should use a Factory object to create maps instead of directly
  79.   /// invoking the constructor, but there are cases where make this
  80.   /// constructor public is useful.
  81.   explicit ImmutableMap(const TreeTy *R) : Root(const_cast<TreeTy *>(R)) {}
  82.  
  83.   class Factory {
  84.     typename TreeTy::Factory F;
  85.     const bool Canonicalize;
  86.  
  87.   public:
  88.     Factory(bool canonicalize = true) : Canonicalize(canonicalize) {}
  89.  
  90.     Factory(BumpPtrAllocator &Alloc, bool canonicalize = true)
  91.         : F(Alloc), Canonicalize(canonicalize) {}
  92.  
  93.     Factory(const Factory &) = delete;
  94.     Factory &operator=(const Factory &) = delete;
  95.  
  96.     ImmutableMap getEmptyMap() { return ImmutableMap(F.getEmptyTree()); }
  97.  
  98.     [[nodiscard]] ImmutableMap add(ImmutableMap Old, key_type_ref K,
  99.                                    data_type_ref D) {
  100.       TreeTy *T = F.add(Old.Root.get(), std::pair<key_type, data_type>(K, D));
  101.       return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T);
  102.     }
  103.  
  104.     [[nodiscard]] ImmutableMap remove(ImmutableMap Old, key_type_ref K) {
  105.       TreeTy *T = F.remove(Old.Root.get(), K);
  106.       return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T);
  107.     }
  108.  
  109.     typename TreeTy::Factory *getTreeFactory() const {
  110.       return const_cast<typename TreeTy::Factory *>(&F);
  111.     }
  112.   };
  113.  
  114.   bool contains(key_type_ref K) const {
  115.     return Root ? Root->contains(K) : false;
  116.   }
  117.  
  118.   bool operator==(const ImmutableMap &RHS) const {
  119.     return Root && RHS.Root ? Root->isEqual(*RHS.Root.get()) : Root == RHS.Root;
  120.   }
  121.  
  122.   bool operator!=(const ImmutableMap &RHS) const {
  123.     return Root && RHS.Root ? Root->isNotEqual(*RHS.Root.get())
  124.                             : Root != RHS.Root;
  125.   }
  126.  
  127.   TreeTy *getRoot() const {
  128.     if (Root) { Root->retain(); }
  129.     return Root.get();
  130.   }
  131.  
  132.   TreeTy *getRootWithoutRetain() const { return Root.get(); }
  133.  
  134.   void manualRetain() {
  135.     if (Root) Root->retain();
  136.   }
  137.  
  138.   void manualRelease() {
  139.     if (Root) Root->release();
  140.   }
  141.  
  142.   bool isEmpty() const { return !Root; }
  143.  
  144. public:
  145.   //===--------------------------------------------------===//
  146.   // For testing.
  147.   //===--------------------------------------------------===//
  148.  
  149.   void verify() const { if (Root) Root->verify(); }
  150.  
  151.   //===--------------------------------------------------===//
  152.   // Iterators.
  153.   //===--------------------------------------------------===//
  154.  
  155.   class iterator : public ImutAVLValueIterator<ImmutableMap> {
  156.     friend class ImmutableMap;
  157.  
  158.     iterator() = default;
  159.     explicit iterator(TreeTy *Tree) : iterator::ImutAVLValueIterator(Tree) {}
  160.  
  161.   public:
  162.     key_type_ref getKey() const { return (*this)->first; }
  163.     data_type_ref getData() const { return (*this)->second; }
  164.   };
  165.  
  166.   iterator begin() const { return iterator(Root.get()); }
  167.   iterator end() const { return iterator(); }
  168.  
  169.   data_type* lookup(key_type_ref K) const {
  170.     if (Root) {
  171.       TreeTy* T = Root->find(K);
  172.       if (T) return &T->getValue().second;
  173.     }
  174.  
  175.     return nullptr;
  176.   }
  177.  
  178.   /// getMaxElement - Returns the <key,value> pair in the ImmutableMap for
  179.   ///  which key is the highest in the ordering of keys in the map.  This
  180.   ///  method returns NULL if the map is empty.
  181.   value_type* getMaxElement() const {
  182.     return Root ? &(Root->getMaxElement()->getValue()) : nullptr;
  183.   }
  184.  
  185.   //===--------------------------------------------------===//
  186.   // Utility methods.
  187.   //===--------------------------------------------------===//
  188.  
  189.   unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
  190.  
  191.   static inline void Profile(FoldingSetNodeID& ID, const ImmutableMap& M) {
  192.     ID.AddPointer(M.Root.get());
  193.   }
  194.  
  195.   inline void Profile(FoldingSetNodeID& ID) const {
  196.     return Profile(ID,*this);
  197.   }
  198. };
  199.  
  200. // NOTE: This will possibly become the new implementation of ImmutableMap some day.
  201. template <typename KeyT, typename ValT,
  202. typename ValInfo = ImutKeyValueInfo<KeyT,ValT>>
  203. class ImmutableMapRef {
  204. public:
  205.   using value_type = typename ValInfo::value_type;
  206.   using value_type_ref = typename ValInfo::value_type_ref;
  207.   using key_type = typename ValInfo::key_type;
  208.   using key_type_ref = typename ValInfo::key_type_ref;
  209.   using data_type = typename ValInfo::data_type;
  210.   using data_type_ref = typename ValInfo::data_type_ref;
  211.   using TreeTy = ImutAVLTree<ValInfo>;
  212.   using FactoryTy = typename TreeTy::Factory;
  213.  
  214. protected:
  215.   IntrusiveRefCntPtr<TreeTy> Root;
  216.   FactoryTy *Factory;
  217.  
  218. public:
  219.   /// Constructs a map from a pointer to a tree root.  In general one
  220.   /// should use a Factory object to create maps instead of directly
  221.   /// invoking the constructor, but there are cases where make this
  222.   /// constructor public is useful.
  223.   ImmutableMapRef(const TreeTy *R, FactoryTy *F)
  224.       : Root(const_cast<TreeTy *>(R)), Factory(F) {}
  225.  
  226.   ImmutableMapRef(const ImmutableMap<KeyT, ValT> &X,
  227.                   typename ImmutableMap<KeyT, ValT>::Factory &F)
  228.       : Root(X.getRootWithoutRetain()), Factory(F.getTreeFactory()) {}
  229.  
  230.   static inline ImmutableMapRef getEmptyMap(FactoryTy *F) {
  231.     return ImmutableMapRef(nullptr, F);
  232.   }
  233.  
  234.   void manualRetain() {
  235.     if (Root) Root->retain();
  236.   }
  237.  
  238.   void manualRelease() {
  239.     if (Root) Root->release();
  240.   }
  241.  
  242.   ImmutableMapRef add(key_type_ref K, data_type_ref D) const {
  243.     TreeTy *NewT =
  244.         Factory->add(Root.get(), std::pair<key_type, data_type>(K, D));
  245.     return ImmutableMapRef(NewT, Factory);
  246.   }
  247.  
  248.   ImmutableMapRef remove(key_type_ref K) const {
  249.     TreeTy *NewT = Factory->remove(Root.get(), K);
  250.     return ImmutableMapRef(NewT, Factory);
  251.   }
  252.  
  253.   bool contains(key_type_ref K) const {
  254.     return Root ? Root->contains(K) : false;
  255.   }
  256.  
  257.   ImmutableMap<KeyT, ValT> asImmutableMap() const {
  258.     return ImmutableMap<KeyT, ValT>(Factory->getCanonicalTree(Root.get()));
  259.   }
  260.  
  261.   bool operator==(const ImmutableMapRef &RHS) const {
  262.     return Root && RHS.Root ? Root->isEqual(*RHS.Root.get()) : Root == RHS.Root;
  263.   }
  264.  
  265.   bool operator!=(const ImmutableMapRef &RHS) const {
  266.     return Root && RHS.Root ? Root->isNotEqual(*RHS.Root.get())
  267.                             : Root != RHS.Root;
  268.   }
  269.  
  270.   bool isEmpty() const { return !Root; }
  271.  
  272.   //===--------------------------------------------------===//
  273.   // For testing.
  274.   //===--------------------------------------------------===//
  275.  
  276.   void verify() const {
  277.     if (Root)
  278.       Root->verify();
  279.   }
  280.  
  281.   //===--------------------------------------------------===//
  282.   // Iterators.
  283.   //===--------------------------------------------------===//
  284.  
  285.   class iterator : public ImutAVLValueIterator<ImmutableMapRef> {
  286.     friend class ImmutableMapRef;
  287.  
  288.     iterator() = default;
  289.     explicit iterator(TreeTy *Tree) : iterator::ImutAVLValueIterator(Tree) {}
  290.  
  291.   public:
  292.     key_type_ref getKey() const { return (*this)->first; }
  293.     data_type_ref getData() const { return (*this)->second; }
  294.   };
  295.  
  296.   iterator begin() const { return iterator(Root.get()); }
  297.   iterator end() const { return iterator(); }
  298.  
  299.   data_type *lookup(key_type_ref K) const {
  300.     if (Root) {
  301.       TreeTy* T = Root->find(K);
  302.       if (T) return &T->getValue().second;
  303.     }
  304.  
  305.     return nullptr;
  306.   }
  307.  
  308.   /// getMaxElement - Returns the <key,value> pair in the ImmutableMap for
  309.   ///  which key is the highest in the ordering of keys in the map.  This
  310.   ///  method returns NULL if the map is empty.
  311.   value_type* getMaxElement() const {
  312.     return Root ? &(Root->getMaxElement()->getValue()) : nullptr;
  313.   }
  314.  
  315.   //===--------------------------------------------------===//
  316.   // Utility methods.
  317.   //===--------------------------------------------------===//
  318.  
  319.   unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
  320.  
  321.   static inline void Profile(FoldingSetNodeID &ID, const ImmutableMapRef &M) {
  322.     ID.AddPointer(M.Root.get());
  323.   }
  324.  
  325.   inline void Profile(FoldingSetNodeID &ID) const { return Profile(ID, *this); }
  326. };
  327.  
  328. } // end namespace llvm
  329.  
  330. #endif // LLVM_ADT_IMMUTABLEMAP_H
  331.