LCOV - code coverage report
Current view: top level - include/llvm/ADT - ImmutableList.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 39 39 100.0 %
Date: 2017-09-14 15:23:50 Functions: 9 9 100.0 %
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        1499 :   ImmutableListImpl(const T& head, const ImmutableListImpl* tail = nullptr)
      35        2998 :     : Head(head), Tail(tail) {}
      36             : 
      37             : public:
      38             :   ImmutableListImpl(const ImmutableListImpl &) = delete;
      39             :   ImmutableListImpl &operator=(const ImmutableListImpl &) = delete;
      40             : 
      41        4554 :   const T& getHead() const { return Head; }
      42             :   const ImmutableListImpl* getTail() const { return Tail; }
      43             : 
      44        1792 :   static inline void Profile(FoldingSetNodeID& ID, const T& H,
      45             :                              const ImmutableListImpl* L){
      46        1995 :     ID.AddPointer(L);
      47        2091 :     ID.Add(H);
      48        1792 :   }
      49             : 
      50             :   void Profile(FoldingSetNodeID& ID) {
      51         331 :     Profile(ID, Head, Tail);
      52             :   }
      53             : };
      54             : 
      55             : /// ImmutableList - This class represents an immutable (functional) list.
      56             : ///  It is implemented as a smart pointer (wraps ImmutableListImpl), so it
      57             : ///  it is intended to always be copied by value as if it were a pointer.
      58             : ///  This interface matches ImmutableSet and ImmutableMap.  ImmutableList
      59             : ///  objects should almost never be created directly, and instead should
      60             : ///  be created by ImmutableListFactory objects that manage the lifetime
      61             : ///  of a group of lists.  When the factory object is reclaimed, all lists
      62             : ///  created by that factory are released as well.
      63             : template <typename T>
      64             : class ImmutableList {
      65             : public:
      66             :   using value_type = T;
      67             :   using Factory = ImmutableListFactory<T>;
      68             : 
      69             : private:
      70             :   const ImmutableListImpl<T>* X;
      71             : 
      72             : public:
      73             :   // This constructor should normally only be called by ImmutableListFactory<T>.
      74             :   // There may be cases, however, when one needs to extract the internal pointer
      75             :   // and reconstruct a list object from that pointer.
      76          24 :   ImmutableList(const ImmutableListImpl<T>* x = nullptr) : X(x) {}
      77             : 
      78             :   const ImmutableListImpl<T>* getInternalPointer() const {
      79        2448 :     return X;
      80             :   }
      81             : 
      82             :   class iterator {
      83             :     const ImmutableListImpl<T>* L = nullptr;
      84             : 
      85             :   public:
      86             :     iterator() = default;
      87        1841 :     iterator(ImmutableList l) : L(l.getInternalPointer()) {}
      88             : 
      89        4563 :     iterator& operator++() { L = L->getTail(); return *this; }
      90        3304 :     bool operator==(const iterator& I) const { return L == I.L; }
      91        2195 :     bool operator!=(const iterator& I) const { return L != I.L; }
      92        9137 :     const value_type& operator*() const { return L->getHead(); }
      93             : 
      94             :     ImmutableList getList() const { return L; }
      95             :   };
      96             : 
      97             :   /// begin - Returns an iterator referring to the head of the list, or
      98             :   ///  an iterator denoting the end of the list if the list is empty.
      99        3682 :   iterator begin() const { return iterator(X); }
     100             : 
     101             :   /// end - Returns an iterator denoting the end of the list.  This iterator
     102             :   ///  does not refer to a valid list element.
     103        1833 :   iterator end() const { return iterator(); }
     104             : 
     105             :   /// isEmpty - Returns true if the list is empty.
     106             :   bool isEmpty() const { return !X; }
     107             : 
     108             :   bool contains(const T& V) const {
     109             :     for (iterator I = begin(), E = end(); I != E; ++I) {
     110             :       if (*I == V)
     111             :         return true;
     112             :     }
     113             :     return false;
     114             :   }
     115             : 
     116             :   /// isEqual - Returns true if two lists are equal.  Because all lists created
     117             :   ///  from the same ImmutableListFactory are uniqued, this has O(1) complexity
     118             :   ///  because it the contents of the list do not need to be compared.  Note
     119             :   ///  that you should only compare two lists created from the same
     120             :   ///  ImmutableListFactory.
     121             :   bool isEqual(const ImmutableList& L) const { return X == L.X; }
     122             : 
     123             :   bool operator==(const ImmutableList& L) const { return isEqual(L); }
     124             : 
     125             :   /// getHead - Returns the head of the list.
     126             :   const T& getHead() {
     127             :     assert(!isEmpty() && "Cannot get the head of an empty list.");
     128        4996 :     return X->getHead();
     129             :   }
     130             : 
     131             :   /// getTail - Returns the tail of the list, which is another (possibly empty)
     132             :   ///  ImmutableList.
     133             :   ImmutableList getTail() {
     134         107 :     return X ? X->getTail() : nullptr;
     135             :   }
     136             : 
     137             :   void Profile(FoldingSetNodeID& ID) const {
     138             :     ID.AddPointer(X);
     139             :   }
     140             : };
     141             : 
     142             : template <typename T>
     143             : class ImmutableListFactory {
     144             :   using ListTy = ImmutableListImpl<T>;
     145             :   using CacheTy = FoldingSet<ListTy>;
     146             : 
     147             :   CacheTy Cache;
     148             :   uintptr_t Allocator;
     149             : 
     150             :   bool ownsAllocator() const {
     151       13762 :     return (Allocator & 0x1) == 0;
     152             :   }
     153             : 
     154             :   BumpPtrAllocator& getAllocator() const {
     155        1499 :     return *reinterpret_cast<BumpPtrAllocator*>(Allocator & ~0x1);
     156             :   }
     157             : 
     158             : public:
     159             :   ImmutableListFactory()
     160             :     : Allocator(reinterpret_cast<uintptr_t>(new BumpPtrAllocator())) {}
     161             : 
     162       13762 :   ImmutableListFactory(BumpPtrAllocator& Alloc)
     163       27524 :   : Allocator(reinterpret_cast<uintptr_t>(&Alloc) | 0x1) {}
     164             : 
     165       13762 :   ~ImmutableListFactory() {
     166       27524 :     if (ownsAllocator()) delete &getAllocator();
     167       27524 :   }
     168             : 
     169        1707 :   ImmutableList<T> concat(const T& Head, ImmutableList<T> Tail) {
     170             :     // Profile the new list to see if it already exists in our cache.
     171        3414 :     FoldingSetNodeID ID;
     172             :     void* InsertPos;
     173             : 
     174        1707 :     const ListTy* TailImpl = Tail.getInternalPointer();
     175        1707 :     ListTy::Profile(ID, Head, TailImpl);
     176        3414 :     ListTy* L = Cache.FindNodeOrInsertPos(ID, InsertPos);
     177             : 
     178        1707 :     if (!L) {
     179             :       // The list does not exist in our cache.  Create it.
     180        2998 :       BumpPtrAllocator& A = getAllocator();
     181        1499 :       L = (ListTy*) A.Allocate<ListTy>();
     182        2998 :       new (L) ListTy(Head, TailImpl);
     183             : 
     184             :       // Insert the new list into the cache.
     185        1499 :       Cache.InsertNode(L, InsertPos);
     186             :     }
     187             : 
     188        3414 :     return L;
     189             :   }
     190             : 
     191             :   ImmutableList<T> add(const T& D, ImmutableList<T> L) {
     192        1707 :     return concat(D, L);
     193             :   }
     194             : 
     195             :   ImmutableList<T> getEmptyList() const {
     196         652 :     return ImmutableList<T>(nullptr);
     197             :   }
     198             : 
     199             :   ImmutableList<T> create(const T& X) {
     200             :     return Concat(X, getEmptyList());
     201             :   }
     202             : };
     203             : 
     204             : //===----------------------------------------------------------------------===//
     205             : // Partially-specialized Traits.
     206             : //===----------------------------------------------------------------------===//
     207             : 
     208             : template<typename T> struct DenseMapInfo;
     209             : template<typename T> struct DenseMapInfo<ImmutableList<T>> {
     210             :   static inline ImmutableList<T> getEmptyKey() {
     211             :     return reinterpret_cast<ImmutableListImpl<T>*>(-1);
     212             :   }
     213             : 
     214             :   static inline ImmutableList<T> getTombstoneKey() {
     215             :     return reinterpret_cast<ImmutableListImpl<T>*>(-2);
     216             :   }
     217             : 
     218             :   static unsigned getHashValue(ImmutableList<T> X) {
     219             :     uintptr_t PtrVal = reinterpret_cast<uintptr_t>(X.getInternalPointer());
     220             :     return (unsigned((uintptr_t)PtrVal) >> 4) ^
     221             :            (unsigned((uintptr_t)PtrVal) >> 9);
     222             :   }
     223             : 
     224             :   static bool isEqual(ImmutableList<T> X1, ImmutableList<T> X2) {
     225             :     return X1 == X2;
     226             :   }
     227             : };
     228             : 
     229             : template <typename T> struct isPodLike;
     230             : template <typename T>
     231             : struct isPodLike<ImmutableList<T>> { static const bool value = true; };
     232             : 
     233             : } // end namespace llvm
     234             : 
     235             : #endif // LLVM_ADT_IMMUTABLELIST_H

Generated by: LCOV version 1.13