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

[Kim Barrett]

On Thu, 5 Oct 2023 10:26:59 GMT, Johan Sjölen <jsjolen at openjdk.org> wrote:

>> Kim Barrett has updated the pull request incrementally with one additional commit since the last revision:
>> 
>>   add IntrusiveListEntry::is_attached()
>
> src/hotspot/share/utilities/intrusiveList.hpp line 45:
> 
>> 43:  * when inserting objects into the list or referencing list objects,
>> 44:  * and removing an object from a list need not involve destroying the
>> 45:  * object.
> 
>>As a result, [...]
> 
> We know what an intrusive linked list is, we have at least 5 of them :)!

And maybe someday we'll have just (this) one?  I can delete this if you really think it's pointless.

> src/hotspot/share/utilities/intrusiveList.hpp line 73:
> 
>> 71:  * * has_size determines whether the list has a size()
>> 72:  * operation, returning the number of elements in the list.  If the
>> 73:  * operation is present, it has constant-time complexity.  The default
> 
> Surely that depends on the time complexity of the operation?

has_size determines whether the list implementation provides a constant-time
size operation or doesn't provide a size operation at all. The size operation
for Standard Library containers is always constant-time. Some containers, such
as std::forward_list, don't provide a size operation because it wouldn't be
constant time. This allows one to write things like

for (size_t i = 0; i < c.size(); ++i) ...

knowing that you've not added another O(N) through that use of size().

It's an option because some use-cases benefit from having it while it's wasted
in others.

> src/hotspot/share/utilities/intrusiveList.hpp line 78:
> 
>> 76:  * * Base is the base class for the list.  This is typically
>> 77:  * used to specify the allocation class.  The default is void, indicating
>> 78:  * no allocation class for the list.
> 
> What's an allocation class?

Referring to the HotSpot allocation classes, like CHeapObj<> and ResourceObj.  I should clarify that.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/15896#discussion_r1349575535
PR Review Comment: https://git.openjdk.org/jdk/pull/15896#discussion_r1349575158
PR Review Comment: https://git.openjdk.org/jdk/pull/15896#discussion_r1349575302