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