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

[Liu, Xin]

Hi, Reviewers, 

May I get this patch reviewed?  Volker helped me to validate portability. 
Here is the webrev: > https://cr.openjdk.java.net/~xliu/8239066/webrev.01/webrev/
Thanks,
--lx


On 2/18/20, 6:05 AM, "Volker Simonis" <volker.simonis at gmail.com> wrote:

    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
    >     >
    >     >
    >     >
    >
    >