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

[Liu, Xin]

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