ADT: Split out simple_ilist, a simple intrusive list

Split out a new, low-level intrusive list type with clear semantics.
Unlike iplist (and ilist), all operations on simple_ilist are intrusive,
and simple_ilist never takes ownership of its nodes.  This enables an
intuitive API that has the right defaults for intrusive lists.
- insert() takes references (not pointers!) to nodes (in iplist/ilist,
  passing a reference will cause the node to be copied).
- erase() takes only iterators (like std::list), and does not destroy
  the nodes.
- remove() takes only references and has the same behaviour as erase().
- clear() does not destroy the nodes.
- The destructor does not destroy the nodes.
- New API {erase,remove,clear}AndDispose() take an extra Disposer
  functor for callsites that want to call some disposal routine (e.g.,
  std::default_delete).

This list is not currently configurable, and has no callbacks.

The initial motivation was to fix iplist<>::sort to work correctly (even
with callbacks in ilist_traits<>).  iplist<> uses simple_ilist<>::sort
directly.  The new test in unittests/IR/ModuleTest.cpp crashes without
this commit.

Fixing sort() via a low-level layer provided a good opportunity to:
- Unit test the low-level functionality thoroughly.
- Modernize the API, largely inspired by other intrusive list
  implementations.

Here's a sketch of a longer-term plan:
- Create BumpPtrList<>, a non-intrusive list implemented using
  simple_ilist<>, and use it for the Token list in
  lib/Support/YAMLParser.cpp.  This will factor out the only real use of
  createNode().
- Evolve the iplist<> and ilist<> APIs in the direction of
  simple_ilist<>, making allocation/deallocation explicit at call sites
  (similar to simple_ilist<>::eraseAndDispose()).
- Factor out remaining calls to createNode() and deleteNode() and remove
  the customization from ilist_traits<>.
- Transition uses of iplist<>/ilist<> that don't need callbacks over to
  simple_ilist<>.

llvm-svn: 280107

1 files changed, 23 insertions, 38 deletions

diff --git a/llvm/unittests/ADT/IListIteratorTest.cpp b/llvm/unittests/ADT/IListIteratorTest.cpp
index 1a87a270a67..ddcab781b9b 100644
--- a/llvm/unittests/ADT/IListIteratorTest.cpp
+++ b/llvm/unittests/ADT/IListIteratorTest.cpp
@@ -7,7 +7,7 @@
 //
 //===----------------------------------------------------------------------===//
 
-#include "llvm/ADT/ilist.h"
+#include "llvm/ADT/simple_ilist.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
@@ -17,10 +17,10 @@ namespace {
 struct Node : ilist_node<Node> {};
 
 TEST(IListIteratorTest, DefaultConstructor) {
-  iplist<Node>::iterator I;
-  iplist<Node>::reverse_iterator RI;
-  iplist<Node>::const_iterator CI;
-  iplist<Node>::const_reverse_iterator CRI;
+  simple_ilist<Node>::iterator I;
+  simple_ilist<Node>::reverse_iterator RI;
+  simple_ilist<Node>::const_iterator CI;
+  simple_ilist<Node>::const_reverse_iterator CRI;
   EXPECT_EQ(nullptr, I.getNodePtr());
   EXPECT_EQ(nullptr, CI.getNodePtr());
   EXPECT_EQ(nullptr, RI.getNodePtr());
@@ -38,7 +38,7 @@ TEST(IListIteratorTest, DefaultConstructor) {
 }
 
 TEST(IListIteratorTest, Empty) {
-  iplist<Node> L;
+  simple_ilist<Node> L;
 
   // Check iterators of L.
   EXPECT_EQ(L.begin(), L.end());
@@ -49,21 +49,18 @@ TEST(IListIteratorTest, Empty) {
   EXPECT_EQ(L.rend(), L.end().getReverse());
 
   // Iterators shouldn't match default constructors.
-  iplist<Node>::iterator I;
-  iplist<Node>::reverse_iterator RI;
+  simple_ilist<Node>::iterator I;
+  simple_ilist<Node>::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<Node> L;
+  simple_ilist<Node> L;
   Node A;
-  L.insert(L.end(), &A);
+  L.insert(L.end(), A);
 
   // Check address of reference.
   EXPECT_EQ(&A, &*L.begin());
@@ -81,16 +78,13 @@ TEST(IListIteratorTest, OneNodeList) {
   // 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<Node> L;
+  simple_ilist<Node> L;
   Node A, B;
-  L.insert(L.end(), &A);
-  L.insert(L.end(), &B);
+  L.insert(L.end(), A);
+  L.insert(L.end(), B);
 
   // Check order.
   EXPECT_EQ(&A, &*L.begin());
@@ -105,45 +99,36 @@ TEST(IListIteratorTest, TwoNodeList) {
   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<Node> L;
+  simple_ilist<Node> L;
   Node A, B;
-  L.insert(L.end(), &A);
-  L.insert(L.end(), &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++));
+  L.remove(*I++);
   EXPECT_EQ(&B, &*I);
-  EXPECT_EQ(&B, L.remove(I++));
+  L.remove(*I++);
   EXPECT_EQ(L.end(), I);
-
-  // Don't delete nodes.
-  L.clearAndLeakNodesUnsafely();
 }
 
 TEST(IListIteratorTest, CheckEraseReverse) {
-  iplist<Node> L;
+  simple_ilist<Node> L;
   Node A, B;
-  L.insert(L.end(), &A);
-  L.insert(L.end(), &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++));
+  L.remove(*RI++);
   EXPECT_EQ(&A, &*RI);
-  EXPECT_EQ(&A, L.remove(&*RI++));
+  L.remove(*RI++);
   EXPECT_EQ(L.rend(), RI);
-
-  // Don't delete nodes.
-  L.clearAndLeakNodesUnsafely();
 }
 
 } // end namespace