Re: [PATCH v2 0/1] MR2622: ntdll: Use log-linear bucketing for free lists.

[Rémi Bernon]

Rémi Bernon (@rbernon) commented about dlls/ntdll/heap.c:
> +    log = b - FREE_LIST_LINEAR_BITS + 1;
> +    block = ( log << FREE_LIST_LINEAR_BITS ) + linear;
> +
> +    return min( block, NB_FREE_LISTS - 1 );
> +}
> +
> +static size_t get_free_list_block_size( unsigned long index )
> +{
> +    unsigned long log = 1 << FREE_LIST_LINEAR_BITS;
> +    unsigned long linear = index & FREE_LIST_LINEAR_MASK;
> +
> +    if ( ( index >> FREE_LIST_LINEAR_BITS ) == 0 )
> +        return index * BLOCK_ALIGN;
> +
> +    return ( ( log + linear ) << ( ( index >> FREE_LIST_LINEAR_BITS ) - 1 ) ) * BLOCK_ALIGN;
> +}
static SIZE_T get_free_list_block_size( UINT index )
{
    UINT linear = index & FREE_LIST_LINEAR_MASK, shift = index >> FREE_LIST_LINEAR_BITS;
    if (shift) linear = (linear + (1 &lt;&lt; FREE_LIST_LINEAR_BITS)) &lt;&lt; (shift - 1);
    return linear * BLOCK_ALIGN;
}

static UINT get_free_list_index( SIZE_T block_size )
{
    UINT linear, shift;
    DWORD bit;

    if (block_size >= get_free_list_block_size( FREE_LIST_COUNT - 1 )) return FREE_LIST_COUNT - 1;

    block_size /= BLOCK_ALIGN;
    if (!BitScanReverse( &bit, block_size ) || bit &lt; FREE_LIST_LINEAR_BITS) return block_size;

    /* the highest bit is always set, ignore it and encode the next FREE_LIST_LINEAR_BITS bits
     * as a linear scale, combined with the shift as a log scale, in the free list index. */
    shift = bit - FREE_LIST_LINEAR_BITS + 1;
    linear = (block_size - (1 &lt;&lt; bit)) >> (shift - 1);

    return (shift &lt;&lt; FREE_LIST_LINEAR_BITS) + (linear & FREE_LIST_LINEAR_MASK);
}

We can use `get_free_list_block_size` to early reject large cases, and make the rest a little bit simpler.

Also note that the style has spaces only in function and macros parentheses. And like @iamahuman suggested, the code around uses win32 types, so prefer `ULONG` / `UINT` over unsigned long, and `SIZE_T` instead of `size_t`.

-- 
https://gitlab.winehq.org/wine/wine/-/merge_requests/2622#note_29532