121962Sdist /*
2*62017Sbostic * Copyright (c) 1983, 1993
3*62017Sbostic * The Regents of the University of California. All rights reserved.
434199Sbostic *
542683Sbostic * %sccs.include.redist.c%
621962Sdist */
721962Sdist
84512Speter #ifndef lint
9*62017Sbostic static char sccsid[] = "@(#)lookup.c 8.1 (Berkeley) 06/06/93";
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 *
nllookup(address)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 }
5052580Smckusick # ifdef DEBUG
5152580Smckusick if ( debug & LOOKUPDEBUG ) {
5252580Smckusick fprintf( stderr , "[nllookup] (%d) binary search fails\n" ,
5352580Smckusick nname-1 );
5452580Smckusick }
5552580Smckusick # endif DEBUG
564512Speter return 0;
574512Speter }
584512Speter
594512Speter arctype *
arclookup(parentp,childp)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