This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

RFA: abstract allocation function from splay tree library



According to src/MAINTAINERS, gcc-patches@gcc.gnu.org is the place to
post patches for libiberty.

As written, the splay tree library can't be used to manage a splay
tree in an obstack.  This patch makes that, and other arrangements,
possible, without introducing any new dependencies to the library.

include/ChangeLog:
2002-02-14  Jim Blandy  <jimb@redhat.com>

	Allow the user to specify functions for allocating memory for
	splay tree roots and nodes.
	* splay-tree.h (splay_tree_allocate_fn, splay_tree_deallocate_fn):
	New types.
	(splay_tree): New fields: `allocate', `deallocate', and
	`allocate_data'.
	(splay_tree_new_with_allocator): New function declaration.

libiberty/ChangeLog:
2002-02-14  Jim Blandy  <jimb@redhat.com>

	* splay-tree.c (splay_tree_xmalloc_allocate,
	splay_tree_xmalloc_deallocate): New functions.
	(splay_tree_new): Call splay_tree_new_with_allocator, passing the
	above functions and a dummy data pointer.
	(splay_tree_new_with_allocator): New function.
	(splay_tree_delete_helper, splay_tree_delete, splay_tree_insert,
	splay_tree_remove): Use the splay tree's allocation and
	deallocation functions.
	
Index: include/splay-tree.h
===================================================================
RCS file: /cvs/src/src/include/splay-tree.h,v
retrieving revision 1.6
diff -c -r1.6 splay-tree.h
*** include/splay-tree.h	2001/08/23 14:51:49	1.6
--- include/splay-tree.h	2002/02/15 05:29:36
***************
*** 61,66 ****
--- 61,78 ----
  /* The type of a function used to iterate over the tree.  */
  typedef int (*splay_tree_foreach_fn) PARAMS((splay_tree_node, void*));
  
+ /* The type of a function used to allocate memory for tree root and
+    node structures.  The first argument is the number of bytes needed;
+    the second is a data pointer the splay tree functions pass through
+    to the allocator.  This function must never return zero.  */
+ typedef void *(*splay_tree_allocate_fn) PARAMS((int, void *));
+ 
+ /* The type of a function used to free memory allocated using the
+    corresponding splay_tree_allocate_fn.  The first argument is the
+    memory to be freed; the latter is a data pointer the splay tree
+    functions pass through to the freer.  */
+ typedef void (*splay_tree_deallocate_fn) PARAMS((void *, void *));
+ 
  /* The nodes in the splay tree.  */
  struct splay_tree_node_s
  {
***************
*** 89,99 ****
--- 101,124 ----
  
    /* The deallocate-value function.  NULL if no cleanup is necessary.  */
    splay_tree_delete_value_fn delete_value;
+ 
+   /* Allocate/free functions, and a data pointer to pass to them.  */
+   splay_tree_allocate_fn allocate;
+   splay_tree_deallocate_fn deallocate;
+   void *allocate_data;
+ 
  } *splay_tree;
  
  extern splay_tree splay_tree_new        PARAMS((splay_tree_compare_fn,
  					        splay_tree_delete_key_fn,
  					        splay_tree_delete_value_fn));
+ extern splay_tree splay_tree_new_with_allocator
+                                         PARAMS((splay_tree_compare_fn,
+ 					        splay_tree_delete_key_fn,
+ 					        splay_tree_delete_value_fn,
+                                                 splay_tree_allocate_fn,
+                                                 splay_tree_deallocate_fn,
+                                                 void *));
  extern void splay_tree_delete           PARAMS((splay_tree));
  extern splay_tree_node splay_tree_insert          
  		                        PARAMS((splay_tree,
Index: libiberty/splay-tree.c
===================================================================
RCS file: /cvs/src/src/libiberty/splay-tree.c,v
retrieving revision 1.7
diff -c -r1.7 splay-tree.c
*** libiberty/splay-tree.c	2001/05/07 16:21:15	1.7
--- libiberty/splay-tree.c	2002/02/15 05:29:40
***************
*** 70,76 ****
    if (sp->delete_value)
      (*sp->delete_value)(node->value);
  
!   free ((char*) node);
  }
  
  /* Help splay SP around KEY.  PARENT and GRANDPARENT are the parent
--- 70,76 ----
    if (sp->delete_value)
      (*sp->delete_value)(node->value);
  
!   (*sp->deallocate) ((char*) node, sp->allocate_data);
  }
  
  /* Help splay SP around KEY.  PARENT and GRANDPARENT are the parent
***************
*** 227,247 ****
    return splay_tree_foreach_helper (sp, node->right, fn, data);
  }
  
  /* Allocate a new splay tree, using COMPARE_FN to compare nodes,
     DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate
!    values.  */
  
  splay_tree 
  splay_tree_new (compare_fn, delete_key_fn, delete_value_fn)
       splay_tree_compare_fn compare_fn;
       splay_tree_delete_key_fn delete_key_fn;
       splay_tree_delete_value_fn delete_value_fn;
  {
!   splay_tree sp = (splay_tree) xmalloc (sizeof (struct splay_tree_s));
    sp->root = 0;
    sp->comp = compare_fn;
    sp->delete_key = delete_key_fn;
    sp->delete_value = delete_value_fn;
  
    return sp;
  }
--- 227,287 ----
    return splay_tree_foreach_helper (sp, node->right, fn, data);
  }
  
+ 
+ /* An allocator and deallocator based on xmalloc.  */
+ static void *
+ splay_tree_xmalloc_allocate (int size, void *data)
+ {
+   return xmalloc (size);
+ }
+ 
+ static void
+ splay_tree_xmalloc_deallocate (void *object, void *data)
+ {
+   free (object);
+ }
+ 
+ 
  /* Allocate a new splay tree, using COMPARE_FN to compare nodes,
     DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate
!    values.  Use xmalloc to allocate the splay tree structure, and any
!    nodes added.  */
  
  splay_tree 
  splay_tree_new (compare_fn, delete_key_fn, delete_value_fn)
       splay_tree_compare_fn compare_fn;
       splay_tree_delete_key_fn delete_key_fn;
       splay_tree_delete_value_fn delete_value_fn;
+ {
+   return (splay_tree_new_with_allocator
+           (compare_fn, delete_key_fn, delete_value_fn,
+            splay_tree_xmalloc_allocate, splay_tree_xmalloc_deallocate, 0));
+ }
+ 
+ 
+ /* Allocate a new splay tree, using COMPARE_FN to compare nodes,
+    DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate
+    values.  */
+ 
+ splay_tree 
+ splay_tree_new_with_allocator (compare_fn, delete_key_fn, delete_value_fn,
+                                allocate_fn, deallocate_fn, allocate_data)
+      splay_tree_compare_fn compare_fn;
+      splay_tree_delete_key_fn delete_key_fn;
+      splay_tree_delete_value_fn delete_value_fn;
+      splay_tree_allocate_fn allocate_fn;
+      splay_tree_deallocate_fn deallocate_fn;
+      void *allocate_data;
  {
!   splay_tree sp = (splay_tree) (*allocate_fn) (sizeof (struct splay_tree_s),
!                                                allocate_data);
    sp->root = 0;
    sp->comp = compare_fn;
    sp->delete_key = delete_key_fn;
    sp->delete_value = delete_value_fn;
+   sp->allocate = allocate_fn;
+   sp->deallocate = deallocate_fn;
+   sp->allocate_data = allocate_data;
  
    return sp;
  }
***************
*** 253,259 ****
       splay_tree sp;
  {
    splay_tree_delete_helper (sp, sp->root);
!   free ((char*) sp);
  }
  
  /* Insert a new node (associating KEY with DATA) into SP.  If a
--- 293,299 ----
       splay_tree sp;
  {
    splay_tree_delete_helper (sp, sp->root);
!   (*sp->deallocate) ((char*) sp, sp->allocate_data);
  }
  
  /* Insert a new node (associating KEY with DATA) into SP.  If a
***************
*** 286,292 ****
        /* Create a new node, and insert it at the root.  */
        splay_tree_node node;
        
!       node = (splay_tree_node) xmalloc (sizeof (struct splay_tree_node_s));
        node->key = key;
        node->value = value;
        
--- 326,334 ----
        /* Create a new node, and insert it at the root.  */
        splay_tree_node node;
        
!       node = ((splay_tree_node)
!               (*sp->allocate) (sizeof (struct splay_tree_node_s),
!                                sp->allocate_data));
        node->key = key;
        node->value = value;
        
***************
*** 330,336 ****
        /* Delete the root node itself.  */
        if (sp->delete_value)
  	(*sp->delete_value) (sp->root->value);
!       free (sp->root);
  
        /* One of the children is now the root.  Doesn't matter much
  	 which, so long as we preserve the properties of the tree.  */
--- 372,378 ----
        /* Delete the root node itself.  */
        if (sp->delete_value)
  	(*sp->delete_value) (sp->root->value);
!       (*sp->deallocate) (sp->root, sp->allocate_data);
  
        /* One of the children is now the root.  Doesn't matter much
  	 which, so long as we preserve the properties of the tree.  */


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]