RFR: 8189088: Add intrusive doubly-linked list utility [v3]

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

Kim Barrett has updated the pull request incrementally with one additional commit since the last revision:

  add IntrusiveListEntry::is_attached()

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

Changes:
  - all: https://git.openjdk.org/jdk/pull/15896/files
  - new: https://git.openjdk.org/jdk/pull/15896/files/3ae62f6c..e85271eb

Webrevs:
 - full: https://webrevs.openjdk.org/?repo=jdk&pr=15896&range=02
 - incr: https://webrevs.openjdk.org/?repo=jdk&pr=15896&range=01-02

  Stats: 13 lines in 2 files changed: 13 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