1*21962Sdist /* 2*21962Sdist * Copyright (c) 1983 Regents of the University of California. 3*21962Sdist * All rights reserved. The Berkeley software License Agreement 4*21962Sdist * specifies the terms and conditions for redistribution. 5*21962Sdist */ 6*21962Sdist 74512Speter #ifndef lint 8*21962Sdist static char sccsid[] = "@(#)lookup.c 5.1 (Berkeley) 06/04/85"; 9*21962Sdist #endif not lint 104512Speter 114560Speter #include "gprof.h" 124512Speter 134512Speter /* 144512Speter * look up an address in a sorted-by-address namelist 154512Speter * this deals with misses by mapping them to the next lower 164512Speter * entry point. 174512Speter */ 184512Speter nltype * 194512Speter nllookup( address ) 204512Speter unsigned long address; 214512Speter { 224512Speter register long low; 234512Speter register long middle; 244512Speter register long high; 254512Speter # ifdef DEBUG 264512Speter register int probes; 274512Speter 284512Speter probes = 0; 294512Speter # endif DEBUG 304512Speter for ( low = 0 , high = nname - 1 ; low != high ; ) { 314512Speter # ifdef DEBUG 324512Speter probes += 1; 334512Speter # endif DEBUG 344512Speter middle = ( high + low ) >> 1; 354512Speter if ( nl[ middle ].value <= address && nl[ middle+1 ].value > address ) { 364512Speter # ifdef DEBUG 374723Speter if ( debug & LOOKUPDEBUG ) { 384512Speter printf( "[nllookup] %d (%d) probes\n" , probes , nname-1 ); 394512Speter } 404512Speter # endif DEBUG 414512Speter return &nl[ middle ]; 424512Speter } 434512Speter if ( nl[ middle ].value > address ) { 444512Speter high = middle; 454512Speter } else { 464512Speter low = middle + 1; 474512Speter } 484512Speter } 494512Speter fprintf( stderr , "[nllookup] binary search fails???\n" ); 504512Speter return 0; 514512Speter } 524512Speter 534512Speter arctype * 544512Speter arclookup( parentp , childp ) 554512Speter nltype *parentp; 564512Speter nltype *childp; 574512Speter { 584512Speter arctype *arcp; 594512Speter 604512Speter if ( parentp == 0 || childp == 0 ) { 614512Speter fprintf( "[arclookup] parentp == 0 || childp == 0\n" ); 624512Speter return 0; 634512Speter } 644512Speter # ifdef DEBUG 654723Speter if ( debug & LOOKUPDEBUG ) { 664512Speter printf( "[arclookup] parent %s child %s\n" , 674512Speter parentp -> name , childp -> name ); 684512Speter } 694512Speter # endif DEBUG 704512Speter for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) { 714512Speter # ifdef DEBUG 724723Speter if ( debug & LOOKUPDEBUG ) { 734512Speter printf( "[arclookup]\t arc_parent %s arc_child %s\n" , 744512Speter arcp -> arc_parentp -> name , 754512Speter arcp -> arc_childp -> name ); 764512Speter } 774512Speter # endif DEBUG 784512Speter if ( arcp -> arc_childp == childp ) { 794512Speter return arcp; 804512Speter } 814512Speter } 824512Speter return 0; 834512Speter } 84