This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch] splay tree nodes may be allocated by alloc-pool
- From: Josef Zlomek <zlomj9am at artax dot karlin dot mff dot cuni dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Date: Sun, 11 May 2003 22:18:25 +0200
- Subject: [patch] splay tree nodes may be allocated by alloc-pool
Hi,
this patch changes splay trees to use 2 allocators - one for the splay
tree structure, the second for splay tree nodes.
With this patch, splay tree nodes may be allocated by alloc-pool
because the size of splay tree structure and splay tree node is
different.
The parameters of splay_tree_allocate_fn and splay_tree_deallocate_fn
were swapped so that pool_free could be used directly.
Bootstrapped/regtested x86-64.
OK for mainline?
Josef
2003-05-11 Josef Zlomek <zlomekj@suse.cz>
* libiberty/splay-tree.c (splay_tree_xmalloc_allocate): Swap arguments.
(splay_tree_xmalloc_deallocate): Likewise.
(splay_tree_new): Use splay_tree_new_with_two_allocators.
(splay_tree_new_with_allocator): Likewise.
(splay_tree_new_with_two_allocators): New function.
(splay_tree_delete): Swap arguments of sp->deallocate.
(splay_tree_delete_helper): Use deallocate_node and allocate_node_data.
(splay_tree_insert): Likewise.
(splay_tree_remove): Likewise.
* include/splay-tree.h (splay_tree_allocate_fn): Swap arguments, fix
comment.
(splay_tree_deallocate_fn): Likewise.
(struct splay_tree_s): Added allocate_node, deallocate_node,
allocate_node_data.
(splay_tree_new_with_two_allocators): New function.
* gcc/ggc.h (splay_tree_new_ggc): Use
splay_tree_new_with_two_allocators.
(ggc_splay_alloc): Swapped arguments.
(ggc_splay_dont_free): Swapped arguments.
* gcc/ggc-common.c (ggc_splay_alloc): Swapped arguments.
(ggc_splay_dont_free): Swapped arguments.
Index: libiberty/splay-tree.c
===================================================================
RCS file: /cvs/gcc/gcc/libiberty/splay-tree.c,v
retrieving revision 1.23
diff -c -3 -p -r1.23 splay-tree.c
*** libiberty/splay-tree.c 7 May 2003 18:19:36 -0000 1.23
--- libiberty/splay-tree.c 11 May 2003 16:28:10 -0000
***************
*** 1,5 ****
/* A splay-tree datatype.
! Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
Contributed by Mark Mitchell (mark@markmitchell.com).
This file is part of GNU CC.
--- 1,6 ----
/* A splay-tree datatype.
! Copyright (C) 1998, 1999, 2000, 2001, 2003
! Free Software Foundation, Inc.
Contributed by Mark Mitchell (mark@markmitchell.com).
This file is part of GNU CC.
*************** splay_tree_delete_helper (sp, node)
*** 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
--- 71,77 ----
if (sp->delete_value)
(*sp->delete_value)(node->value);
! (*sp->deallocate_node) (sp->allocate_node_data, (char*) node);
}
/* Help splay SP around KEY. PARENT and GRANDPARENT are the parent
*************** splay_tree_foreach_helper (sp, node, fn,
*** 230,246 ****
/* An allocator and deallocator based on xmalloc. */
static void *
! splay_tree_xmalloc_allocate (size, data)
! int size;
void *data ATTRIBUTE_UNUSED;
{
return (void *) xmalloc (size);
}
static void
! splay_tree_xmalloc_deallocate (object, data)
! void *object;
void *data ATTRIBUTE_UNUSED;
{
free (object);
}
--- 231,247 ----
/* An allocator and deallocator based on xmalloc. */
static void *
! splay_tree_xmalloc_allocate (data, size)
void *data ATTRIBUTE_UNUSED;
+ int size;
{
return (void *) xmalloc (size);
}
static void
! splay_tree_xmalloc_deallocate (data, object)
void *data ATTRIBUTE_UNUSED;
+ void *object;
{
free (object);
}
*************** splay_tree_new (compare_fn, delete_key_f
*** 257,271 ****
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,
--- 258,274 ----
splay_tree_delete_key_fn delete_key_fn;
splay_tree_delete_value_fn delete_value_fn;
{
! return (splay_tree_new_with_two_allocators
(compare_fn, delete_key_fn, delete_value_fn,
+ splay_tree_xmalloc_allocate, splay_tree_xmalloc_deallocate, 0,
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. Use ALLOCATE_FN for allocating memory, DEALLOCATE_FN for freeing,
! pass ALLOCATE_DATA to the allocator. */
splay_tree
splay_tree_new_with_allocator (compare_fn, delete_key_fn, delete_value_fn,
*************** splay_tree_new_with_allocator (compare_f
*** 277,284 ****
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;
--- 280,315 ----
splay_tree_deallocate_fn deallocate_fn;
void *allocate_data;
{
! return (splay_tree_new_with_two_allocators
! (compare_fn, delete_key_fn, delete_value_fn,
! allocate_fn, deallocate_fn, allocate_data,
! allocate_fn, deallocate_fn, allocate_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. Use ALLOCATE_FN for allocating splay tree structure,
! DEALLOCATE_FN for freeing it, pass ALLOCATE_DATA to the allocator.
! Use ALLOCATE_NODE_FN for allocating tree node structures, DEALLOCATE_NODE_FN
! for freeing, pass ALLOCATE_NODE_DATA to the allocator. */
!
! splay_tree
! splay_tree_new_with_two_allocators (compare_fn, delete_key_fn, delete_value_fn,
! allocate_fn, deallocate_fn, allocate_data,
! allocate_node_fn, deallocate_node_fn,
! allocate_node_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_allocate_fn allocate_node_fn;
! splay_tree_deallocate_fn deallocate_node_fn;
! void *allocate_node_data;
! {
! splay_tree sp = (splay_tree) (*allocate_fn) (allocate_data,
! sizeof (struct splay_tree_s));
sp->root = 0;
sp->comp = compare_fn;
sp->delete_key = delete_key_fn;
*************** splay_tree_new_with_allocator (compare_f
*** 286,291 ****
--- 317,325 ----
sp->allocate = allocate_fn;
sp->deallocate = deallocate_fn;
sp->allocate_data = allocate_data;
+ sp->allocate_node = allocate_node_fn;
+ sp->deallocate_node = deallocate_node_fn;
+ sp->allocate_node_data = allocate_node_data;
return sp;
}
*************** splay_tree_delete (sp)
*** 297,303 ****
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
--- 331,337 ----
splay_tree sp;
{
splay_tree_delete_helper (sp, sp->root);
! (*sp->deallocate) (sp->allocate_data, (char*) sp);
}
/* Insert a new node (associating KEY with DATA) into SP. If a
*************** splay_tree_insert (sp, key, value)
*** 331,338 ****
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;
--- 365,372 ----
splay_tree_node node;
node = ((splay_tree_node)
! (*sp->allocate_node) (sp->allocate_node_data,
! sizeof (struct splay_tree_node_s)));
node->key = key;
node->value = value;
*************** splay_tree_remove (sp, key)
*** 376,382 ****
/* 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. */
--- 410,416 ----
/* Delete the root node itself. */
if (sp->delete_value)
(*sp->delete_value) (sp->root->value);
! (*sp->deallocate_node) (sp->allocate_node_data, 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. */
Index: include/splay-tree.h
===================================================================
RCS file: /cvs/gcc/gcc/include/splay-tree.h,v
retrieving revision 1.18
diff -c -3 -p -r1.18 splay-tree.h
*** include/splay-tree.h 10 Jan 2003 02:22:34 -0000 1.18
--- include/splay-tree.h 11 May 2003 16:28:10 -0000
***************
*** 1,5 ****
/* A splay-tree datatype.
! Copyright 1998, 1999, 2000, 2002 Free Software Foundation, Inc.
Contributed by Mark Mitchell (mark@markmitchell.com).
This file is part of GCC.
--- 1,6 ----
/* A splay-tree datatype.
! Copyright 1998, 1999, 2000, 2002, 2003
! Free Software Foundation, Inc.
Contributed by Mark Mitchell (mark@markmitchell.com).
This file is part of GCC.
*************** typedef void (*splay_tree_delete_value_f
*** 66,80 ****
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 PTR (*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. */
--- 67,81 ----
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 a data pointer the splay
! tree functions pass through to the allocator; the second is the
! number of bytes needed. This function must never return zero. */
! typedef PTR (*splay_tree_allocate_fn) PARAMS((void *, int));
/* The type of a function used to free memory allocated using the
! corresponding splay_tree_allocate_fn. The first argument is
! a data pointer the splay tree functions pass through to the freer;
! the second is the memory to be freed. */
typedef void (*splay_tree_deallocate_fn) PARAMS((void *, void *));
/* The nodes in the splay tree. */
*************** struct splay_tree_s GTY(())
*** 111,116 ****
--- 112,121 ----
splay_tree_deallocate_fn deallocate;
PTR GTY((skip (""))) allocate_data;
+ /* Allocate/free functions for nodes, and a data pointer to pass to them. */
+ splay_tree_allocate_fn allocate_node;
+ splay_tree_deallocate_fn deallocate_node;
+ PTR GTY((skip (""))) allocate_node_data;
};
typedef struct splay_tree_s *splay_tree;
*************** extern splay_tree splay_tree_new_with_al
*** 121,126 ****
--- 126,141 ----
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 splay_tree splay_tree_new_with_two_allocators
+ PARAMS((splay_tree_compare_fn,
+ splay_tree_delete_key_fn,
+ splay_tree_delete_value_fn,
+ splay_tree_allocate_fn,
+ splay_tree_deallocate_fn,
+ void *,
splay_tree_allocate_fn,
splay_tree_deallocate_fn,
void *));
Index: gcc/ggc.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/ggc.h,v
retrieving revision 1.50
diff -c -3 -p -r1.50 ggc.h
*** gcc/ggc.h 3 Apr 2003 21:00:56 -0000 1.50
--- gcc/ggc.h 11 May 2003 16:28:10 -0000
***************
*** 1,5 ****
/* Garbage collection for the GNU compiler.
! Copyright (C) 1998, 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
This file is part of GCC.
--- 1,6 ----
/* Garbage collection for the GNU compiler.
! Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003
! Free Software Foundation, Inc.
This file is part of GCC.
*************** extern void *ggc_calloc PARAMS ((size_t
*** 218,227 ****
htab_create_alloc (SIZE, HASH, EQ, DEL, ggc_calloc, NULL)
#define splay_tree_new_ggc(COMPARE) \
! splay_tree_new_with_allocator (COMPARE, NULL, NULL, \
&ggc_splay_alloc, &ggc_splay_dont_free, \
NULL)
! extern PTR ggc_splay_alloc PARAMS ((int, void *));
extern void ggc_splay_dont_free PARAMS ((void *, void *));
/* Allocate a gc-able string, and fill it with LENGTH bytes from CONTENTS.
--- 219,230 ----
htab_create_alloc (SIZE, HASH, EQ, DEL, ggc_calloc, NULL)
#define splay_tree_new_ggc(COMPARE) \
! splay_tree_new_with_two_allocators (COMPARE, NULL, NULL, \
&ggc_splay_alloc, &ggc_splay_dont_free, \
+ NULL, \
+ &ggc_splay_alloc, &ggc_splay_dont_free, \
NULL)
! extern PTR ggc_splay_alloc PARAMS ((void *, int));
extern void ggc_splay_dont_free PARAMS ((void *, void *));
/* Allocate a gc-able string, and fill it with LENGTH bytes from CONTENTS.
Index: gcc/ggc-common.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/ggc-common.c,v
retrieving revision 1.67
diff -c -3 -p -r1.67 ggc-common.c
*** gcc/ggc-common.c 3 Apr 2003 21:00:55 -0000 1.67
--- gcc/ggc-common.c 11 May 2003 16:28:10 -0000
*************** ggc_calloc (s1, s2)
*** 185,193 ****
/* These are for splay_tree_new_ggc. */
PTR
! ggc_splay_alloc (sz, nl)
! int sz;
PTR nl;
{
if (nl != NULL)
abort ();
--- 185,193 ----
/* These are for splay_tree_new_ggc. */
PTR
! ggc_splay_alloc (nl, sz)
PTR nl;
+ int sz;
{
if (nl != NULL)
abort ();
*************** ggc_splay_alloc (sz, nl)
*** 195,203 ****
}
void
! ggc_splay_dont_free (x, nl)
! PTR x ATTRIBUTE_UNUSED;
PTR nl;
{
if (nl != NULL)
abort ();
--- 195,203 ----
}
void
! ggc_splay_dont_free (nl, x)
PTR nl;
+ PTR x ATTRIBUTE_UNUSED;
{
if (nl != NULL)
abort ();