//
//===----------------------------------------------------------------------===//
-#ifndef LLVM_ADT_IMLIST_H
-#define LLVM_ADT_IMLIST_H
+#ifndef LLVM_ADT_IMMUTABLELIST_H
+#define LLVM_ADT_IMMUTABLELIST_H
-#include "llvm/Support/Allocator.h"
#include "llvm/ADT/FoldingSet.h"
+#include "llvm/Support/Allocator.h"
#include "llvm/Support/DataTypes.h"
#include <cassert>
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 = nullptr)
: Head(head), Tail(tail) {}
-
+
friend class ImmutableListFactory<T>;
-
- // Do not implement.
- void operator=(const ImmutableListImpl&);
- ImmutableListImpl(const ImmutableListImpl&);
-
+
+ void operator=(const ImmutableListImpl&) = delete;
+ ImmutableListImpl(const ImmutableListImpl&) = delete;
+
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.
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) : X(x) {}
+ ImmutableList(const ImmutableListImpl<T>* x = nullptr) : 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() : L(nullptr) {}
iterator(ImmutableList l) : L(l.getInternalPointer()) {}
-
- iterator& operator++() { L = L->Tail; return *this; }
+
+ iterator& operator++() { L = L->getTail(); return *this; }
bool operator==(const iterator& I) const { return L == I.L; }
- ImmutableList operator*() const { return L; }
+ bool operator!=(const iterator& I) const { return L != I.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); }
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;
- }
+ return X ? X->getTail() : nullptr;
+ }
+
+ 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 {
- return ImmutableList<T>(0);
+
+ ImmutableList<T> getEmptyList() const {
+ return ImmutableList<T>(nullptr);
}
-
- 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() {
+ return reinterpret_cast<ImmutableListImpl<T>*>(-1);
+ }
+ static inline ImmutableList<T> getTombstoneKey() {
+ return reinterpret_cast<ImmutableListImpl<T>*>(-2);
+ }
+ static unsigned getHashValue(ImmutableList<T> X) {
+ uintptr_t PtrVal = reinterpret_cast<uintptr_t>(X.getInternalPointer());
+ return (unsigned((uintptr_t)PtrVal) >> 4) ^
+ (unsigned((uintptr_t)PtrVal) >> 9);
+ }
+ static bool isEqual(ImmutableList<T> X1, ImmutableList<T> X2) {
+ return X1 == X2;
+ }
+};
+
+template <typename T> struct isPodLike;
+template <typename T>
+struct isPodLike<ImmutableList<T> > { static const bool value = true; };
+
} // end llvm namespace
-#endif
+#endif // LLVM_ADT_IMMUTABLELIST_H
projects / oota-llvm.git / blobdiff