* [libmudflap] splay tree improvements
@ 2004-07-08 20:07 Frank Ch. Eigler
0 siblings, 0 replies; only message in thread
From: Frank Ch. Eigler @ 2004-07-08 20:07 UTC (permalink / raw)
To: gcc-patches
Hi -
I've been in discussion with RMS about how to let the splay-tree code
be used in libmudflap (recall the gpl vs libgcc licensing issue that
some brought up). It appears to be leading toward acceptance if the
code is specialized more, in essence forked, for use in libmudflap.
So I've been making numerous specialization changes toward this end
in the interim.
One big change is to let the code tolerate degenerate access patterns
without running out of stack space with its recursive algorithms.
The attached patch includes code to back out of excessive recursion
during searches, rebalance the entire binary tree, and try again.
A test case submitted by a contributor illustrates how easily such
degenerate tree topologies can be created.
- FChE
2004-07-08 Frank Ch. Eigler <fche@redhat.com>
ANSI C conversion, libmudflap specialization, recursion limiting.
* splay-tree.h (splay_tree_{de,}allocate_fn): Remove allocation_data
argument and indirection function pointers, update callers.
(splay_tree_s): Add statistics and recursion control fields
num_keys, max_depth, depth, rebalance_p.
* splay-tree.c (splay_tree_splay_helper): Track recursion depth.
Back out of search if it exceeds limit.
(splay_tree_splay): Manage recursion limiting with rebalancing as
needed.
(splay_tree_new): More initialization.
(splay_tree_rebalance): New function.
(splay_tree_foreach): Rewrite using nonrecursive logic.
(splay_tree_xmalloc_allocate, splay_tree_xmalloc_deallocate):
Remove. Point indirect calls to mf-runtime.c's routines.
(splay_tree_compare_ints, splay_tree_compare_pointers): Remove unused
functions.
(splay_tree_delete, splay_tree_delete_helper): Ditto.
* testsuite/heap-scalestress.c: New test based on one from
Eyal Lebedinsky <eyal@eyal.emu.id.au>:
Index: splay-tree.c
===================================================================
RCS file: /cvs/gcc/gcc/libmudflap/splay-tree.c,v
retrieving revision 1.1
diff -c -p -s -w -r1.1 splay-tree.c
*** splay-tree.c 29 Jun 2004 22:30:53 -0000 1.1
--- splay-tree.c 8 Jul 2004 18:58:30 -0000
*************** Boston, MA 02111-1307, USA. */
*** 38,57 ****
#include <stdio.h>
#include "splay-tree.h"
! static void splay_tree_delete_helper PARAMS((splay_tree,
! splay_tree_node));
! static void splay_tree_splay PARAMS((splay_tree,
! splay_tree_key));
! static splay_tree_node splay_tree_splay_helper
! PARAMS((splay_tree,
splay_tree_key,
splay_tree_node*,
splay_tree_node*,
! splay_tree_node*));
! static int splay_tree_foreach_helper PARAMS((splay_tree,
! splay_tree_node,
! splay_tree_foreach_fn,
! void*));
--- 38,53 ----
#include <stdio.h>
#include "splay-tree.h"
!
! static void splay_tree_delete_helper (splay_tree, splay_tree_node);
! static void splay_tree_splay (splay_tree, splay_tree_key);
! static splay_tree_node splay_tree_splay_helper (splay_tree,
splay_tree_key,
splay_tree_node *,
splay_tree_node *,
! splay_tree_node *);
! static void *splay_tree_xmalloc (size_t size);
! static void splay_tree_free (void *object);
*************** compare_uintptr_t (splay_tree_key k1, sp
*** 68,99 ****
}
-
- /* Deallocate NODE (a member of SP), and all its sub-trees. */
-
- static void
- splay_tree_delete_helper (sp, node)
- splay_tree sp;
- splay_tree_node node;
- {
- if (!node)
- return;
-
- splay_tree_delete_helper (sp, node->left);
- splay_tree_delete_helper (sp, node->right);
- (*sp->deallocate) ((char*) node, sp->allocate_data);
- }
-
/* Help splay SP around KEY. PARENT and GRANDPARENT are the parent
and grandparent, respectively, of NODE. */
static splay_tree_node
! splay_tree_splay_helper (sp, key, node, parent, grandparent)
! splay_tree sp;
! splay_tree_key key;
! splay_tree_node *node;
! splay_tree_node *parent;
! splay_tree_node *grandparent;
{
splay_tree_node *next;
splay_tree_node n;
--- 64,78 ----
}
/* Help splay SP around KEY. PARENT and GRANDPARENT are the parent
and grandparent, respectively, of NODE. */
static splay_tree_node
! splay_tree_splay_helper (splay_tree sp,
! splay_tree_key key,
! splay_tree_node * node,
! splay_tree_node * parent,
! splay_tree_node * grandparent)
{
splay_tree_node *next;
splay_tree_node n;
*************** splay_tree_splay_helper (sp, key, node,
*** 118,129 ****
if (next)
{
/* Continue down the tree. */
n = splay_tree_splay_helper (sp, key, next, node, parent);
/* The recursive call will change the place to which NODE
points. */
! if (*node != n)
return n;
}
--- 97,118 ----
if (next)
{
+ /* Check whether our recursion depth is too high. Abort this search,
+ and signal that a rebalance is required to continue. */
+ if (sp->depth > sp->max_depth)
+ {
+ sp->rebalance_p = 1;
+ return n;
+ }
+
/* Continue down the tree. */
+ sp->depth ++;
n = splay_tree_splay_helper (sp, key, next, node, parent);
+ sp->depth --;
/* The recursive call will change the place to which NODE
points. */
! if (*node != n || sp->rebalance_p)
return n;
}
*************** splay_tree_splay_helper (sp, key, node,
*** 196,312 ****
}
}
- /* Splay SP around KEY. */
! static void
! splay_tree_splay (sp, key)
! splay_tree sp;
! splay_tree_key key;
{
! if (sp->root == 0)
! return;
- /* If we just splayed the tree with the same key, do nothing. */
- if (sp->last_splayed_key_p &&
- compare_uintptr_t (sp->last_splayed_key, key) == 0)
- return;
! splay_tree_splay_helper (sp, key, &sp->root,
! /*grandparent=*/0, /*parent=*/0);
! /* Cache this splay key. */
! sp->last_splayed_key = key;
! sp->last_splayed_key_p = 1;
}
- /* Call FN, passing it the DATA, for every node below NODE, all of
- which are from SP, following an in-order traversal. If FN every
- returns a non-zero value, the iteration ceases immediately, and the
- value is returned. Otherwise, this function returns 0. */
! static int
! splay_tree_foreach_helper (sp, node, fn, data)
! splay_tree sp;
! splay_tree_node node;
! splay_tree_foreach_fn fn;
! void* data;
{
! int val;
! if (!node)
! return 0;
! val = splay_tree_foreach_helper (sp, node->left, fn, data);
! if (val)
! return val;
! val = (*fn)(node, data);
! if (val)
! return val;
! return splay_tree_foreach_helper (sp, node->right, fn, data);
}
! /* 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);
}
- /* 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 ()
{
! splay_tree_allocate_fn allocate_fn = splay_tree_xmalloc_allocate;
! splay_tree_deallocate_fn deallocate_fn = splay_tree_xmalloc_deallocate;
! void *allocate_data = NULL;
! splay_tree sp = (splay_tree) (*allocate_fn) (sizeof (struct splay_tree_s),
! allocate_data);
! sp->root = 0;
! sp->allocate = allocate_fn;
! sp->deallocate = deallocate_fn;
! sp->allocate_data = allocate_data;
sp->last_splayed_key_p = 0;
return sp;
}
- /* Deallocate SP. */
- void
- splay_tree_delete (sp)
- 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
previous node with the indicated KEY exists, its data is replaced
with the new value. Returns the new node. */
-
splay_tree_node
! splay_tree_insert (sp, key, value)
! splay_tree sp;
! splay_tree_key key;
! splay_tree_value value;
{
int comparison = 0;
--- 185,312 ----
}
}
!
! static int
! splay_tree_rebalance_helper1 (splay_tree_node n, void *array_ptr)
{
! splay_tree_node **p = array_ptr;
! *(*p) = n;
! (*p)++;
! return 0;
! }
! static splay_tree_node
! splay_tree_rebalance_helper2 (splay_tree_node * array, unsigned low,
! unsigned high)
! {
! unsigned middle = low + (high - low) / 2;
! splay_tree_node n = array[middle];
! /* Note that since we're producing a balanced binary tree, it is not a problem
! that this function is recursive. */
! if (low + 1 <= middle)
! n->left = splay_tree_rebalance_helper2 (array, low, middle - 1);
! else
! n->left = NULL;
!
! if (middle + 1 <= high)
! n->right = splay_tree_rebalance_helper2 (array, middle + 1, high);
! else
! n->right = NULL;
!
! return n;
}
! /* Rebalance the entire tree. Do this by copying all the node
! pointers into an array, then cleverly re-linking them. */
! void
! splay_tree_rebalance (splay_tree sp)
{
! splay_tree_node *all_nodes, *all_nodes_1;
! if (sp->num_keys <= 2)
! return;
! all_nodes = splay_tree_xmalloc (sizeof (splay_tree_node) * sp->num_keys);
! /* Traverse all nodes to copy their addresses into this array. */
! all_nodes_1 = all_nodes;
! splay_tree_foreach (sp, splay_tree_rebalance_helper1,
! (void *) &all_nodes_1);
!
! /* Relink all the nodes. */
! sp->root = splay_tree_rebalance_helper2 (all_nodes, 0, sp->num_keys - 1);
! splay_tree_free (all_nodes);
}
! /* Splay SP around KEY. */
! static void
! splay_tree_splay (splay_tree sp, splay_tree_key key)
! {
! if (sp->root == 0)
! return;
!
! /* If we just splayed the tree with the same key, do nothing. */
! if (sp->last_splayed_key_p &&
! compare_uintptr_t (sp->last_splayed_key, key) == 0)
! return;
!
! /* Compute a maximum recursion depth for a splay tree with NUM nodes.
! The idea is to limit excessive stack usage if we're facing
! degenerate access patterns. Unfortunately such patterns can occur
! e.g. during static initialization, where many static objects might
! be registered in increasing address sequence, or during a case where
! large tree-like heap data structures are allocated quickly.
!
! On x86, this corresponds to roughly 200K of stack usage.
! XXX: For libmudflapth, this could be a function of __mf_opts.thread_stack. */
! sp->max_depth = 2500;
! sp->rebalance_p = sp->depth = 0;
!
! splay_tree_splay_helper (sp, key, &sp->root, NULL, NULL);
! if (sp->rebalance_p)
{
! splay_tree_rebalance (sp);
!
! sp->rebalance_p = sp->depth = 0;
! splay_tree_splay_helper (sp, key, &sp->root, NULL, NULL);
!
! if (sp->rebalance_p)
! abort ();
}
!
! /* Cache this splay key. */
! sp->last_splayed_key = key;
! sp->last_splayed_key_p = 1;
}
+ /* Allocate a new splay tree. */
splay_tree
splay_tree_new ()
{
! splay_tree sp = splay_tree_xmalloc (sizeof (struct splay_tree_s));
! sp->root = NULL;
sp->last_splayed_key_p = 0;
+ sp->num_keys = 0;
return sp;
}
/* Insert a new node (associating KEY with DATA) into SP. If a
previous node with the indicated KEY exists, its data is replaced
with the new value. Returns the new node. */
splay_tree_node
! splay_tree_insert (splay_tree sp, splay_tree_key key, splay_tree_value value)
{
int comparison = 0;
*************** splay_tree_insert (sp, key, value)
*** 326,337 ****
/* 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;
!
if (!sp->root)
node->left = node->right = 0;
else if (comparison < 0)
--- 326,335 ----
/* Create a new node, and insert it at the root. */
splay_tree_node node;
! node = splay_tree_xmalloc (sizeof (struct splay_tree_node_s));
node->key = key;
node->value = value;
! sp->num_keys++;
if (!sp->root)
node->left = node->right = 0;
else if (comparison < 0)
*************** splay_tree_insert (sp, key, value)
*** 357,385 ****
/* Remove KEY from SP. It is not an error if it did not exist. */
void
! splay_tree_remove (sp, key)
! splay_tree sp;
! splay_tree_key key;
{
splay_tree_splay (sp, key);
sp->last_splayed_key_p = 0;
-
if (sp->root && compare_uintptr_t (sp->root->key, key) == 0)
{
splay_tree_node left, right;
-
left = sp->root->left;
right = sp->root->right;
-
/* Delete the root node itself. */
! (*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. */
if (left)
{
sp->root = left;
-
/* If there was a right child as well, hang it off the
right-most leaf of the left child. */
if (right)
--- 355,377 ----
/* Remove KEY from SP. It is not an error if it did not exist. */
void
! splay_tree_remove (splay_tree sp, splay_tree_key key)
{
splay_tree_splay (sp, key);
sp->last_splayed_key_p = 0;
if (sp->root && compare_uintptr_t (sp->root->key, key) == 0)
{
splay_tree_node left, right;
left = sp->root->left;
right = sp->root->right;
/* Delete the root node itself. */
! splay_tree_free (sp->root);
! sp->num_keys--;
/* One of the children is now the root. Doesn't matter much
which, so long as we preserve the properties of the tree. */
if (left)
{
sp->root = left;
/* If there was a right child as well, hang it off the
right-most leaf of the left child. */
if (right)
*************** splay_tree_remove (sp, key)
*** 398,409 ****
otherwise. */
splay_tree_node
! splay_tree_lookup (sp, key)
! splay_tree sp;
! splay_tree_key key;
{
splay_tree_splay (sp, key);
-
if (sp->root && compare_uintptr_t (sp->root->key, key) == 0)
return sp->root;
else
--- 390,398 ----
otherwise. */
splay_tree_node
! splay_tree_lookup (splay_tree sp, splay_tree_key key)
{
splay_tree_splay (sp, key);
if (sp->root && compare_uintptr_t (sp->root->key, key) == 0)
return sp->root;
else
*************** splay_tree_lookup (sp, key)
*** 413,446 ****
/* Return the node in SP with the greatest key. */
splay_tree_node
! splay_tree_max (sp)
! splay_tree sp;
{
splay_tree_node n = sp->root;
-
if (!n)
return NULL;
-
while (n->right)
n = n->right;
-
return n;
}
/* Return the node in SP with the smallest key. */
splay_tree_node
! splay_tree_min (sp)
! splay_tree sp;
{
splay_tree_node n = sp->root;
-
if (!n)
return NULL;
-
while (n->left)
n = n->left;
-
return n;
}
--- 402,427 ----
/* Return the node in SP with the greatest key. */
splay_tree_node
! splay_tree_max (splay_tree sp)
{
splay_tree_node n = sp->root;
if (!n)
return NULL;
while (n->right)
n = n->right;
return n;
}
/* Return the node in SP with the smallest key. */
splay_tree_node
! splay_tree_min (splay_tree sp)
{
splay_tree_node n = sp->root;
if (!n)
return NULL;
while (n->left)
n = n->left;
return n;
}
*************** splay_tree_min (sp)
*** 448,479 ****
predecessor. KEY need not be present in the tree. */
splay_tree_node
! splay_tree_predecessor (sp, key)
! splay_tree sp;
! splay_tree_key key;
{
int comparison;
splay_tree_node node;
-
/* If the tree is empty, there is certainly no predecessor. */
if (!sp->root)
return NULL;
-
/* 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 = compare_uintptr_t (sp->root->key, key);
-
/* If the predecessor is at the root, just return it. */
if (comparison < 0)
return sp->root;
-
/* Otherwise, find the rightmost element of the left subtree. */
node = sp->root->left;
if (node)
while (node->right)
node = node->right;
-
return node;
}
--- 429,453 ----
predecessor. KEY need not be present in the tree. */
splay_tree_node
! splay_tree_predecessor (splay_tree sp, splay_tree_key key)
{
int comparison;
splay_tree_node node;
/* If the tree is empty, there is certainly no predecessor. */
if (!sp->root)
return NULL;
/* 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 = compare_uintptr_t (sp->root->key, key);
/* If the predecessor is at the root, just return it. */
if (comparison < 0)
return sp->root;
/* Otherwise, find the rightmost element of the left subtree. */
node = sp->root->left;
if (node)
while (node->right)
node = node->right;
return node;
}
*************** splay_tree_predecessor (sp, key)
*** 481,525 ****
successor. KEY need not be present in the tree. */
splay_tree_node
! splay_tree_successor (sp, key)
! splay_tree sp;
! splay_tree_key key;
{
int comparison;
splay_tree_node node;
-
/* If the tree is empty, there is certainly no successor. */
if (!sp->root)
return NULL;
-
/* 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 = compare_uintptr_t (sp->root->key, key);
-
/* If the successor is at the root, just return it. */
if (comparison > 0)
return sp->root;
-
/* Otherwise, find the leftmost element of the right subtree. */
node = sp->root->right;
if (node)
while (node->left)
node = node->left;
-
return node;
}
/* Call FN, passing it the DATA, for every node in SP, following an
in-order traversal. If FN every returns a non-zero value, the
iteration ceases immediately, and the value is returned.
! Otherwise, this function returns 0. */
int
! splay_tree_foreach (sp, fn, data)
! splay_tree sp;
! splay_tree_foreach_fn fn;
! void *data;
{
! return splay_tree_foreach_helper (sp, sp->root, fn, data);
}
--- 455,565 ----
successor. KEY need not be present in the tree. */
splay_tree_node
! splay_tree_successor (splay_tree sp, splay_tree_key key)
{
int comparison;
splay_tree_node node;
/* If the tree is empty, there is certainly no successor. */
if (!sp->root)
return NULL;
/* 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 = compare_uintptr_t (sp->root->key, key);
/* If the successor is at the root, just return it. */
if (comparison > 0)
return sp->root;
/* Otherwise, find the leftmost element of the right subtree. */
node = sp->root->right;
if (node)
while (node->left)
node = node->left;
return node;
}
/* Call FN, passing it the DATA, for every node in SP, following an
in-order traversal. If FN every returns a non-zero value, the
iteration ceases immediately, and the value is returned.
! Otherwise, this function returns 0.
+ This function simulates recursion using dynamically allocated
+ arrays, since it may be called from splay_tree_rebalance(), which
+ in turn means that the tree is already uncomfortably deep for stack
+ space limits. */
int
! splay_tree_foreach (splay_tree st, splay_tree_foreach_fn fn, void *data)
{
! splay_tree_node *stack1;
! char *stack2;
! unsigned sp;
! int val = 0;
! enum s { s_left, s_here, s_right, s_up };
!
! if (st->root == NULL) /* => num_keys == 0 */
! return 0;
!
! stack1 = splay_tree_xmalloc (sizeof (splay_tree_node) * st->num_keys);
! stack2 = splay_tree_xmalloc (sizeof (char) * st->num_keys);
!
! sp = 0;
! stack1 [sp] = st->root;
! stack2 [sp] = s_left;
!
! while (1)
! {
! splay_tree_node n;
! enum s s;
!
! n = stack1 [sp];
! s = stack2 [sp];
!
! /* Handle each of the four possible states separately. */
!
! /* 1: We're here to traverse the left subtree (if any). */
! if (s == s_left)
! {
! stack2 [sp] = s_here;
! if (n->left != NULL)
! {
! sp ++;
! stack1 [sp] = n->left;
! stack2 [sp] = s_left;
! }
! }
!
! /* 2: We're here to traverse this node. */
! else if (s == s_here)
! {
! stack2 [sp] = s_right;
! val = (*fn) (n, data);
! if (val) break;
! }
!
! /* 3: We're here to traverse the right subtree (if any). */
! else if (s == s_right)
! {
! stack2 [sp] = s_up;
! if (n->right != NULL)
! {
! sp ++;
! stack1 [sp] = n->right;
! stack2 [sp] = s_left;
! }
! }
!
! /* 4: We're here after both subtrees (if any) have been traversed. */
! else if (s == s_up)
! {
! /* Pop the stack. */
! if (sp == 0) break; /* Popping off the root note: we're finished! */
! sp --;
! }
!
! else
! abort ();
! }
!
! splay_tree_free (stack1);
! splay_tree_free (stack2);
! return val;
}
Index: splay-tree.h
===================================================================
RCS file: /cvs/gcc/gcc/libmudflap/splay-tree.h,v
retrieving revision 1.1
diff -c -p -s -w -r1.1 splay-tree.h
*** splay-tree.h 29 Jun 2004 22:30:53 -0000 1.1
--- splay-tree.h 8 Jul 2004 18:58:31 -0000
***************
*** 1,7 ****
/* A splay-tree datatype.
Copyright 1998, 1999, 2000, 2002, 2004 Free Software Foundation, Inc.
Contributed by Mark Mitchell (mark@markmitchell.com).
! Adapted for libmudflap from libiberty.
This file is part of GCC.
--- 1,7 ----
/* A splay-tree datatype.
Copyright 1998, 1999, 2000, 2002, 2004 Free Software Foundation, Inc.
Contributed by Mark Mitchell (mark@markmitchell.com).
! Adapted for libmudflap from libiberty by Frank Ch. Eigler <fche@redhat.com>.
This file is part of GCC.
*************** Boston, MA 02111-1307, USA. */
*** 26,48 ****
Algorithms. Harper-Collins, Inc. 1991.
The major feature of splay trees is that all basic tree operations
! are amortized O(log n) time for a tree with n nodes. */
#ifndef _SPLAY_TREE_H
#define _SPLAY_TREE_H
- #ifdef __cplusplus
- extern "C" {
- #endif /* __cplusplus */
-
- #define PARAMS(X) X
- #define PTR void *
- #define ATTRIBUTE_UNUSED __attribute__((__unused__))
-
- #ifndef GTY
- #define GTY(X)
- #endif
-
/* Use typedefs for the key and data types to facilitate changing
these types, if necessary. These types should be sufficiently wide
that any pointer or scalar can be cast to these types, and then
--- 26,41 ----
Algorithms. Harper-Collins, Inc. 1991.
The major feature of splay trees is that all basic tree operations
! are amortized O(log n) time for a tree with n nodes.
!
! This version has been further modified to periodically rebalance
! the entire tree, should degenerate access patterns result in a very
! lopsided tree.
! */
#ifndef _SPLAY_TREE_H
#define _SPLAY_TREE_H
/* Use typedefs for the key and data types to facilitate changing
these types, if necessary. These types should be sufficiently wide
that any pointer or scalar can be cast to these types, and then
*************** typedef void *splay_tree_value;
*** 54,136 ****
typedef struct splay_tree_node_s *splay_tree_node;
/* 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 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. */
! struct splay_tree_node_s GTY(())
{
! /* The key. */
! splay_tree_key GTY ((use_param1)) key;
!
! /* The value. */
! splay_tree_value GTY ((use_param2)) value;
!
! /* The left and right children, respectively. */
! splay_tree_node GTY ((use_params)) left;
! splay_tree_node GTY ((use_params)) right;
};
/* The splay tree itself. */
! struct splay_tree_s GTY(())
{
/* The root of the tree. */
! splay_tree_node GTY ((use_params)) root;
!
! /* Allocate/free functions, and a data pointer to pass to them. */
! splay_tree_allocate_fn allocate;
! splay_tree_deallocate_fn deallocate;
! PTR GTY((skip)) allocate_data;
/* The last key value for which the tree has been splayed, but not
since modified. */
! splay_tree_key GTY ((use_param1)) last_splayed_key;
int last_splayed_key_p;
};
typedef struct splay_tree_s *splay_tree;
! extern splay_tree splay_tree_new PARAMS((void));
! extern void splay_tree_delete PARAMS((splay_tree));
! extern splay_tree_node splay_tree_insert
! PARAMS((splay_tree,
! splay_tree_key,
! splay_tree_value));
! extern void splay_tree_remove PARAMS((splay_tree,
! splay_tree_key));
! extern splay_tree_node splay_tree_lookup
! PARAMS((splay_tree,
! splay_tree_key));
! extern splay_tree_node splay_tree_predecessor
! PARAMS((splay_tree,
! splay_tree_key));
! extern splay_tree_node splay_tree_successor
! PARAMS((splay_tree,
! splay_tree_key));
! extern splay_tree_node splay_tree_max
! PARAMS((splay_tree));
! extern splay_tree_node splay_tree_min
! PARAMS((splay_tree));
! extern int splay_tree_foreach PARAMS((splay_tree,
! splay_tree_foreach_fn,
! void*));
! extern int splay_tree_compare_ints PARAMS((splay_tree_key,
! splay_tree_key));
! extern int splay_tree_compare_pointers PARAMS((splay_tree_key,
! splay_tree_key));
!
! #ifdef __cplusplus
! }
! #endif /* __cplusplus */
#endif /* _SPLAY_TREE_H */
--- 47,96 ----
typedef struct splay_tree_node_s *splay_tree_node;
/* The type of a function used to iterate over the tree. */
! typedef int (*splay_tree_foreach_fn) (splay_tree_node, void *);
/* The nodes in the splay tree. */
! struct splay_tree_node_s
{
! /* Data. */
! splay_tree_key key;
! splay_tree_value value;
! /* Children. */
! splay_tree_node left;
! splay_tree_node right;
};
/* The splay tree itself. */
! struct splay_tree_s
{
/* The root of the tree. */
! splay_tree_node root;
/* The last key value for which the tree has been splayed, but not
since modified. */
! splay_tree_key last_splayed_key;
int last_splayed_key_p;
+
+ /* Statistics. */
+ unsigned num_keys;
+
+ /* Traversal recursion control flags. */
+ unsigned max_depth;
+ unsigned depth;
+ unsigned rebalance_p;
};
typedef struct splay_tree_s *splay_tree;
! extern splay_tree splay_tree_new (void);
! extern splay_tree_node splay_tree_insert (splay_tree, splay_tree_key, splay_tree_value);
! extern void splay_tree_remove (splay_tree, splay_tree_key);
! extern splay_tree_node splay_tree_lookup (splay_tree, splay_tree_key);
! extern splay_tree_node splay_tree_predecessor (splay_tree, splay_tree_key);
! extern splay_tree_node splay_tree_successor (splay_tree, splay_tree_key);
! 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 void splay_tree_rebalance (splay_tree sp);
!
#endif /* _SPLAY_TREE_H */
Index: testsuite/libmudflap.c/heap-scalestress.c
===================================================================
RCS file: testsuite/libmudflap.c/heap-scalestress.c
diff -N testsuite/libmudflap.c/heap-scalestress.c
*** /dev/null 1 Jan 1970 00:00:00 -0000
--- testsuite/libmudflap.c/heap-scalestress.c 8 Jul 2004 18:58:31 -0000
***************
*** 0 ****
--- 1,79 ----
+ /* zz30
+ *
+ * demonstrate a splay-tree depth problem
+ */
+
+ #include <stdlib.h>
+ #include <stdio.h>
+ #include <unistd.h>
+
+ #ifndef SCALE
+ #define SCALE 100000
+ #endif
+
+
+ struct list
+ {
+ struct list *next;
+ };
+
+
+ int
+ main ()
+ {
+ struct list *head = NULL;
+ struct list *tail = NULL;
+ struct list *p;
+ long n;
+ int direction;
+
+ for (direction = 0; direction < 2; direction++)
+ {
+ fprintf (stdout, "allocating\n");
+ fflush (stdout);
+
+ for (n = 0; n < SCALE; ++n)
+ {
+ p = malloc (sizeof *p);
+ if (NULL == p)
+ {
+ fprintf (stdout, "malloc failed\n");
+ break;
+ }
+ if (direction == 0)
+ { /* add at tail */
+ p->next = NULL;
+ if (NULL != tail)
+ tail->next = p;
+ else
+ head = p;
+ tail = p;
+ }
+ else
+ { /* add at head */
+ p->next = head;
+ if (NULL == tail)
+ tail = p;
+ head = p;
+ }
+ }
+
+ fprintf (stdout, "freeing\n");
+ fflush (stdout);
+
+ while (NULL != head)
+ {
+ p = head;
+ head = head->next;
+ free (p);
+ }
+
+ }
+
+ fprintf (stdout, "done\n");
+ fflush (stdout);
+
+ return (0);
+ }
+
+ /* { dg-output "allocating.*freeing.*allocating.*freeing.*done" } */
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2004-07-08 19:16 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2004-07-08 20:07 [libmudflap] splay tree improvements Frank Ch. Eigler
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).