LCOV - code coverage report
Current view: top level - include/llvm/ADT - ImmutableList.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 135 198 68.2 %
Date: 2018-10-20 13:21:21 Functions: 31 139 22.3 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //==--- ImmutableList.h - Immutable (functional) list 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 ImmutableList class.
      11             : //
      12             : //===----------------------------------------------------------------------===//
      13             : 
      14             : #ifndef LLVM_ADT_IMMUTABLELIST_H
      15             : #define LLVM_ADT_IMMUTABLELIST_H
      16             : 
      17             : #include "llvm/ADT/FoldingSet.h"
      18             : #include "llvm/Support/Allocator.h"
      19             : #include <cassert>
      20             : #include <cstdint>
      21             : #include <new>
      22             : 
      23             : namespace llvm {
      24             : 
      25             : template <typename T> class ImmutableListFactory;
      26             : 
      27             : template <typename T>
      28             : class ImmutableListImpl : public FoldingSetNode {
      29             :   friend class ImmutableListFactory<T>;
      30             : 
      31             :   T Head;
      32             :   const ImmutableListImpl* Tail;
      33             : 
      34             :   template <typename ElemT>
      35        2204 :   ImmutableListImpl(ElemT &&head, const ImmutableListImpl *tail = nullptr)
      36        2206 :     : Head(std::forward<ElemT>(head)), Tail(tail) {}
      37             : 
      38             : public:
      39             :   ImmutableListImpl(const ImmutableListImpl &) = delete;
      40             :   ImmutableListImpl &operator=(const ImmutableListImpl &) = delete;
      41             : 
      42        5514 :   const T& getHead() const { return Head; }
      43           0 :   const ImmutableListImpl* getTail() const { return Tail; }
      44             : 
      45        2222 :   static inline void Profile(FoldingSetNodeID& ID, const T& H,
      46             :                              const ImmutableListImpl* L){
      47        2550 :     ID.AddPointer(L);
      48          81 :     ID.Add(H);
      49        2222 :   }
      50             : 
      51           0 :   void Profile(FoldingSetNodeID& ID) {
      52         283 :     Profile(ID, Head, Tail);
      53           0 :   }
      54             : };
      55             : 
      56             : /// ImmutableList - This class represents an immutable (functional) list.
      57             : ///  It is implemented as a smart pointer (wraps ImmutableListImpl), so it
      58             : ///  it is intended to always be copied by value as if it were a pointer.
      59             : ///  This interface matches ImmutableSet and ImmutableMap.  ImmutableList
      60             : ///  objects should almost never be created directly, and instead should
      61             : ///  be created by ImmutableListFactory objects that manage the lifetime
      62             : ///  of a group of lists.  When the factory object is reclaimed, all lists
      63             : ///  created by that factory are released as well.
      64             : template <typename T>
      65             : class ImmutableList {
      66             : public:
      67             :   using value_type = T;
      68             :   using Factory = ImmutableListFactory<T>;
      69             : 
      70             :   static_assert(std::is_trivially_destructible<T>::value,
      71             :                 "T must be trivially destructible!");
      72             : 
      73             : private:
      74             :   const ImmutableListImpl<T>* X;
      75             : 
      76             : public:
      77             :   // This constructor should normally only be called by ImmutableListFactory<T>.
      78             :   // There may be cases, however, when one needs to extract the internal pointer
      79             :   // and reconstruct a list object from that pointer.
      80         297 :   ImmutableList(const ImmutableListImpl<T>* x = nullptr) : X(x) {}
      81             : 
      82           0 :   const ImmutableListImpl<T>* getInternalPointer() const {
      83           0 :     return X;
      84             :   }
      85           0 : 
      86           0 :   class iterator {
      87             :     const ImmutableListImpl<T>* L = nullptr;
      88           0 : 
      89           0 :   public:
      90             :     iterator() = default;
      91           0 :     iterator(ImmutableList l) : L(l.getInternalPointer()) {}
      92           0 : 
      93        6019 :     iterator& operator++() { L = L->getTail(); return *this; }
      94           0 :     bool operator==(const iterator& I) const { return L == I.L; }
      95           0 :     bool operator!=(const iterator& I) const { return L != I.L; }
      96         529 :     const value_type& operator*() const { return L->getHead(); }
      97           0 :     const typename std::remove_reference<value_type>::type* operator->() const {
      98           0 :       return &L->getHead();
      99           0 :     }
     100             : 
     101           0 :     ImmutableList getList() const { return L; }
     102           0 :   };
     103             : 
     104             :   /// begin - Returns an iterator referring to the head of the list, or
     105           0 :   ///  an iterator denoting the end of the list if the list is empty.
     106           0 :   iterator begin() const { return iterator(X); }
     107             : 
     108          60 :   /// end - Returns an iterator denoting the end of the list.  This iterator
     109           0 :   ///  does not refer to a valid list element.
     110           0 :   iterator end() const { return iterator(); }
     111           0 : 
     112           0 :   /// isEmpty - Returns true if the list is empty.
     113           0 :   bool isEmpty() const { return !X; }
     114             : 
     115             :   bool contains(const T& V) const {
     116           0 :     for (iterator I = begin(), E = end(); I != E; ++I) {
     117             :       if (*I == V)
     118             :         return true;
     119             :     }
     120             :     return false;
     121           0 :   }
     122             : 
     123             :   /// isEqual - Returns true if two lists are equal.  Because all lists created
     124             :   ///  from the same ImmutableListFactory are uniqued, this has O(1) complexity
     125           0 :   ///  because it the contents of the list do not need to be compared.  Note
     126             :   ///  that you should only compare two lists created from the same
     127             :   ///  ImmutableListFactory.
     128           3 :   bool isEqual(const ImmutableList& L) const { return X == L.X; }
     129             : 
     130             :   bool operator==(const ImmutableList& L) const { return isEqual(L); }
     131          70 : 
     132          60 :   /// getHead - Returns the head of the list.
     133           0 :   const T& getHead() const {
     134             :     assert(!isEmpty() && "Cannot get the head of an empty list.");
     135         620 :     return X->getHead();
     136             :   }
     137             : 
     138             :   /// getTail - Returns the tail of the list, which is another (possibly empty)
     139             :   ///  ImmutableList.
     140           0 :   ImmutableList getTail() const {
     141         484 :     return X ? X->getTail() : nullptr;
     142             :   }
     143          15 : 
     144             :   void Profile(FoldingSetNodeID& ID) const {
     145             :     ID.AddPointer(X);
     146             :   }
     147             : };
     148           0 : 
     149             : template <typename T>
     150           0 : class ImmutableListFactory {
     151             :   using ListTy = ImmutableListImpl<T>;
     152           0 :   using CacheTy = FoldingSet<ListTy>;
     153             : 
     154           0 :   CacheTy Cache;
     155             :   uintptr_t Allocator;
     156           0 : 
     157           0 :   bool ownsAllocator() const {
     158         420 :     return (Allocator & 0x1) == 0;
     159             :   }
     160             : 
     161           0 :   BumpPtrAllocator& getAllocator() const {
     162        2461 :     return *reinterpret_cast<BumpPtrAllocator*>(Allocator & ~0x1);
     163           0 :   }
     164       19538 : 
     165             : public:
     166         297 :   ImmutableListFactory()
     167         297 :     : Allocator(reinterpret_cast<uintptr_t>(new BumpPtrAllocator())) {}
     168             : 
     169        9882 :   ImmutableListFactory(BumpPtrAllocator& Alloc)
     170        9882 :   : Allocator(reinterpret_cast<uintptr_t>(&Alloc) | 0x1) {}
     171             : 
     172         420 :   ~ImmutableListFactory() {
     173         420 :     if (ownsAllocator()) delete &getAllocator();
     174         442 :   }
     175             : 
     176           0 :   template <typename ElemT>
     177        2534 :   LLVM_NODISCARD ImmutableList<T> concat(ElemT &&Head, ImmutableList<T> Tail) {
     178             :     // Profile the new list to see if it already exists in our cache.
     179           0 :     FoldingSetNodeID ID;
     180           0 :     void* InsertPos;
     181             : 
     182        2534 :     const ListTy* TailImpl = Tail.getInternalPointer();
     183        2293 :     ListTy::Profile(ID, Head, TailImpl);
     184             :     ListTy* L = Cache.FindNodeOrInsertPos(ID, InsertPos);
     185             : 
     186        2534 :     if (!L) {
     187           8 :       // The list does not exist in our cache.  Create it.
     188        2164 :       BumpPtrAllocator& A = getAllocator();
     189           0 :       L = (ListTy*) A.Allocate<ListTy>();
     190       19518 :       new (L) ListTy(std::forward<ElemT>(Head), TailImpl);
     191       19518 : 
     192       19518 :       // Insert the new list into the cache.
     193       11923 :       Cache.InsertNode(L, InsertPos);
     194        9759 :     }
     195        9759 : 
     196       12293 :     return L;
     197        9759 :   }
     198        9867 : 
     199           0 :   template <typename ElemT>
     200             :   LLVM_NODISCARD ImmutableList<T> add(ElemT &&Data, ImmutableList<T> L) {
     201        2208 :     return concat(std::forward<ElemT>(Data), L);
     202           0 :   }
     203         108 : 
     204         108 :   template <typename ...CtorArgs>
     205           0 :   LLVM_NODISCARD ImmutableList<T> emplace(ImmutableList<T> Tail,
     206          60 :                                           CtorArgs &&...Args) {
     207         108 :     return concat(T(std::forward<CtorArgs>(Args)...), Tail);
     208           0 :   }
     209          67 : 
     210          28 :   ImmutableList<T> getEmptyList() const {
     211           0 :     return ImmutableList<T>(nullptr);
     212          22 :   }
     213             : 
     214          67 :   template <typename ElemT>
     215           0 :   ImmutableList<T> create(ElemT &&Data) {
     216             :     return concat(std::forward<ElemT>(Data), getEmptyList());
     217         130 :   }
     218           0 : };
     219         180 : 
     220          28 : //===----------------------------------------------------------------------===//
     221           0 : // Partially-specialized Traits.
     222             : //===----------------------------------------------------------------------===//
     223             : 
     224         180 : template<typename T> struct DenseMapInfo;
     225         216 : template<typename T> struct DenseMapInfo<ImmutableList<T>> {
     226           8 :   static inline ImmutableList<T> getEmptyKey() {
     227           1 :     return reinterpret_cast<ImmutableListImpl<T>*>(-1);
     228         181 :   }
     229           1 : 
     230         141 :   static inline ImmutableList<T> getTombstoneKey() {
     231           1 :     return reinterpret_cast<ImmutableListImpl<T>*>(-2);
     232           1 :   }
     233           1 : 
     234           1 :   static unsigned getHashValue(ImmutableList<T> X) {
     235         144 :     uintptr_t PtrVal = reinterpret_cast<uintptr_t>(X.getInternalPointer());
     236           4 :     return (unsigned((uintptr_t)PtrVal) >> 4) ^
     237             :            (unsigned((uintptr_t)PtrVal) >> 9);
     238         180 :   }
     239             : 
     240          66 :   static bool isEqual(ImmutableList<T> X1, ImmutableList<T> X2) {
     241           8 :     return X1 == X2;
     242           8 :   }
     243         275 : };
     244           1 : 
     245          67 : template <typename T> struct isPodLike;
     246          67 : template <typename T>
     247           1 : struct isPodLike<ImmutableList<T>> { static const bool value = true; };
     248           1 : 
     249          67 : } // end namespace llvm
     250           1 : 
     251          57 : #endif // LLVM_ADT_IMMUTABLELIST_H

Generated by: LCOV version 1.13