RFR: 8189088: Add intrusive doubly-linked list utility

[Kim Barrett]

Please review this new facility, providing a general mechanism for intrusive
doubly-linked lists. A class supports inclusion in a list by having an
IntrusiveListEntry member, and providing structured information about how to
access that member. A class supports inclusion in multiple lists by having
multiple IntrusiveListEntry members, with different lists specified to use
different members.

The IntrusiveList class template provides the list management. It is modelled
on bidirectional containers such as std::list and boost::intrusive::list,
providing many of the expected member types and functions. (Note that the
member types use the Standard's naming conventions.) (Not all standard
container requirements are met; some operations are not presently supported
because they haven't been needed yet.) This includes iteration support using
(mostly) standard-conforming iterator types (they are presently missing
iterator_category member types, pending being able to include <iterator> so we
can use std::bidirectional_iterator_tag).

This change only provides the new facility, and doesn't include any uses of
it. It is intended to replace the 4-5 (or maybe more) competing intrusive
doubly-linked lists presently in HotSpot.  Unlike most (or perhaps all?) of
those alterantives, this proposal provides a suite of unit tests.

An example of a place that I think might benefit from this is G1's region
handling. There are various places where G1 iterates over all regions in order
to do something with those which satisfy some property (humongous regions,
regions in the collection set, &etc). If it were trivial to create new region
sublists (and this facility makes that easy), some of these could be turned
into direct iteration over only the regions of interest.

Some specific points to consider when reviewing this proposal:

(1) This proposal follows Standard Library API conventions, which differ from
HotSpot in various ways.

(1a) Lists and iterators provide various type members, with names per the
Standard Library. There has been discussion of using some parts of the
Standard Library eventually, in which case this would be important. But for
now some of the naming choices are atypical for HotSpot.

(1b) Some of the function signatures follow the Standard Library APIs even
though the reasons for that form might not apply to HotSpot. For example, the
list pop operations don't return the removed value. For node-based containers
in Standard Library that would introduce exception safety problems, so the
Standard Library API is designed to avoid that. HotSpot doesn't use
exceptions, so the exception safety issue isn't relevant. And for an intrusive
container like this, there isn't an exception safety problem anyway for pop
operations.

(2) It has been suggested this class should be named "List" rather than
"IntrusiveList", as this should be the "list" one usually reaches for in
HotSpot code (because no allocation is involved in list manipulation), and if
one wanted the other kind of list then just use std::list (if we permitted use
of some of the Standard Library).

(3) This proposal use a pointer-to-data-member to access the embedded list
entry in an object. NonblockingQueue and LockFreeStack use a function for that
access. There was a version of MSVC where the pointer to data member approach
didn't work. It also didn't work on some versions of Solaris Studio. Those are
no longer problems for us. We could change those other classes, or we could
change this to similarly use a function, or we could have the inconsistency.

(4) This proposal provides support for a parameterized IntrusiveList allocation
base. If we were using the Standard Library we would need a solution for heap
allocation of Standard Library containers. If we had such, it might be simpler
to use that same approach for this class, rather than using the allocation
base class approach. This of course assumes that there is a need for
heap/resource/arena allocated lists.

Testing:
mach5 tier1, building for all Oracle-supported platforms and running the new
unit tests.

-------------

Commit messages:
 - modernize and expand
 - old prototype

Changes: https://git.openjdk.org/jdk/pull/15896/files
 Webrev: https://webrevs.openjdk.org/?repo=jdk&pr=15896&range=00
  Issue: https://bugs.openjdk.org/browse/JDK-8189088
  Stats: 3190 lines in 3 files changed: 3190 ins; 0 del; 0 mod
  Patch: https://git.openjdk.org/jdk/pull/15896.diff
  Fetch: git fetch https://git.openjdk.org/jdk.git pull/15896/head:pull/15896

PR: https://git.openjdk.org/jdk/pull/15896