ADT: Add sentinel tracking and custom tags to ilists
This adds two declarative configuration options for intrusive lists
(available for simple_ilist, iplist, and ilist). Both of these options
affect ilist_node interoperability and need to be passed both to the
node and the list. Instead of adding a new traits class, they're
specified as optional template parameters (in any order).
The two options:
1. Pass ilist_sentinel_tracking<true> or ilist_sentinel_tracking<false>
to control whether there's a bit on ilist_node "prev" pointer
indicating whether it's the sentinel. The default behaviour is to
use a bit if and only if LLVM_ENABLE_ABI_BREAKING_CHECKS.
2. Pass ilist_tag<TagA> and ilist_tag<TagB> to allow insertion of a
single node into two different lists (simultaneously).
I have an immediate use-case for (1) ilist_sentinel_tracking: fixing the
validation semantics of MachineBasicBlock::reverse_iterator to match
ilist::reverse_iterator (ala r280032: see the comments at the end of the
commit message there). I'm adding (2) ilist_tag in the same commit to
validate that the options framework supports expansion. Justin Bogner
mentioned this might enable a possible cleanup in SelectionDAG, but I'll
leave this to others to explore. In the meantime, the unit tests and
the comments for simple_ilist and ilist_node have usage examples.
Note that there's a layer of indirection to support optional,
out-of-order, template paramaters. Internal classes are templated on an
instantiation of the non-variadic ilist_detail::node_options.
User-facing classes use ilist_detail::compute_node_options to compute
the correct instantiation of ilist_detail::node_options.
The comments for ilist_detail::is_valid_option describe how to add new
options (e.g., ilist_packed_int<int NumBits>).
llvm-svn: 281167
diff --git a/llvm/unittests/ADT/SimpleIListTest.cpp b/llvm/unittests/ADT/SimpleIListTest.cpp
index f252080..5a38348 100644
--- a/llvm/unittests/ADT/SimpleIListTest.cpp
+++ b/llvm/unittests/ADT/SimpleIListTest.cpp
@@ -583,4 +583,55 @@
L.sort();
}
+struct Tag1 {};
+struct Tag2 {};
+
+struct DoubleNode : ilist_node<DoubleNode, ilist_tag<Tag1>>,
+ ilist_node<DoubleNode, ilist_tag<Tag2>> {
+ typedef ilist_node<DoubleNode, ilist_tag<Tag1>> Node1Type;
+ typedef ilist_node<DoubleNode, ilist_tag<Tag2>> Node2Type;
+
+ Node1Type::self_iterator getIterator1() { return Node1Type::getIterator(); }
+ Node2Type::self_iterator getIterator2() { return Node2Type::getIterator(); }
+ Node1Type::const_self_iterator getIterator1() const {
+ return Node1Type::getIterator();
+ }
+ Node2Type::const_self_iterator getIterator2() const {
+ return Node2Type::getIterator();
+ }
+};
+typedef simple_ilist<DoubleNode, ilist_tag<Tag1>> TaggedList1Type;
+typedef simple_ilist<DoubleNode, ilist_tag<Tag2>> TaggedList2Type;
+
+TEST(SimpleIListTest, TaggedLists) {
+ TaggedList1Type L1;
+ TaggedList2Type L2;
+
+ // Build the two lists, sharing a couple of nodes.
+ DoubleNode Ns[10];
+ int Order1[] = {0, 1, 2, 3, 4, 7, 9};
+ int Order2[] = {2, 5, 6, 7, 8, 4, 9, 1};
+ for (int I : Order1)
+ L1.push_back(Ns[I]);
+ for (int I : Order2)
+ L2.push_back(Ns[I]);
+
+ // Check that each list is correct.
+ EXPECT_EQ(sizeof(Order1) / sizeof(int), L1.size());
+ auto I1 = L1.begin();
+ for (int I : Order1) {
+ EXPECT_EQ(Ns[I].getIterator1(), I1);
+ EXPECT_EQ(&Ns[I], &*I1++);
+ }
+ EXPECT_EQ(L1.end(), I1);
+
+ EXPECT_EQ(sizeof(Order2) / sizeof(int), L2.size());
+ auto I2 = L2.begin();
+ for (int I : Order2) {
+ EXPECT_EQ(Ns[I].getIterator2(), I2);
+ EXPECT_EQ(&Ns[I], &*I2++);
+ }
+ EXPECT_EQ(L2.end(), I2);
+}
+
} // end namespace