| Message ID | DB6PR0701MB266437EB2B10745722CDB8B6E40B0@DB6PR0701MB2664.eurprd07.prod.outlook.com |
|---|---|
| State | New |
| Headers | show |
| Series | Avoid excessive function type casts with splay-trees | expand |
On Fri, Dec 15, 2017 at 10:44:54AM +0000, Bernd Edlinger wrote: > 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. Just formatting nits, not full review: > + return strcmp ((char*) k1, (char*) k2); char * instead of char*, please. > +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; Too long line, should be: splay_tree_delete_key_fn delete_key = (splay_tree_delete_key_fn) (uintptr_t) fn; > +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; Ditto. Jakub
On 12/15/17 11:51, Jakub Jelinek wrote: > On Fri, Dec 15, 2017 at 10:44:54AM +0000, Bernd Edlinger wrote: >> 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. > > Just formatting nits, not full review: > >> + return strcmp ((char*) k1, (char*) k2); > > char * instead of char*, please. > >> +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; > > Too long line, should be: > splay_tree_delete_key_fn delete_key > = (splay_tree_delete_key_fn) (uintptr_t) fn; > >> +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; > > Ditto. > Yes, thanks. Updated patch attached. Bernd. include: 2017-12-15 Bernd Edlinger <bernd.edlinger@hotmail.de> * splay-tree.h (splay_tree_compare_ex_fn, splay_tree_delete_key_ex_fn, splay_tree_delete_value_ex_fn): New function types. (splay_tree_s): Update to use new function types. (splay_tree_ex_new): Declare new constructor. (splay_tree_compare_strings, splay_tree_delete_pointers, splay_tree_compare_wrapper, splay_tree_delete_key_wrapper, splay_tree_delete_value_wrapper, splay_tree_xmalloc_allocate, splay_tree_xmalloc_deallocate): Declare new utility functions. libiberty: 2017-12-15 Bernd Edlinger <bernd.edlinger@hotmail.de> * splay-tree.c (splay_tree_delete_helper, splay_tree_splay, splay_tree_insert, splay_tree_remove, splay_tree_lookup, splay_tree_predecessor, splay_tree_successor): Adjust. (splay_tree_new_typed_alloc): Call splay_tree_ex_new. (splay_tree_ex_new): New constructor. (splay_tree_compare_strings, splay_tree_delete_pointers, splay_tree_compare_wrapper, splay_tree_delete_key_wrapper, splay_tree_delete_value_wrapper): New utility functions. (splay_tree_xmalloc_allocate, splay_tree_xmalloc_deallocate): Export. gcc: 2017-12-15 Bernd Edlinger <bernd.edlinger@hotmail.de> * typed-splay-tree.h (typed_splay_tree::m_compare_outer_fn, typed_splay_tree::m_delete_key_outer_fn, typed_splay_tree::m_delete_value_outer_fn): New data members. (typed_splay_tree::compare_inner_fn, typed_splay_tree::delete_key_inner_fn, typed_splay_tree::delete_value_inner_fn): New helper functions. (typed_splay_tree::typed_splay_tree): Use splay_tree_ex_new. * tree-dump.c (dump_node): Use splay_tree_delete_pointers. c-family: 2017-12-15 Bernd Edlinger <bernd.edlinger@hotmail.de> * c-lex.c (get_fileinfo): Use splay_tree_compare_strings and splay_tree_delete_pointers. cp: 2017-12-15 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 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 delere 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 delere 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); +}
Ping? On 12/15/17 19:59, Bernd Edlinger wrote: > On 12/15/17 11:51, Jakub Jelinek wrote: >> On Fri, Dec 15, 2017 at 10:44:54AM +0000, Bernd Edlinger wrote: >>> 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. >> >> Just formatting nits, not full review: >> >>> + return strcmp ((char*) k1, (char*) k2); >> >> char * instead of char*, please. >> >>> +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; >> >> Too long line, should be: >> splay_tree_delete_key_fn delete_key >> = (splay_tree_delete_key_fn) (uintptr_t) fn; >> >>> +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; >> >> Ditto. >> > > Yes, thanks. > > Updated patch attached. > > > 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,49 @@ 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 delere 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 delere 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); +}