148069Sbostic /*-
2*62163Sbostic  * Copyright (c) 1980, 1993
3*62163Sbostic  *	The Regents of the University of California.  All rights reserved.
448069Sbostic  *
548069Sbostic  * %sccs.include.redist.c%
622564Sdist  */
75540Slinton 
822564Sdist #ifndef lint
9*62163Sbostic static char sccsid[] = "@(#)tr_equal.c	8.1 (Berkeley) 06/06/93";
1048069Sbostic #endif /* not lint */
115540Slinton 
125540Slinton /*
135540Slinton  * A recursive tree search routine to test if two trees
145540Slinton  * are structurally equivalent.
155540Slinton  */
165540Slinton 
175540Slinton #include "defs.h"
185540Slinton #include "tree.h"
195540Slinton #include "tree.rep"
205540Slinton 
tr_equal(t1,t2)215540Slinton BOOLEAN tr_equal(t1, t2)
225540Slinton register NODE *t1;
235540Slinton register NODE *t2;
245540Slinton {
255540Slinton 	if (t1 == NIL && t2 == NIL) {
265540Slinton 		return(TRUE);
275540Slinton 	}
285540Slinton 	if (t1 == NIL || t2 == NIL) {
295540Slinton 		return(FALSE);
305540Slinton 	}
315540Slinton 	if (t1->op != t2->op || degree(t1->op) != degree(t2->op)) {
325540Slinton 		return(FALSE);
335540Slinton 	}
345540Slinton 	switch(degree(t1->op)) {
355540Slinton 		case LEAF:
365540Slinton 			switch(t1->op) {
375540Slinton 				case O_NAME:
385540Slinton 					return(t1->nameval == t2->nameval);
395540Slinton 
405540Slinton 				case O_QNAME:
415540Slinton 					if (!tr_equal(t1->right, t2->right)) {
425540Slinton 						return(FALSE);
435540Slinton 					}
445540Slinton 					return(tr_equal(t1->left, t2->left));
455540Slinton 
465540Slinton 				case O_LCON:
475540Slinton 					return(t1->lconval == t2->lconval);
485540Slinton 
495540Slinton 				case O_FCON:
505540Slinton 					return(t1->fconval == t2->fconval);
515540Slinton 
525540Slinton 				case O_SCON:
535540Slinton 					return(t1->sconval == t2->sconval);
545540Slinton 
555540Slinton 				default:
565540Slinton 					panic("tr_equal: leaf %d\n", t1->op);
575540Slinton 			}
585540Slinton 			/*NOTREACHED*/
595540Slinton 
605540Slinton 		case BINARY:
615540Slinton 			if (!tr_equal(t1->right, t2->right)) {
625540Slinton 				return(FALSE);
635540Slinton 			}
645540Slinton 			/* else fall through */
655540Slinton 		case UNARY:
665540Slinton 			return(tr_equal(t1->left, t2->left));
675540Slinton 
685540Slinton 		default:
695540Slinton 			panic("tr_equal: bad degree for op %d\n", t1->op);
705540Slinton 	}
715540Slinton 	/*NOTREACHED*/
725540Slinton }
73