Re: [PATCH] Avoid excessive function type casts with splay-trees

[Bernd Edlinger <bernd dot edlinger at hotmail dot de>]

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.

Attachment: changelog-splay-tree.txt
Description: changelog-splay-tree.txt

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);
+}