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

[Volker Simonis]

Submit repo tests all passed:

Job: mach5-one-simonis-JDK-8239066-1-20200218-1227-8815611

BuildId: 2020-02-18-1226193.volker.simonis.source

No failed tests

Tasks Summary

UNABLE_TO_RUN: 0
PASSED: 79
FAILED: 0
NA: 0
NOTHING_TO_RUN: 0
EXECUTED_WITH_FAILURE: 0
HARNESS_ERROR: 0
KILLED: 0

On Tue, Feb 18, 2020 at 6:36 AM Liu, Xin <xxinliu at amazon.com> wrote:
>
> Hi,
>
> Thanks for reviewing it.
> I put find/remove back to the classes. Volker's approach is great.  I only did minor change from his code.
> 1. I gave the member function pointer a name for easy understanding.
> 2.  I changed from equal<E>(_data, t, 0) to equal<E>(_data, t, NULL).  Indeed, there's an implicit conversion from 0 to NULL in C++.  But I think it's easy to understand using NULL.
> It's also convenient if we substitute all NULLs with nullptr in the future.
> 3. hide SFINAE templates functions in private section.
>
> I passed both gtest:all and test-tier1.  @Volker, Could you help me verify it using submit repo?
> Here is the new webrev:
> https://cr.openjdk.java.net/~xliu/8239066/webrev.01/webrev/
>
> Thanks,
> --lx
>
> On 2/17/20, 4:48 AM, "Volker Simonis" <volker.simonis at gmail.com> wrote:
>
>     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
>     >
>     >
>     >
>
>