1 /* 2 * Copyright (c) 1983, 1993 3 * The Regents of the University of California. All rights reserved. 4 * 5 * %sccs.include.redist.c% 6 */ 7 8 #ifndef lint 9 static char sccsid[] = "@(#)lookup.c 8.1 (Berkeley) 06/06/93"; 10 #endif /* not lint */ 11 12 #include "gprof.h" 13 14 /* 15 * look up an address in a sorted-by-address namelist 16 * this deals with misses by mapping them to the next lower 17 * entry point. 18 */ 19 nltype * 20 nllookup( address ) 21 unsigned long address; 22 { 23 register long low; 24 register long middle; 25 register long high; 26 # ifdef DEBUG 27 register int probes; 28 29 probes = 0; 30 # endif DEBUG 31 for ( low = 0 , high = nname - 1 ; low != high ; ) { 32 # ifdef DEBUG 33 probes += 1; 34 # endif DEBUG 35 middle = ( high + low ) >> 1; 36 if ( nl[ middle ].value <= address && nl[ middle+1 ].value > address ) { 37 # ifdef DEBUG 38 if ( debug & LOOKUPDEBUG ) { 39 printf( "[nllookup] %d (%d) probes\n" , probes , nname-1 ); 40 } 41 # endif DEBUG 42 return &nl[ middle ]; 43 } 44 if ( nl[ middle ].value > address ) { 45 high = middle; 46 } else { 47 low = middle + 1; 48 } 49 } 50 # ifdef DEBUG 51 if ( debug & LOOKUPDEBUG ) { 52 fprintf( stderr , "[nllookup] (%d) binary search fails\n" , 53 nname-1 ); 54 } 55 # endif DEBUG 56 return 0; 57 } 58 59 arctype * 60 arclookup( parentp , childp ) 61 nltype *parentp; 62 nltype *childp; 63 { 64 arctype *arcp; 65 66 if ( parentp == 0 || childp == 0 ) { 67 fprintf( stderr, "[arclookup] parentp == 0 || childp == 0\n" ); 68 return 0; 69 } 70 # ifdef DEBUG 71 if ( debug & LOOKUPDEBUG ) { 72 printf( "[arclookup] parent %s child %s\n" , 73 parentp -> name , childp -> name ); 74 } 75 # endif DEBUG 76 for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) { 77 # ifdef DEBUG 78 if ( debug & LOOKUPDEBUG ) { 79 printf( "[arclookup]\t arc_parent %s arc_child %s\n" , 80 arcp -> arc_parentp -> name , 81 arcp -> arc_childp -> name ); 82 } 83 # endif DEBUG 84 if ( arcp -> arc_childp == childp ) { 85 return arcp; 86 } 87 } 88 return 0; 89 } 90