1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
|
/*
* Copyright (c) 1983 Regents of the University of California.
* All rights reserved.
*
* Redistribution and use in source and binary forms are permitted
* provided that: (1) source distributions retain this entire copyright
* notice and comment, and (2) distributions including binaries display
* the following acknowledgement: ``This product includes software
* developed by the University of California, Berkeley and its contributors''
* in the documentation or other materials provided with the distribution
* and in all advertising materials mentioning features or use of this
* software. Neither the name of the University nor the names of its
* contributors may be used to endorse or promote products derived
* from this software without specific prior written permission.
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
* IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
*/
#ifndef lint
static char sccsid[] = "@(#)lookup.c 5.4 (Berkeley) 6/1/90";
#endif /* not lint */
#include "gprof.h"
/*
* look up an address in a sorted-by-address namelist
* this deals with misses by mapping them to the next lower
* entry point.
*/
#ifdef DEBUG
nltype *dbg_nllookup();
#endif
nltype *
nllookup( address )
unsigned long address;
{
register long low;
register long middle;
register long high;
# ifdef DEBUG
register int probes;
probes = 0;
# endif DEBUG
for ( low = 0 , high = nname - 1 ; low != high ; ) {
# ifdef DEBUG
probes += 1;
# endif DEBUG
middle = ( high + low ) >> 1;
if ( nl[ middle ].value <= address && nl[ middle+1 ].value > address ) {
# ifdef DEBUG
if ( debug & LOOKUPDEBUG ) {
printf( "[nllookup] %d (%d) probes\n" , probes , nname-1 );
}
# endif DEBUG
return &nl[ middle ];
}
if ( nl[ middle ].value > address ) {
high = middle;
} else {
low = middle + 1;
}
}
if(nl[middle+1].value <= address) {
# ifdef DEBUG
if (debug & LOOKUPDEBUG ) {
printf("[nllookup] %d (%d) probes, fall off\n", probes, nname-1);
}
# endif
return &nl[middle+1];
}
fprintf( stderr , "[nllookup] binary search fails???\n" );
#ifdef DEBUG
dbg_nllookup(address);
#endif
return 0;
}
#ifdef DEBUG
nltype *
dbg_nllookup( address )
unsigned long address;
{
register long low;
register long middle;
register long high;
fprintf(stderr,"[nllookup] address 0x%x\n",address);
for ( low = 0 , high = nname - 1 ; low != high ; ) {
middle = ( high + low ) >> 1;
fprintf(stderr, "[nllookup] low 0x%x middle 0x%x high 0x%x nl[m] 0x%x nl[m+1] 0x%x\n",
low,middle,high,nl[middle].value,nl[middle+1].value);
if ( nl[ middle ].value <= address && nl[ middle+1 ].value > address) {
return &nl[ middle ];
}
if ( nl[ middle ].value > address ) {
high = middle;
} else {
low = middle + 1;
}
}
fprintf( stderr , "[nllookup] binary search fails???\n" );
return 0;
}
#endif DEBUG
arctype *
arclookup( parentp , childp )
nltype *parentp;
nltype *childp;
{
arctype *arcp;
if ( parentp == 0 || childp == 0 ) {
printf( "[arclookup] parentp == 0 || childp == 0\n" );
return 0;
}
# ifdef DEBUG
if ( debug & LOOKUPDEBUG ) {
printf( "[arclookup] parent %s child %s\n" ,
parentp -> name , childp -> name );
}
# endif DEBUG
for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) {
# ifdef DEBUG
if ( debug & LOOKUPDEBUG ) {
printf( "[arclookup]\t arc_parent %s arc_child %s\n" ,
arcp -> arc_parentp -> name ,
arcp -> arc_childp -> name );
}
# endif DEBUG
if ( arcp -> arc_childp == childp ) {
return arcp;
}
}
return 0;
}
|
