130fdf1140b8d1ce93f3821d986fa165552023440lgao/* Abstract syntax tree manipulation functions 230fdf1140b8d1ce93f3821d986fa165552023440lgao * 330fdf1140b8d1ce93f3821d986fa165552023440lgao * SOFTWARE RIGHTS 430fdf1140b8d1ce93f3821d986fa165552023440lgao * 530fdf1140b8d1ce93f3821d986fa165552023440lgao * We reserve no LEGAL rights to the Purdue Compiler Construction Tool 630fdf1140b8d1ce93f3821d986fa165552023440lgao * Set (PCCTS) -- PCCTS is in the public domain. An individual or 730fdf1140b8d1ce93f3821d986fa165552023440lgao * company may do whatever they wish with source code distributed with 830fdf1140b8d1ce93f3821d986fa165552023440lgao * PCCTS or the code generated by PCCTS, including the incorporation of 930fdf1140b8d1ce93f3821d986fa165552023440lgao * PCCTS, or its output, into commerical software. 1030fdf1140b8d1ce93f3821d986fa165552023440lgao * 1130fdf1140b8d1ce93f3821d986fa165552023440lgao * We encourage users to develop software with PCCTS. However, we do ask 1230fdf1140b8d1ce93f3821d986fa165552023440lgao * that credit is given to us for developing PCCTS. By "credit", 1330fdf1140b8d1ce93f3821d986fa165552023440lgao * we mean that if you incorporate our source code into one of your 1430fdf1140b8d1ce93f3821d986fa165552023440lgao * programs (commercial product, research project, or otherwise) that you 1530fdf1140b8d1ce93f3821d986fa165552023440lgao * acknowledge this fact somewhere in the documentation, research report, 1630fdf1140b8d1ce93f3821d986fa165552023440lgao * etc... If you like PCCTS and have developed a nice tool with the 1730fdf1140b8d1ce93f3821d986fa165552023440lgao * output, please mention that you developed it using PCCTS. In 1830fdf1140b8d1ce93f3821d986fa165552023440lgao * addition, we ask that this header remain intact in our source code. 1930fdf1140b8d1ce93f3821d986fa165552023440lgao * As long as these guidelines are kept, we expect to continue enhancing 2030fdf1140b8d1ce93f3821d986fa165552023440lgao * this system and expect to make other tools available as they are 2130fdf1140b8d1ce93f3821d986fa165552023440lgao * completed. 2230fdf1140b8d1ce93f3821d986fa165552023440lgao * 2330fdf1140b8d1ce93f3821d986fa165552023440lgao * ANTLR 1.33 2430fdf1140b8d1ce93f3821d986fa165552023440lgao * Terence Parr 2530fdf1140b8d1ce93f3821d986fa165552023440lgao * Parr Research Corporation 2630fdf1140b8d1ce93f3821d986fa165552023440lgao * with Purdue University and AHPCRC, University of Minnesota 2730fdf1140b8d1ce93f3821d986fa165552023440lgao * 1989-2000 2830fdf1140b8d1ce93f3821d986fa165552023440lgao */ 2930fdf1140b8d1ce93f3821d986fa165552023440lgao 3030fdf1140b8d1ce93f3821d986fa165552023440lgao#include "pcctscfg.h" 3130fdf1140b8d1ce93f3821d986fa165552023440lgao 3230fdf1140b8d1ce93f3821d986fa165552023440lgao#ifdef PCCTS_USE_STDARG 3330fdf1140b8d1ce93f3821d986fa165552023440lgao#include "pccts_stdarg.h" 3430fdf1140b8d1ce93f3821d986fa165552023440lgao#else 3530fdf1140b8d1ce93f3821d986fa165552023440lgao#include <varargs.h> 3630fdf1140b8d1ce93f3821d986fa165552023440lgao#endif 3730fdf1140b8d1ce93f3821d986fa165552023440lgao 3830fdf1140b8d1ce93f3821d986fa165552023440lgao/* ensure that tree manipulation variables are current after a rule 3930fdf1140b8d1ce93f3821d986fa165552023440lgao * reference 4030fdf1140b8d1ce93f3821d986fa165552023440lgao */ 4130fdf1140b8d1ce93f3821d986fa165552023440lgao 4230fdf1140b8d1ce93f3821d986fa165552023440lgaovoid 4330fdf1140b8d1ce93f3821d986fa165552023440lgao#ifdef __USE_PROTOS 4430fdf1140b8d1ce93f3821d986fa165552023440lgaozzlink(AST **_root, AST **_sibling, AST **_tail) 4530fdf1140b8d1ce93f3821d986fa165552023440lgao#else 4630fdf1140b8d1ce93f3821d986fa165552023440lgaozzlink(_root, _sibling, _tail) 4730fdf1140b8d1ce93f3821d986fa165552023440lgaoAST **_root, **_sibling, **_tail; 4830fdf1140b8d1ce93f3821d986fa165552023440lgao#endif 4930fdf1140b8d1ce93f3821d986fa165552023440lgao{ 5030fdf1140b8d1ce93f3821d986fa165552023440lgao if ( *_sibling == NULL ) return; 5130fdf1140b8d1ce93f3821d986fa165552023440lgao if ( *_root == NULL ) *_root = *_sibling; 5230fdf1140b8d1ce93f3821d986fa165552023440lgao else if ( *_root != *_sibling ) (*_root)->down = *_sibling; 5330fdf1140b8d1ce93f3821d986fa165552023440lgao if ( *_tail==NULL ) *_tail = *_sibling; 5430fdf1140b8d1ce93f3821d986fa165552023440lgao while ( (*_tail)->right != NULL ) *_tail = (*_tail)->right; 5530fdf1140b8d1ce93f3821d986fa165552023440lgao} 5630fdf1140b8d1ce93f3821d986fa165552023440lgao 5730fdf1140b8d1ce93f3821d986fa165552023440lgaoAST * 5830fdf1140b8d1ce93f3821d986fa165552023440lgao#ifdef __USE_PROTOS 5930fdf1140b8d1ce93f3821d986fa165552023440lgaozzastnew(void) 6030fdf1140b8d1ce93f3821d986fa165552023440lgao#else 6130fdf1140b8d1ce93f3821d986fa165552023440lgaozzastnew() 6230fdf1140b8d1ce93f3821d986fa165552023440lgao#endif 6330fdf1140b8d1ce93f3821d986fa165552023440lgao{ 6430fdf1140b8d1ce93f3821d986fa165552023440lgao AST *p = (AST *) calloc(1, sizeof(AST)); 6530fdf1140b8d1ce93f3821d986fa165552023440lgao if ( p == NULL ) fprintf(stderr,"%s(%d): cannot allocate AST node\n",__FILE__,__LINE__); 6630fdf1140b8d1ce93f3821d986fa165552023440lgao return p; 6730fdf1140b8d1ce93f3821d986fa165552023440lgao} 6830fdf1140b8d1ce93f3821d986fa165552023440lgao 6930fdf1140b8d1ce93f3821d986fa165552023440lgao/* add a child node to the current sibling list */ 7030fdf1140b8d1ce93f3821d986fa165552023440lgaovoid 7130fdf1140b8d1ce93f3821d986fa165552023440lgao#ifdef __USE_PROTOS 7230fdf1140b8d1ce93f3821d986fa165552023440lgaozzsubchild(AST **_root, AST **_sibling, AST **_tail) 7330fdf1140b8d1ce93f3821d986fa165552023440lgao#else 7430fdf1140b8d1ce93f3821d986fa165552023440lgaozzsubchild(_root, _sibling, _tail) 7530fdf1140b8d1ce93f3821d986fa165552023440lgaoAST **_root, **_sibling, **_tail; 7630fdf1140b8d1ce93f3821d986fa165552023440lgao#endif 7730fdf1140b8d1ce93f3821d986fa165552023440lgao{ 7830fdf1140b8d1ce93f3821d986fa165552023440lgao AST *n; 7930fdf1140b8d1ce93f3821d986fa165552023440lgao zzNON_GUESS_MODE { 8030fdf1140b8d1ce93f3821d986fa165552023440lgao n = zzastnew(); 8130fdf1140b8d1ce93f3821d986fa165552023440lgao#ifdef DEMAND_LOOK 8230fdf1140b8d1ce93f3821d986fa165552023440lgao zzcr_ast(n, &(zzaCur), LA(0), LATEXT(0)); 8330fdf1140b8d1ce93f3821d986fa165552023440lgao#else 8430fdf1140b8d1ce93f3821d986fa165552023440lgao zzcr_ast(n, &(zzaCur), LA(1), LATEXT(1)); 8530fdf1140b8d1ce93f3821d986fa165552023440lgao#endif 8630fdf1140b8d1ce93f3821d986fa165552023440lgao zzastPush( n ); 8730fdf1140b8d1ce93f3821d986fa165552023440lgao if ( *_tail != NULL ) (*_tail)->right = n; 8830fdf1140b8d1ce93f3821d986fa165552023440lgao else { 8930fdf1140b8d1ce93f3821d986fa165552023440lgao *_sibling = n; 9030fdf1140b8d1ce93f3821d986fa165552023440lgao if ( *_root != NULL ) (*_root)->down = *_sibling; 9130fdf1140b8d1ce93f3821d986fa165552023440lgao } 9230fdf1140b8d1ce93f3821d986fa165552023440lgao *_tail = n; 9330fdf1140b8d1ce93f3821d986fa165552023440lgao if ( *_root == NULL ) *_root = *_sibling; 9430fdf1140b8d1ce93f3821d986fa165552023440lgao } 9530fdf1140b8d1ce93f3821d986fa165552023440lgao} 9630fdf1140b8d1ce93f3821d986fa165552023440lgao 9730fdf1140b8d1ce93f3821d986fa165552023440lgao/* make a new AST node. Make the newly-created 9830fdf1140b8d1ce93f3821d986fa165552023440lgao * node the root for the current sibling list. If a root node already 9930fdf1140b8d1ce93f3821d986fa165552023440lgao * exists, make the newly-created node the root of the current root. 10030fdf1140b8d1ce93f3821d986fa165552023440lgao */ 10130fdf1140b8d1ce93f3821d986fa165552023440lgaovoid 10230fdf1140b8d1ce93f3821d986fa165552023440lgao#ifdef __USE_PROTOS 10330fdf1140b8d1ce93f3821d986fa165552023440lgaozzsubroot(AST **_root, AST **_sibling, AST **_tail) 10430fdf1140b8d1ce93f3821d986fa165552023440lgao#else 10530fdf1140b8d1ce93f3821d986fa165552023440lgaozzsubroot(_root, _sibling, _tail) 10630fdf1140b8d1ce93f3821d986fa165552023440lgaoAST **_root, **_sibling, **_tail; 10730fdf1140b8d1ce93f3821d986fa165552023440lgao#endif 10830fdf1140b8d1ce93f3821d986fa165552023440lgao{ 10930fdf1140b8d1ce93f3821d986fa165552023440lgao AST *n; 11030fdf1140b8d1ce93f3821d986fa165552023440lgao zzNON_GUESS_MODE { 11130fdf1140b8d1ce93f3821d986fa165552023440lgao n = zzastnew(); 11230fdf1140b8d1ce93f3821d986fa165552023440lgao#ifdef DEMAND_LOOK 11330fdf1140b8d1ce93f3821d986fa165552023440lgao zzcr_ast(n, &(zzaCur), LA(0), LATEXT(0)); 11430fdf1140b8d1ce93f3821d986fa165552023440lgao#else 11530fdf1140b8d1ce93f3821d986fa165552023440lgao zzcr_ast(n, &(zzaCur), LA(1), LATEXT(1)); 11630fdf1140b8d1ce93f3821d986fa165552023440lgao#endif 11730fdf1140b8d1ce93f3821d986fa165552023440lgao zzastPush( n ); 11830fdf1140b8d1ce93f3821d986fa165552023440lgao if ( *_root != NULL ) 11930fdf1140b8d1ce93f3821d986fa165552023440lgao if ( (*_root)->down == *_sibling ) *_sibling = *_tail = *_root; 12030fdf1140b8d1ce93f3821d986fa165552023440lgao *_root = n; 12130fdf1140b8d1ce93f3821d986fa165552023440lgao (*_root)->down = *_sibling; 12230fdf1140b8d1ce93f3821d986fa165552023440lgao } 12330fdf1140b8d1ce93f3821d986fa165552023440lgao} 12430fdf1140b8d1ce93f3821d986fa165552023440lgao 12530fdf1140b8d1ce93f3821d986fa165552023440lgao/* Apply function to root then each sibling 12630fdf1140b8d1ce93f3821d986fa165552023440lgao * example: print tree in child-sibling LISP-format (AST has token field) 12730fdf1140b8d1ce93f3821d986fa165552023440lgao * 12830fdf1140b8d1ce93f3821d986fa165552023440lgao * void show(tree) 12930fdf1140b8d1ce93f3821d986fa165552023440lgao * AST *tree; 13030fdf1140b8d1ce93f3821d986fa165552023440lgao * { 13130fdf1140b8d1ce93f3821d986fa165552023440lgao * if ( tree == NULL ) return; 13230fdf1140b8d1ce93f3821d986fa165552023440lgao * printf(" %s", zztokens[tree->token]); 13330fdf1140b8d1ce93f3821d986fa165552023440lgao * } 13430fdf1140b8d1ce93f3821d986fa165552023440lgao * 13530fdf1140b8d1ce93f3821d986fa165552023440lgao * void before() { printf(" ("); } 13630fdf1140b8d1ce93f3821d986fa165552023440lgao * void after() { printf(" )"); } 13730fdf1140b8d1ce93f3821d986fa165552023440lgao * 13830fdf1140b8d1ce93f3821d986fa165552023440lgao * LISPdump() { zzpre_ast(tree, show, before, after); } 13930fdf1140b8d1ce93f3821d986fa165552023440lgao * 14030fdf1140b8d1ce93f3821d986fa165552023440lgao */ 14130fdf1140b8d1ce93f3821d986fa165552023440lgaovoid 14230fdf1140b8d1ce93f3821d986fa165552023440lgao#ifdef __USE_PROTOS 14330fdf1140b8d1ce93f3821d986fa165552023440lgaozzpre_ast( 14430fdf1140b8d1ce93f3821d986fa165552023440lgao AST *tree, 14530fdf1140b8d1ce93f3821d986fa165552023440lgao void (*func)(AST *), /* apply this to each tree node */ 14630fdf1140b8d1ce93f3821d986fa165552023440lgao void (*before)(AST *), /* apply this to root of subtree before preordering it */ 14730fdf1140b8d1ce93f3821d986fa165552023440lgao void (*after)(AST *)) /* apply this to root of subtree after preordering it */ 14830fdf1140b8d1ce93f3821d986fa165552023440lgao#else 14930fdf1140b8d1ce93f3821d986fa165552023440lgaozzpre_ast(tree, func, before, after) 15030fdf1140b8d1ce93f3821d986fa165552023440lgaoAST *tree; 15130fdf1140b8d1ce93f3821d986fa165552023440lgaovoid (*func)(), /* apply this to each tree node */ 15230fdf1140b8d1ce93f3821d986fa165552023440lgao (*before)(), /* apply this to root of subtree before preordering it */ 15330fdf1140b8d1ce93f3821d986fa165552023440lgao (*after)(); /* apply this to root of subtree after preordering it */ 15430fdf1140b8d1ce93f3821d986fa165552023440lgao#endif 15530fdf1140b8d1ce93f3821d986fa165552023440lgao{ 15630fdf1140b8d1ce93f3821d986fa165552023440lgao while ( tree!= NULL ) 15730fdf1140b8d1ce93f3821d986fa165552023440lgao { 15830fdf1140b8d1ce93f3821d986fa165552023440lgao if ( tree->down != NULL ) (*before)(tree); 15930fdf1140b8d1ce93f3821d986fa165552023440lgao (*func)(tree); 16030fdf1140b8d1ce93f3821d986fa165552023440lgao zzpre_ast(tree->down, func, before, after); 16130fdf1140b8d1ce93f3821d986fa165552023440lgao if ( tree->down != NULL ) (*after)(tree); 16230fdf1140b8d1ce93f3821d986fa165552023440lgao tree = tree->right; 16330fdf1140b8d1ce93f3821d986fa165552023440lgao } 16430fdf1140b8d1ce93f3821d986fa165552023440lgao} 16530fdf1140b8d1ce93f3821d986fa165552023440lgao 16630fdf1140b8d1ce93f3821d986fa165552023440lgao/* free all AST nodes in tree; apply func to each before freeing */ 16730fdf1140b8d1ce93f3821d986fa165552023440lgao 16830fdf1140b8d1ce93f3821d986fa165552023440lgao#if 0 16930fdf1140b8d1ce93f3821d986fa165552023440lgao////void 17030fdf1140b8d1ce93f3821d986fa165552023440lgao////#ifdef __USE_PROTOS 17130fdf1140b8d1ce93f3821d986fa165552023440lgao////zzfree_ast(AST *tree) 17230fdf1140b8d1ce93f3821d986fa165552023440lgao////#else 17330fdf1140b8d1ce93f3821d986fa165552023440lgao////zzfree_ast(tree) 17430fdf1140b8d1ce93f3821d986fa165552023440lgao////AST *tree; 17530fdf1140b8d1ce93f3821d986fa165552023440lgao////#endif 17630fdf1140b8d1ce93f3821d986fa165552023440lgao////{ 17730fdf1140b8d1ce93f3821d986fa165552023440lgao//// if ( tree == NULL ) return; 17830fdf1140b8d1ce93f3821d986fa165552023440lgao//// zzfree_ast( tree->down ); 17930fdf1140b8d1ce93f3821d986fa165552023440lgao//// zzfree_ast( tree->right ); 18030fdf1140b8d1ce93f3821d986fa165552023440lgao//// zztfree( tree ); 18130fdf1140b8d1ce93f3821d986fa165552023440lgao////} 18230fdf1140b8d1ce93f3821d986fa165552023440lgao#endif 18330fdf1140b8d1ce93f3821d986fa165552023440lgao 18430fdf1140b8d1ce93f3821d986fa165552023440lgao/* 18530fdf1140b8d1ce93f3821d986fa165552023440lgao MR19 Optimize freeing of the following structure to limit recursion 18630fdf1140b8d1ce93f3821d986fa165552023440lgao SAKAI Kiyotaka (ksakai@isr.co.jp) 18730fdf1140b8d1ce93f3821d986fa165552023440lgao*/ 18830fdf1140b8d1ce93f3821d986fa165552023440lgao 18930fdf1140b8d1ce93f3821d986fa165552023440lgao/* 19030fdf1140b8d1ce93f3821d986fa165552023440lgao NULL o 19130fdf1140b8d1ce93f3821d986fa165552023440lgao / \ 19230fdf1140b8d1ce93f3821d986fa165552023440lgao NULL o 19330fdf1140b8d1ce93f3821d986fa165552023440lgao / \ 19430fdf1140b8d1ce93f3821d986fa165552023440lgao NULL NULL 19530fdf1140b8d1ce93f3821d986fa165552023440lgao*/ 19630fdf1140b8d1ce93f3821d986fa165552023440lgao 19730fdf1140b8d1ce93f3821d986fa165552023440lgao/* 19830fdf1140b8d1ce93f3821d986fa165552023440lgao MR21 Another refinement to replace recursion with iteration 19930fdf1140b8d1ce93f3821d986fa165552023440lgao NAKAJIMA Mutsuki (muc@isr.co.jp). 20030fdf1140b8d1ce93f3821d986fa165552023440lgao*/ 20130fdf1140b8d1ce93f3821d986fa165552023440lgao 20230fdf1140b8d1ce93f3821d986fa165552023440lgaovoid 20330fdf1140b8d1ce93f3821d986fa165552023440lgao#ifdef __USE_PROTOS 20430fdf1140b8d1ce93f3821d986fa165552023440lgaozzfree_ast(AST *tree) 20530fdf1140b8d1ce93f3821d986fa165552023440lgao#else 20630fdf1140b8d1ce93f3821d986fa165552023440lgaozzfree_ast(tree) 20730fdf1140b8d1ce93f3821d986fa165552023440lgaoAST *tree; 20830fdf1140b8d1ce93f3821d986fa165552023440lgao#endif 20930fdf1140b8d1ce93f3821d986fa165552023440lgao{ 21030fdf1140b8d1ce93f3821d986fa165552023440lgao 21130fdf1140b8d1ce93f3821d986fa165552023440lgao AST *otree; 21230fdf1140b8d1ce93f3821d986fa165552023440lgao 21330fdf1140b8d1ce93f3821d986fa165552023440lgao if (tree == NULL) return; 21430fdf1140b8d1ce93f3821d986fa165552023440lgao 21530fdf1140b8d1ce93f3821d986fa165552023440lgao while (tree->down == NULL || tree->right == NULL) { 21630fdf1140b8d1ce93f3821d986fa165552023440lgao 21730fdf1140b8d1ce93f3821d986fa165552023440lgao if (tree->down == NULL && tree->right == NULL) { 21830fdf1140b8d1ce93f3821d986fa165552023440lgao zztfree(tree); 21930fdf1140b8d1ce93f3821d986fa165552023440lgao return; 22030fdf1140b8d1ce93f3821d986fa165552023440lgao } 22130fdf1140b8d1ce93f3821d986fa165552023440lgao 22230fdf1140b8d1ce93f3821d986fa165552023440lgao otree = tree; 22330fdf1140b8d1ce93f3821d986fa165552023440lgao if (tree->down == NULL) { 22430fdf1140b8d1ce93f3821d986fa165552023440lgao tree = tree->right; 22530fdf1140b8d1ce93f3821d986fa165552023440lgao } else { 22630fdf1140b8d1ce93f3821d986fa165552023440lgao tree = tree->down; 22730fdf1140b8d1ce93f3821d986fa165552023440lgao } 22830fdf1140b8d1ce93f3821d986fa165552023440lgao zztfree( otree ); 22930fdf1140b8d1ce93f3821d986fa165552023440lgao } 23030fdf1140b8d1ce93f3821d986fa165552023440lgao 23130fdf1140b8d1ce93f3821d986fa165552023440lgao while (tree != NULL) { 23230fdf1140b8d1ce93f3821d986fa165552023440lgao zzfree_ast(tree->down); 23330fdf1140b8d1ce93f3821d986fa165552023440lgao otree = tree; 23430fdf1140b8d1ce93f3821d986fa165552023440lgao tree = otree->right; 23530fdf1140b8d1ce93f3821d986fa165552023440lgao zztfree(otree); 23630fdf1140b8d1ce93f3821d986fa165552023440lgao } 23730fdf1140b8d1ce93f3821d986fa165552023440lgao} 23830fdf1140b8d1ce93f3821d986fa165552023440lgao 23930fdf1140b8d1ce93f3821d986fa165552023440lgao/* build a tree (root child1 child2 ... NULL) 24030fdf1140b8d1ce93f3821d986fa165552023440lgao * If root is NULL, simply make the children siblings and return ptr 24130fdf1140b8d1ce93f3821d986fa165552023440lgao * to 1st sibling (child1). If root is not single node, return NULL. 24230fdf1140b8d1ce93f3821d986fa165552023440lgao * 24330fdf1140b8d1ce93f3821d986fa165552023440lgao * Siblings that are actually siblins lists themselves are handled 24430fdf1140b8d1ce93f3821d986fa165552023440lgao * correctly. For example #( NULL, #( NULL, A, B, C), D) results 24530fdf1140b8d1ce93f3821d986fa165552023440lgao * in the tree ( NULL A B C D ). 24630fdf1140b8d1ce93f3821d986fa165552023440lgao * 24730fdf1140b8d1ce93f3821d986fa165552023440lgao * Requires at least two parameters with the last one being NULL. If 24830fdf1140b8d1ce93f3821d986fa165552023440lgao * both are NULL, return NULL. 24930fdf1140b8d1ce93f3821d986fa165552023440lgao */ 25030fdf1140b8d1ce93f3821d986fa165552023440lgao#ifdef PCCTS_USE_STDARG 25130fdf1140b8d1ce93f3821d986fa165552023440lgaoAST *zztmake(AST *rt, ...) 25230fdf1140b8d1ce93f3821d986fa165552023440lgao#else 25330fdf1140b8d1ce93f3821d986fa165552023440lgaoAST *zztmake(va_alist) 25430fdf1140b8d1ce93f3821d986fa165552023440lgaova_dcl 25530fdf1140b8d1ce93f3821d986fa165552023440lgao#endif 25630fdf1140b8d1ce93f3821d986fa165552023440lgao{ 25730fdf1140b8d1ce93f3821d986fa165552023440lgao va_list ap; 25830fdf1140b8d1ce93f3821d986fa165552023440lgao register AST *child, *sibling=NULL, *tail=NULL /* MR20 */, *w; 25930fdf1140b8d1ce93f3821d986fa165552023440lgao AST *root; 26030fdf1140b8d1ce93f3821d986fa165552023440lgao 26130fdf1140b8d1ce93f3821d986fa165552023440lgao#ifdef PCCTS_USE_STDARG 26230fdf1140b8d1ce93f3821d986fa165552023440lgao va_start(ap, rt); 26330fdf1140b8d1ce93f3821d986fa165552023440lgao root = rt; 26430fdf1140b8d1ce93f3821d986fa165552023440lgao#else 26530fdf1140b8d1ce93f3821d986fa165552023440lgao va_start(ap); 26630fdf1140b8d1ce93f3821d986fa165552023440lgao root = va_arg(ap, AST *); 26730fdf1140b8d1ce93f3821d986fa165552023440lgao#endif 26830fdf1140b8d1ce93f3821d986fa165552023440lgao 26930fdf1140b8d1ce93f3821d986fa165552023440lgao if ( root != NULL ) 27030fdf1140b8d1ce93f3821d986fa165552023440lgao if ( root->down != NULL ) return NULL; 27130fdf1140b8d1ce93f3821d986fa165552023440lgao child = va_arg(ap, AST *); 27230fdf1140b8d1ce93f3821d986fa165552023440lgao while ( child != NULL ) 27330fdf1140b8d1ce93f3821d986fa165552023440lgao { 27430fdf1140b8d1ce93f3821d986fa165552023440lgao for (w=child; w->right!=NULL; w=w->right) {;} /* find end of child */ 27530fdf1140b8d1ce93f3821d986fa165552023440lgao if ( sibling == NULL ) {sibling = child; tail = w;} 27630fdf1140b8d1ce93f3821d986fa165552023440lgao else {tail->right = child; tail = w;} 27730fdf1140b8d1ce93f3821d986fa165552023440lgao child = va_arg(ap, AST *); 27830fdf1140b8d1ce93f3821d986fa165552023440lgao } 27930fdf1140b8d1ce93f3821d986fa165552023440lgao if ( root==NULL ) root = sibling; 28030fdf1140b8d1ce93f3821d986fa165552023440lgao else root->down = sibling; 28130fdf1140b8d1ce93f3821d986fa165552023440lgao va_end(ap); 28230fdf1140b8d1ce93f3821d986fa165552023440lgao return root; 28330fdf1140b8d1ce93f3821d986fa165552023440lgao} 28430fdf1140b8d1ce93f3821d986fa165552023440lgao 28530fdf1140b8d1ce93f3821d986fa165552023440lgao/* tree duplicate */ 28630fdf1140b8d1ce93f3821d986fa165552023440lgaoAST * 28730fdf1140b8d1ce93f3821d986fa165552023440lgao#ifdef __USE_PROTOS 28830fdf1140b8d1ce93f3821d986fa165552023440lgaozzdup_ast(AST *t) 28930fdf1140b8d1ce93f3821d986fa165552023440lgao#else 29030fdf1140b8d1ce93f3821d986fa165552023440lgaozzdup_ast(t) 29130fdf1140b8d1ce93f3821d986fa165552023440lgaoAST *t; 29230fdf1140b8d1ce93f3821d986fa165552023440lgao#endif 29330fdf1140b8d1ce93f3821d986fa165552023440lgao{ 29430fdf1140b8d1ce93f3821d986fa165552023440lgao AST *u; 29530fdf1140b8d1ce93f3821d986fa165552023440lgao 29630fdf1140b8d1ce93f3821d986fa165552023440lgao if ( t == NULL ) return NULL; 29730fdf1140b8d1ce93f3821d986fa165552023440lgao u = zzastnew(); 29830fdf1140b8d1ce93f3821d986fa165552023440lgao *u = *t; 29930fdf1140b8d1ce93f3821d986fa165552023440lgao#ifdef zzAST_DOUBLE 30030fdf1140b8d1ce93f3821d986fa165552023440lgao u->up = NULL; /* set by calling invocation */ 30130fdf1140b8d1ce93f3821d986fa165552023440lgao u->left = NULL; 30230fdf1140b8d1ce93f3821d986fa165552023440lgao#endif 30330fdf1140b8d1ce93f3821d986fa165552023440lgao u->right = zzdup_ast(t->right); 30430fdf1140b8d1ce93f3821d986fa165552023440lgao u->down = zzdup_ast(t->down); 30530fdf1140b8d1ce93f3821d986fa165552023440lgao#ifdef zzAST_DOUBLE 30630fdf1140b8d1ce93f3821d986fa165552023440lgao if ( u->right!=NULL ) u->right->left = u; 30730fdf1140b8d1ce93f3821d986fa165552023440lgao if ( u->down!=NULL ) u->down->up = u; 30830fdf1140b8d1ce93f3821d986fa165552023440lgao#endif 30930fdf1140b8d1ce93f3821d986fa165552023440lgao return u; 31030fdf1140b8d1ce93f3821d986fa165552023440lgao} 31130fdf1140b8d1ce93f3821d986fa165552023440lgao 31230fdf1140b8d1ce93f3821d986fa165552023440lgaovoid 31330fdf1140b8d1ce93f3821d986fa165552023440lgao#ifdef __USE_PROTOS 31430fdf1140b8d1ce93f3821d986fa165552023440lgaozztfree(AST *t) 31530fdf1140b8d1ce93f3821d986fa165552023440lgao#else 31630fdf1140b8d1ce93f3821d986fa165552023440lgaozztfree(t) 31730fdf1140b8d1ce93f3821d986fa165552023440lgaoAST *t; 31830fdf1140b8d1ce93f3821d986fa165552023440lgao#endif 31930fdf1140b8d1ce93f3821d986fa165552023440lgao{ 32030fdf1140b8d1ce93f3821d986fa165552023440lgao#ifdef zzd_ast 32130fdf1140b8d1ce93f3821d986fa165552023440lgao zzd_ast( t ); 32230fdf1140b8d1ce93f3821d986fa165552023440lgao#endif 32330fdf1140b8d1ce93f3821d986fa165552023440lgao free( t ); 32430fdf1140b8d1ce93f3821d986fa165552023440lgao} 32530fdf1140b8d1ce93f3821d986fa165552023440lgao 32630fdf1140b8d1ce93f3821d986fa165552023440lgao#ifdef zzAST_DOUBLE 32730fdf1140b8d1ce93f3821d986fa165552023440lgao/* 32830fdf1140b8d1ce93f3821d986fa165552023440lgao * Set the 'up', and 'left' pointers of all nodes in 't'. 32930fdf1140b8d1ce93f3821d986fa165552023440lgao * Initial call is double_link(your_tree, NULL, NULL). 33030fdf1140b8d1ce93f3821d986fa165552023440lgao */ 33130fdf1140b8d1ce93f3821d986fa165552023440lgaovoid 33230fdf1140b8d1ce93f3821d986fa165552023440lgao#ifdef __USE_PROTOS 33330fdf1140b8d1ce93f3821d986fa165552023440lgaozzdouble_link(AST *t, AST *left, AST *up) 33430fdf1140b8d1ce93f3821d986fa165552023440lgao#else 33530fdf1140b8d1ce93f3821d986fa165552023440lgaozzdouble_link(t, left, up) 33630fdf1140b8d1ce93f3821d986fa165552023440lgaoAST *t, *left, *up; 33730fdf1140b8d1ce93f3821d986fa165552023440lgao#endif 33830fdf1140b8d1ce93f3821d986fa165552023440lgao{ 33930fdf1140b8d1ce93f3821d986fa165552023440lgao if ( t==NULL ) return; 34030fdf1140b8d1ce93f3821d986fa165552023440lgao t->left = left; 34130fdf1140b8d1ce93f3821d986fa165552023440lgao t->up = up; 34230fdf1140b8d1ce93f3821d986fa165552023440lgao zzdouble_link(t->down, NULL, t); 34330fdf1140b8d1ce93f3821d986fa165552023440lgao zzdouble_link(t->right, t, up); 34430fdf1140b8d1ce93f3821d986fa165552023440lgao} 34530fdf1140b8d1ce93f3821d986fa165552023440lgao#endif 346