RFR: 8345314: Add a red–black tree as a utility data structure [v12]

[Thomas Stuefe]

On Thu, 16 Jan 2025 12:11:18 GMT, Andrew Haley <aph at openjdk.org> wrote:

>> I think the case for making the whole thing in a header depends on how much code there is, that's all.
>
>> @theRealAph
>> 
>> > Yes of course we can. Users add their own instantiations as required. I'm not saying you must do this, but I am saying it's not hard.
>> 
>> But for that the compiler must see the implementation of the functions, right? So, we cannot move the implementation into a cpp file?
> 
> Sure we can. That's what explicit template instantiation does. The cpp file contains the definition of the functions plus the explicit instantiations of whatever template types are needed.
> 
> As an example, imagine that the rbtree.inline.hpp implementation were moved to rbtree.cpp. Then there could be a number of  explicit template instantiations in rbtree.cpp like this one:
> 
> `template class RBTree<concreteK, concreteV, concreteCOMPARATOR, concreteALLOCATOR>;`
> 
> This generates all of the code for the template functions. But it's generated once and called, rather than inlined. The only stuff in the header would be the declarations.
> 
> NB: Again, i am _not_ saying that we should do this, but I am saying that it's an option for large template classes.

@theRealAph Just to be sure I understand, this means that if I want to add a new variant at a later point, I need to add its explicit instantiation to this cpp file, right? Including adding all the headers it needs to resolve the new template types.

I guess this is what others meant by "we don't know the types others use upfront". We could do this, its just a bit of a hassle. OTOH, it could reduce template bloat.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/22360#discussion_r1918415522