121962Sdist /* 221962Sdist * Copyright (c) 1983 Regents of the University of California. 3*34199Sbostic * All rights reserved. 4*34199Sbostic * 5*34199Sbostic * Redistribution and use in source and binary forms are permitted 6*34199Sbostic * provided that this notice is preserved and that due credit is given 7*34199Sbostic * to the University of California at Berkeley. The name of the University 8*34199Sbostic * may not be used to endorse or promote products derived from this 9*34199Sbostic * software without specific prior written permission. This software 10*34199Sbostic * is provided ``as is'' without express or implied warranty. 1121962Sdist */ 1221962Sdist 134512Speter #ifndef lint 14*34199Sbostic static char sccsid[] = "@(#)lookup.c 5.2 (Berkeley) 05/05/88"; 15*34199Sbostic #endif /* not lint */ 164512Speter 174560Speter #include "gprof.h" 184512Speter 194512Speter /* 204512Speter * look up an address in a sorted-by-address namelist 214512Speter * this deals with misses by mapping them to the next lower 224512Speter * entry point. 234512Speter */ 244512Speter nltype * 254512Speter nllookup( address ) 264512Speter unsigned long address; 274512Speter { 284512Speter register long low; 294512Speter register long middle; 304512Speter register long high; 314512Speter # ifdef DEBUG 324512Speter register int probes; 334512Speter 344512Speter probes = 0; 354512Speter # endif DEBUG 364512Speter for ( low = 0 , high = nname - 1 ; low != high ; ) { 374512Speter # ifdef DEBUG 384512Speter probes += 1; 394512Speter # endif DEBUG 404512Speter middle = ( high + low ) >> 1; 414512Speter if ( nl[ middle ].value <= address && nl[ middle+1 ].value > address ) { 424512Speter # ifdef DEBUG 434723Speter if ( debug & LOOKUPDEBUG ) { 444512Speter printf( "[nllookup] %d (%d) probes\n" , probes , nname-1 ); 454512Speter } 464512Speter # endif DEBUG 474512Speter return &nl[ middle ]; 484512Speter } 494512Speter if ( nl[ middle ].value > address ) { 504512Speter high = middle; 514512Speter } else { 524512Speter low = middle + 1; 534512Speter } 544512Speter } 554512Speter fprintf( stderr , "[nllookup] binary search fails???\n" ); 564512Speter return 0; 574512Speter } 584512Speter 594512Speter arctype * 604512Speter arclookup( parentp , childp ) 614512Speter nltype *parentp; 624512Speter nltype *childp; 634512Speter { 644512Speter arctype *arcp; 654512Speter 664512Speter if ( parentp == 0 || childp == 0 ) { 674512Speter fprintf( "[arclookup] parentp == 0 || childp == 0\n" ); 684512Speter return 0; 694512Speter } 704512Speter # ifdef DEBUG 714723Speter if ( debug & LOOKUPDEBUG ) { 724512Speter printf( "[arclookup] parent %s child %s\n" , 734512Speter parentp -> name , childp -> name ); 744512Speter } 754512Speter # endif DEBUG 764512Speter for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) { 774512Speter # ifdef DEBUG 784723Speter if ( debug & LOOKUPDEBUG ) { 794512Speter printf( "[arclookup]\t arc_parent %s arc_child %s\n" , 804512Speter arcp -> arc_parentp -> name , 814512Speter arcp -> arc_childp -> name ); 824512Speter } 834512Speter # endif DEBUG 844512Speter if ( arcp -> arc_childp == childp ) { 854512Speter return arcp; 864512Speter } 874512Speter } 884512Speter return 0; 894512Speter } 90