#ifndef LLVM_ADT_ILIST_H
#define LLVM_ADT_ILIST_H
-#include "llvm/ADT/iterator.h"
+#include "llvm/Support/Compiler.h"
+#include <algorithm>
#include <cassert>
+#include <cstddef>
+#include <iterator>
namespace llvm {
static void setNext(NodeTy *N, NodeTy *Next) { N->setNext(Next); }
};
+template<typename NodeTy>
+struct ilist_traits;
+
/// ilist_sentinel_traits - A fragment for template traits for intrusive list
/// that provides default sentinel implementations for common operations.
///
+/// ilist_sentinel_traits implements a lazy dynamic sentinel allocation
+/// strategy. The sentinel is stored in the prev field of ilist's Head.
+///
template<typename NodeTy>
struct ilist_sentinel_traits {
+ /// createSentinel - create the dynamic sentinel
static NodeTy *createSentinel() { return new NodeTy(); }
+
+ /// destroySentinel - deallocate the dynamic sentinel
static void destroySentinel(NodeTy *N) { delete N; }
+
+ /// provideInitialHead - when constructing an ilist, provide a starting
+ /// value for its Head
+ /// @return null node to indicate that it needs to be allocated later
+ static NodeTy *provideInitialHead() { return 0; }
+
+ /// ensureHead - make sure that Head is either already
+ /// initialized or assigned a fresh sentinel
+ /// @return the sentinel
+ static NodeTy *ensureHead(NodeTy *&Head) {
+ if (!Head) {
+ Head = ilist_traits<NodeTy>::createSentinel();
+ ilist_traits<NodeTy>::noteHead(Head, Head);
+ ilist_traits<NodeTy>::setNext(Head, 0);
+ return Head;
+ }
+ return ilist_traits<NodeTy>::getPrev(Head);
+ }
+
+ /// noteHead - stash the sentinel into its default location
+ static void noteHead(NodeTy *NewHead, NodeTy *Sentinel) {
+ ilist_traits<NodeTy>::setPrev(NewHead, Sentinel);
+ }
};
-/// ilist_default_traits - Default template traits for intrusive list.
-/// By inheriting from this, you can easily use default implementations
-/// for all common operations.
+/// ilist_node_traits - A fragment for template traits for intrusive list
+/// that provides default node related operations.
///
template<typename NodeTy>
-struct ilist_default_traits : ilist_nextprev_traits<NodeTy>,
- ilist_sentinel_traits<NodeTy> {
+struct ilist_node_traits {
static NodeTy *createNode(const NodeTy &V) { return new NodeTy(V); }
static void deleteNode(NodeTy *V) { delete V; }
void addNodeToList(NodeTy *) {}
void removeNodeFromList(NodeTy *) {}
- void transferNodesFromList(ilist_default_traits & /*SrcTraits*/,
+ void transferNodesFromList(ilist_node_traits & /*SrcTraits*/,
ilist_iterator<NodeTy> /*first*/,
ilist_iterator<NodeTy> /*last*/) {}
};
+/// ilist_default_traits - Default template traits for intrusive list.
+/// By inheriting from this, you can easily use default implementations
+/// for all common operations.
+///
+template<typename 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 {
- assert(Traits::getNext(NodePtr) != 0 && "Dereferencing end()!");
return NodePtr;
}
reference operator*() const {
- assert(Traits::getNext(NodePtr) != 0 && "Dereferencing end()!");
return *NodePtr;
}
pointer operator->() const { return &operator*(); }
// Increment and decrement operators...
ilist_iterator &operator--() { // predecrement - Back up
NodePtr = Traits::getPrev(NodePtr);
- assert(Traits::getNext(NodePtr) && "--'d off the beginning of an ilist!");
+ assert(NodePtr && "--'d off the beginning of an ilist!");
return *this;
}
ilist_iterator &operator++() { // preincrement - Advance
NodePtr = Traits::getNext(NodePtr);
- assert(NodePtr && "++'d off the end of an ilist!");
return *this;
}
ilist_iterator operator--(int) { // postdecrement operators...
//===----------------------------------------------------------------------===//
//
/// 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.
///
// circularly linked list where we snip the 'next' link from the sentinel node
// back to the first node in the list (to preserve assertions about going off
// the end of the list).
- NodeTy *getTail() { return this->getPrev(Head); }
- const NodeTy *getTail() const { return this->getPrev(Head); }
- void setTail(NodeTy *N) const { this->setPrev(Head, N); }
+ NodeTy *getTail() { return this->ensureHead(Head); }
+ const NodeTy *getTail() const { return this->ensureHead(Head); }
+ void setTail(NodeTy *N) const { this->noteHead(Head, N); }
/// CreateLazySentinel - This method verifies whether the sentinel for the
/// list has been created and lazily makes it if not.
void CreateLazySentinel() const {
- if (Head != 0) return;
- Head = Traits::createSentinel();
- this->setNext(Head, 0);
- setTail(Head);
+ this->ensureHead(Head);
}
static bool op_less(NodeTy &L, NodeTy &R) { return L < R; }
static bool op_equal(NodeTy &L, NodeTy &R) { return L == R; }
- // No fundamental reason why iplist can't by copyable, but the default
+ // 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;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
typedef std::reverse_iterator<iterator> reverse_iterator;
- iplist() : Head(0) {}
+ iplist() : Head(this->provideInitialHead()) {}
~iplist() {
if (!Head) return;
clear();
}
iterator insert(iterator where, NodeTy *New) {
- NodeTy *CurNode = where.getNodePtrUnchecked(), *PrevNode = this->getPrev(CurNode);
+ NodeTy *CurNode = where.getNodePtrUnchecked();
+ NodeTy *PrevNode = this->getPrev(CurNode);
this->setNext(New, CurNode);
this->setPrev(New, PrevNode);
}
iterator insertAfter(iterator where, NodeTy *New) {
- if (empty())
+ if (empty())
return insert(begin(), New);
else
return insert(++where, New);
L2.setTail(0);
// Remove [first, last) from its old position.
- NodeTy *First = &*first, *Prev = getPrev(First);
- NodeTy *Next = last.getNodePtrUnchecked(), *Last = getPrev(Next);
+ NodeTy *First = &*first, *Prev = this->getPrev(First);
+ NodeTy *Next = last.getNodePtrUnchecked(), *Last = this->getPrev(Next);
if (Prev)
this->setNext(Prev, Next);
else
// Splice [first, last) into its new position.
NodeTy *PosNext = position.getNodePtrUnchecked();
- NodeTy *PosPrev = getPrev(PosNext);
+ NodeTy *PosPrev = this->getPrev(PosNext);
// Fix head of list...
if (PosPrev)
this->setNext(Last, PosNext);
this->setPrev(PosNext, Last);
- transferNodesFromList(L2, First, PosNext);
+ this->transferNodesFromList(L2, First, PosNext);
// Now that everything is set, restore the pointers to the list sentinels.
L2.setTail(L2Sentinel);
size_type size() const {
if (Head == 0) return 0; // Don't require construction of sentinel if empty.
-#if __GNUC__ == 2
- // GCC 2.95 has a broken std::distance
- size_type Result = 0;
- std::distance(begin(), end(), Result);
- return Result;
-#else
return std::distance(begin(), end());
-#endif
}
iterator erase(iterator first, iterator last) {
template<class Pr3> void sort(Pr3 pred);
void sort() { sort(op_less); }
- void reverse();
};
insert(this->begin(), first, last);
}
-
- // Forwarding functions: A workaround for GCC 2.95 which does not correctly
- // support 'using' declarations to bring a hidden member into scope.
- //
- iterator insert(iterator a, NodeTy *b){ return iplist<NodeTy>::insert(a, b); }
- void push_front(NodeTy *a) { iplist<NodeTy>::push_front(a); }
- void push_back(NodeTy *a) { iplist<NodeTy>::push_back(a); }
-
+ // bring hidden functions into scope
+ using iplist<NodeTy>::insert;
+ using iplist<NodeTy>::push_front;
+ using iplist<NodeTy>::push_back;
// 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);
}