121962Sdist /* 221962Sdist * Copyright (c) 1983 Regents of the University of California. 334199Sbostic * All rights reserved. 434199Sbostic * 542683Sbostic * %sccs.include.redist.c% 621962Sdist */ 721962Sdist 84512Speter #ifndef lint 9*52580Smckusick static char sccsid[] = "@(#)lookup.c 5.6 (Berkeley) 02/19/92"; 1034199Sbostic #endif /* not lint */ 114512Speter 124560Speter #include "gprof.h" 134512Speter 144512Speter /* 154512Speter * look up an address in a sorted-by-address namelist 164512Speter * this deals with misses by mapping them to the next lower 174512Speter * entry point. 184512Speter */ 194512Speter nltype * 204512Speter nllookup( address ) 214512Speter unsigned long address; 224512Speter { 234512Speter register long low; 244512Speter register long middle; 254512Speter register long high; 264512Speter # ifdef DEBUG 274512Speter register int probes; 284512Speter 294512Speter probes = 0; 304512Speter # endif DEBUG 314512Speter for ( low = 0 , high = nname - 1 ; low != high ; ) { 324512Speter # ifdef DEBUG 334512Speter probes += 1; 344512Speter # endif DEBUG 354512Speter middle = ( high + low ) >> 1; 364512Speter if ( nl[ middle ].value <= address && nl[ middle+1 ].value > address ) { 374512Speter # ifdef DEBUG 384723Speter if ( debug & LOOKUPDEBUG ) { 394512Speter printf( "[nllookup] %d (%d) probes\n" , probes , nname-1 ); 404512Speter } 414512Speter # endif DEBUG 424512Speter return &nl[ middle ]; 434512Speter } 444512Speter if ( nl[ middle ].value > address ) { 454512Speter high = middle; 464512Speter } else { 474512Speter low = middle + 1; 484512Speter } 494512Speter } 50*52580Smckusick # ifdef DEBUG 51*52580Smckusick if ( debug & LOOKUPDEBUG ) { 52*52580Smckusick fprintf( stderr , "[nllookup] (%d) binary search fails\n" , 53*52580Smckusick nname-1 ); 54*52580Smckusick } 55*52580Smckusick # endif DEBUG 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 ) { 6746314Storek fprintf( stderr, "[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