| Message ID | AM5PR0701MB2657E35007D9ED3FA811A876E4870@AM5PR0701MB2657.eurprd07.prod.outlook.com |
|---|---|
| State | New |
| Headers | show |
| Series | [REPOST] Avoid excessive function type casts with splay-trees | expand |
Ping... On 05/03/18 22:13, Bernd Edlinger wrote: > Hi, > > this is basically the same patch I posted a few months ago, > with a few formatting nits by Jakub fixed. > > Bootstrapped and reg-tested again with current trunk. > > Is it OK for trunk? > > > Bernd. > > On 12/15/17 11:44, Bernd Edlinger wrote: >> Hi, >> >> when working on the -Wcast-function-type patch I noticed some rather >> ugly and non-portable function type casts that are necessary to >> accomplish >> some actually very simple tasks. >> >> Often functions taking pointer arguments are called with a different >> signature >> taking uintptr_t arguments, which is IMHO not really safe to do... >> >> The attached patch adds a context argument to the callback functions but >> keeps the existing interface as far as possible. >> >> >> Bootstrapped and reg-tested on x86_64-pc-linux-gnu. >> Is it OK for trunk? >> >> >> Thanks >> Bernd. >>
On Thu, May 17, 2018 at 3:21 PM Bernd Edlinger <bernd.edlinger@hotmail.de> wrote: > Ping... So this makes all traditional users go through the indirect splay_tree_compare_wrapper and friends (which is also exported for no good reason?). And all users are traditional at the moment. So I wonder if it's better to have a complete alternate interface? I do not see many users besides gcc, there's a use in bfd elf32-xtensa.c and some uses in gdb. Of course disregarding any users outside of SRC. Richard. > On 05/03/18 22:13, Bernd Edlinger wrote: > > Hi, > > > > this is basically the same patch I posted a few months ago, > > with a few formatting nits by Jakub fixed. > > > > Bootstrapped and reg-tested again with current trunk. > > > > Is it OK for trunk? > > > > > > Bernd. > > > > On 12/15/17 11:44, Bernd Edlinger wrote: > >> Hi, > >> > >> when working on the -Wcast-function-type patch I noticed some rather > >> ugly and non-portable function type casts that are necessary to > >> accomplish > >> some actually very simple tasks. > >> > >> Often functions taking pointer arguments are called with a different > >> signature > >> taking uintptr_t arguments, which is IMHO not really safe to do... > >> > >> The attached patch adds a context argument to the callback functions but > >> keeps the existing interface as far as possible. > >> > >> > >> Bootstrapped and reg-tested on x86_64-pc-linux-gnu. > >> Is it OK for trunk? > >> > >> > >> Thanks > >> Bernd. > >>
On Thu, May 17, 2018 at 03:39:42PM +0200, Richard Biener wrote: > On Thu, May 17, 2018 at 3:21 PM Bernd Edlinger <bernd.edlinger@hotmail.de> > wrote: > > > Ping... > > So this makes all traditional users go through the indirect > splay_tree_compare_wrapper > and friends (which is also exported for no good reason?). And all users > are traditional > at the moment. > > So I wonder if it's better to have a complete alternate interface? I do > not see many > users besides gcc, there's a use in bfd elf32-xtensa.c and some uses in libgomp has a copy (intentionally so, it is slightly changed). Jakub
On Thu, May 17, 2018 at 4:04 PM Jakub Jelinek <jakub@redhat.com> wrote: > On Thu, May 17, 2018 at 03:39:42PM +0200, Richard Biener wrote: > > On Thu, May 17, 2018 at 3:21 PM Bernd Edlinger < bernd.edlinger@hotmail.de> > > wrote: > > > > > Ping... > > > > So this makes all traditional users go through the indirect > > splay_tree_compare_wrapper > > and friends (which is also exported for no good reason?). And all users > > are traditional > > at the moment. > > > > So I wonder if it's better to have a complete alternate interface? I do > > not see many > > users besides gcc, there's a use in bfd elf32-xtensa.c and some uses in > libgomp has a copy (intentionally so, it is slightly changed). So if that is not exported ABI wise then maybe we can unshare it again into an even more improved splay_tree2 in libiberty and deprecate the "old" one? DJ, how's "compatibility" supposed to work with libiberty? Richard. > Jakub
On 05/17/18 15:39, Richard Biener wrote: > On Thu, May 17, 2018 at 3:21 PM Bernd Edlinger <bernd.edlinger@hotmail.de> > wrote: > >> Ping... > > So this makes all traditional users go through the indirect > splay_tree_compare_wrapper > and friends (which is also exported for no good reason?). And all users > are traditional > at the moment. > all except gcc/typed-splay-tree.h which only works if VALUE_TYPE is compatible with uint_ptr_t but cannot check this requirement. This one worried me the most. But not having to rewrite omp-low.c for instance where splay_tree_lookup and access to n->value are made all the time, made me think it will not work to rip out the old interface completely. Bernd. > So I wonder if it's better to have a complete alternate interface? I do > not see many > users besides gcc, there's a use in bfd elf32-xtensa.c and some uses in > gdb. Of course > disregarding any users outside of SRC. > > Richard. > > >> On 05/03/18 22:13, Bernd Edlinger wrote: >>> Hi, >>> >>> this is basically the same patch I posted a few months ago, >>> with a few formatting nits by Jakub fixed. >>> >>> Bootstrapped and reg-tested again with current trunk. >>> >>> Is it OK for trunk? >>> >>> >>> Bernd. >>> >>> On 12/15/17 11:44, Bernd Edlinger wrote: >>>> Hi, >>>> >>>> when working on the -Wcast-function-type patch I noticed some rather >>>> ugly and non-portable function type casts that are necessary to >>>> accomplish >>>> some actually very simple tasks. >>>> >>>> Often functions taking pointer arguments are called with a different >>>> signature >>>> taking uintptr_t arguments, which is IMHO not really safe to do... >>>> >>>> The attached patch adds a context argument to the callback functions > but >>>> keeps the existing interface as far as possible. >>>> >>>> >>>> Bootstrapped and reg-tested on x86_64-pc-linux-gnu. >>>> Is it OK for trunk? >>>> >>>> >>>> Thanks >>>> Bernd. >>>>
On 05/17/18 16:37, Bernd Edlinger wrote: > On 05/17/18 15:39, Richard Biener wrote: >> On Thu, May 17, 2018 at 3:21 PM Bernd Edlinger >> <bernd.edlinger@hotmail.de> >> wrote: >> >>> Ping... >> >> So this makes all traditional users go through the indirect >> splay_tree_compare_wrapper >> and friends (which is also exported for no good reason?). And all users >> are traditional >> at the moment. >> > > all except gcc/typed-splay-tree.h which only works if VALUE_TYPE is > compatible with uint_ptr_t but cannot check this requirement. > This one worried me the most. > > But not having to rewrite omp-low.c for instance where splay_tree_lookup > and access to n->value are made all the time, made me think it > will not work to rip out the old interface completely. > Well, I think it will be best to split this patch in two parts: One that adds just two utility functions for avoiding undefined function type casts which can be used with the original C interface. This first part is attached. And another part that uses a similar approach as the splay-tree in libgomp, but instead of creating a type-safe C interface it should translate the complete code from splay-tree.c/.h into a template. The second part, I plan to do at a later time. Is this OK for trunk? Thanks Bernd. include: 2018-05-26 Bernd Edlinger <bernd.edlinger@hotmail.de> * splay-tree.h (splay_tree_compare_strings, splay_tree_delete_pointers): Declare new utility functions. libiberty: 2018-05-26 Bernd Edlinger <bernd.edlinger@hotmail.de> * splay-tree.c (splay_tree_compare_strings, splay_tree_delete_pointers): New utility functions. gcc: 2018-05-26 Bernd Edlinger <bernd.edlinger@hotmail.de> * tree-dump.c (dump_node): Use splay_tree_delete_pointers. c-family: 2018-05-26 Bernd Edlinger <bernd.edlinger@hotmail.de> * c-lex.c (get_fileinfo): Use splay_tree_compare_strings and splay_tree_delete_pointers. cp: 2018-05-26 Bernd Edlinger <bernd.edlinger@hotmail.de> * decl2.c (start_static_storage_duration_function): Use splay_tree_delete_pointers. Index: gcc/c-family/c-lex.c =================================================================== --- gcc/c-family/c-lex.c (revision 260671) +++ gcc/c-family/c-lex.c (working copy) @@ -103,11 +103,9 @@ get_fileinfo (const char *name) struct c_fileinfo *fi; if (!file_info_tree) - file_info_tree = splay_tree_new ((splay_tree_compare_fn) - (void (*) (void)) strcmp, + file_info_tree = splay_tree_new (splay_tree_compare_strings, 0, - (splay_tree_delete_value_fn) - (void (*) (void)) free); + splay_tree_delete_pointers); n = splay_tree_lookup (file_info_tree, (splay_tree_key) name); if (n) Index: gcc/cp/decl2.c =================================================================== --- gcc/cp/decl2.c (revision 260671) +++ gcc/cp/decl2.c (working copy) @@ -3595,8 +3595,7 @@ start_static_storage_duration_function (unsigned c priority_info_map = splay_tree_new (splay_tree_compare_ints, /*delete_key_fn=*/0, /*delete_value_fn=*/ - (splay_tree_delete_value_fn) - (void (*) (void)) free); + splay_tree_delete_pointers); /* We always need to generate functions for the DEFAULT_INIT_PRIORITY so enter it now. That way when we walk Index: gcc/tree-dump.c =================================================================== --- gcc/tree-dump.c (revision 260671) +++ gcc/tree-dump.c (working copy) @@ -736,8 +736,7 @@ dump_node (const_tree t, dump_flags_t flags, FILE di.flags = flags; di.node = t; di.nodes = splay_tree_new (splay_tree_compare_pointers, 0, - (splay_tree_delete_value_fn) - (void (*) (void)) free); + splay_tree_delete_pointers); /* Queue up the first node. */ queue (&di, t, DUMP_NONE); Index: include/splay-tree.h =================================================================== --- include/splay-tree.h (revision 260671) +++ include/splay-tree.h (working copy) @@ -147,7 +147,9 @@ extern splay_tree_node splay_tree_max (splay_tree) extern splay_tree_node splay_tree_min (splay_tree); extern int splay_tree_foreach (splay_tree, splay_tree_foreach_fn, void*); extern int splay_tree_compare_ints (splay_tree_key, splay_tree_key); -extern int splay_tree_compare_pointers (splay_tree_key, splay_tree_key); +extern int splay_tree_compare_pointers (splay_tree_key, splay_tree_key); +extern int splay_tree_compare_strings (splay_tree_key, splay_tree_key); +extern void splay_tree_delete_pointers (splay_tree_value); #ifdef __cplusplus } Index: libiberty/splay-tree.c =================================================================== --- libiberty/splay-tree.c (revision 260671) +++ libiberty/splay-tree.c (working copy) @@ -31,6 +31,9 @@ Boston, MA 02110-1301, USA. */ #ifdef HAVE_STDLIB_H #include <stdlib.h> #endif +#ifdef HAVE_STRING_H +#include <string.h> +#endif #include <stdio.h> @@ -590,3 +593,19 @@ splay_tree_compare_pointers (splay_tree_key k1, sp else return 0; } + +/* Splay-tree comparison function, treating the keys as strings. */ + +int +splay_tree_compare_strings (splay_tree_key k1, splay_tree_key k2) +{ + return strcmp ((char *) k1, (char *) k2); +} + +/* Splay-tree delete function, simply using free. */ + +void +splay_tree_delete_pointers (splay_tree_value value) +{ + free ((void *) value); +}
On Sat, May 26, 2018 at 10:19 AM Bernd Edlinger <bernd.edlinger@hotmail.de> wrote: > On 05/17/18 16:37, Bernd Edlinger wrote: > > On 05/17/18 15:39, Richard Biener wrote: > >> On Thu, May 17, 2018 at 3:21 PM Bernd Edlinger > >> <bernd.edlinger@hotmail.de> > >> wrote: > >> > >>> Ping... > >> > >> So this makes all traditional users go through the indirect > >> splay_tree_compare_wrapper > >> and friends (which is also exported for no good reason?). And all users > >> are traditional > >> at the moment. > >> > > > > all except gcc/typed-splay-tree.h which only works if VALUE_TYPE is > > compatible with uint_ptr_t but cannot check this requirement. > > This one worried me the most. > > > > But not having to rewrite omp-low.c for instance where splay_tree_lookup > > and access to n->value are made all the time, made me think it > > will not work to rip out the old interface completely. > > > Well, I think it will be best to split this patch in two parts: > One that adds just two utility functions for avoiding undefined > function type casts which can be used with the original C interface. > This first part is attached. > And another part that uses a similar approach as the splay-tree in > libgomp, but instead of creating a type-safe C interface it should > translate the complete code from splay-tree.c/.h into a template. > The second part, I plan to do at a later time. > Is this OK for trunk? Looks ok to me. Do we need to worry about !HAVE_STRING_H and using strcmp? Thanks, Richard. > Thanks > Bernd.
On 05/28/18 11:19, Richard Biener wrote: > On Sat, May 26, 2018 at 10:19 AM Bernd Edlinger <bernd.edlinger@hotmail.de> > wrote: > > > >> On 05/17/18 16:37, Bernd Edlinger wrote: >>> On 05/17/18 15:39, Richard Biener wrote: >>>> On Thu, May 17, 2018 at 3:21 PM Bernd Edlinger >>>> <bernd.edlinger@hotmail.de> >>>> wrote: >>>> >>>>> Ping... >>>> >>>> So this makes all traditional users go through the indirect >>>> splay_tree_compare_wrapper >>>> and friends (which is also exported for no good reason?). And all > users >>>> are traditional >>>> at the moment. >>>> >>> >>> all except gcc/typed-splay-tree.h which only works if VALUE_TYPE is >>> compatible with uint_ptr_t but cannot check this requirement. >>> This one worried me the most. >>> >>> But not having to rewrite omp-low.c for instance where splay_tree_lookup >>> and access to n->value are made all the time, made me think it >>> will not work to rip out the old interface completely. >>> > >> Well, I think it will be best to split this patch in two parts: > >> One that adds just two utility functions for avoiding undefined >> function type casts which can be used with the original C interface. >> This first part is attached. > >> And another part that uses a similar approach as the splay-tree in >> libgomp, but instead of creating a type-safe C interface it should >> translate the complete code from splay-tree.c/.h into a template. >> The second part, I plan to do at a later time. > > >> Is this OK for trunk? > > Looks ok to me. Do we need to worry about !HAVE_STRING_H and > using strcmp? > No, I would be rather surprised if libiberty would compile at all without string.h. First some files include it without HAVE_STRING_H for instance sha1.c and argv.c, so I just replicated what the majority of the code base here did. Most sources include <string.h> ifdef HAVE_STRING_H, and use strcmp even if it is not declared (which should work for functions with int result). So I would commit this patch as is, if you agree. Bernd. > Thanks, > Richard. > > >> Thanks >> Bernd.
On May 28, 2018 4:25:02 PM GMT+02:00, Bernd Edlinger <bernd.edlinger@hotmail.de> wrote: >On 05/28/18 11:19, Richard Biener wrote: >> On Sat, May 26, 2018 at 10:19 AM Bernd Edlinger ><bernd.edlinger@hotmail.de> >> wrote: >> >> >> >>> On 05/17/18 16:37, Bernd Edlinger wrote: >>>> On 05/17/18 15:39, Richard Biener wrote: >>>>> On Thu, May 17, 2018 at 3:21 PM Bernd Edlinger >>>>> <bernd.edlinger@hotmail.de> >>>>> wrote: >>>>> >>>>>> Ping... >>>>> >>>>> So this makes all traditional users go through the indirect >>>>> splay_tree_compare_wrapper >>>>> and friends (which is also exported for no good reason?). And all >> users >>>>> are traditional >>>>> at the moment. >>>>> >>>> >>>> all except gcc/typed-splay-tree.h which only works if VALUE_TYPE is >>>> compatible with uint_ptr_t but cannot check this requirement. >>>> This one worried me the most. >>>> >>>> But not having to rewrite omp-low.c for instance where >splay_tree_lookup >>>> and access to n->value are made all the time, made me think it >>>> will not work to rip out the old interface completely. >>>> >> >>> Well, I think it will be best to split this patch in two parts: >> >>> One that adds just two utility functions for avoiding undefined >>> function type casts which can be used with the original C interface. >>> This first part is attached. >> >>> And another part that uses a similar approach as the splay-tree in >>> libgomp, but instead of creating a type-safe C interface it should >>> translate the complete code from splay-tree.c/.h into a template. >>> The second part, I plan to do at a later time. >> >> >>> Is this OK for trunk? >> >> Looks ok to me. Do we need to worry about !HAVE_STRING_H and >> using strcmp? >> > >No, I would be rather surprised if libiberty would compile at all >without string.h. First some files include it without HAVE_STRING_H >for instance sha1.c and argv.c, so I just replicated what >the majority of the code base here did. > >Most sources include <string.h> ifdef HAVE_STRING_H, and use strcmp >even if it is not declared (which should work for functions with int >result). > >So I would commit this patch as is, if you agree. Sure - go ahead. Richard. > >Bernd. > > >> Thanks, >> Richard. >> >> >>> Thanks >>> Bernd.
Index: gcc/c-family/c-lex.c =================================================================== --- gcc/c-family/c-lex.c (revision 255661) +++ gcc/c-family/c-lex.c (working copy) @@ -101,11 +101,9 @@ get_fileinfo (const char *name) struct c_fileinfo *fi; if (!file_info_tree) - file_info_tree = splay_tree_new ((splay_tree_compare_fn) - (void (*) (void)) strcmp, + file_info_tree = splay_tree_new (splay_tree_compare_strings, 0, - (splay_tree_delete_value_fn) - (void (*) (void)) free); + splay_tree_delete_pointers); n = splay_tree_lookup (file_info_tree, (splay_tree_key) name); if (n) Index: gcc/cp/decl2.c =================================================================== --- gcc/cp/decl2.c (revision 255661) +++ gcc/cp/decl2.c (working copy) @@ -3558,8 +3558,7 @@ start_static_storage_duration_function (unsigned c priority_info_map = splay_tree_new (splay_tree_compare_ints, /*delete_key_fn=*/0, /*delete_value_fn=*/ - (splay_tree_delete_value_fn) - (void (*) (void)) free); + splay_tree_delete_pointers); /* We always need to generate functions for the DEFAULT_INIT_PRIORITY so enter it now. That way when we walk Index: gcc/tree-dump.c =================================================================== --- gcc/tree-dump.c (revision 255661) +++ gcc/tree-dump.c (working copy) @@ -736,8 +736,7 @@ dump_node (const_tree t, dump_flags_t flags, FILE di.flags = flags; di.node = t; di.nodes = splay_tree_new (splay_tree_compare_pointers, 0, - (splay_tree_delete_value_fn) - (void (*) (void)) free); + splay_tree_delete_pointers); /* Queue up the first node. */ queue (&di, t, DUMP_NONE); Index: gcc/typed-splay-tree.h =================================================================== --- gcc/typed-splay-tree.h (revision 255661) +++ gcc/typed-splay-tree.h (working copy) @@ -63,7 +63,30 @@ class typed_splay_tree static value_type node_to_value (splay_tree_node node); - private: + compare_fn m_compare_outer_fn; + static int compare_inner_fn (splay_tree_key k1, splay_tree_key k2, + void *user_data) + { + typed_splay_tree *myself = (typed_splay_tree *) user_data; + return myself->m_compare_outer_fn ((key_type) k1, (key_type) k2); + } + + delete_key_fn m_delete_key_outer_fn; + static void delete_key_inner_fn (splay_tree_key key, void *user_data) + { + typed_splay_tree *myself = (typed_splay_tree *) user_data; + if (myself->m_delete_key_outer_fn) + myself->m_delete_key_outer_fn ((key_type) key); + } + + delete_value_fn m_delete_value_outer_fn; + static void delete_value_inner_fn (splay_tree_value value, void *user_data) + { + typed_splay_tree *myself = (typed_splay_tree *) user_data; + if (myself->m_delete_value_outer_fn) + myself->m_delete_value_outer_fn ((value_type) value); + } + ::splay_tree m_inner; }; @@ -75,12 +98,16 @@ inline typed_splay_tree<KEY_TYPE, VALUE_TYPE>:: delete_key_fn delete_key_fn, delete_value_fn delete_value_fn) { - m_inner = splay_tree_new ((splay_tree_compare_fn) - (void (*) (void)) compare_fn, - (splay_tree_delete_key_fn) - (void (*) (void)) delete_key_fn, - (splay_tree_delete_value_fn) - (void (*) (void)) delete_value_fn); + m_compare_outer_fn = compare_fn; + m_delete_key_outer_fn = delete_key_fn; + m_delete_value_outer_fn = delete_value_fn; + m_inner = splay_tree_ex_new (compare_inner_fn, this, + delete_key_inner_fn, this, + delete_value_inner_fn, this, + splay_tree_xmalloc_allocate, + splay_tree_xmalloc_allocate, + splay_tree_xmalloc_deallocate, + NULL); } /* Destructor for typed_splay_tree <K, V>. */ Index: include/splay-tree.h =================================================================== --- include/splay-tree.h (revision 255661) +++ include/splay-tree.h (working copy) @@ -57,14 +57,28 @@ typedef struct splay_tree_node_s *splay_tree_node; function should return values as for qsort. */ typedef int (*splay_tree_compare_fn) (splay_tree_key, splay_tree_key); +/* The type of a function which compares two splay-tree keys. The + function should return values as for qsort. + The last parameter contains context data. */ +typedef int (*splay_tree_compare_ex_fn) (splay_tree_key, splay_tree_key, + void *); + /* The type of a function used to deallocate any resources associated with the key. */ typedef void (*splay_tree_delete_key_fn) (splay_tree_key); /* The type of a function used to deallocate any resources associated + with the key. The last parameter contains context data. */ +typedef void (*splay_tree_delete_key_ex_fn) (splay_tree_key, void *); + +/* The type of a function used to deallocate any resources associated with the value. */ typedef void (*splay_tree_delete_value_fn) (splay_tree_value); +/* The type of a function used to deallocate any resources associated + with the value. The last parameter contains context data. */ +typedef void (*splay_tree_delete_value_ex_fn) (splay_tree_value, void *); + /* The type of a function used to iterate over the tree. */ typedef int (*splay_tree_foreach_fn) (splay_tree_node, void*); @@ -99,14 +113,23 @@ struct splay_tree_s { splay_tree_node root; /* The comparision function. */ - splay_tree_compare_fn comp; + splay_tree_compare_ex_fn comp; + /* Parameter for comparison function. */ + void *comp_data; + /* The deallocate-key function. NULL if no cleanup is necessary. */ - splay_tree_delete_key_fn delete_key; + splay_tree_delete_key_ex_fn delete_key; + /* Parameter for delete key function. */ + void *delete_key_data; + /* The deallocate-value function. NULL if no cleanup is necessary. */ - splay_tree_delete_value_fn delete_value; + splay_tree_delete_value_ex_fn delete_value; + /* Parameter for delete key function. */ + void *delete_value_data; + /* Node allocate function. Takes allocate_data as a parameter. */ splay_tree_allocate_fn allocate; @@ -135,6 +158,16 @@ extern splay_tree splay_tree_new_typed_alloc (spla splay_tree_allocate_fn, splay_tree_deallocate_fn, void *); +extern splay_tree splay_tree_ex_new (splay_tree_compare_ex_fn, + void *, + splay_tree_delete_key_ex_fn, + void *, + splay_tree_delete_value_ex_fn, + void *, + splay_tree_allocate_fn, + splay_tree_allocate_fn, + splay_tree_deallocate_fn, + void *); extern void splay_tree_delete (splay_tree); extern splay_tree_node splay_tree_insert (splay_tree, splay_tree_key, @@ -147,7 +180,14 @@ extern splay_tree_node splay_tree_max (splay_tree) extern splay_tree_node splay_tree_min (splay_tree); extern int splay_tree_foreach (splay_tree, splay_tree_foreach_fn, void*); extern int splay_tree_compare_ints (splay_tree_key, splay_tree_key); -extern int splay_tree_compare_pointers (splay_tree_key, splay_tree_key); +extern int splay_tree_compare_pointers (splay_tree_key, splay_tree_key); +extern int splay_tree_compare_strings (splay_tree_key, splay_tree_key); +extern void splay_tree_delete_pointers (splay_tree_value); +extern int splay_tree_compare_wrapper (splay_tree_key, splay_tree_key, void *); +extern void splay_tree_delete_key_wrapper (splay_tree_key, void *); +extern void splay_tree_delete_value_wrapper (splay_tree_value, void *); +extern void *splay_tree_xmalloc_allocate (int, void *); +extern void splay_tree_xmalloc_deallocate (void *, void *); #ifdef __cplusplus } Index: libiberty/splay-tree.c =================================================================== --- libiberty/splay-tree.c (revision 255661) +++ libiberty/splay-tree.c (working copy) @@ -31,6 +31,9 @@ Boston, MA 02110-1301, USA. */ #ifdef HAVE_STDLIB_H #include <stdlib.h> #endif +#ifdef HAVE_STRING_H +#include <string.h> +#endif #include <stdio.h> @@ -57,8 +60,8 @@ splay_tree_delete_helper (splay_tree sp, splay_tre if (!node) return; -#define KDEL(x) if (sp->delete_key) (*sp->delete_key)(x); -#define VDEL(x) if (sp->delete_value) (*sp->delete_value)(x); +#define KDEL(x) if (sp->delete_key) (*sp->delete_key)(x, sp->delete_key_data); +#define VDEL(x) if (sp->delete_value) (*sp->delete_value)(x, sp->delete_value_data); KDEL (node->key); VDEL (node->value); @@ -145,7 +148,7 @@ splay_tree_splay (splay_tree sp, splay_tree_key ke splay_tree_node n, c; n = sp->root; - cmp1 = (*sp->comp) (key, n->key); + cmp1 = (*sp->comp) (key, n->key, sp->comp_data); /* Found. */ if (cmp1 == 0) @@ -161,7 +164,7 @@ splay_tree_splay (splay_tree sp, splay_tree_key ke /* Next one left or right? If found or no child, we're done after one rotation. */ - cmp2 = (*sp->comp) (key, c->key); + cmp2 = (*sp->comp) (key, c->key, sp->comp_data); if (cmp2 == 0 || (cmp2 < 0 && !c->left) || (cmp2 > 0 && !c->right)) @@ -250,13 +253,13 @@ splay_tree_foreach_helper (splay_tree_node node, } /* An allocator and deallocator based on xmalloc. */ -static void * +void * splay_tree_xmalloc_allocate (int size, void *data ATTRIBUTE_UNUSED) { return (void *) xmalloc (size); } -static void +void splay_tree_xmalloc_deallocate (void *object, void *data ATTRIBUTE_UNUSED) { free (object); @@ -330,13 +333,42 @@ splay_tree_new_typed_alloc (splay_tree_compare_fn splay_tree_deallocate_fn deallocate_fn, void * allocate_data) { + return + splay_tree_ex_new (splay_tree_compare_wrapper, + (void *) (uintptr_t) compare_fn, + delete_key_fn ? splay_tree_delete_key_wrapper : NULL, + (void *) (uintptr_t) delete_key_fn, + delete_value_fn ? splay_tree_delete_value_wrapper : NULL, + (void *) (uintptr_t) delete_value_fn, + tree_allocate_fn, node_allocate_fn, deallocate_fn, + allocate_data); +} + +/* This function creates a splay tree that uses extended compare and delete + functions with context data. */ + +splay_tree +splay_tree_ex_new (splay_tree_compare_ex_fn compare_fn, + void * compare_data, + splay_tree_delete_key_ex_fn delete_key_fn, + void * delete_key_data, + splay_tree_delete_value_ex_fn delete_value_fn, + void * delete_value_data, + splay_tree_allocate_fn tree_allocate_fn, + splay_tree_allocate_fn node_allocate_fn, + splay_tree_deallocate_fn deallocate_fn, + void * allocate_data) +{ splay_tree sp = (splay_tree) (*tree_allocate_fn) (sizeof (struct splay_tree_s), allocate_data); sp->root = 0; sp->comp = compare_fn; + sp->comp_data = compare_data; sp->delete_key = delete_key_fn; + sp->delete_key_data = delete_key_data; sp->delete_value = delete_value_fn; + sp->delete_value_data = delete_value_data; sp->allocate = node_allocate_fn; sp->deallocate = deallocate_fn; sp->allocate_data = allocate_data; @@ -365,7 +397,7 @@ splay_tree_insert (splay_tree sp, splay_tree_key k splay_tree_splay (sp, key); if (sp->root) - comparison = (*sp->comp)(sp->root->key, key); + comparison = (*sp->comp)(sp->root->key, key, sp->comp_data); if (sp->root && comparison == 0) { @@ -372,7 +404,7 @@ splay_tree_insert (splay_tree sp, splay_tree_key k /* 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->delete_value)(sp->root->value, sp->delete_value_data); sp->root->value = value; } else @@ -414,7 +446,7 @@ splay_tree_remove (splay_tree sp, splay_tree_key k { splay_tree_splay (sp, key); - if (sp->root && (*sp->comp) (sp->root->key, key) == 0) + if (sp->root && (*sp->comp) (sp->root->key, key, sp->comp_data) == 0) { splay_tree_node left, right; @@ -423,7 +455,7 @@ splay_tree_remove (splay_tree sp, splay_tree_key k /* Delete the root node itself. */ if (sp->delete_value) - (*sp->delete_value) (sp->root->value); + (*sp->delete_value) (sp->root->value, sp->delete_value_data); (*sp->deallocate) (sp->root, sp->allocate_data); /* One of the children is now the root. Doesn't matter much @@ -454,7 +486,7 @@ splay_tree_lookup (splay_tree sp, splay_tree_key k { splay_tree_splay (sp, key); - if (sp->root && (*sp->comp)(sp->root->key, key) == 0) + if (sp->root && (*sp->comp)(sp->root->key, key, sp->comp_data) == 0) return sp->root; else return 0; @@ -508,7 +540,7 @@ splay_tree_predecessor (splay_tree sp, splay_tree_ /* Splay the tree around KEY. That will leave either the KEY itself, its predecessor, or its successor at the root. */ splay_tree_splay (sp, key); - comparison = (*sp->comp)(sp->root->key, key); + comparison = (*sp->comp)(sp->root->key, key, sp->comp_data); /* If the predecessor is at the root, just return it. */ if (comparison < 0) @@ -539,7 +571,7 @@ splay_tree_successor (splay_tree sp, splay_tree_ke /* Splay the tree around KEY. That will leave either the KEY itself, its predecessor, or its successor at the root. */ splay_tree_splay (sp, key); - comparison = (*sp->comp)(sp->root->key, key); + comparison = (*sp->comp)(sp->root->key, key, sp->comp_data); /* If the successor is at the root, just return it. */ if (comparison > 0) @@ -590,3 +622,51 @@ splay_tree_compare_pointers (splay_tree_key k1, sp else return 0; } + +/* Splay-tree comparison function, treating the keys as strings. */ + +int +splay_tree_compare_strings (splay_tree_key k1, splay_tree_key k2) +{ + return strcmp ((char *) k1, (char *) k2); +} + +/* Splay-tree delete function, simply using free. */ + +void +splay_tree_delete_pointers (splay_tree_value value) +{ + free ((void *) value); +} + +/* Splay-tree compare wrapper function. */ + +int +splay_tree_compare_wrapper (splay_tree_key k1, splay_tree_key k2, void *fn) +{ + splay_tree_compare_fn comp = (splay_tree_compare_fn) (uintptr_t) fn; + + return (*comp) (k1, k2); +} + +/* Splay-tree delete key wrapper function. */ + +void +splay_tree_delete_key_wrapper (splay_tree_key key, void *fn) +{ + splay_tree_delete_key_fn delete_key + = (splay_tree_delete_key_fn) (uintptr_t) fn; + + (*delete_key) (key); +} + +/* Splay-tree delete value wrapper function. */ + +void +splay_tree_delete_value_wrapper (splay_tree_value value, void *fn) +{ + splay_tree_delete_value_fn delete_value + = (splay_tree_delete_value_fn) (uintptr_t) fn; + + (*delete_value) (value); +}