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*46314Storek static char sccsid[] = "@(#)lookup.c 5.5 (Berkeley) 02/06/91"; 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 } 504512Speter fprintf( stderr , "[nllookup] binary search fails???\n" ); 514512Speter return 0; 524512Speter } 534512Speter 544512Speter arctype * 554512Speter arclookup( parentp , childp ) 564512Speter nltype *parentp; 574512Speter nltype *childp; 584512Speter { 594512Speter arctype *arcp; 604512Speter 614512Speter if ( parentp == 0 || childp == 0 ) { 62*46314Storek fprintf( stderr, "[arclookup] parentp == 0 || childp == 0\n" ); 634512Speter return 0; 644512Speter } 654512Speter # ifdef DEBUG 664723Speter if ( debug & LOOKUPDEBUG ) { 674512Speter printf( "[arclookup] parent %s child %s\n" , 684512Speter parentp -> name , childp -> name ); 694512Speter } 704512Speter # endif DEBUG 714512Speter for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) { 724512Speter # ifdef DEBUG 734723Speter if ( debug & LOOKUPDEBUG ) { 744512Speter printf( "[arclookup]\t arc_parent %s arc_child %s\n" , 754512Speter arcp -> arc_parentp -> name , 764512Speter arcp -> arc_childp -> name ); 774512Speter } 784512Speter # endif DEBUG 794512Speter if ( arcp -> arc_childp == childp ) { 804512Speter return arcp; 814512Speter } 824512Speter } 834512Speter return 0; 844512Speter } 85