On 6/15/18, Bernd Edlinger <bernd.edlin...@hotmail.de> wrote: > 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. > >
While you're looking at changing splay trees, could you take a look at bug 30920, too? It's also about splay trees: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=30920 Just an idea. Thanks! > Thanks > Bernd. >
