ADT: Separate some list manipulation API into ilist_base, NFC

Separate algorithms in iplist<T> that don't depend on T into ilist_base,
and unit test them.

While I was adding unit tests for these algorithms anyway, I also added
unit tests for ilist_node_base and ilist_sentinel<T>.

To make the algorithms and unit tests easier to write, I also did the
following minor changes as a drive-by:
- encapsulate Prev/Next in ilist_node_base to so that algorithms are
  easier to read, and
- update ilist_node_access API to take nodes by reference.

There should be no real functionality change here.

llvm-svn: 279484

4 files changed, 202 insertions, 0 deletions

diff --git a/llvm/unittests/ADT/CMakeLists.txt b/llvm/unittests/ADT/CMakeLists.txt
index 881d197a008..485c0e8690d 100644
--- a/llvm/unittests/ADT/CMakeLists.txt
+++ b/llvm/unittests/ADT/CMakeLists.txt
@@ -18,6 +18,9 @@ set(ADTSources
   FunctionRefTest.cpp
   HashingTest.cpp
   ilistTest.cpp
+  IListBaseTest.cpp
+  IListNodeBaseTest.cpp
+  IListSentinelTest.cpp
   ImmutableMapTest.cpp
   ImmutableSetTest.cpp
   IntEqClassesTest.cpp
diff --git a/llvm/unittests/ADT/IListBaseTest.cpp b/llvm/unittests/ADT/IListBaseTest.cpp
new file mode 100644
index 00000000000..1cb8fff5561
--- /dev/null
+++ b/llvm/unittests/ADT/IListBaseTest.cpp
@@ -0,0 +1,102 @@
+//===- unittests/ADT/IListBaseTest.cpp - ilist_base 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 {
+
+TEST(IListBaseTest, insertBeforeImpl) {
+  ilist_node_base S, A, B;
+  // [S] <-> [S]
+  S.setPrev(&S);
+  S.setNext(&S);
+
+  // [S] <-> A <-> [S]
+  ilist_base::insertBeforeImpl(S, A);
+  EXPECT_EQ(&A, S.getPrev());
+  EXPECT_EQ(&S, A.getPrev());
+  EXPECT_EQ(&A, S.getNext());
+  EXPECT_EQ(&S, A.getNext());
+
+  // [S] <-> A <-> B <-> [S]
+  ilist_base::insertBeforeImpl(S, B);
+  EXPECT_EQ(&B, S.getPrev());
+  EXPECT_EQ(&A, B.getPrev());
+  EXPECT_EQ(&S, A.getPrev());
+  EXPECT_EQ(&A, S.getNext());
+  EXPECT_EQ(&B, A.getNext());
+  EXPECT_EQ(&S, B.getNext());
+}
+
+TEST(IListBaseTest, removeImpl) {
+  ilist_node_base S, A, B;
+
+  // [S] <-> A <-> B <-> [S]
+  S.setPrev(&S);
+  S.setNext(&S);
+  ilist_base::insertBeforeImpl(S, A);
+  ilist_base::insertBeforeImpl(S, B);
+
+  // [S] <-> B <-> [S]
+  ilist_base::removeImpl(A);
+  EXPECT_EQ(&B, S.getPrev());
+  EXPECT_EQ(&S, B.getPrev());
+  EXPECT_EQ(&B, S.getNext());
+  EXPECT_EQ(&S, B.getNext());
+  EXPECT_EQ(nullptr, A.getPrev());
+  EXPECT_EQ(nullptr, A.getNext());
+
+  // [S] <-> [S]
+  ilist_base::removeImpl(B);
+  EXPECT_EQ(&S, S.getPrev());
+  EXPECT_EQ(&S, S.getNext());
+  EXPECT_EQ(nullptr, B.getPrev());
+  EXPECT_EQ(nullptr, B.getNext());
+}
+
+TEST(IListBaseTest, transferBeforeImpl) {
+  ilist_node_base S1, S2, A, B, C, D, E;
+
+  // [S1] <-> A <-> B <-> C <-> [S1]
+  S1.setPrev(&S1);
+  S1.setNext(&S1);
+  ilist_base::insertBeforeImpl(S1, A);
+  ilist_base::insertBeforeImpl(S1, B);
+  ilist_base::insertBeforeImpl(S1, C);
+
+  // [S2] <-> D <-> E <-> [S2]
+  S2.setPrev(&S2);
+  S2.setNext(&S2);
+  ilist_base::insertBeforeImpl(S2, D);
+  ilist_base::insertBeforeImpl(S2, E);
+
+  // [S1] <-> C <-> [S1]
+  ilist_base::transferBeforeImpl(D, A, C);
+  EXPECT_EQ(&C, S1.getPrev());
+  EXPECT_EQ(&S1, C.getPrev());
+  EXPECT_EQ(&C, S1.getNext());
+  EXPECT_EQ(&S1, C.getNext());
+
+  // [S2] <-> A <-> B <-> D <-> E <-> [S2]
+  EXPECT_EQ(&E, S2.getPrev());
+  EXPECT_EQ(&D, E.getPrev());
+  EXPECT_EQ(&B, D.getPrev());
+  EXPECT_EQ(&A, B.getPrev());
+  EXPECT_EQ(&S2, A.getPrev());
+  EXPECT_EQ(&A, S2.getNext());
+  EXPECT_EQ(&B, A.getNext());
+  EXPECT_EQ(&D, B.getNext());
+  EXPECT_EQ(&E, D.getNext());
+  EXPECT_EQ(&S2, E.getNext());
+}
+
+} // end namespace
diff --git a/llvm/unittests/ADT/IListNodeBaseTest.cpp b/llvm/unittests/ADT/IListNodeBaseTest.cpp
new file mode 100644
index 00000000000..1e9c2a1fa04
--- /dev/null
+++ b/llvm/unittests/ADT/IListNodeBaseTest.cpp
@@ -0,0 +1,60 @@
+//===- unittests/ADT/IListNodeBaseTest.cpp - ilist_node_base 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_node.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+namespace {
+
+TEST(IListNodeBaseTest, DefaultConstructor) {
+  ilist_node_base A;
+  EXPECT_EQ(nullptr, A.getPrev());
+  EXPECT_EQ(nullptr, A.getNext());
+  EXPECT_FALSE(A.isKnownSentinel());
+}
+
+TEST(IListNodeBaseTest, setPrevAndNext) {
+  ilist_node_base A, B, C;
+  A.setPrev(&B);
+  EXPECT_EQ(&B, A.getPrev());
+  EXPECT_EQ(nullptr, A.getNext());
+  EXPECT_EQ(nullptr, B.getPrev());
+  EXPECT_EQ(nullptr, B.getNext());
+  EXPECT_EQ(nullptr, C.getPrev());
+  EXPECT_EQ(nullptr, C.getNext());
+
+  A.setNext(&C);
+  EXPECT_EQ(&B, A.getPrev());
+  EXPECT_EQ(&C, A.getNext());
+  EXPECT_EQ(nullptr, B.getPrev());
+  EXPECT_EQ(nullptr, B.getNext());
+  EXPECT_EQ(nullptr, C.getPrev());
+  EXPECT_EQ(nullptr, C.getNext());
+}
+
+TEST(IListNodeBaseTest, isKnownSentinel) {
+  ilist_node_base A, B;
+  EXPECT_FALSE(A.isKnownSentinel());
+  A.setPrev(&B);
+  A.setNext(&B);
+  EXPECT_EQ(&B, A.getPrev());
+  EXPECT_EQ(&B, A.getNext());
+  A.initializeSentinel();
+#ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
+  EXPECT_TRUE(A.isKnownSentinel());
+#else
+  EXPECT_FALSE(A.isKnownSentinel());
+#endif
+  EXPECT_EQ(&B, A.getPrev());
+  EXPECT_EQ(&B, A.getNext());
+}
+
+} // end namespace
diff --git a/llvm/unittests/ADT/IListSentinelTest.cpp b/llvm/unittests/ADT/IListSentinelTest.cpp
new file mode 100644
index 00000000000..533421e8504
--- /dev/null
+++ b/llvm/unittests/ADT/IListSentinelTest.cpp
@@ -0,0 +1,37 @@
+//===- unittests/ADT/IListSentinelTest.cpp - ilist_sentinel 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 {
+
+class Node : public ilist_node<Node> {};
+
+TEST(IListSentinelTest, DefaultConstructor) {
+  ilist_sentinel<Node> S;
+  EXPECT_EQ(&S, ilist_node_access::getPrev(S));
+  EXPECT_EQ(&S, ilist_node_access::getNext(S));
+#ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
+  EXPECT_TRUE(S.isKnownSentinel());
+#else
+  EXPECT_FALSE(S.isKnownSentinel());
+#endif
+}
+
+TEST(IListSentinelTest, NormalNodeIsNotKnownSentinel) {
+  Node N;
+  EXPECT_EQ(nullptr, ilist_node_access::getPrev(N));
+  EXPECT_EQ(nullptr, ilist_node_access::getNext(N));
+  EXPECT_FALSE(N.isKnownSentinel());
+}
+
+} // end namespace