Withdrawn: 8335701: Make GrowableArray templated by an Index

[Johan Sjölen]

On Thu, 4 Jul 2024 11:34:23 GMT, Johan Sjölen <jsjolen at openjdk.org> wrote:

> Hi,
> 
> Today the GrowableArray has a set index type of `int`, this PR makes it so that you can set your own index type through a template parameter.
> 
> This opens up for a few new design choices:
> 
> - Do you know that you have a very small array? Use an `uint8_t` for len and cap, each.
> - Do you have a very large one? Use an `uint64_t`.
> 
> The code has opted for `int` being default, as to keep identical semantics for all existing code and to let users not have to worry about the index if they don't care.
> 
> One "major" change that I don't want to get lost in the review: I've changed the mid-point calculation to be overflow insensitive without casting.
> 
> 
> 
> // Old 
> mid = ((max + min) / 2);
> // New
> mid = min + ((max - min) / 2);
> 
> Some semi-rigorous thinking:
> min \in [0, len)
> max \in [0, len)
> min <= max
> max - min / 2 \in [0, len/2)
> Maximizing min and max => len + 0
> Maximizing max, minimizing min => len/2
> Minimizing max, maximizing min => max = min => min
> 
> 
> // Proof that they're identical when m, h, l \in N
> (1) m = l + (h - l) / 2 <=>
> 2m = 2l + h - l = h + l
> 
> (2) m = (h + l) / 2 <=>
> 2m = h + l
> (1) = (2)
> QED

This pull request has been closed without being integrated.

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

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