Annotation of src/usr.bin/gprof/lookup.c, Revision 1.5
1.5 ! danh 1: /* $OpenBSD: lookup.c,v 1.4 2001/11/19 19:02:14 mpech 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.5 ! danh 41: static char rcsid[] = "$OpenBSD: lookup.c,v 1.4 2001/11/19 19:02:14 mpech 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: {
1.4 mpech 56: long low;
57: long middle;
58: long high;
1.1 deraadt 59: # ifdef DEBUG
1.4 mpech 60: int probes;
1.1 deraadt 61:
62: probes = 0;
1.5 ! danh 63: # endif /* DEBUG */
1.1 deraadt 64: for ( low = 0 , high = nname - 1 ; low != high ; ) {
65: # ifdef DEBUG
66: probes += 1;
1.5 ! danh 67: # endif /* DEBUG */
1.1 deraadt 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: }
1.5 ! danh 74: # endif /* DEBUG */
1.1 deraadt 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
1.3 mickey 84: if ( debug & LOOKUPDEBUG )
85: warnx("[nllookup] (%d) binary search fails", nname - 1);
1.5 ! danh 86: # endif /* DEBUG */
1.1 deraadt 87: return 0;
88: }
89:
90: arctype *
91: arclookup( parentp , childp )
92: nltype *parentp;
93: nltype *childp;
94: {
95: arctype *arcp;
96:
97: if ( parentp == 0 || childp == 0 ) {
1.3 mickey 98: warnx("[arclookup] parentp == 0 || childp == 0");
1.1 deraadt 99: return 0;
100: }
101: # ifdef DEBUG
102: if ( debug & LOOKUPDEBUG ) {
103: printf( "[arclookup] parent %s child %s\n" ,
104: parentp -> name , childp -> name );
105: }
1.5 ! danh 106: # endif /* DEBUG */
1.1 deraadt 107: for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) {
108: # ifdef DEBUG
109: if ( debug & LOOKUPDEBUG ) {
110: printf( "[arclookup]\t arc_parent %s arc_child %s\n" ,
111: arcp -> arc_parentp -> name ,
112: arcp -> arc_childp -> name );
113: }
1.5 ! danh 114: # endif /* DEBUG */
1.1 deraadt 115: if ( arcp -> arc_childp == childp ) {
116: return arcp;
117: }
118: }
119: return 0;
120: }