On 06/15/18 09:07, Richard Biener wrote:
> On Thu, 14 Jun 2018, Bernd Edlinger wrote:
>
>> On 06/14/18 15:43, Richard Biener wrote:
>>> On Fri, 8 Jun 2018, Bernd Edlinger wrote:
>>>
>>>> Hi!
>>>>
>>>>
>>>> This patch converts the splay-tree internals into a template, and makes
>>>> the typed_splay_tree template really type-safe. Previously everything
>>>> would break apart if KEY_TYPE or VALUE_TYPE would not be pointer types.
>>>> This limitation is now removed.
>>>>
>>>> I took the freedom to add a remove function which is only for
>>>> completeness and test coverage, but not (yet) used in a productive way.
>>>>
>>>>
>>>> Bootstrapped and reg-tested on x86_64-linux-gnu.
>>>> Is it OK for trunk?
>>>
>>> It looks OK to me but I wonder if we can avoid some of the code
>>> duplication due to template instantiation by deriving from a non-templated
>>> base class somehow? The cc1* binaries keep growing with more and
>>> more template use :/
>>>
>>
>>
>> No problem. The first version used an approach where splay-tree
>> exposes an extended interface with a context pointer.
>>
>> See: https://gcc.gnu.org/ml/gcc-patches/2018-05/msg00178.html
>>
>> But it has also a limitation when the value or type is a class, it will
>> not be possible to cast to uintptr_t, it will fail to compile, which is
>> still an improvement since the current version just casts incompatible
>> function pointers, and since I had to silence the -Wcast-function-type
>> the warning would not help either.
>>
>>
>> If you like the original patch better than the template, I can cleanup
>> the original patch as an alternative?
>
> No, I like the template more but wondered if we can somehow outline
> some of the main worker code?
>
The major difficulty with that are the splay_tree_compare_fn and
splay_tree_delete_key/value_fn callbacks which don't pass a context
value in addition to the splay_tree_key and splay_tree_value.
I thought about passing a "glue" object which contains a context
pointer together with the true key and/or value object, but I gave
up when I saw this in splay_tree_insert:
if (sp->root)
comparison = (*sp->comp)(sp->root->key, key);
if (sp->root && comparison == 0)
{
/* If the root of the tree already has the indicated KEY, just
replace the value with VALUE. */
if (sp->delete_value)
(*sp->delete_value)(sp->root->value);
sp->root->value = value;
}
There is a delete_key callback missing, and sp->root->key will not
be updated. So the resource flow of the glue objects will not work.
This code simply assumes that key equality implies pointer equality,
or the key does not need to be freed after use, but this is not the
case with glue objects.
So, I don't see how to use the old code in a type-safe template without
changing the C interface.
Or maybe duplicating the C implementation...
Currently there are not more than two or three uses of this
template, so it will not be a big difference anyways.
But shouldn't different template functions be folded together
when the resulting code is identical?
Or is there maybe another template where optimizing the code size
would be more profitable?
So, I would still prefer the splay tree template unless there is a
better idea, how to proceed.
Thanks
Bernd.
