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