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

[Andrew Haley]

On Wed, 4 Dec 2024 12:21:26 GMT, Andrew Haley <aph at openjdk.org> wrote:

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

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

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