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