#ifndef LLVM_ADT_ILIST_H
#define LLVM_ADT_ILIST_H
-#include "llvm/ADT/iterator.h"
+#include "llvm/Support/Compiler.h"
+#include <algorithm>
#include <cassert>
-
-#undef LLVM_COMPACTIFY_SENTINELS
-/// @brief activate small sentinel structs
-/// Comment out if you want better debuggability
-/// of ilist<> end() iterators.
-/// See also llvm/ADT/ilist_node.h, where the
-/// same change must be made.
-///
-#define LLVM_COMPACTIFY_SENTINELS 1
-
-#if defined(LLVM_COMPACTIFY_SENTINELS) && LLVM_COMPACTIFY_SENTINELS
-# define sentinel_tail_assert(COND)
-#else
-# define sentinel_tail_assert(COND) assert(COND)
-#endif
+#include <cstddef>
+#include <iterator>
namespace llvm {
/// for all common operations.
///
template<typename NodeTy>
-struct ilist_default_traits : ilist_nextprev_traits<NodeTy>,
- ilist_sentinel_traits<NodeTy>,
- ilist_node_traits<NodeTy> {
+struct ilist_default_traits : public ilist_nextprev_traits<NodeTy>,
+ public ilist_sentinel_traits<NodeTy>,
+ public ilist_node_traits<NodeTy> {
};
// Template traits for intrusive list. By specializing this template class, you
// can change what next/prev fields are used to store the links...
template<typename NodeTy>
-struct ilist_traits : ilist_default_traits<NodeTy> {};
+struct ilist_traits : public ilist_default_traits<NodeTy> {};
// Const traits are the same as nonconst traits...
template<typename Ty>
//
template<typename NodeTy>
class ilist_iterator
- : public bidirectional_iterator<NodeTy, ptrdiff_t> {
+ : public std::iterator<std::bidirectional_iterator_tag, NodeTy, ptrdiff_t> {
public:
typedef ilist_traits<NodeTy> Traits;
- typedef bidirectional_iterator<NodeTy, ptrdiff_t> super;
+ typedef std::iterator<std::bidirectional_iterator_tag,
+ NodeTy, ptrdiff_t> super;
typedef typename super::value_type value_type;
typedef typename super::difference_type difference_type;
// Accessors...
operator pointer() const {
- sentinel_tail_assert(Traits::getNext(NodePtr) != 0 && "Dereferencing end()!");
return NodePtr;
}
reference operator*() const {
- sentinel_tail_assert(Traits::getNext(NodePtr) != 0 && "Dereferencing end()!");
return *NodePtr;
}
pointer operator->() const { return &operator*(); }
}
ilist_iterator &operator++() { // preincrement - Advance
NodePtr = Traits::getNext(NodePtr);
- sentinel_tail_assert(NodePtr && "++'d off the end of an ilist!");
return *this;
}
ilist_iterator operator--(int) { // postdecrement operators...
pointer getNodePtrUnchecked() const { return NodePtr; }
};
-// do not implement. this is to catch errors when people try to use
-// them as random access iterators
+// These are to catch errors when people try to use them as random access
+// iterators.
template<typename T>
-void operator-(int, ilist_iterator<T>);
+void operator-(int, ilist_iterator<T>) LLVM_DELETED_FUNCTION;
template<typename T>
-void operator-(ilist_iterator<T>,int);
+void operator-(ilist_iterator<T>,int) LLVM_DELETED_FUNCTION;
template<typename T>
-void operator+(int, ilist_iterator<T>);
+void operator+(int, ilist_iterator<T>) LLVM_DELETED_FUNCTION;
template<typename T>
-void operator+(ilist_iterator<T>,int);
+void operator+(ilist_iterator<T>,int) LLVM_DELETED_FUNCTION;
// operator!=/operator== - Allow mixed comparisons without dereferencing
// the iterator, which could very likely be pointing to end().
template<typename NodeTy> struct simplify_type<ilist_iterator<NodeTy> > {
typedef NodeTy* SimpleType;
- static SimpleType getSimplifiedValue(const ilist_iterator<NodeTy> &Node) {
+ static SimpleType getSimplifiedValue(ilist_iterator<NodeTy> &Node) {
return &*Node;
}
};
template<typename NodeTy> struct simplify_type<const ilist_iterator<NodeTy> > {
- typedef NodeTy* SimpleType;
+ typedef /*const*/ NodeTy* SimpleType;
static SimpleType getSimplifiedValue(const ilist_iterator<NodeTy> &Node) {
return &*Node;
//===----------------------------------------------------------------------===//
//
/// iplist - The subset of list functionality that can safely be used on nodes
-/// of polymorphic types, i.e. a heterogenous list with a common base class that
+/// of polymorphic types, i.e. a heterogeneous list with a common base class that
/// holds the next/prev pointers. The only state of the list itself is a single
/// pointer to the head of the list.
///
// No fundamental reason why iplist can't be copyable, but the default
// copy/copy-assign won't do.
- iplist(const iplist &); // do not implement
- void operator=(const iplist &); // do not implement
+ iplist(const iplist &) LLVM_DELETED_FUNCTION;
+ void operator=(const iplist &) LLVM_DELETED_FUNCTION;
public:
typedef NodeTy *pointer;
return where;
}
+ /// Remove all nodes from the list like clear(), but do not call
+ /// removeNodeFromList() or deleteNode().
+ ///
+ /// This should only be used immediately before freeing nodes in bulk to
+ /// avoid traversing the list and bringing all the nodes into cache.
+ void clearAndLeakNodesUnsafely() {
+ if (Head) {
+ Head = getTail();
+ this->setPrev(Head, Head);
+ }
+ }
private:
// transfer - The heart of the splice function. Move linked list nodes from
//
void transfer(iterator position, iplist &L2, iterator first, iterator last) {
assert(first != last && "Should be checked by callers");
+ // Position cannot be contained in the range to be transferred.
+ // Check for the most common mistake.
+ assert(position != first &&
+ "Insertion point can't be one of the transferred nodes");
if (position != last) {
// Note: we have to be careful about the case when we move the first node
template<class Pr3> void sort(Pr3 pred);
void sort() { sort(op_less); }
- void reverse();
};
// Main implementation here - Insert for a node passed by value...
iterator insert(iterator where, const NodeTy &val) {
- return insert(where, createNode(val));
+ return insert(where, this->createNode(val));
}
void push_front(const NodeTy &val) { insert(this->begin(), val); }
void push_back(const NodeTy &val) { insert(this->end(), val); }
- // Special forms of insert...
- template<class InIt> void insert(iterator where, InIt first, InIt last) {
- for (; first != last; ++first) insert(where, *first);
- }
void insert(iterator where, size_type count, const NodeTy &val) {
for (; count != 0; --count) insert(where, val);
}