1 /*-
2  * Copyright (c) 1980, 1993
3  *	The Regents of the University of California.  All rights reserved.
4  *
5  * %sccs.include.redist.c%
6  */
7 
8 #ifndef lint
9 static char sccsid[] = "@(#)tr_equal.c	8.1 (Berkeley) 06/06/93";
10 #endif /* not lint */
11 
12 /*
13  * A recursive tree search routine to test if two trees
14  * are structurally equivalent.
15  */
16 
17 #include "defs.h"
18 #include "tree.h"
19 #include "tree.rep"
20 
21 BOOLEAN tr_equal(t1, t2)
22 register NODE *t1;
23 register NODE *t2;
24 {
25 	if (t1 == NIL && t2 == NIL) {
26 		return(TRUE);
27 	}
28 	if (t1 == NIL || t2 == NIL) {
29 		return(FALSE);
30 	}
31 	if (t1->op != t2->op || degree(t1->op) != degree(t2->op)) {
32 		return(FALSE);
33 	}
34 	switch(degree(t1->op)) {
35 		case LEAF:
36 			switch(t1->op) {
37 				case O_NAME:
38 					return(t1->nameval == t2->nameval);
39 
40 				case O_QNAME:
41 					if (!tr_equal(t1->right, t2->right)) {
42 						return(FALSE);
43 					}
44 					return(tr_equal(t1->left, t2->left));
45 
46 				case O_LCON:
47 					return(t1->lconval == t2->lconval);
48 
49 				case O_FCON:
50 					return(t1->fconval == t2->fconval);
51 
52 				case O_SCON:
53 					return(t1->sconval == t2->sconval);
54 
55 				default:
56 					panic("tr_equal: leaf %d\n", t1->op);
57 			}
58 			/*NOTREACHED*/
59 
60 		case BINARY:
61 			if (!tr_equal(t1->right, t2->right)) {
62 				return(FALSE);
63 			}
64 			/* else fall through */
65 		case UNARY:
66 			return(tr_equal(t1->left, t2->left));
67 
68 		default:
69 			panic("tr_equal: bad degree for op %d\n", t1->op);
70 	}
71 	/*NOTREACHED*/
72 }
73