38 #ifndef LLVM_ADT_ILIST_H
39 #define LLVM_ADT_ILIST_H
49 template<
typename NodeTy,
typename Traits>
class iplist;
55 template<
typename NodeTy>
57 static NodeTy *
getPrev(NodeTy *
N) {
return N->getPrev(); }
58 static NodeTy *
getNext(NodeTy *
N) {
return N->getNext(); }
59 static const NodeTy *
getPrev(
const NodeTy *
N) {
return N->getPrev(); }
60 static const NodeTy *
getNext(
const NodeTy *
N) {
return N->getNext(); }
62 static void setPrev(NodeTy *
N, NodeTy *Prev) { N->setPrev(Prev); }
63 static void setNext(NodeTy *
N, NodeTy *Next) { N->setNext(Next); }
66 template<
typename NodeTy>
75 template<
typename NodeTy>
102 static void noteHead(NodeTy *NewHead, NodeTy *Sentinel) {
110 template<
typename NodeTy>
112 static NodeTy *
createNode(
const NodeTy &V) {
return new NodeTy(V); }
126 template<
typename NodeTy>
134 template<
typename NodeTy>
138 template<
typename Ty>
144 template<
typename NodeTy>
146 :
public std::iterator<std::bidirectional_iterator_tag, NodeTy, ptrdiff_t> {
150 typedef std::iterator<std::bidirectional_iterator_tag,
169 template<
class T>
void operator<(
T)
const;
170 template<
class T>
void operator<=(
T)
const;
171 template<
class T>
void operator>(
T)
const;
172 template<
class T>
void operator>=(
T)
const;
173 template<
class T>
void operator-(
T)
const;
182 template<
class node_ty>
188 template<
class node_ty>
206 return NodePtr == RHS.NodePtr;
209 return NodePtr != RHS.NodePtr;
215 assert(NodePtr &&
"--'d off the beginning of an ilist!");
242 void operator-(ilist_iterator<
T>,
int) LLVM_DELETED_FUNCTION;
245 void operator+(
int, ilist_iterator<T>) LLVM_DELETED_FUNCTION;
247 void operator+(ilist_iterator<T>,
int) LLVM_DELETED_FUNCTION;
253 return LHS != RHS.getNodePtrUnchecked();
312 template<
typename NodeTy,
typename Traits=ilist_traits<NodeTy> >
313 class iplist :
public Traits {
314 mutable NodeTy *Head;
320 NodeTy *getTail() {
return this->ensureHead(Head); }
321 const NodeTy *getTail()
const {
return this->ensureHead(Head); }
322 void setTail(NodeTy *
N)
const { this->noteHead(Head, N); }
326 void CreateLazySentinel()
const {
327 this->ensureHead(Head);
330 static bool op_less(NodeTy &L, NodeTy &R) {
return L < R; }
331 static bool op_equal(NodeTy &L, NodeTy &R) {
return L == R; }
336 void operator=(const
iplist &) LLVM_DELETED_FUNCTION;
351 iplist() : Head(this->provideInitialHead()) {}
355 Traits::destroySentinel(getTail());
360 CreateLazySentinel();
364 CreateLazySentinel();
368 CreateLazySentinel();
372 CreateLazySentinel();
386 return Head == 0 || Head == getTail();
391 assert(!
empty() &&
"Called front() on empty list!");
395 assert(!
empty() &&
"Called front() on empty list!");
399 assert(!
empty() &&
"Called back() on empty list!");
400 return *this->getPrev(getTail());
403 assert(!
empty() &&
"Called back() on empty list!");
404 return *this->getPrev(getTail());
408 assert(0 &&
"Swap does not use list traits callback correctly yet!");
414 NodeTy *PrevNode = this->getPrev(CurNode);
415 this->setNext(New, CurNode);
416 this->setPrev(New, PrevNode);
419 this->setNext(PrevNode, New);
422 this->setPrev(CurNode, New);
424 this->addNodeToList(New);
432 return insert(++where, New);
436 assert(
IT !=
end() &&
"Cannot remove end of list!");
438 NodeTy *NextNode = this->getNext(Node);
439 NodeTy *PrevNode = this->getPrev(Node);
442 this->setNext(PrevNode, NextNode);
445 this->setPrev(NextNode, PrevNode);
447 this->removeNodeFromList(Node);
454 this->setNext(Node, 0);
455 this->setPrev(Node, 0);
461 return remove(MutIt);
466 this->deleteNode(
remove(where));
478 this->setPrev(Head, Head);
487 assert(first != last &&
"Should be checked by callers");
490 assert(position != first &&
491 "Insertion point can't be one of the transferred nodes");
493 if (position != last) {
496 NodeTy *ThisSentinel = getTail();
498 NodeTy *L2Sentinel = L2.getTail();
502 NodeTy *First = &*first, *Prev = this->getPrev(First);
503 NodeTy *Next = last.getNodePtrUnchecked(), *Last = this->getPrev(Next);
505 this->setNext(Prev, Next);
508 this->setPrev(Next, Prev);
511 NodeTy *PosNext = position.getNodePtrUnchecked();
512 NodeTy *PosPrev = this->getPrev(PosNext);
516 this->setNext(PosPrev, First);
519 this->setPrev(First, PosPrev);
522 this->setNext(Last, PosNext);
523 this->setPrev(PosNext, Last);
525 this->transferNodesFromList(L2, First, PosNext);
528 L2.setTail(L2Sentinel);
529 setTail(ThisSentinel);
540 if (Head == 0)
return 0;
541 return std::distance(
begin(),
end());
545 while (first != last)
546 first =
erase(first);
556 assert(!
empty() &&
"pop_front() on empty list!");
560 assert(!
empty() &&
"pop_back() on empty list!");
566 for (; first != last; ++first)
insert(where, *first);
572 transfer(where, L2, L2.begin(), L2.end());
576 if (where == first || where == last)
return;
577 transfer(where, L2, first, last);
580 if (first != last) transfer(where, L2, first, last);
607 template<
class Pr2>
void unique(Pr2 pred) {
621 iterator first2 = right.begin(), last2 = right.end();
622 while (first1 != last1 && first2 != last2)
623 if (pred(*first2, *first1)) {
625 transfer(first1, right, first2, ++next);
630 if (first2 != last2) transfer(last1, right, first2, last2);
634 template<
class Pr3>
void sort(Pr3 pred);
639 template<
typename NodeTy>
654 template<
class InIt>
ilist(InIt first, InIt last) {
665 return insert(where, this->createNode(val));
674 for (; count != 0; --count)
insert(where, val);
680 for (; I != this->
end() && count != 0; ++
I, --count)
687 template<
class InIt>
void assign(InIt first1, InIt last1) {
689 for ( ; first1 != last1 && first2 != last2; ++first1, ++first2)
692 erase(first1, last1);
694 insert(last1, first2, last2);
702 for ( ; i != this->
end() && len < newsize; ++i, ++len) ;
722 #endif // LLVM_ADT_ILIST_H
static void setNext(NodeTy *N, NodeTy *Next)
static NodeTy * ensureHead(NodeTy *&Head)
const_reference front() const
void operator-(int, ilist_iterator< T >) LLVM_DELETED_FUNCTION
void splice(iterator where, iplist &L2, iterator first)
ilist_iterator< const NodeTy > const_iterator
std::iterator< std::bidirectional_iterator_tag, NodeTy, ptrdiff_t > super
void transferNodesFromList(ilist_node_traits &, ilist_iterator< NodeTy >, ilist_iterator< NodeTy >)
#define LLVM_ATTRIBUTE_UNUSED_RESULT
LLVM Argument representation.
void removeNodeFromList(NodeTy *)
ilist_iterator & operator++()
iplist< NodeTy >::iterator iterator
static NodeTy * createNode(const NodeTy &V)
const_iterator begin() const
void assign(InIt first1, InIt last1)
void insert(iterator where, InIt first, InIt last)
const_reverse_iterator rend() const
ilist_iterator & operator--()
ilist_iterator< NodeTy > iterator
iplist< NodeTy >::size_type size_type
ilist_iterator(pointer NP)
static SimpleType getSimplifiedValue(ilist_iterator< NodeTy > &Node)
reverse_iterator rbegin()
static void setPrev(NodeTy *N, NodeTy *Prev)
void push_back(NodeTy *val)
static cl::opt< ITMode > IT(cl::desc("IT block support"), cl::Hidden, cl::init(DefaultIT), cl::ZeroOrMore, cl::values(clEnumValN(DefaultIT,"arm-default-it","Generate IT block based on arch"), clEnumValN(RestrictedIT,"arm-restrict-it","Disallow deprecated IT based on ARMv8"), clEnumValN(NoRestrictedIT,"arm-no-restrict-it","Allow IT blocks based on ARMv7"), clEnumValEnd))
ilist(size_type count, const NodeTy &val)
static void destroySentinel(NodeTy *N)
destroySentinel - deallocate the dynamic sentinel
void push_front(const NodeTy &val)
iterator erase(iterator first, iterator last)
static NodeTy * getNext(NodeTy *N)
ilist_iterator operator++(int)
static NodeTy * provideInitialHead()
const_iterator end() const
static const NodeTy * getNext(const NodeTy *N)
static void noteHead(NodeTy *NewHead, NodeTy *Sentinel)
noteHead - stash the sentinel into its default location
ilist(const ilist &right)
ilist(InIt first, InIt last)
static NodeTy * getPrev(NodeTy *N)
ilist_iterator(reference NR)
void resize(size_type newsize)
void merge(iplist &right)
size_type LLVM_ATTRIBUTE_UNUSED_RESULT size() const
bool operator==(const ilist_iterator &RHS) const
ilist_iterator(const ilist_iterator< node_ty > &RHS)
iterator insertAfter(iterator where, NodeTy *New)
iterator insert(iterator where, const NodeTy &val)
ItTy next(ItTy it, Dist n)
iterator insert(iterator where, NodeTy *New)
super::reference reference
iterator erase(iterator where)
pointer operator->() const
super::value_type value_type
super::difference_type difference_type
ptrdiff_t difference_type
void assign(size_type count, const NodeTy &val)
void push_front(NodeTy *val)
bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const
std::reverse_iterator< iterator > reverse_iterator
static const NodeTy * getPrev(const NodeTy *N)
void splice(iterator where, iplist &L2)
#define LLVM_DELETED_FUNCTION
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
pointer getNodePtrUnchecked() const
static void deleteNode(NodeTy *V)
bool operator!=(const ilist_iterator &RHS) const
bool operator!=(uint64_t V1, const APInt &V2)
const_reverse_iterator rbegin() const
void addNodeToList(NodeTy *)
void merge(iplist &right, Pr3 pred)
size_type max_size() const
void clearAndLeakNodesUnsafely()
void splice(iterator where, iplist &L2, iterator first, iterator last)
void insert(iterator where, size_type count, const NodeTy &val)
const_reference back() const
static NodeTy * createSentinel()
createSentinel - create the dynamic sentinel
reference operator*() const
void resize(size_type newsize, NodeTy val)
std::reverse_iterator< const_iterator > const_reverse_iterator
void erase(const NodeTy &val)
static SimpleType getSimplifiedValue(const ilist_iterator< NodeTy > &Node)
ilist_iterator operator--(int)
bool operator==(uint64_t V1, const APInt &V2)
void push_back(const NodeTy &val)
const ilist_iterator & operator=(const ilist_iterator< node_ty > &RHS)
ilist_traits< NodeTy > Traits