lookup.c revision 105243
1296177Sjhibbits/* 2296177Sjhibbits * Copyright (c) 1983, 1993 3296177Sjhibbits * The Regents of the University of California. All rights reserved. 4296177Sjhibbits * 5296177Sjhibbits * Redistribution and use in source and binary forms, with or without 6296177Sjhibbits * modification, are permitted provided that the following conditions 7296177Sjhibbits * are met: 8296177Sjhibbits * 1. Redistributions of source code must retain the above copyright 9296177Sjhibbits * notice, this list of conditions and the following disclaimer. 10296177Sjhibbits * 2. Redistributions in binary form must reproduce the above copyright 11296177Sjhibbits * notice, this list of conditions and the following disclaimer in the 12296177Sjhibbits * documentation and/or other materials provided with the distribution. 13296177Sjhibbits * 3. All advertising materials mentioning features or use of this software 14296177Sjhibbits * must display the following acknowledgement: 15296177Sjhibbits * This product includes software developed by the University of 16296177Sjhibbits * California, Berkeley and its contributors. 17296177Sjhibbits * 4. Neither the name of the University nor the names of its contributors 18296177Sjhibbits * may be used to endorse or promote products derived from this software 19296177Sjhibbits * without specific prior written permission. 20296177Sjhibbits * 21296177Sjhibbits * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 22296177Sjhibbits * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 23296177Sjhibbits * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 24296177Sjhibbits * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 25296177Sjhibbits * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 26296177Sjhibbits * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 27296177Sjhibbits * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 28296177Sjhibbits * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 29296177Sjhibbits * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 30296177Sjhibbits * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 31296177Sjhibbits * SUCH DAMAGE. 32296177Sjhibbits */ 33296177Sjhibbits 34296177Sjhibbits#if 0 35296177Sjhibbits#ifndef lint 36296177Sjhibbitsstatic char sccsid[] = "@(#)lookup.c 8.1 (Berkeley) 6/6/93"; 37296177Sjhibbits#endif /* not lint */ 38296177Sjhibbits#endif 39296177Sjhibbits 40296177Sjhibbits#include <sys/cdefs.h> 41296177Sjhibbits__FBSDID("$FreeBSD: head/usr.bin/gprof/lookup.c 105243 2002-10-16 13:50:09Z charnier $"); 42296177Sjhibbits 43296177Sjhibbits#include "gprof.h" 44296177Sjhibbits 45296177Sjhibbits /* 46296177Sjhibbits * look up an address in a sorted-by-address namelist 47296177Sjhibbits * this deals with misses by mapping them to the next lower 48296177Sjhibbits * entry point. 49296177Sjhibbits */ 50296177Sjhibbitsnltype * 51296177Sjhibbitsnllookup( address ) 52296177Sjhibbits unsigned long address; 53296177Sjhibbits{ 54296177Sjhibbits register long low; 55296177Sjhibbits register long middle; 56296177Sjhibbits register long high; 57296177Sjhibbits# ifdef DEBUG 58296177Sjhibbits register int probes; 59296177Sjhibbits 60296177Sjhibbits probes = 0; 61296177Sjhibbits# endif /* DEBUG */ 62296177Sjhibbits for ( low = 0 , high = nname - 1 ; low != high ; ) { 63296177Sjhibbits# ifdef DEBUG 64296177Sjhibbits probes += 1; 65296177Sjhibbits# endif /* DEBUG */ 66296177Sjhibbits middle = ( high + low ) >> 1; 67296177Sjhibbits if ( nl[ middle ].value <= address && nl[ middle+1 ].value > address ) { 68296177Sjhibbits# ifdef DEBUG 69296177Sjhibbits if ( debug & LOOKUPDEBUG ) { 70296177Sjhibbits printf( "[nllookup] %d (%d) probes\n" , probes , nname-1 ); 71296177Sjhibbits } 72296177Sjhibbits# endif /* DEBUG */ 73296177Sjhibbits return &nl[ middle ]; 74296177Sjhibbits } 75296177Sjhibbits if ( nl[ middle ].value > address ) { 76296177Sjhibbits high = middle; 77296177Sjhibbits } else { 78296177Sjhibbits low = middle + 1; 79296177Sjhibbits } 80296177Sjhibbits } 81296177Sjhibbits# ifdef DEBUG 82296177Sjhibbits if ( debug & LOOKUPDEBUG ) { 83296177Sjhibbits fprintf( stderr , "[nllookup] (%d) binary search fails\n" , 84296177Sjhibbits nname-1 ); 85296177Sjhibbits } 86296177Sjhibbits# endif /* DEBUG */ 87296177Sjhibbits return 0; 88296177Sjhibbits} 89296177Sjhibbits 90296177Sjhibbitsarctype * 91296177Sjhibbitsarclookup( parentp , childp ) 92296177Sjhibbits nltype *parentp; 93296177Sjhibbits nltype *childp; 94296177Sjhibbits{ 95296177Sjhibbits arctype *arcp; 96296177Sjhibbits 97296177Sjhibbits if ( parentp == 0 || childp == 0 ) { 98296177Sjhibbits fprintf( stderr, "[arclookup] parentp == 0 || childp == 0\n" ); 99296177Sjhibbits return 0; 100296177Sjhibbits } 101296177Sjhibbits# ifdef DEBUG 102296177Sjhibbits if ( debug & LOOKUPDEBUG ) { 103296177Sjhibbits printf( "[arclookup] parent %s child %s\n" , 104296177Sjhibbits parentp -> name , childp -> name ); 105296177Sjhibbits } 106296177Sjhibbits# endif /* DEBUG */ 107296177Sjhibbits for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) { 108296177Sjhibbits# ifdef DEBUG 109296177Sjhibbits if ( debug & LOOKUPDEBUG ) { 110296177Sjhibbits printf( "[arclookup]\t arc_parent %s arc_child %s\n" , 111296177Sjhibbits arcp -> arc_parentp -> name , 112296177Sjhibbits arcp -> arc_childp -> name ); 113296177Sjhibbits } 114296177Sjhibbits# endif /* DEBUG */ 115296177Sjhibbits if ( arcp -> arc_childp == childp ) { 116296177Sjhibbits return arcp; 117296177Sjhibbits } 118296177Sjhibbits } 119296177Sjhibbits return 0; 120296177Sjhibbits} 121296177Sjhibbits