From dfdf6a9440609d8a58c6625b31d34509dd2df838 Mon Sep 17 00:00:00 2001 From: "Frank Ch. Eigler" Date: Tue, 29 Jun 2004 22:30:53 +0000 Subject: [PATCH] [multiple changes] 2004-06-29 Frank Ch. Eigler Splay tree implementation fork. * splay-tree.c, splay-tree.h: Copied & modified from libiberty. Use hard-coded comparison function for uintptr_t. Remove key/value deallocation logic. Cache last splayed key for consecutive lookups. * Makefile.am, Makefile.in: Use them, don't link to them. * mf-runtime.c (__mf_object_tree): Adapt to simpler splay_tree_new. (__mf_find_objects2): Flip successor/predecessor search sequence. * ansidecl.h, libiberty.h: Removed dummy files. 2004-06-29 Nick Clifton From-SVN: r83879 --- libmudflap/ChangeLog | 11 + libmudflap/Makefile.am | 9 - libmudflap/Makefile.in | 10 - libmudflap/ansidecl.h | 4 - libmudflap/libiberty.h | 1 - libmudflap/mf-runtime.c | 4 +- libmudflap/splay-tree.c | 525 ++++++++++++++++++++++++++++++++++++++++ libmudflap/splay-tree.h | 136 +++++++++++ 8 files changed, 674 insertions(+), 26 deletions(-) delete mode 100644 libmudflap/ansidecl.h delete mode 100644 libmudflap/libiberty.h create mode 100644 libmudflap/splay-tree.c create mode 100644 libmudflap/splay-tree.h diff --git a/libmudflap/ChangeLog b/libmudflap/ChangeLog index 94f81dffbb0..20545cdf9ef 100644 --- a/libmudflap/ChangeLog +++ b/libmudflap/ChangeLog @@ -1,3 +1,14 @@ +2004-06-29 Frank Ch. Eigler + + Splay tree implementation fork. + * splay-tree.c, splay-tree.h: Copied & modified from libiberty. + Use hard-coded comparison function for uintptr_t. Remove key/value + deallocation logic. Cache last splayed key for consecutive lookups. + * Makefile.am, Makefile.in: Use them, don't link to them. + * mf-runtime.c (__mf_object_tree): Adapt to simpler splay_tree_new. + (__mf_find_objects2): Flip successor/predecessor search sequence. + * ansidecl.h, libiberty.h: Removed dummy files. + 2004-06-29 Nick Clifton * configure.ac (AC_CHECK_HEADERS): Add dirent.h diff --git a/libmudflap/Makefile.am b/libmudflap/Makefile.am index 639db4218d4..457737141b5 100644 --- a/libmudflap/Makefile.am +++ b/libmudflap/Makefile.am @@ -20,14 +20,6 @@ endif toolexeclib_LTLIBRARIES = libmudflap.la $(libmudflapth) include_HEADERS = mf-runtime.h -# Copy this out of libiberty's source tree, so it can be built here via libtool -splay-tree.c: - rm -f $@ - $(LN_S) $(srcdir)/../libiberty/splay-tree.c $@ -# Copy this so that top-level include/ does not have to be put into -I path -splay-tree.h: - rm -f $@ - $(LN_S) $(srcdir)/../include/splay-tree.h $@ libmudflap_la_SOURCES = \ mf-runtime.c \ @@ -40,7 +32,6 @@ libmudflap_la_DEPENDENCIES = $(libmudflap_la_LIBADD) clean-local: rm -f pth/*.o pth/*.lo - rm -f splay-tree.c splay-tree.h pth/mf-runtime.lo: mf-runtime.c mf-runtime.h mf-impl.h splay-tree.c splay-tree.h $(LTCOMPILE) -DLIBMUDFLAPTH -c $(srcdir)/mf-runtime.c -o $@ diff --git a/libmudflap/Makefile.in b/libmudflap/Makefile.in index 787007ac66b..75547e50f9a 100644 --- a/libmudflap/Makefile.in +++ b/libmudflap/Makefile.in @@ -817,20 +817,10 @@ uninstall-info: uninstall-info-recursive uninstall uninstall-am uninstall-includeHEADERS \ uninstall-info-am uninstall-toolexeclibLTLIBRARIES - -# Copy this out of libiberty's source tree, so it can be built here via libtool -splay-tree.c: - rm -f $@ - $(LN_S) $(srcdir)/../libiberty/splay-tree.c $@ -# Copy this so that top-level include/ does not have to be put into -I path -splay-tree.h: - rm -f $@ - $(LN_S) $(srcdir)/../include/splay-tree.h $@ mf-runtime.lo: mf-runtime.c splay-tree.c splay-tree.h clean-local: rm -f pth/*.o pth/*.lo - rm -f splay-tree.c splay-tree.h pth/mf-runtime.lo: mf-runtime.c mf-runtime.h mf-impl.h splay-tree.c splay-tree.h $(LTCOMPILE) -DLIBMUDFLAPTH -c $(srcdir)/mf-runtime.c -o $@ diff --git a/libmudflap/ansidecl.h b/libmudflap/ansidecl.h deleted file mode 100644 index 26e83d021bd..00000000000 --- a/libmudflap/ansidecl.h +++ /dev/null @@ -1,4 +0,0 @@ -/* A minimal ansidecl.h file for use by splay-tree only. */ -#define PARAMS(X) X -#define PTR void * -#define ATTRIBUTE_UNUSED __attribute__((__unused__)) diff --git a/libmudflap/libiberty.h b/libmudflap/libiberty.h deleted file mode 100644 index 2b752576db9..00000000000 --- a/libmudflap/libiberty.h +++ /dev/null @@ -1 +0,0 @@ -/* Placeholder for splay-tree use only. */ diff --git a/libmudflap/mf-runtime.c b/libmudflap/mf-runtime.c index c1f0a6a4828..f1cd0a22db7 100644 --- a/libmudflap/mf-runtime.c +++ b/libmudflap/mf-runtime.c @@ -610,7 +610,7 @@ __mf_object_tree (int type) static splay_tree trees [__MF_TYPE_MAX+1]; assert (type >= 0 && type <= __MF_TYPE_MAX); if (UNLIKELY (trees[type] == NULL)) - trees[type] = splay_tree_new (splay_tree_compare_pointers, NULL, NULL); + trees[type] = splay_tree_new (); return trees[type]; } @@ -1390,7 +1390,7 @@ __mf_find_objects2 (uintptr_t ptr_low, uintptr_t ptr_high, { __mf_object_t *obj; - n = (direction == 0 ? splay_tree_predecessor (t, k) : splay_tree_successor (t, k)); + n = (direction == 0 ? splay_tree_successor (t, k) : splay_tree_predecessor (t, k)); if (n == NULL) break; obj = (__mf_object_t *) n->value; diff --git a/libmudflap/splay-tree.c b/libmudflap/splay-tree.c new file mode 100644 index 00000000000..037baee87d9 --- /dev/null +++ b/libmudflap/splay-tree.c @@ -0,0 +1,525 @@ +/* A splay-tree datatype. + Copyright (C) 1998, 1999, 2000, 2001, 2004 Free Software Foundation, Inc. + Contributed by Mark Mitchell (mark@markmitchell.com). + Adapted for libmudflap from libiberty. + +This file is part of GNU CC. + +GNU CC is free software; you can redistribute it and/or modify it +under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2, or (at your option) +any later version. + +In addition to the permissions in the GNU General Public License, the +Free Software Foundation gives you unlimited permission to link the +compiled version of this file into combinations with other programs, +and to distribute those combinations without any restriction coming +from the use of this file. (The General Public License restrictions +do apply in other respects; for example, they cover modification of +the file, and distribution when not linked into a combine +executable.) + +GNU CC is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GNU CC; see the file COPYING. If not, write to +the Free Software Foundation, 59 Temple Place - Suite 330, +Boston, MA 02111-1307, USA. */ + +/* For an easily readable description of splay-trees, see: + + Lewis, Harry R. and Denenberg, Larry. Data Structures and Their + Algorithms. Harper-Collins, Inc. 1991. */ + +#include +#include +#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*)); + + + +/* Inline comparison function specialized for libmudflap's key type. */ +static inline int +compare_uintptr_t (splay_tree_key k1, splay_tree_key k2) +{ + if ((uintptr_t) k1 < (uintptr_t) k2) + return -1; + else if ((uintptr_t) k1 > (uintptr_t) k2) + return 1; + else + return 0; +} + + + +/* 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; + int comparison; + + n = *node; + + if (!n) + return *parent; + + comparison = compare_uintptr_t (key, n->key); + + if (comparison == 0) + /* We've found the target. */ + next = 0; + else if (comparison < 0) + /* The target is to the left. */ + next = &n->left; + else + /* The target is to the right. */ + next = &n->right; + + 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; + } + + if (!parent) + /* NODE is the root. We are done. */ + return n; + + /* First, handle the case where there is no grandparent (i.e., + *PARENT is the root of the tree.) */ + if (!grandparent) + { + if (n == (*parent)->left) + { + *node = n->right; + n->right = *parent; + } + else + { + *node = n->left; + n->left = *parent; + } + *parent = n; + return n; + } + + /* Next handle the cases where both N and *PARENT are left children, + or where both are right children. */ + if (n == (*parent)->left && *parent == (*grandparent)->left) + { + splay_tree_node p = *parent; + + (*grandparent)->left = p->right; + p->right = *grandparent; + p->left = n->right; + n->right = p; + *grandparent = n; + return n; + } + else if (n == (*parent)->right && *parent == (*grandparent)->right) + { + splay_tree_node p = *parent; + + (*grandparent)->right = p->left; + p->left = *grandparent; + p->right = n->left; + n->left = p; + *grandparent = n; + return n; + } + + /* Finally, deal with the case where N is a left child, but *PARENT + is a right child, or vice versa. */ + if (n == (*parent)->left) + { + (*parent)->left = n->right; + n->right = *parent; + (*grandparent)->right = n->left; + n->left = *grandparent; + *grandparent = n; + return n; + } + else + { + (*parent)->right = n->left; + n->left = *parent; + (*grandparent)->left = n->right; + n->right = *grandparent; + *grandparent = n; + return n; + } +} + +/* 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; + + splay_tree_splay (sp, key); + + if (sp->root) + comparison = compare_uintptr_t (sp->root->key, key); + + if (sp->root && comparison == 0) + { + /* If the root of the tree already has the indicated KEY, just + replace the value with VALUE. */ + sp->root->value = value; + } + else + { + /* 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) + { + node->left = sp->root; + node->right = node->left->right; + node->left->right = 0; + } + else + { + node->right = sp->root; + node->left = node->right->left; + node->right->left = 0; + } + + sp->root = node; + sp->last_splayed_key_p = 0; + } + + return sp->root; +} + +/* 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) + { + while (left->right) + left = left->right; + left->right = right; + } + } + else + sp->root = right; + } +} + +/* Lookup KEY in SP, returning VALUE if present, and NULL + 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 + return 0; +} + +/* 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; +} + +/* Return the immediate predecessor KEY, or NULL if there is no + 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; +} + +/* Return the immediate successor KEY, or NULL if there is no + 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); +} diff --git a/libmudflap/splay-tree.h b/libmudflap/splay-tree.h new file mode 100644 index 00000000000..269394d2109 --- /dev/null +++ b/libmudflap/splay-tree.h @@ -0,0 +1,136 @@ +/* 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. + +GCC is free software; you can redistribute it and/or modify it +under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2, or (at your option) +any later version. + +GCC is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING. If not, write to +the Free Software Foundation, 59 Temple Place - Suite 330, +Boston, MA 02111-1307, USA. */ + +/* For an easily readable description of splay-trees, see: + + Lewis, Harry R. and Denenberg, Larry. Data Structures and Their + 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 + cast back, without loss of precision. */ +typedef uintptr_t splay_tree_key; +typedef void *splay_tree_value; + +/* Forward declaration for a node in the tree. */ +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 */ -- 2.30.2