summaryrefslogtreecommitdiffstats
path: root/llvm/unittests/ADT/ilistTest.cpp
Commit message (Collapse)AuthorAgeFilesLines
* ADT: Avoid relying on UB in ilist_node::getNextNode()Duncan P. N. Exon Smith2015-11-111-6/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Re-implement `ilist_node::getNextNode()` and `getPrevNode()` without relying on the sentinel having a "next" pointer. Instead, get access to the owning list and compare against the `begin()` and `end()` iterators. This only works when the node *can* get access to the owning list. The new support is in `ilist_node_with_parent<>`, and any class `Ty` inheriting from `ilist_node<NodeTy>` that wants `getNextNode()` and/or `getPrevNode()` should inherit from `ilist_node_with_parent<NodeTy, ParentTy>` instead. The requirements: - `NodeTy` must have a `getParent()` function that returns the parent. - `ParentTy` must have a `getSublistAccess()` static that, given a(n ignored) `NodeTy*` (to determine which list), returns a member field pointer to the appropriate `ilist<>`. This isn't the cleanest way to get access to the owning list, but it leverages the API already used in the IR hierarchy (see, e.g., `Instruction::getSublistAccess()`). If anyone feels like ripping out the calls to `getNextNode()` and `getPrevNode()` and replacing with direct iterator logic, they can also remove the access function, etc., but as an incremental step, I'm maintaining the API where it's currently used in tree. If these requirements are *not* met, call sites with access to the ilist can call `iplist<NodeTy>::getNextNode(NodeTy*)` directly, as in ilistTest.cpp. Why rewrite this? The old code was broken, calling `getNext()` on a sentinel that possibly didn't have a "next" pointer at all! The new code avoids that particular flavour of UB (see the commit message for r252538 for more details about the "lucky" memory layout that made this function so interesting). There's still some UB here: the end iterator gets downcast to `NodeTy*`, even when it's a sentinel (which is typically `ilist_half_node<NodeTy*>`). I'll tackle that in follow-up commits. See this llvm-dev thread for more details: http://lists.llvm.org/pipermail/llvm-dev/2015-October/091115.html What's the danger? There might be some code that relies on `getNextNode()` or `getPrevNode()` *never* returning `nullptr` -- i.e., that relies on them being broken when the sentinel is an `ilist_half_node<NodeTy>`. I tried to root out those cases with the audits I did leading up to r252380, but it's possible I missed one or two. I hope not. (If (1) you have out-of-tree code, (2) you've reverted r252380 temporarily, and (3) you get some weird crashes with this commit, then I recommend un-reverting r252380 and auditing the compile errors looking for "strange" implicit conversions.) llvm-svn: 252694
* unittests: Remove implicit ilist iterator conversions, NFCDuncan P. N. Exon Smith2015-10-201-1/+1
| | | | llvm-svn: 250843
* Explicitly default ilistTest::Node's copy constructorDavid Blaikie2015-03-041-1/+2
| | | | | | | In the presence of a user-declared dtor, calling an implicit copy ctor is deprecated in C++11. llvm-svn: 231256
* Revert "Remove the explicit SDNodeIterator::operator= in favor of the ↵David Blaikie2015-03-031-3/+1
| | | | | | | | | | | implicit default" Accidentally committed a few more of these cleanup changes than intended. Still breaking these out & tidying them up. This reverts commit r231135. llvm-svn: 231136
* Remove the explicit SDNodeIterator::operator= in favor of the implicit defaultDavid Blaikie2015-03-031-1/+3
| | | | | | | | | | There doesn't seem to be any need to assert that iterator assignment is between iterators over the same node - if you want to reuse an iterator variable to iterate another node, that's perfectly acceptable. Just don't mix comparisons between iterators into disjoint sequences, as usual. llvm-svn: 231135
* [C++11] Use 'nullptr'.Craig Topper2014-06-081-2/+2
| | | | llvm-svn: 210442
* [C++11] Replace llvm::next and llvm::prior with std::next and std::prev.Benjamin Kramer2014-03-021-3/+3
| | | | | | Remove the old functions. llvm-svn: 202636
* Add an iplist::clearAndLeakNodesUnsafely() function.Jakob Stoklund Olesen2013-01-041-0/+33
| | | | | | | | | | | | The iplist::clear() function can be quite expensive because it traverses the entire list, calling deleteNode() and removeNodeFromList() on each element. If node destruction and deallocation can be handled some other way, clearAndLeakNodesUnsafely() can be used to jettison all nodes without bringing them into cache. The function name is meant to be ominous. llvm-svn: 171540
* Sort a few more #include lines in tools/... unittests/... and utils/...Chandler Carruth2013-01-021-1/+1
| | | | llvm-svn: 171363
* Add an assertion for a likely ilist::splice() contract violation.Jakob Stoklund Olesen2012-12-181-0/+21
| | | | | | | | | | | | | | | | | | | | | | | The single-element ilist::splice() function supports a noop move: List.splice(I, List, I); The corresponding std::list function doesn't allow that, so add a unit test to document that behavior. This also means that List.splice(I, List, F); is somewhat surprisingly not equivalent to List.splice(I, List, F, next(F)); This patch adds an assertion to catch the illegal case I == F above. Alternatively, we could make I == F a legal noop, but that would make ilist differ even more from std::list. llvm-svn: 170443
* Sort the #include lines for unittest/...Chandler Carruth2012-12-041-2/+2
| | | | llvm-svn: 169250
* Fix const ilist_node::get{Prev,Next}Node() to actually compile. Picky, picky.Daniel Dunbar2010-05-131-0/+5
| | | | llvm-svn: 103723
* ADT: Add ilist_node::get{Prev,Next}Node, which return the adjacent node or null.Daniel Dunbar2010-05-121-0/+39
- This provides a convenient alternative to using something llvm::prior or manual iterator access, for example:: if (T *Prev = foo->getPrevNode()) ... instead of:: iterator it(foo); if (it != begin()) { --it; ... } - Chris, please review. llvm-svn: 103647
OpenPOWER on IntegriCloud