RFR(S): 8239066: make LinkedList<T> more generic

[Volker Simonis]

Hi Xin,

I think you can drastically simplify your change by using the SFINAE
("Substitution Failure Is Not An Error" [1]) pattern. The following
little patch will "retrofit" LinkedList to primitive types without the
need to change any existing users of LinkedList:

diff -r 2c95b65b3f21 src/hotspot/share/utilities/linkedlist.hpp
--- a/src/hotspot/share/utilities/linkedlist.hpp        Thu Feb 13
10:48:19 2020 +0100
+++ b/src/hotspot/share/utilities/linkedlist.hpp        Mon Feb 17
13:37:52 2020 +0100
@@ -51,6 +51,12 @@

   E*  data() { return &_data; }
   const E* peek() const { return &_data; }
+  template <typename T> bool equals(const T& t, bool (T::*)(const T&)) const {
+    return _data.equals(t);
+  }
+  template <typename T> bool equals(const T& t, ...) const {
+    return _data == t;
+  }
 };

 // A linked list interface. It does not specify
@@ -182,7 +188,7 @@

   virtual LinkedListNode<E>* find_node(const E& e) {
     LinkedListNode<E>* p = this->head();
-    while (p != NULL && !p->peek()->equals(e)) {
+    while (p != NULL && !p->template equals<E>(e, 0)) {
       p = p->next();
     }
     return p;
@@ -229,7 +235,7 @@
      LinkedListNode<E>* prev = NULL;

      while (tmp != NULL) {
-       if (tmp->peek()->equals(e)) {
+       if (tmp->template equals<E>(e, 0)) {
          return remove_after(prev);
        }
        prev = tmp;
diff -r 2c95b65b3f21 test/hotspot/gtest/utilities/test_linkedlist.cpp
--- a/test/hotspot/gtest/utilities/test_linkedlist.cpp  Thu Feb 13
10:48:19 2020 +0100
+++ b/test/hotspot/gtest/utilities/test_linkedlist.cpp  Mon Feb 17
13:37:52 2020 +0100
@@ -85,6 +85,28 @@
   check_list_values(expected, &ll);
 }

+TEST(LinkedList, generic) {
+  LinkedListImpl<int> il;
+  const int N = 100;
+  for (int i=0; i<N; ++i) {
+    il.add(i);
+  }
+  EXPECT_EQ(il.size(), (size_t)N);
+
+}
+
+TEST(LinkedList, algorithm) {
+  LinkedListImpl<int> il;
+  il.add(1);
+  il.add(2);
+  il.add(3);
+  EXPECT_EQ(*il.find(1), 1);
+  EXPECT_EQ(il.find(404), (int* )NULL);
+  EXPECT_TRUE(il.remove(1));
+  EXPECT_FALSE(il.remove(404));
+
+}
+
 // Test sorted linked list
 TEST(SortedLinkedList, simple) {
   LinkedListImpl<Integer, ResourceObj::C_HEAP, mtTest> ll;

I've only checked this with gcc for now, but it is C++ 98, so it
should work with any compiler we currently use.

Best regards,
Volker

[1] https://en.cppreference.com/w/cpp/language/sfinae

On Fri, Feb 14, 2020 at 10:22 PM Liu, Xin <xxinliu at amazon.com> wrote:
>
> Hi,
>
> 1.  Could I get reviewed for this patch?  I ran into some problems when I reuse this data structure. It’s a prerequisite of JDK-8229517<https://bugs.openjdk.java.net/browse/JDK-8229517>.
> 2.
> Webrev: https://cr.openjdk.java.net/~xliu/8239066/webrev.00/webrev/
> Bugs: https://bugs.openjdk.java.net/browse/JDK-8239066
>
> Currently, we can’t instantiate it using basic types such as int or arbitrary type.  It’s because E::equals is too intrusive.
> I move out find/remove and provide them like <algorithm>.  Usage is almost same as original because of template parameter type inference.
>
> I also fix some minor issues mentioned in JDK-8239066.  I think we can implement CompileQueue, G1BufferNodeList in the future.
>
> Thanks,
> --lx
>
>
>