From 251653b5b4d169b03027373bffdc68aa2d58433d Mon Sep 17 00:00:00 2001 From: eschnett Date: Fri, 15 Jun 2012 20:17:10 +0000 Subject: Remove unused and broken BinaryTree implementation git-svn-id: http://svn.cactuscode.org/flesh/trunk@4834 17b73243-c579-4c4c-a9d2-2d5706c11dac --- src/util/BinaryTree.c | 519 ------------------------------------------------ src/util/make.code.defn | 1 - 2 files changed, 520 deletions(-) delete mode 100644 src/util/BinaryTree.c (limited to 'src/util') diff --git a/src/util/BinaryTree.c b/src/util/BinaryTree.c deleted file mode 100644 index dbd45cdf..00000000 --- a/src/util/BinaryTree.c +++ /dev/null @@ -1,519 +0,0 @@ - /*@@ - @file BinaryTree.c - @date Mon Oct 5 11:00:01 1998 - @author Tom Goodale - @desc - Routines to deal with binary trees - @enddesc - @version $Header$ - @@*/ - -#include -#include -#include - -#include "cctk_Flesh.h" -#include "util_BinaryTree.h" - -static const char *rcsid = "$Header$"; - -CCTK_FILEVERSION(util_BinaryTree_c); - -/******************************************************************** - ******************** External Routines ************************ - ********************************************************************/ - - - /*@@ - @routine Util_BinTreeStoreData - @date Mon Oct 5 11:04:55 1998 - @author Tom Goodale - @desc - Stores data in a binary tree. - @enddesc - @calls - @calledby - @history - - @endhistory - @var root - @vdesc Root of tree - @vtype uBinTree * - @vio in - @vcomment - This is the root of the tree on entry to the routine. - On first entry it should be a NULL variable to create the tree - @endvar - @var subtree - @vdesc Subtree to insert data into - @vtype uBinTree * - @vio in - @vcomment - When called by a user this should always be the same as root. - When called internally it may be different as the tree gets traversed. - @endvar - @var data - @vdesc data to store - @vtype void * - @vio in - @vcomment - - @endvar - @var compare - @vdesc comparison function - @vtype int (*)(const void *, const void *) - @vio in - @vcomment - This function is used to compare two pieces of data. - It should return -ve if the first piece is less than the - second piece, 0 if the are equal, or +ve if the first is - greater than the second. - @endvar - - @returntype uBinTree * - @returndesc - This is the new root of the tree. - @endreturndesc - -@@*/ -uBinTree *Util_BinTreeStoreData(uBinTree *root, - uBinTree *subtree, - void *data, - int (*compare)(const void *, const void *)) -{ - int order; - - if(!subtree) - { - /* Create a new element. */ - subtree = (uBinTree *)malloc(sizeof(uBinTree)); - if(subtree) - { - subtree->left=NULL; - subtree->right=NULL; - - subtree->data = data; - - if(root) - { - if((order = compare(data, root->data)) < 0) - { - root->left = subtree; - } - else - { - root->right = subtree; - } - } - } - } - else - { - /* Go down left or right branch. */ - if((order = compare(data, root->data)) < 0) - { - subtree = Util_BinTreeStoreData(subtree, subtree->left, data, compare); - } - else if(order > 0) - { - subtree = Util_BinTreeStoreData(subtree, subtree->right, data, compare); - } - else if(order==0) - { - /* Duplicate key. */ - subtree = NULL; - } - } - - /* Return either the new node, or NULL if either a duplicate value or - * memory failure. - */ - - return subtree; - -} - - /*@@ - @routine Util_BinTreeTraverseInorder - @date Mon Oct 5 11:05:54 1998 - @author Tom Goodale - @desc - Traverse a tree 'inorder' - @enddesc - @calls - @calledby - @history - - @endhistory - @var root - @vdesc Root of the tree - @vtype uBinTree * - @vio in - @vcomment - - @endvar - @var process - @vdesc function to process each data item - @vtype int (*)(void *, void *) - @vio in - @vcomment - This function is passed the data item and the info item. - If it returns true, this is the last item processed. - @endvar - @var info - @vdesc info data to be passes to process function - @vtype void * - @vio inout - @vcomment - - @endvar - - @returntype int - @returndesc - True - terminate this traversal. - False - continue the traversal. - @endreturndesc - -@@*/ -int Util_BinTreeTraverseInorder(uBinTree *root, - int (*process)(void *, void *), - void *info) -{ - int terminate; - - terminate = 0; - - if(root) - { - terminate = Util_BinTreeTraverseInorder(root->left, process, info); - if(!terminate) terminate = process(root->data,info); - if(!terminate) terminate = Util_BinTreeTraverseInorder(root->right, process, info); - } - - return terminate; -} - - /*@@ - @routine Util_BinTreeTraversePreorder - @date Mon Oct 5 11:05:54 1998 - @author Tom Goodale - @desc - Traverse a tree 'preorder' - @enddesc - @calls - @calledby - @history - - @endhistory - @var root - @vdesc Root of the tree - @vtype uBinTree * - @vio in - @vcomment - - @endvar - @var process - @vdesc function to process each data item - @vtype int (*)(void *, void *) - @vio in - @vcomment - This function is passed the data item and the info item. - If it returns true, this is the last item processed. - @endvar - @var info - @vdesc info data to be passes to process function - @vtype void * - @vio inout - @vcomment - - @endvar - - @returntype int - @returndesc - True - terminate this traversal. - False - continue the traversal. - @endreturndesc - -@@*/ -int Util_BinTreeTraversePreorder(uBinTree *root, - int (*process)(void *, void *), - void *info) -{ - int terminate; - - terminate = 0; - - if(root) - { - terminate = process(root->data, info); - if(!terminate) terminate = Util_BinTreeTraversePreorder(root->left, process, info); - if(!terminate) terminate = Util_BinTreeTraversePreorder(root->right, process,info); - } - - return terminate; -} - - /*@@ - @routine Util_BinTreeTraversePostorder - @date Mon Oct 5 11:05:54 1998 - @author Tom Goodale - @desc - Traverse a tree 'postorder' - @enddesc - @calls - @calledby - @history - - @endhistory - @var root - @vdesc Root of the tree - @vtype uBinTree * - @vio in - @vcomment - - @endvar - @var process - @vdesc function to process each data item - @vtype int (*)(void *, void *) - @vio in - @vcomment - This function is passed the data item and the info item. - If it returns true, this is the last item processed. - @endvar - @var info - @vdesc info data to be passes to process function - @vtype void * - @vio inout - @vcomment - - @endvar - - @returntype int - @returndesc - True - terminate this traversal. - False - continue the traversal. - @endreturndesc - -@@*/ -int Util_BinTreeTraversePostorder(uBinTree *root, - int (*process)(void *, void *), - void *info) -{ - int terminate; - - terminate = 0; - - if(root) - { - terminate = Util_BinTreeTraversePostorder(root->left, process, info); - if(!terminate) terminate = Util_BinTreeTraversePostorder(root->right, process, info); - if(!terminate) terminate = process(root->data, info); - } - - return terminate; -} - - /*@@ - @routine Util_BinTreePrintNodes - @date Mon Oct 5 11:06:52 1998 - @author Tom Goodale - @desc - Allows a binary tree to be printed out. - @enddesc - @calls - @calledby - @history - - @endhistory - @var root - @vdesc Root of tree - @vtype uBinTree * - @vio in - @vcomment - - @endvar - @var depth - @vdesc current depth - @vtype int - @vio in - @vcomment - This will normally be 0 when a user calls it. - @endvar - @var print_node - @vdesc Function to print data about a node - @vtype void (*)(void *, int) - @vio in - @vcomment - This gets passed the data item and the depth. - @endvar - - @returntype int - @returndesc - Always 0. - @endreturndesc -@@*/ -int Util_BinTreePrintNodes(uBinTree *root, - int depth, - void (*print_node)(void *, int)) -{ - if(root) - { - Util_BinTreePrintNodes(root->left, depth+1,print_node); - print_node(root->data,depth); - Util_BinTreePrintNodes(root->right, depth+1, print_node); - } - return 0; -} - - - /*@@ - @routine Util_BinTreeFindNode - @date Mon Oct 5 11:06:52 1998 - @author Tom Goodale - @desc - Find a node. - @enddesc - @calls - @calledby - @history - - @endhistory - @var root - @vdesc Root of tree - @vtype uBinTree * - @vio in - @vcomment - - @endvar - @var data - @vdesc Data to compare a node against. - @vtype void * - @vio in - @vcomment - - @endvar - @var compare - @vdesc comparison function - @vtype int (*)(const void *, const void *) - @vio in - @vcomment - This function is used to compare two pieces of data. - It should return -ve if the first piece is less than the - second piece, 0 if the are equal, or +ve if the first is - greater than the second. - This is passed the input data and the data from the node in - that order. - @endvar - - @returntype uBinTree * - @returndesc - The data if found, otherwise NULL - @endreturndesc - -@@*/ -uBinTree *Util_BinTreeFindNode(uBinTree *root, - void *data, - int (*compare)(const void *, const void *)) -{ - int order; - - uBinTree *node; - - /* Go down left or right branch. */ - if((order = compare(data, root->data)) < 0) - { - node = Util_BinTreeFindNode(root->left, data, compare); - } - else if(order > 0) - { - node = Util_BinTreeFindNode(root->right, data, compare); - } - else if(order==0) - { - /* Found it. */ - node = root; - } - else - { - node = NULL; - } - - return node; -} - - -/* Stuff to test the routines. */ - -/*#define TEST_BinaryTree*/ -#ifdef TEST_BinaryTree - -typedef struct -{ - int i; -} t_infodata ; - -int process(char *data, t_infodata *infodata) -{ - printf("%d, %s\n", infodata->i, data); - - infodata->i++; - - return 0; -} - -void print_node(char *data, int depth) -{ - int i; - for(i=0; i < depth; i++) printf("*"); - printf("%s\n", data); -} - -int main(void) -{ - uBinTree *root; - t_infodata infodata; - char instring[500]; - char *newstring; - uBinTree *node; - - infodata.i=0; - - root = NULL; - - while(scanf("%s", instring) && strcmp("quit", instring)) - { - newstring = malloc(strlen(instring)*sizeof(char)); - strcpy(newstring, instring); - - if(!root) - { - root = Util_BinTreeStoreData(root, root, newstring, (int (*)(const void *, const void *))strcmp); - } - else - { - Util_BinTreeStoreData(root, root, newstring, (int (*)(const void *, const void *))strcmp); - } - } - - Util_BinTreeTraverseInorder(root, (int (*)(void *, void *))process, (void *)&infodata); - - Util_BinTreePrintNodes(root, 0, (void (*)(void *, int))print_node); - - printf("String to find ? "); - scanf("%s", instring); - - node = Util_BinTreeFindNode(root, instring, (int (*)(const void *, const void *))strcmp); - - if(node) - { - printf("Found a node, node->data is %s\n", node->data); - } - else - { - printf("Unable to find node with %s\n", instring); - } - - return 0; -} - -#endif diff --git a/src/util/make.code.defn b/src/util/make.code.defn index 3c4996d4..547e1459 100644 --- a/src/util/make.code.defn +++ b/src/util/make.code.defn @@ -1,7 +1,6 @@ # $Header$ SRCS=\ -BinaryTree.c\ CactusTimers.c\ File.c\ ParseFile.c\ -- cgit v1.2.3