Annotation of src/usr.bin/gprof/lookup.c, Revision 1.2
1.2 ! deraadt 1: /* $OpenBSD: lookup.c,v 1.5 1995/04/19 07:16:06 cgd Exp $ */
1.1 deraadt 2: /* $NetBSD: lookup.c,v 1.5 1995/04/19 07:16:06 cgd Exp $ */
3:
4: /*
5: * Copyright (c) 1983, 1993
6: * The Regents of the University of California. All rights reserved.
7: *
8: * Redistribution and use in source and binary forms, with or without
9: * modification, are permitted provided that the following conditions
10: * are met:
11: * 1. Redistributions of source code must retain the above copyright
12: * notice, this list of conditions and the following disclaimer.
13: * 2. Redistributions in binary form must reproduce the above copyright
14: * notice, this list of conditions and the following disclaimer in the
15: * documentation and/or other materials provided with the distribution.
16: * 3. All advertising materials mentioning features or use of this software
17: * must display the following acknowledgement:
18: * This product includes software developed by the University of
19: * California, Berkeley and its contributors.
20: * 4. Neither the name of the University nor the names of its contributors
21: * may be used to endorse or promote products derived from this software
22: * without specific prior written permission.
23: *
24: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34: * SUCH DAMAGE.
35: */
36:
37: #ifndef lint
38: #if 0
39: static char sccsid[] = "@(#)lookup.c 8.1 (Berkeley) 6/6/93";
40: #else
1.2 ! deraadt 41: static char rcsid[] = "$OpenBSD: lookup.c,v 1.5 1995/04/19 07:16:06 cgd Exp $";
1.1 deraadt 42: #endif
43: #endif /* not lint */
44:
45: #include "gprof.h"
46:
47: /*
48: * look up an address in a sorted-by-address namelist
49: * this deals with misses by mapping them to the next lower
50: * entry point.
51: */
52: nltype *
53: nllookup( address )
54: unsigned long address;
55: {
56: register long low;
57: register long middle;
58: register long high;
59: # ifdef DEBUG
60: register int probes;
61:
62: probes = 0;
63: # endif DEBUG
64: for ( low = 0 , high = nname - 1 ; low != high ; ) {
65: # ifdef DEBUG
66: probes += 1;
67: # endif DEBUG
68: middle = ( high + low ) >> 1;
69: if ( nl[ middle ].value <= address && nl[ middle+1 ].value > address ) {
70: # ifdef DEBUG
71: if ( debug & LOOKUPDEBUG ) {
72: printf( "[nllookup] %d (%d) probes\n" , probes , nname-1 );
73: }
74: # endif DEBUG
75: return &nl[ middle ];
76: }
77: if ( nl[ middle ].value > address ) {
78: high = middle;
79: } else {
80: low = middle + 1;
81: }
82: }
83: # ifdef DEBUG
84: if ( debug & LOOKUPDEBUG ) {
85: fprintf( stderr , "[nllookup] (%d) binary search fails\n" ,
86: nname-1 );
87: }
88: # endif DEBUG
89: return 0;
90: }
91:
92: arctype *
93: arclookup( parentp , childp )
94: nltype *parentp;
95: nltype *childp;
96: {
97: arctype *arcp;
98:
99: if ( parentp == 0 || childp == 0 ) {
100: fprintf( stderr, "[arclookup] parentp == 0 || childp == 0\n" );
101: return 0;
102: }
103: # ifdef DEBUG
104: if ( debug & LOOKUPDEBUG ) {
105: printf( "[arclookup] parent %s child %s\n" ,
106: parentp -> name , childp -> name );
107: }
108: # endif DEBUG
109: for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) {
110: # ifdef DEBUG
111: if ( debug & LOOKUPDEBUG ) {
112: printf( "[arclookup]\t arc_parent %s arc_child %s\n" ,
113: arcp -> arc_parentp -> name ,
114: arcp -> arc_childp -> name );
115: }
116: # endif DEBUG
117: if ( arcp -> arc_childp == childp ) {
118: return arcp;
119: }
120: }
121: return 0;
122: }