1 /* 2 * Copyright (c) 1983 Regents of the University of California. 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms are permitted 6 * provided that the above copyright notice and this paragraph are 7 * duplicated in all such forms and that any documentation, 8 * advertising materials, and other materials related to such 9 * distribution and use acknowledge that the software was developed 10 * by the University of California, Berkeley. The name of the 11 * University may not be used to endorse or promote products derived 12 * from this software without specific prior written permission. 13 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR 14 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED 15 * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. 16 */ 17 18 #ifndef lint 19 static char sccsid[] = "@(#)lookup.c 5.3 (Berkeley) 06/29/88"; 20 #endif /* not lint */ 21 22 #include "gprof.h" 23 24 /* 25 * look up an address in a sorted-by-address namelist 26 * this deals with misses by mapping them to the next lower 27 * entry point. 28 */ 29 nltype * 30 nllookup( address ) 31 unsigned long address; 32 { 33 register long low; 34 register long middle; 35 register long high; 36 # ifdef DEBUG 37 register int probes; 38 39 probes = 0; 40 # endif DEBUG 41 for ( low = 0 , high = nname - 1 ; low != high ; ) { 42 # ifdef DEBUG 43 probes += 1; 44 # endif DEBUG 45 middle = ( high + low ) >> 1; 46 if ( nl[ middle ].value <= address && nl[ middle+1 ].value > address ) { 47 # ifdef DEBUG 48 if ( debug & LOOKUPDEBUG ) { 49 printf( "[nllookup] %d (%d) probes\n" , probes , nname-1 ); 50 } 51 # endif DEBUG 52 return &nl[ middle ]; 53 } 54 if ( nl[ middle ].value > address ) { 55 high = middle; 56 } else { 57 low = middle + 1; 58 } 59 } 60 fprintf( stderr , "[nllookup] binary search fails???\n" ); 61 return 0; 62 } 63 64 arctype * 65 arclookup( parentp , childp ) 66 nltype *parentp; 67 nltype *childp; 68 { 69 arctype *arcp; 70 71 if ( parentp == 0 || childp == 0 ) { 72 fprintf( "[arclookup] parentp == 0 || childp == 0\n" ); 73 return 0; 74 } 75 # ifdef DEBUG 76 if ( debug & LOOKUPDEBUG ) { 77 printf( "[arclookup] parent %s child %s\n" , 78 parentp -> name , childp -> name ); 79 } 80 # endif DEBUG 81 for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) { 82 # ifdef DEBUG 83 if ( debug & LOOKUPDEBUG ) { 84 printf( "[arclookup]\t arc_parent %s arc_child %s\n" , 85 arcp -> arc_parentp -> name , 86 arcp -> arc_childp -> name ); 87 } 88 # endif DEBUG 89 if ( arcp -> arc_childp == childp ) { 90 return arcp; 91 } 92 } 93 return 0; 94 } 95