X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FImmutableList.h;h=d7c0074a9f0827e83f5b9a07abd06a07ada6e095;hb=b4c28fc93f5149a0bd7967af44c429412e751c56;hp=dd88023fd1f90ba832d54632798ade0ca517224c;hpb=eca64f0980e3f686a36007c53272780119635337;p=oota-llvm.git

diff --git a/include/llvm/ADT/ImmutableList.h b/include/llvm/ADT/ImmutableList.h
index dd88023fd1f..d7c0074a9f0 100644
--- a/include/llvm/ADT/ImmutableList.h
+++ b/include/llvm/ADT/ImmutableList.h
@@ -22,36 +22,36 @@
 namespace llvm {
 
 template <typename T> class ImmutableListFactory;
-  
+
 template <typename T>
 class ImmutableListImpl : public FoldingSetNode {
   T Head;
-  ImmutableListImpl* Tail;
+  const ImmutableListImpl* Tail;
 
-  ImmutableListImpl(const T& head, ImmutableListImpl* tail = 0)
+  ImmutableListImpl(const T& head, const ImmutableListImpl* tail = 0)
     : Head(head), Tail(tail) {}
-  
+
   friend class ImmutableListFactory<T>;
-  
+
   // Do not implement.
   void operator=(const ImmutableListImpl&);
   ImmutableListImpl(const ImmutableListImpl&);
-  
+
 public:
   const T& getHead() const { return Head; }
-  ImmutableListImpl* getTail() const { return Tail; }
-  
+  const ImmutableListImpl* getTail() const { return Tail; }
+
   static inline void Profile(FoldingSetNodeID& ID, const T& H,
-                             ImmutableListImpl* L){
+                             const ImmutableListImpl* L){
     ID.AddPointer(L);
     ID.Add(H);
   }
-  
+
   void Profile(FoldingSetNodeID& ID) {
     Profile(ID, Head, Tail);
   }
 };
-  
+
 /// ImmutableList - This class represents an immutable (functional) list.
 ///  It is implemented as a smart pointer (wraps ImmutableListImpl), so it
 ///  it is intended to always be copied by value as if it were a pointer.
@@ -67,48 +67,56 @@ public:
   typedef ImmutableListFactory<T> Factory;
 
 private:
-  ImmutableListImpl<T>* X;
+  const ImmutableListImpl<T>* X;
 
 public:
   // This constructor should normally only be called by ImmutableListFactory<T>.
   // There may be cases, however, when one needs to extract the internal pointer
   // and reconstruct a list object from that pointer.
-  ImmutableList(ImmutableListImpl<T>* x = 0) : X(x) {}
+  ImmutableList(const ImmutableListImpl<T>* x = 0) : X(x) {}
 
-  ImmutableListImpl<T>* getInternalPointer() const {
+  const ImmutableListImpl<T>* getInternalPointer() const {
     return X;
   }
-  
+
   class iterator {
-    ImmutableListImpl<T>* L;
+    const ImmutableListImpl<T>* L;
   public:
     iterator() : L(0) {}
     iterator(ImmutableList l) : L(l.getInternalPointer()) {}
-    
+
     iterator& operator++() { L = L->getTail(); return *this; }
     bool operator==(const iterator& I) const { return L == I.L; }
     bool operator!=(const iterator& I) const { return L != I.L; }
-    const value_type& operator*() const { return L->getHead(); }    
-    ImmutableList getList() const { return L; }    
+    const value_type& operator*() const { return L->getHead(); }
+    ImmutableList getList() const { return L; }
   };
 
   /// begin - Returns an iterator referring to the head of the list, or
   ///  an iterator denoting the end of the list if the list is empty.
   iterator begin() const { return iterator(X); }
-    
+
   /// end - Returns an iterator denoting the end of the list.  This iterator
   ///  does not refer to a valid list element.
   iterator end() const { return iterator(); }
 
   /// isEmpty - Returns true if the list is empty.
   bool isEmpty() const { return !X; }
-  
+
+  bool contains(const T& V) const {
+    for (iterator I = begin(), E = end(); I != E; ++I) {
+      if (*I == V)
+        return true;
+    }
+    return false;
+  }
+
   /// isEqual - Returns true if two lists are equal.  Because all lists created
   ///  from the same ImmutableListFactory are uniqued, this has O(1) complexity
   ///  because it the contents of the list do not need to be compared.  Note
   ///  that you should only compare two lists created from the same
   ///  ImmutableListFactory.
-  bool isEqual(const ImmutableList& L) const { return X == L.X; }  
+  bool isEqual(const ImmutableList& L) const { return X == L.X; }
 
   bool operator==(const ImmutableList& L) const { return isEqual(L); }
 
@@ -117,80 +125,84 @@ public:
     assert (!isEmpty() && "Cannot get the head of an empty list.");
     return X->getHead();
   }
-  
+
   /// getTail - Returns the tail of the list, which is another (possibly empty)
   ///  ImmutableList.
   ImmutableList getTail() {
     return X ? X->getTail() : 0;
-  }  
+  }
+
+  void Profile(FoldingSetNodeID& ID) const {
+    ID.AddPointer(X);
+  }
 };
-  
+
 template <typename T>
 class ImmutableListFactory {
-  typedef ImmutableListImpl<T> ListTy;  
+  typedef ImmutableListImpl<T> ListTy;
   typedef FoldingSet<ListTy>   CacheTy;
-  
+
   CacheTy Cache;
   uintptr_t Allocator;
-  
+
   bool ownsAllocator() const {
     return Allocator & 0x1 ? false : true;
   }
-  
-  BumpPtrAllocator& getAllocator() const { 
+
+  BumpPtrAllocator& getAllocator() const {
     return *reinterpret_cast<BumpPtrAllocator*>(Allocator & ~0x1);
-  }  
+  }
 
 public:
   ImmutableListFactory()
     : Allocator(reinterpret_cast<uintptr_t>(new BumpPtrAllocator())) {}
-  
+
   ImmutableListFactory(BumpPtrAllocator& Alloc)
   : Allocator(reinterpret_cast<uintptr_t>(&Alloc) | 0x1) {}
-  
+
   ~ImmutableListFactory() {
     if (ownsAllocator()) delete &getAllocator();
   }
-  
-  ImmutableList<T> Concat(const T& Head, ImmutableList<T> Tail) {
+
+  ImmutableList<T> concat(const T& Head, ImmutableList<T> Tail) {
     // Profile the new list to see if it already exists in our cache.
     FoldingSetNodeID ID;
     void* InsertPos;
-    
-    ListTy* TailImpl = Tail.getInternalPointer();
+
+    const ListTy* TailImpl = Tail.getInternalPointer();
     ListTy::Profile(ID, Head, TailImpl);
     ListTy* L = Cache.FindNodeOrInsertPos(ID, InsertPos);
-    
+
     if (!L) {
       // The list does not exist in our cache.  Create it.
       BumpPtrAllocator& A = getAllocator();
       L = (ListTy*) A.Allocate<ListTy>();
       new (L) ListTy(Head, TailImpl);
-    
+
       // Insert the new list into the cache.
       Cache.InsertNode(L, InsertPos);
     }
-    
+
     return L;
   }
-  
-  ImmutableList<T> Add(const T& D, ImmutableList<T> L) {
-    return Concat(D, L);
+
+  ImmutableList<T> add(const T& D, ImmutableList<T> L) {
+    return concat(D, L);
   }
-  
-  ImmutableList<T> GetEmptyList() const {
+
+  ImmutableList<T> getEmptyList() const {
     return ImmutableList<T>(0);
   }
-  
-  ImmutableList<T> Create(const T& X) {
-    return Concat(X, GetEmptyList());
+
+  ImmutableList<T> create(const T& X) {
+    return Concat(X, getEmptyList());
   }
 };
-  
-//===----------------------------------------------------------------------===//  
+
+//===----------------------------------------------------------------------===//
 // Partially-specialized Traits.
-//===----------------------------------------------------------------------===//  
-  
+//===----------------------------------------------------------------------===//
+
 template<typename T> struct DenseMapInfo;
 template<typename T> struct DenseMapInfo<ImmutableList<T> > {
   static inline ImmutableList<T> getEmptyKey() {
@@ -201,15 +213,18 @@ template<typename T> struct DenseMapInfo<ImmutableList<T> > {
   }
   static unsigned getHashValue(ImmutableList<T> X) {
     uintptr_t PtrVal = reinterpret_cast<uintptr_t>(X.getInternalPointer());
-    return (unsigned((uintptr_t)PtrVal) >> 4) ^ 
+    return (unsigned((uintptr_t)PtrVal) >> 4) ^
            (unsigned((uintptr_t)PtrVal) >> 9);
   }
   static bool isEqual(ImmutableList<T> X1, ImmutableList<T> X2) {
     return X1 == X2;
   }
-  static bool isPod() { return true; }
 };
-  
+
+template <typename T> struct isPodLike;
+template <typename T>
+struct isPodLike<ImmutableList<T> > { static const bool value = true; };
+
 } // end llvm namespace
 
 #endif