14512Speter #ifndef lint 2*4723Speter static char *sccsid = "@(#)lookup.c 1.3 (Berkeley) 11/02/81"; 34512Speter #endif lint 44512Speter 54560Speter #include "gprof.h" 64512Speter 74512Speter /* 84512Speter * look up an address in a sorted-by-address namelist 94512Speter * this deals with misses by mapping them to the next lower 104512Speter * entry point. 114512Speter */ 124512Speter nltype * 134512Speter nllookup( address ) 144512Speter unsigned long address; 154512Speter { 164512Speter register long low; 174512Speter register long middle; 184512Speter register long high; 194512Speter # ifdef DEBUG 204512Speter register int probes; 214512Speter 224512Speter probes = 0; 234512Speter # endif DEBUG 244512Speter for ( low = 0 , high = nname - 1 ; low != high ; ) { 254512Speter # ifdef DEBUG 264512Speter probes += 1; 274512Speter # endif DEBUG 284512Speter middle = ( high + low ) >> 1; 294512Speter if ( nl[ middle ].value <= address && nl[ middle+1 ].value > address ) { 304512Speter # ifdef DEBUG 31*4723Speter if ( debug & LOOKUPDEBUG ) { 324512Speter printf( "[nllookup] %d (%d) probes\n" , probes , nname-1 ); 334512Speter } 344512Speter # endif DEBUG 354512Speter return &nl[ middle ]; 364512Speter } 374512Speter if ( nl[ middle ].value > address ) { 384512Speter high = middle; 394512Speter } else { 404512Speter low = middle + 1; 414512Speter } 424512Speter } 434512Speter fprintf( stderr , "[nllookup] binary search fails???\n" ); 444512Speter return 0; 454512Speter } 464512Speter 474512Speter arctype * 484512Speter arclookup( parentp , childp ) 494512Speter nltype *parentp; 504512Speter nltype *childp; 514512Speter { 524512Speter arctype *arcp; 534512Speter 544512Speter if ( parentp == 0 || childp == 0 ) { 554512Speter fprintf( "[arclookup] parentp == 0 || childp == 0\n" ); 564512Speter return 0; 574512Speter } 584512Speter # ifdef DEBUG 59*4723Speter if ( debug & LOOKUPDEBUG ) { 604512Speter printf( "[arclookup] parent %s child %s\n" , 614512Speter parentp -> name , childp -> name ); 624512Speter } 634512Speter # endif DEBUG 644512Speter for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) { 654512Speter # ifdef DEBUG 66*4723Speter if ( debug & LOOKUPDEBUG ) { 674512Speter printf( "[arclookup]\t arc_parent %s arc_child %s\n" , 684512Speter arcp -> arc_parentp -> name , 694512Speter arcp -> arc_childp -> name ); 704512Speter } 714512Speter # endif DEBUG 724512Speter if ( arcp -> arc_childp == childp ) { 734512Speter return arcp; 744512Speter } 754512Speter } 764512Speter return 0; 774512Speter } 78