From 5c001c367f75c39f105ac5be3eeffa7921a820ca Mon Sep 17 00:00:00 2001 From: "Duncan P. N. Exon Smith" Date: Tue, 30 Aug 2016 00:13:12 +0000 Subject: [PATCH] ADT: Give ilist::reverse_iterator a handle to the current node Reverse iterators to doubly-linked lists can be simpler (and cheaper) than std::reverse_iterator. Make it so. In particular, change ilist::reverse_iterator so that it is *never* invalidated unless the node it references is deleted. This matches the guarantees of ilist::iterator. (Note: MachineBasicBlock::iterator is *not* an ilist iterator, but a MachineInstrBundleIterator. This commit does not change MachineBasicBlock::reverse_iterator, but it does update MachineBasicBlock::reverse_instr_iterator. See note at end of commit message for details on bundle iterators.) Given the list (with the Sentinel showing twice for simplicity): [Sentinel] <-> A <-> B <-> [Sentinel] the following is now true: 1. begin() represents A. 2. begin() holds the pointer for A. 3. end() represents [Sentinel]. 4. end() holds the poitner for [Sentinel]. 5. rbegin() represents B. 6. rbegin() holds the pointer for B. 7. rend() represents [Sentinel]. 8. rend() holds the pointer for [Sentinel]. The changes are #6 and #8. Here are some properties from the old scheme (which used std::reverse_iterator): - rbegin() held the pointer for [Sentinel] and rend() held the pointer for A; - operator*() cost two dereferences instead of one; - converting from a valid iterator to its valid reverse_iterator involved a confusing increment; and - "RI++->erase()" left RI invalid. The unintuitive replacement was "RI->erase(), RE = end()". With vector-like data structures these properties are hard to avoid (since past-the-beginning is not a valid pointer), and don't impose a real cost (since there's still only one dereference, and all iterators are invalidated on erase). But with lists, this was a poor design. Specifically, the following code (which obviously works with normal iterators) now works with ilist::reverse_iterator as well: for (auto RI = L.rbegin(), RE = L.rend(); RI != RE;) fooThatMightRemoveArgFromList(*RI++); Converting between iterator and reverse_iterator for the same node uses the getReverse() function. reverse_iterator iterator::getReverse(); iterator reverse_iterator::getReverse(); Why doesn't iterator <=> reverse_iterator conversion use constructors? In order to catch and update old code, reverse_iterator does not even have an explicit conversion from iterator. It wouldn't be safe because there would be no reasonable way to catch all the bugs from the changed semantic (see the changes at call sites that are part of this patch). Old code used this API: std::reverse_iterator::reverse_iterator(iterator); iterator std::reverse_iterator::base(); Here's how to update from old code to new (that incorporates the semantic change), assuming I is an ilist<>::iterator and RI is an ilist<>::reverse_iterator: [Old] ==> [New] reverse_iterator(I) (--I).getReverse() reverse_iterator(I) ++I.getReverse() --reverse_iterator(I) I.getReverse() reverse_iterator(++I) I.getReverse() RI.base() (--RI).getReverse() RI.base() ++RI.getReverse() --RI.base() RI.getReverse() (++RI).base() RI.getReverse() delete &*RI, RE = end() delete &*RI++ RI->erase(), RE = end() RI++->erase() ======================================= Note: bundle iterators are out of scope ======================================= MachineBasicBlock::iterator, also known as MachineInstrBundleIterator, is a wrapper to represent MachineInstr bundles. The idea is that each operator++ takes you to the beginning of the next bundle. Implementing a sane reverse iterator for this is harder than ilist. Here are the options: - Use std::reverse_iterator. Store a handle to the beginning of the next bundle. A call to operator*() runs a loop (usually operator--() will be called 1 time, for unbundled instructions). Increment/decrement just works. This is the status quo. - Store a handle to the final node in the bundle. A call to operator*() still runs a loop, but it iterates one time fewer (usually operator--() will be called 0 times, for unbundled instructions). Increment/decrement just works. - Make the ilist_sentinel *always* store that it's the sentinel (instead of just in asserts mode). Then the bundle iterator can sniff the sentinel bit in operator++(). I initially tried implementing the end() option as part of this commit, but updating iterator/reverse_iterator conversion call sites was error-prone. I have a WIP series of patches that implements the final option. llvm-svn: 280032 --- llvm/include/llvm/ADT/ilist.h | 55 ++++++-- llvm/include/llvm/ADT/ilist_node.h | 5 +- llvm/include/llvm/CodeGen/MachineBasicBlock.h | 17 ++- llvm/include/llvm/CodeGen/MachineFunction.h | 4 +- llvm/include/llvm/IR/SymbolTableListTraits.h | 12 +- llvm/lib/CodeGen/MachinePipeliner.cpp | 3 +- llvm/lib/Target/Lanai/LanaiDelaySlotFiller.cpp | 11 +- llvm/lib/Target/X86/X86FixupSetCC.cpp | 3 +- llvm/lib/Transforms/Scalar/LoopRerollPass.cpp | 9 +- .../Transforms/Scalar/RewriteStatepointsForGC.cpp | 4 +- llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp | 11 +- llvm/unittests/ADT/CMakeLists.txt | 1 + llvm/unittests/ADT/IListIteratorTest.cpp | 149 +++++++++++++++++++++ 13 files changed, 230 insertions(+), 54 deletions(-) create mode 100644 llvm/unittests/ADT/IListIteratorTest.cpp diff --git a/llvm/include/llvm/ADT/ilist.h b/llvm/include/llvm/ADT/ilist.h index 9ee5a283..1a8f67f 100644 --- a/llvm/include/llvm/ADT/ilist.h +++ b/llvm/include/llvm/ADT/ilist.h @@ -35,7 +35,7 @@ namespace llvm { template class iplist; -template class ilist_iterator; +template class ilist_iterator; /// An access class for ilist_node private API. /// @@ -146,12 +146,30 @@ template struct ConstCorrectNodeType { template struct ConstCorrectNodeType { typedef const ilist_node type; }; + +template struct IteratorHelper { + template static void increment(T *&I) { + I = ilist_node_access::getNext(*I); + } + template static void decrement(T *&I) { + I = ilist_node_access::getPrev(*I); + } +}; +template <> struct IteratorHelper { + template static void increment(T *&I) { + IteratorHelper::decrement(I); + } + template static void decrement(T *&I) { + IteratorHelper::increment(I); + } +}; + } // end namespace ilist_detail //===----------------------------------------------------------------------===// // Iterator for intrusive list. // -template +template class ilist_iterator : public std::iterator { public: @@ -185,7 +203,7 @@ public: // a nonconst iterator... template ilist_iterator( - const ilist_iterator &RHS, + const ilist_iterator &RHS, typename std::enable_if::value, void *>::type = nullptr) : NodePtr(RHS.getNodePtr()) {} @@ -193,11 +211,22 @@ public: // This is templated so that we can allow assigning to a const iterator from // a nonconst iterator... template - const ilist_iterator &operator=(const ilist_iterator &RHS) { + const ilist_iterator & + operator=(const ilist_iterator &RHS) { NodePtr = RHS.getNodePtr(); return *this; } + /// Convert from an iterator to its reverse. + /// + /// TODO: Roll this into the implicit constructor once we're sure that no one + /// is relying on the std::reverse_iterator off-by-one semantics. + ilist_iterator getReverse() const { + if (NodePtr) + return ilist_iterator(*NodePtr); + return ilist_iterator(); + } + void reset(pointer NP) { NodePtr = NP; } // Accessors... @@ -217,12 +246,11 @@ public: // Increment and decrement operators... ilist_iterator &operator--() { - NodePtr = ilist_node_access::getPrev(*NodePtr); - assert(NodePtr && "--'d off the beginning of an ilist!"); + ilist_detail::IteratorHelper::decrement(NodePtr); return *this; } ilist_iterator &operator++() { - NodePtr = ilist_node_access::getNext(*NodePtr); + ilist_detail::IteratorHelper::increment(NodePtr); return *this; } ilist_iterator operator--(int) { @@ -356,8 +384,8 @@ public: typedef ilist_iterator const_iterator; typedef size_t size_type; typedef ptrdiff_t difference_type; - typedef std::reverse_iterator const_reverse_iterator; - typedef std::reverse_iterator reverse_iterator; + typedef ilist_iterator const_reverse_iterator; + typedef ilist_iterator reverse_iterator; iplist() = default; ~iplist() { clear(); } @@ -369,11 +397,10 @@ public: const_iterator end() const { return const_iterator(Sentinel); } // 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());} - + reverse_iterator rbegin() { return ++reverse_iterator(Sentinel); } + const_reverse_iterator rbegin() const{ return ++const_reverse_iterator(Sentinel); } + reverse_iterator rend() { return reverse_iterator(Sentinel); } + const_reverse_iterator rend() const { return const_reverse_iterator(Sentinel); } // Miscellaneous inspection routines. size_type max_size() const { return size_type(-1); } diff --git a/llvm/include/llvm/ADT/ilist_node.h b/llvm/include/llvm/ADT/ilist_node.h index a817b4b..0e4bd97 100644 --- a/llvm/include/llvm/ADT/ilist_node.h +++ b/llvm/include/llvm/ADT/ilist_node.h @@ -51,7 +51,7 @@ public: }; struct ilist_node_access; -template class ilist_iterator; +template class ilist_iterator; template class ilist_sentinel; /// Templated wrapper class. @@ -59,7 +59,8 @@ template class ilist_node : ilist_node_base { friend class ilist_base; friend struct ilist_node_access; friend struct ilist_traits; - friend class ilist_iterator; + friend class ilist_iterator; + friend class ilist_iterator; friend class ilist_sentinel; protected: diff --git a/llvm/include/llvm/CodeGen/MachineBasicBlock.h b/llvm/include/llvm/CodeGen/MachineBasicBlock.h index 68a6ef3..60268b1 100644 --- a/llvm/include/llvm/CodeGen/MachineBasicBlock.h +++ b/llvm/include/llvm/CodeGen/MachineBasicBlock.h @@ -150,9 +150,8 @@ public: typedef Instructions::iterator instr_iterator; typedef Instructions::const_iterator const_instr_iterator; - typedef std::reverse_iterator reverse_instr_iterator; - typedef - std::reverse_iterator const_reverse_instr_iterator; + typedef Instructions::reverse_iterator reverse_instr_iterator; + typedef Instructions::const_reverse_iterator const_reverse_instr_iterator; typedef MachineInstrBundleIterator iterator; typedef MachineInstrBundleIterator const_iterator; @@ -193,10 +192,14 @@ public: const_iterator begin() const { return instr_begin(); } iterator end () { return instr_end(); } const_iterator end () const { return instr_end(); } - reverse_iterator rbegin() { return instr_rbegin(); } - const_reverse_iterator rbegin() const { return instr_rbegin(); } - reverse_iterator rend () { return instr_rend(); } - const_reverse_iterator rend () const { return instr_rend(); } + 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()); + } /// Support for MachineInstr::getNextNode(). static Instructions MachineBasicBlock::*getSublistAccess(MachineInstr *) { diff --git a/llvm/include/llvm/CodeGen/MachineFunction.h b/llvm/include/llvm/CodeGen/MachineFunction.h index e14614c..b6c1a08 100644 --- a/llvm/include/llvm/CodeGen/MachineFunction.h +++ b/llvm/include/llvm/CodeGen/MachineFunction.h @@ -445,8 +445,8 @@ public: // Provide accessors for the MachineBasicBlock list... typedef BasicBlockListType::iterator iterator; typedef BasicBlockListType::const_iterator const_iterator; - typedef std::reverse_iterator const_reverse_iterator; - typedef std::reverse_iterator reverse_iterator; + typedef BasicBlockListType::const_reverse_iterator const_reverse_iterator; + typedef BasicBlockListType::reverse_iterator reverse_iterator; /// Support for MachineBasicBlock::getNextNode(). static BasicBlockListType MachineFunction::* diff --git a/llvm/include/llvm/IR/SymbolTableListTraits.h b/llvm/include/llvm/IR/SymbolTableListTraits.h index f0f8ba3..87364aa 100644 --- a/llvm/include/llvm/IR/SymbolTableListTraits.h +++ b/llvm/include/llvm/IR/SymbolTableListTraits.h @@ -30,10 +30,6 @@ namespace llvm { class ValueSymbolTable; -template class ilist_iterator; -template class iplist; -template struct ilist_traits; - /// Template metafunction to get the parent type for a symbol table list. /// /// Implementations create a typedef called \c type so that we only need a @@ -66,6 +62,7 @@ template class SymbolTableList; template class SymbolTableListTraits : public ilist_node_traits { typedef SymbolTableList ListTy; + typedef ilist_iterator iterator; typedef typename SymbolTableListParentType::type ItemParentClass; @@ -94,10 +91,9 @@ private: public: void addNodeToList(ValueSubClass *V); void removeNodeFromList(ValueSubClass *V); - void transferNodesFromList(SymbolTableListTraits &L2, - ilist_iterator first, - ilist_iterator last); -//private: + void transferNodesFromList(SymbolTableListTraits &L2, iterator first, + iterator last); + // private: template void setSymTabObject(TPtr *, TPtr); static ValueSymbolTable *toPtr(ValueSymbolTable *P) { return P; } diff --git a/llvm/lib/CodeGen/MachinePipeliner.cpp b/llvm/lib/CodeGen/MachinePipeliner.cpp index 0eff6e6..9648fd8 100644 --- a/llvm/lib/CodeGen/MachinePipeliner.cpp +++ b/llvm/lib/CodeGen/MachinePipeliner.cpp @@ -2880,8 +2880,7 @@ void SwingSchedulerDAG::removeDeadInstructions(MachineBasicBlock *KernelBB, used = false; } if (!used) { - MI->eraseFromParent(); - ME = (*MBB)->instr_rend(); + MI++->eraseFromParent(); continue; } ++MI; diff --git a/llvm/lib/Target/Lanai/LanaiDelaySlotFiller.cpp b/llvm/lib/Target/Lanai/LanaiDelaySlotFiller.cpp index e0798bf..be94090 100644 --- a/llvm/lib/Target/Lanai/LanaiDelaySlotFiller.cpp +++ b/llvm/lib/Target/Lanai/LanaiDelaySlotFiller.cpp @@ -105,7 +105,7 @@ bool Filler::runOnMachineBasicBlock(MachineBasicBlock &MBB) { // RET is generated as part of epilogue generation and hence we know // what the two instructions preceding it are and that it is safe to // insert RET above them. - MachineBasicBlock::reverse_instr_iterator RI(I); + MachineBasicBlock::reverse_instr_iterator RI = ++I.getReverse(); assert(RI->getOpcode() == Lanai::LDW_RI && RI->getOperand(0).isReg() && RI->getOperand(0).getReg() == Lanai::FP && RI->getOperand(1).isReg() && @@ -117,8 +117,7 @@ bool Filler::runOnMachineBasicBlock(MachineBasicBlock &MBB) { RI->getOperand(0).getReg() == Lanai::SP && RI->getOperand(1).isReg() && RI->getOperand(1).getReg() == Lanai::FP); - ++RI; - MachineBasicBlock::instr_iterator FI(RI.base()); + MachineBasicBlock::instr_iterator FI = RI.getReverse(); MBB.splice(std::next(I), &MBB, FI, I); FilledSlots += 2; } else { @@ -154,14 +153,14 @@ bool Filler::findDelayInstr(MachineBasicBlock &MBB, bool SawLoad = false; bool SawStore = false; - for (MachineBasicBlock::reverse_instr_iterator I(Slot); I != MBB.instr_rend(); - ++I) { + for (MachineBasicBlock::reverse_instr_iterator I = ++Slot.getReverse(); + I != MBB.instr_rend(); ++I) { // skip debug value if (I->isDebugValue()) continue; // Convert to forward iterator. - MachineBasicBlock::instr_iterator FI(std::next(I).base()); + MachineBasicBlock::instr_iterator FI = I.getReverse(); if (I->hasUnmodeledSideEffects() || I->isInlineAsm() || I->isLabel() || FI == LastFiller || I->isPseudo()) diff --git a/llvm/lib/Target/X86/X86FixupSetCC.cpp b/llvm/lib/Target/X86/X86FixupSetCC.cpp index fb317da..cf3d431 100644 --- a/llvm/lib/Target/X86/X86FixupSetCC.cpp +++ b/llvm/lib/Target/X86/X86FixupSetCC.cpp @@ -99,7 +99,8 @@ bool X86FixupSetCCPass::isSetCCr(unsigned Opcode) { MachineInstr * X86FixupSetCCPass::findFlagsImpDef(MachineBasicBlock *MBB, MachineBasicBlock::reverse_iterator MI) { - auto MBBStart = MBB->instr_rend(); + // FIXME: Should this be instr_rend(), and MI be reverse_instr_iterator? + auto MBBStart = MBB->rend(); for (int i = 0; (i < SearchBound) && (MI != MBBStart); ++i, ++MI) for (auto &Op : MI->implicit_operands()) if ((Op.getReg() == X86::EFLAGS) && (Op.isDef())) diff --git a/llvm/lib/Transforms/Scalar/LoopRerollPass.cpp b/llvm/lib/Transforms/Scalar/LoopRerollPass.cpp index 4e9fdf8..6523674 100644 --- a/llvm/lib/Transforms/Scalar/LoopRerollPass.cpp +++ b/llvm/lib/Transforms/Scalar/LoopRerollPass.cpp @@ -1412,13 +1412,12 @@ bool LoopReroll::DAGRootTracker::validate(ReductionTracker &Reductions) { void LoopReroll::DAGRootTracker::replace(const SCEV *IterCount) { BasicBlock *Header = L->getHeader(); // Remove instructions associated with non-base iterations. - for (BasicBlock::reverse_iterator J = Header->rbegin(); - J != Header->rend();) { + for (BasicBlock::reverse_iterator J = Header->rbegin(), JE = Header->rend(); + J != JE;) { unsigned I = Uses[&*J].find_first(); if (I > 0 && I < IL_All) { - Instruction *D = &*J; - DEBUG(dbgs() << "LRR: removing: " << *D << "\n"); - D->eraseFromParent(); + DEBUG(dbgs() << "LRR: removing: " << *J << "\n"); + J++->eraseFromParent(); continue; } diff --git a/llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp b/llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp index 6726e0e..eafdb46 100644 --- a/llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp +++ b/llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp @@ -2578,8 +2578,8 @@ static void findLiveSetAtInst(Instruction *Inst, GCPtrLivenessData &Data, // call result is not live (normal), nor are it's arguments // (unless they're used again later). This adjustment is // specifically what we need to relocate - BasicBlock::reverse_iterator rend(Inst->getIterator()); - computeLiveInValues(BB->rbegin(), rend, LiveOut); + computeLiveInValues(BB->rbegin(), ++Inst->getIterator().getReverse(), + LiveOut); LiveOut.remove(Inst); Out.insert(LiveOut.begin(), LiveOut.end()); } diff --git a/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp b/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp index d9915d3..83e6509 100644 --- a/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp +++ b/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp @@ -1868,9 +1868,9 @@ int BoUpSLP::getSpillCost() { ); // Now find the sequence of instructions between PrevInst and Inst. - BasicBlock::reverse_iterator InstIt(Inst->getIterator()), - PrevInstIt(PrevInst->getIterator()); - --PrevInstIt; + BasicBlock::reverse_iterator InstIt = ++Inst->getIterator().getReverse(), + PrevInstIt = + PrevInst->getIterator().getReverse(); while (InstIt != PrevInstIt) { if (PrevInstIt == PrevInst->getParent()->rend()) { PrevInstIt = Inst->getParent()->rbegin(); @@ -3036,9 +3036,10 @@ bool BoUpSLP::BlockScheduling::extendSchedulingRegion(Value *V) { } // Search up and down at the same time, because we don't know if the new // instruction is above or below the existing scheduling region. - BasicBlock::reverse_iterator UpIter(ScheduleStart->getIterator()); + BasicBlock::reverse_iterator UpIter = + ++ScheduleStart->getIterator().getReverse(); BasicBlock::reverse_iterator UpperEnd = BB->rend(); - BasicBlock::iterator DownIter(ScheduleEnd); + BasicBlock::iterator DownIter = ScheduleEnd->getIterator(); BasicBlock::iterator LowerEnd = BB->end(); for (;;) { if (++ScheduleRegionSize > ScheduleRegionSizeLimit) { diff --git a/llvm/unittests/ADT/CMakeLists.txt b/llvm/unittests/ADT/CMakeLists.txt index ed008a3..4026a07 100644 --- a/llvm/unittests/ADT/CMakeLists.txt +++ b/llvm/unittests/ADT/CMakeLists.txt @@ -19,6 +19,7 @@ set(ADTSources HashingTest.cpp ilistTestTemp.cpp IListBaseTest.cpp + IListIteratorTest.cpp IListNodeBaseTest.cpp IListSentinelTest.cpp ImmutableMapTest.cpp diff --git a/llvm/unittests/ADT/IListIteratorTest.cpp b/llvm/unittests/ADT/IListIteratorTest.cpp new file mode 100644 index 0000000..1a87a27 --- /dev/null +++ b/llvm/unittests/ADT/IListIteratorTest.cpp @@ -0,0 +1,149 @@ +//===- unittests/ADT/IListIteratorTest.cpp - ilist_iterator unit tests ----===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "llvm/ADT/ilist.h" +#include "gtest/gtest.h" + +using namespace llvm; + +namespace { + +struct Node : ilist_node {}; + +TEST(IListIteratorTest, DefaultConstructor) { + iplist::iterator I; + iplist::reverse_iterator RI; + iplist::const_iterator CI; + iplist::const_reverse_iterator CRI; + EXPECT_EQ(nullptr, I.getNodePtr()); + EXPECT_EQ(nullptr, CI.getNodePtr()); + EXPECT_EQ(nullptr, RI.getNodePtr()); + EXPECT_EQ(nullptr, CRI.getNodePtr()); + EXPECT_EQ(I, I); + EXPECT_EQ(I, CI); + EXPECT_EQ(CI, I); + EXPECT_EQ(CI, CI); + EXPECT_EQ(RI, RI); + EXPECT_EQ(RI, CRI); + EXPECT_EQ(CRI, RI); + EXPECT_EQ(CRI, CRI); + EXPECT_EQ(I, RI.getReverse()); + EXPECT_EQ(RI, I.getReverse()); +} + +TEST(IListIteratorTest, Empty) { + iplist L; + + // Check iterators of L. + EXPECT_EQ(L.begin(), L.end()); + EXPECT_EQ(L.rbegin(), L.rend()); + + // Reverse of end should be rend (since the sentinel sits on both sides). + EXPECT_EQ(L.end(), L.rend().getReverse()); + EXPECT_EQ(L.rend(), L.end().getReverse()); + + // Iterators shouldn't match default constructors. + iplist::iterator I; + iplist::reverse_iterator RI; + EXPECT_NE(I, L.begin()); + EXPECT_NE(I, L.end()); + EXPECT_NE(RI, L.rbegin()); + EXPECT_NE(RI, L.rend()); + + // Don't delete nodes. + L.clearAndLeakNodesUnsafely(); +} + +TEST(IListIteratorTest, OneNodeList) { + iplist L; + Node A; + L.insert(L.end(), &A); + + // Check address of reference. + EXPECT_EQ(&A, &*L.begin()); + EXPECT_EQ(&A, &*L.rbegin()); + + // Check that the handle matches. + EXPECT_EQ(L.rbegin().getNodePtr(), L.begin().getNodePtr()); + + // Check iteration. + EXPECT_EQ(L.end(), ++L.begin()); + EXPECT_EQ(L.begin(), --L.end()); + EXPECT_EQ(L.rend(), ++L.rbegin()); + EXPECT_EQ(L.rbegin(), --L.rend()); + + // Check conversions. + EXPECT_EQ(L.rbegin(), L.begin().getReverse()); + EXPECT_EQ(L.begin(), L.rbegin().getReverse()); + + // Don't delete nodes. + L.clearAndLeakNodesUnsafely(); +} + +TEST(IListIteratorTest, TwoNodeList) { + iplist L; + Node A, B; + L.insert(L.end(), &A); + L.insert(L.end(), &B); + + // Check order. + EXPECT_EQ(&A, &*L.begin()); + EXPECT_EQ(&B, &*++L.begin()); + EXPECT_EQ(L.end(), ++++L.begin()); + EXPECT_EQ(&B, &*L.rbegin()); + EXPECT_EQ(&A, &*++L.rbegin()); + EXPECT_EQ(L.rend(), ++++L.rbegin()); + + // Check conversions. + EXPECT_EQ(++L.rbegin(), L.begin().getReverse()); + EXPECT_EQ(L.rbegin(), (++L.begin()).getReverse()); + EXPECT_EQ(++L.begin(), L.rbegin().getReverse()); + EXPECT_EQ(L.begin(), (++L.rbegin()).getReverse()); + + // Don't delete nodes. + L.clearAndLeakNodesUnsafely(); +} + +TEST(IListIteratorTest, CheckEraseForward) { + iplist L; + Node A, B; + L.insert(L.end(), &A); + L.insert(L.end(), &B); + + // Erase nodes. + auto I = L.begin(); + EXPECT_EQ(&A, &*I); + EXPECT_EQ(&A, L.remove(I++)); + EXPECT_EQ(&B, &*I); + EXPECT_EQ(&B, L.remove(I++)); + EXPECT_EQ(L.end(), I); + + // Don't delete nodes. + L.clearAndLeakNodesUnsafely(); +} + +TEST(IListIteratorTest, CheckEraseReverse) { + iplist L; + Node A, B; + L.insert(L.end(), &A); + L.insert(L.end(), &B); + + // Erase nodes. + auto RI = L.rbegin(); + EXPECT_EQ(&B, &*RI); + EXPECT_EQ(&B, L.remove(&*RI++)); + EXPECT_EQ(&A, &*RI); + EXPECT_EQ(&A, L.remove(&*RI++)); + EXPECT_EQ(L.rend(), RI); + + // Don't delete nodes. + L.clearAndLeakNodesUnsafely(); +} + +} // end namespace -- 2.7.4