-//===-- Support/ilist - Intrusive Linked List Template ----------*- C++ -*-===//
+//===-- llvm/ADT/ilist - Intrusive Linked List Template ---------*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
//
//===----------------------------------------------------------------------===//
-#ifndef SUPPORT_ILIST
-#define SUPPORT_ILIST
+#ifndef LLVM_ADT_ILIST
+#define LLVM_ADT_ILIST
-#include <algorithm>
-#include <Support/iterator>
+#include "llvm/ADT/iterator"
#include <cassert>
+namespace llvm {
+
template<typename NodeTy, typename Traits> class iplist;
template<typename NodeTy> class ilist_iterator;
static void setPrev(NodeTy *N, NodeTy *Prev) { N->setPrev(Prev); }
static void setNext(NodeTy *N, NodeTy *Next) { N->setNext(Next); }
- static NodeTy *createNode() { return new NodeTy(); }
static NodeTy *createNode(const NodeTy &V) { return new NodeTy(V); }
+ static NodeTy *createSentinel() { return new NodeTy(); }
+ static void destroySentinel(NodeTy *N) { delete N; }
void addNodeToList(NodeTy *NTy) {}
void removeNodeFromList(NodeTy *NTy) {}
return tmp;
}
-
- // Dummy operators to make errors apparent...
- template<class X> void operator+(X Val) {}
- template<class X> void operator-(X Val) {}
-
// Internal interface, do not use...
pointer getNodePtrUnchecked() const { return NodePtr; }
};
+// do not implement. this is to catch errors when people try to use
+// them as random access iterators
+template<typename T>
+void operator-(int, ilist_iterator<T>);
+template<typename T>
+void operator-(ilist_iterator<T>,int);
+
+template<typename T>
+void operator+(int, ilist_iterator<T>);
+template<typename T>
+void operator+(ilist_iterator<T>,int);
+
+// operator!=/operator== - Allow mixed comparisons without dereferencing
+// the iterator, which could very likely be pointing to end().
+template<typename T>
+bool operator!=(const T* LHS, const ilist_iterator<const T> &RHS) {
+ return LHS != RHS.getNodePtrUnchecked();
+}
+template<typename T>
+bool operator==(const T* LHS, const ilist_iterator<const T> &RHS) {
+ return LHS == RHS.getNodePtrUnchecked();
+}
+template<typename T>
+bool operator!=(T* LHS, const ilist_iterator<T> &RHS) {
+ return LHS != RHS.getNodePtrUnchecked();
+}
+template<typename T>
+bool operator==(T* LHS, const ilist_iterator<T> &RHS) {
+ return LHS == RHS.getNodePtrUnchecked();
+}
+
+
// Allow ilist_iterators to convert into pointers to a node automatically when
// used by the dyn_cast, cast, isa mechanisms...
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
typedef std::reverse_iterator<iterator> reverse_iterator;
- iplist() : Head(this->createNode()), Tail(Head) {
+ iplist() : Head(Traits::createSentinel()), Tail(Head) {
setNext(Head, 0);
setPrev(Head, 0);
}
- ~iplist() { clear(); delete Tail; }
+ ~iplist() { clear(); Traits::destroySentinel(Tail); }
- // Iterator creation methods...
+ // Iterator creation methods.
iterator begin() { return iterator(Head); }
const_iterator begin() const { return const_iterator(Head); }
iterator end() { return iterator(Tail); }
const_iterator end() const { return const_iterator(Tail); }
- // reverse iterator creation methods...
+ // reverse iterator creation methods.
reverse_iterator rbegin() { return reverse_iterator(end()); }
const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); }
reverse_iterator rend() { return reverse_iterator(begin()); }
const_reverse_iterator rend() const {return const_reverse_iterator(begin());}
- // Miscellaneous inspection routines...
+
+ // Miscellaneous inspection routines.
size_type max_size() const { return size_type(-1); }
bool empty() const { return Head == Tail; }
Head = NextNode;
setPrev(NextNode, PrevNode);
IT = NextNode;
- removeNodeFromList(Node); // Notify traits that we added a node...
+ removeNodeFromList(Node); // Notify traits that we removed a node...
return Node;
}
//
size_type size() const {
-#if __GNUC__ == 3
- size_type Result = std::distance(begin(), end());
-#else
+#if __GNUC__ == 2
+ // GCC 2.95 has a broken std::distance
size_type Result = 0;
std::distance(begin(), end(), Result);
-#endif
return Result;
+#else
+ return std::distance(begin(), end());
+#endif
}
iterator erase(iterator first, iterator last) {
void resize(size_type newsize) { resize(newsize, NodeTy()); }
};
+} // End llvm namespace
+
namespace std {
// Ensure that swap uses the fast list swap...
template<class Ty>
- void swap(iplist<Ty> &Left, iplist<Ty> &Right) {
+ void swap(llvm::iplist<Ty> &Left, llvm::iplist<Ty> &Right) {
Left.swap(Right);
}
} // End 'std' extensions...