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 *
nllookup(address)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 *
arclookup(parentp,childp)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