Home | History | Annotate | Download | only in ADT
      1 //===--- ImmutableMap.h - Immutable (functional) map interface --*- C++ -*-===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 //
     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   typedef const std::pair<T,S> value_type;
     30   typedef const value_type& value_type_ref;
     31   typedef const T   key_type;
     32   typedef const T&  key_type_ref;
     33   typedef const S   data_type;
     34   typedef const S&  data_type_ref;
     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   typedef typename ValInfo::value_type      value_type;
     66   typedef typename ValInfo::value_type_ref  value_type_ref;
     67   typedef typename ValInfo::key_type        key_type;
     68   typedef typename ValInfo::key_type_ref    key_type_ref;
     69   typedef typename ValInfo::data_type       data_type;
     70   typedef typename ValInfo::data_type_ref   data_type_ref;
     71   typedef ImutAVLTree<ValInfo>              TreeTy;
     72 
     73 protected:
     74   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     if (Root) { Root->retain(); }
     83   }
     84 
     85   ImmutableMap(const ImmutableMap &X) : Root(X.Root) {
     86     if (Root) { Root->retain(); }
     87   }
     88 
     89   ImmutableMap &operator=(const ImmutableMap &X) {
     90     if (Root != X.Root) {
     91       if (X.Root) { X.Root->retain(); }
     92       if (Root) { Root->release(); }
     93       Root = X.Root;
     94     }
     95     return *this;
     96   }
     97 
     98   ~ImmutableMap() {
     99     if (Root) { Root->release(); }
    100   }
    101 
    102   class Factory {
    103     typename TreeTy::Factory F;
    104     const bool Canonicalize;
    105 
    106   public:
    107     Factory(bool canonicalize = true) : Canonicalize(canonicalize) {}
    108 
    109     Factory(BumpPtrAllocator &Alloc, bool canonicalize = true)
    110         : F(Alloc), Canonicalize(canonicalize) {}
    111 
    112     Factory(const Factory &) = delete;
    113     Factory &operator=(const Factory &) = delete;
    114 
    115     ImmutableMap getEmptyMap() { return ImmutableMap(F.getEmptyTree()); }
    116 
    117     ImmutableMap add(ImmutableMap Old, key_type_ref K, data_type_ref D) {
    118       TreeTy *T = F.add(Old.Root, std::pair<key_type,data_type>(K,D));
    119       return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T);
    120     }
    121 
    122     ImmutableMap remove(ImmutableMap Old, key_type_ref K) {
    123       TreeTy *T = F.remove(Old.Root,K);
    124       return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T);
    125     }
    126 
    127     typename TreeTy::Factory *getTreeFactory() const {
    128       return const_cast<typename TreeTy::Factory *>(&F);
    129     }
    130   };
    131 
    132   bool contains(key_type_ref K) const {
    133     return Root ? Root->contains(K) : false;
    134   }
    135 
    136   bool operator==(const ImmutableMap &RHS) const {
    137     return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root;
    138   }
    139 
    140   bool operator!=(const ImmutableMap &RHS) const {
    141     return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;
    142   }
    143 
    144   TreeTy *getRoot() const {
    145     if (Root) { Root->retain(); }
    146     return Root;
    147   }
    148 
    149   TreeTy *getRootWithoutRetain() const { return Root; }
    150 
    151   void manualRetain() {
    152     if (Root) Root->retain();
    153   }
    154 
    155   void manualRelease() {
    156     if (Root) Root->release();
    157   }
    158 
    159   bool isEmpty() const { return !Root; }
    160 
    161   //===--------------------------------------------------===//
    162   // Foreach - A limited form of map iteration.
    163   //===--------------------------------------------------===//
    164 
    165 private:
    166   template <typename Callback>
    167   struct CBWrapper {
    168     Callback C;
    169     void operator()(value_type_ref V) { C(V.first,V.second); }
    170   };
    171 
    172   template <typename Callback>
    173   struct CBWrapperRef {
    174     Callback &C;
    175     CBWrapperRef(Callback& c) : C(c) {}
    176 
    177     void operator()(value_type_ref V) { C(V.first,V.second); }
    178   };
    179 
    180 public:
    181   template <typename Callback>
    182   void foreach(Callback& C) {
    183     if (Root) {
    184       CBWrapperRef<Callback> CB(C);
    185       Root->foreach(CB);
    186     }
    187   }
    188 
    189   template <typename Callback>
    190   void foreach() {
    191     if (Root) {
    192       CBWrapper<Callback> CB;
    193       Root->foreach(CB);
    194     }
    195   }
    196 
    197   //===--------------------------------------------------===//
    198   // For testing.
    199   //===--------------------------------------------------===//
    200 
    201   void verify() const { if (Root) Root->verify(); }
    202 
    203   //===--------------------------------------------------===//
    204   // Iterators.
    205   //===--------------------------------------------------===//
    206 
    207   class iterator : public ImutAVLValueIterator<ImmutableMap> {
    208     friend class ImmutableMap;
    209 
    210     iterator() = default;
    211     explicit iterator(TreeTy *Tree) : iterator::ImutAVLValueIterator(Tree) {}
    212 
    213   public:
    214     key_type_ref getKey() const { return (*this)->first; }
    215     data_type_ref getData() const { return (*this)->second; }
    216   };
    217 
    218   iterator begin() const { return iterator(Root); }
    219   iterator end() const { return iterator(); }
    220 
    221   data_type* lookup(key_type_ref K) const {
    222     if (Root) {
    223       TreeTy* T = Root->find(K);
    224       if (T) return &T->getValue().second;
    225     }
    226 
    227     return nullptr;
    228   }
    229 
    230   /// getMaxElement - Returns the <key,value> pair in the ImmutableMap for
    231   ///  which key is the highest in the ordering of keys in the map.  This
    232   ///  method returns NULL if the map is empty.
    233   value_type* getMaxElement() const {
    234     return Root ? &(Root->getMaxElement()->getValue()) : nullptr;
    235   }
    236 
    237   //===--------------------------------------------------===//
    238   // Utility methods.
    239   //===--------------------------------------------------===//
    240 
    241   unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
    242 
    243   static inline void Profile(FoldingSetNodeID& ID, const ImmutableMap& M) {
    244     ID.AddPointer(M.Root);
    245   }
    246 
    247   inline void Profile(FoldingSetNodeID& ID) const {
    248     return Profile(ID,*this);
    249   }
    250 };
    251 
    252 // NOTE: This will possibly become the new implementation of ImmutableMap some day.
    253 template <typename KeyT, typename ValT,
    254 typename ValInfo = ImutKeyValueInfo<KeyT,ValT>>
    255 class ImmutableMapRef {
    256 public:
    257   typedef typename ValInfo::value_type      value_type;
    258   typedef typename ValInfo::value_type_ref  value_type_ref;
    259   typedef typename ValInfo::key_type        key_type;
    260   typedef typename ValInfo::key_type_ref    key_type_ref;
    261   typedef typename ValInfo::data_type       data_type;
    262   typedef typename ValInfo::data_type_ref   data_type_ref;
    263   typedef ImutAVLTree<ValInfo>              TreeTy;
    264   typedef typename TreeTy::Factory          FactoryTy;
    265 
    266 protected:
    267   TreeTy *Root;
    268   FactoryTy *Factory;
    269 
    270 public:
    271   /// Constructs a map from a pointer to a tree root.  In general one
    272   /// should use a Factory object to create maps instead of directly
    273   /// invoking the constructor, but there are cases where make this
    274   /// constructor public is useful.
    275   explicit ImmutableMapRef(const TreeTy *R, FactoryTy *F)
    276       : Root(const_cast<TreeTy *>(R)), Factory(F) {
    277     if (Root) {
    278       Root->retain();
    279     }
    280   }
    281 
    282   explicit ImmutableMapRef(const ImmutableMap<KeyT, ValT> &X,
    283                            typename ImmutableMap<KeyT, ValT>::Factory &F)
    284     : Root(X.getRootWithoutRetain()),
    285       Factory(F.getTreeFactory()) {
    286     if (Root) { Root->retain(); }
    287   }
    288 
    289   ImmutableMapRef(const ImmutableMapRef &X) : Root(X.Root), Factory(X.Factory) {
    290     if (Root) {
    291       Root->retain();
    292     }
    293   }
    294 
    295   ImmutableMapRef &operator=(const ImmutableMapRef &X) {
    296     if (Root != X.Root) {
    297       if (X.Root)
    298         X.Root->retain();
    299 
    300       if (Root)
    301         Root->release();
    302 
    303       Root = X.Root;
    304       Factory = X.Factory;
    305     }
    306     return *this;
    307   }
    308 
    309   ~ImmutableMapRef() {
    310     if (Root)
    311       Root->release();
    312   }
    313 
    314   static inline ImmutableMapRef getEmptyMap(FactoryTy *F) {
    315     return ImmutableMapRef(0, F);
    316   }
    317 
    318   void manualRetain() {
    319     if (Root) Root->retain();
    320   }
    321 
    322   void manualRelease() {
    323     if (Root) Root->release();
    324   }
    325 
    326   ImmutableMapRef add(key_type_ref K, data_type_ref D) const {
    327     TreeTy *NewT = Factory->add(Root, std::pair<key_type, data_type>(K, D));
    328     return ImmutableMapRef(NewT, Factory);
    329   }
    330 
    331   ImmutableMapRef remove(key_type_ref K) const {
    332     TreeTy *NewT = Factory->remove(Root, K);
    333     return ImmutableMapRef(NewT, Factory);
    334   }
    335 
    336   bool contains(key_type_ref K) const {
    337     return Root ? Root->contains(K) : false;
    338   }
    339 
    340   ImmutableMap<KeyT, ValT> asImmutableMap() const {
    341     return ImmutableMap<KeyT, ValT>(Factory->getCanonicalTree(Root));
    342   }
    343 
    344   bool operator==(const ImmutableMapRef &RHS) const {
    345     return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root;
    346   }
    347 
    348   bool operator!=(const ImmutableMapRef &RHS) const {
    349     return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;
    350   }
    351 
    352   bool isEmpty() const { return !Root; }
    353 
    354   //===--------------------------------------------------===//
    355   // For testing.
    356   //===--------------------------------------------------===//
    357 
    358   void verify() const {
    359     if (Root)
    360       Root->verify();
    361   }
    362 
    363   //===--------------------------------------------------===//
    364   // Iterators.
    365   //===--------------------------------------------------===//
    366 
    367   class iterator : public ImutAVLValueIterator<ImmutableMapRef> {
    368     friend class ImmutableMapRef;
    369 
    370     iterator() = default;
    371     explicit iterator(TreeTy *Tree) : iterator::ImutAVLValueIterator(Tree) {}
    372 
    373   public:
    374     key_type_ref getKey() const { return (*this)->first; }
    375     data_type_ref getData() const { return (*this)->second; }
    376   };
    377 
    378   iterator begin() const { return iterator(Root); }
    379   iterator end() const { return iterator(); }
    380 
    381   data_type *lookup(key_type_ref K) const {
    382     if (Root) {
    383       TreeTy* T = Root->find(K);
    384       if (T) return &T->getValue().second;
    385     }
    386 
    387     return nullptr;
    388   }
    389 
    390   /// getMaxElement - Returns the <key,value> pair in the ImmutableMap for
    391   ///  which key is the highest in the ordering of keys in the map.  This
    392   ///  method returns NULL if the map is empty.
    393   value_type* getMaxElement() const {
    394     return Root ? &(Root->getMaxElement()->getValue()) : 0;
    395   }
    396 
    397   //===--------------------------------------------------===//
    398   // Utility methods.
    399   //===--------------------------------------------------===//
    400 
    401   unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
    402 
    403   static inline void Profile(FoldingSetNodeID &ID, const ImmutableMapRef &M) {
    404     ID.AddPointer(M.Root);
    405   }
    406 
    407   inline void Profile(FoldingSetNodeID &ID) const { return Profile(ID, *this); }
    408 };
    409 
    410 } // end namespace llvm
    411 
    412 #endif // LLVM_ADT_IMMUTABLEMAP_H
    413