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