From: kvigor Date: Sat, 7 Jul 2001 06:08:57 +0000 (+0000) Subject: remove duplicated files X-Git-Url: https://git.gag.com/?p=fw%2Fsdcc;a=commitdiff_plain;h=50458e3879f70505d746ecc47add177f62055239 remove duplicated files git-svn-id: https://sdcc.svn.sourceforge.net/svnroot/sdcc/trunk/sdcc@1039 4a8a32a2-be11-0410-ad9d-d568d2c75423 --- diff --git a/support/cpp2/splay-tree.c b/support/cpp2/splay-tree.c deleted file mode 100644 index a7123952..00000000 --- a/support/cpp2/splay-tree.c +++ /dev/null @@ -1,513 +0,0 @@ -/* 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. - -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. - -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. */ - -#ifdef HAVE_CONFIG_H -#include "config.h" -#endif - -#ifdef HAVE_STDLIB_H -#include -#endif - -#include - -#include "libiberty.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*)); - -/* 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); - - if (sp->delete_key) - (*sp->delete_key)(node->key); - if (sp->delete_value) - (*sp->delete_value)(node->value); - - free ((char*) node); -} - -/* 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 = (*sp->comp) (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; - - splay_tree_splay_helper (sp, key, &sp->root, - /*grandparent=*/0, /*parent=*/0); -} - -/* 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); -} - -/* 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; -} - -/* Deallocate SP. */ - -void -splay_tree_delete (sp) - 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 - 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 = (*sp->comp)(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. */ - if (sp->delete_value) - (*sp->delete_value)(sp->root->value); - sp->root->value = value; - } - else - { - /* 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; - - 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; - } - - 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); - - if (sp->root && (*sp->comp) (sp->root->key, key) == 0) - { - splay_tree_node left, right; - - left = sp->root->left; - right = sp->root->right; - - /* 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. */ - 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 && (*sp->comp)(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 = (*sp->comp)(sp->root->key, key); - - /* If the predecessor 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->left; - if (node) - while (node->right) - node = node->right; - - return node; -} - -/* Return the immediate successor KEY, or NULL if there is no - predecessor. 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 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 = (*sp->comp)(sp->root->key, key); - - /* If the successor 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->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); -} - -/* Splay-tree comparison function, treating the keys as ints. */ - -int -splay_tree_compare_ints (k1, k2) - splay_tree_key k1; - splay_tree_key k2; -{ - if ((int) k1 < (int) k2) - return -1; - else if ((int) k1 > (int) k2) - return 1; - else - return 0; -} - -/* Splay-tree comparison function, treating the keys as pointers. */ - -int -splay_tree_compare_pointers (k1, k2) - splay_tree_key k1; - splay_tree_key k2; -{ - if ((char*) k1 < (char*) k2) - return -1; - else if ((char*) k1 > (char*) k2) - return 1; - else - return 0; -} diff --git a/support/cpp2/splay-tree.h b/support/cpp2/splay-tree.h deleted file mode 100644 index 37e9a359..00000000 --- a/support/cpp2/splay-tree.h +++ /dev/null @@ -1,129 +0,0 @@ -/* A splay-tree datatype. - Copyright 1998, 1999, 2000 Free Software Foundation, Inc. - Contributed by Mark Mitchell (mark@markmitchell.com). - -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. - -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. - - 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 */ - -#include - -/* 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 unsigned long int splay_tree_key; -typedef unsigned long int 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 which compares two splay-tree keys. The - function should return values as for qsort. */ -typedef int (*splay_tree_compare_fn) PARAMS((splay_tree_key, splay_tree_key)); - -/* The type of a function used to deallocate any resources associated - with the key. */ -typedef void (*splay_tree_delete_key_fn) PARAMS((splay_tree_key)); - -/* The type of a function used to deallocate any resources associated - with the value. */ -typedef void (*splay_tree_delete_value_fn) PARAMS((splay_tree_value)); - -/* The type of a function used to iterate over the tree. */ -typedef int (*splay_tree_foreach_fn) PARAMS((splay_tree_node, void*)); - -/* The nodes in the splay tree. */ -struct splay_tree_node_s -{ - /* The key. */ - splay_tree_key key; - - /* The value. */ - splay_tree_value value; - - /* The left and right children, respectively. */ - splay_tree_node left; - splay_tree_node right; -}; - -/* The splay tree itself. */ -typedef struct splay_tree_s -{ - /* The root of the tree. */ - splay_tree_node root; - - /* The comparision function. */ - splay_tree_compare_fn comp; - - /* The deallocate-key function. NULL if no cleanup is necessary. */ - splay_tree_delete_key_fn delete_key; - - /* The deallocate-value function. NULL if no cleanup is necessary. */ - splay_tree_delete_value_fn delete_value; -} *splay_tree; - -extern splay_tree splay_tree_new PARAMS((splay_tree_compare_fn, - splay_tree_delete_key_fn, - splay_tree_delete_value_fn)); -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 */