lookup.c revision 216370
150397Sobrien/* 2122180Skan * Copyright (c) 1983, 1993 390075Sobrien * The Regents of the University of California. All rights reserved. 4122180Skan * 550397Sobrien * Redistribution and use in source and binary forms, with or without 6132718Skan * modification, are permitted provided that the following conditions 750397Sobrien * are met: 8132718Skan * 1. Redistributions of source code must retain the above copyright 950397Sobrien * notice, this list of conditions and the following disclaimer. 1050397Sobrien * 2. Redistributions in binary form must reproduce the above copyright 1150397Sobrien * notice, this list of conditions and the following disclaimer in the 1250397Sobrien * documentation and/or other materials provided with the distribution. 13132718Skan * 4. Neither the name of the University nor the names of its contributors 1450397Sobrien * may be used to endorse or promote products derived from this software 1550397Sobrien * without specific prior written permission. 1650397Sobrien * 1750397Sobrien * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 1850397Sobrien * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19132718Skan * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 2050397Sobrien * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 2150397Sobrien * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 2250397Sobrien * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 23122180Skan * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 2450397Sobrien * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 2550397Sobrien * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 2690075Sobrien * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 2750397Sobrien * SUCH DAMAGE. 2850397Sobrien */ 2990075Sobrien 3050397Sobrien#if 0 3150397Sobrien#ifndef lint 32122180Skanstatic char sccsid[] = "@(#)lookup.c 8.1 (Berkeley) 6/6/93"; 33122180Skan#endif /* not lint */ 34122180Skan#endif 35122180Skan 36122180Skan#include <sys/cdefs.h> 37122180Skan__FBSDID("$FreeBSD: head/usr.bin/gprof/lookup.c 216370 2010-12-11 08:32:16Z joel $"); 38122180Skan 39122180Skan#include "gprof.h" 40122180Skan 41122180Skan /* 42122180Skan * look up an address in a sorted-by-address namelist 43122180Skan * this deals with misses by mapping them to the next lower 44122180Skan * entry point. 45122180Skan */ 4650397Sobriennltype * 47122180Skannllookup( address ) 48122180Skan unsigned long address; 49122180Skan{ 5050397Sobrien register long low; 5150397Sobrien register long middle; 5250397Sobrien register long high; 5350397Sobrien# ifdef DEBUG 5450397Sobrien register int probes; 5550397Sobrien 5650397Sobrien probes = 0; 57122180Skan# endif /* DEBUG */ 5850397Sobrien for ( low = 0 , high = nname - 1 ; low != high ; ) { 5950397Sobrien# ifdef DEBUG 60122180Skan probes += 1; 6150397Sobrien# endif /* DEBUG */ 62122180Skan middle = ( high + low ) >> 1; 63122180Skan if ( nl[ middle ].value <= address && nl[ middle+1 ].value > address ) { 64117395Skan# ifdef DEBUG 65117395Skan if ( debug & LOOKUPDEBUG ) { 66122180Skan printf( "[nllookup] %d (%d) probes\n" , probes , nname-1 ); 6750397Sobrien } 68122180Skan# endif /* DEBUG */ 69122180Skan return &nl[ middle ]; 7050397Sobrien } 7150397Sobrien if ( nl[ middle ].value > address ) { 72122180Skan high = middle; 7350397Sobrien } else { 7450397Sobrien low = middle + 1; 7550397Sobrien } 7650397Sobrien } 7750397Sobrien# ifdef DEBUG 7850397Sobrien if ( debug & LOOKUPDEBUG ) { 7950397Sobrien fprintf( stderr , "[nllookup] (%d) binary search fails\n" , 8050397Sobrien nname-1 ); 8150397Sobrien } 8250397Sobrien# endif /* DEBUG */ 8350397Sobrien return 0; 8450397Sobrien} 8550397Sobrien 8650397Sobrienarctype * 8750397Sobrienarclookup( parentp , childp ) 8890075Sobrien nltype *parentp; 8990075Sobrien nltype *childp; 9050397Sobrien{ 9150397Sobrien arctype *arcp; 9250397Sobrien 9350397Sobrien if ( parentp == 0 || childp == 0 ) { 9450397Sobrien fprintf( stderr, "[arclookup] parentp == 0 || childp == 0\n" ); 9550397Sobrien return 0; 9650397Sobrien } 9750397Sobrien# ifdef DEBUG 98122180Skan if ( debug & LOOKUPDEBUG ) { 9950397Sobrien printf( "[arclookup] parent %s child %s\n" , 10050397Sobrien parentp -> name , childp -> name ); 10150397Sobrien } 10250397Sobrien# endif /* DEBUG */ 10350397Sobrien for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) { 104122180Skan# ifdef DEBUG 105122180Skan if ( debug & LOOKUPDEBUG ) { 10650397Sobrien printf( "[arclookup]\t arc_parent %s arc_child %s\n" , 10750397Sobrien arcp -> arc_parentp -> name , 10850397Sobrien arcp -> arc_childp -> name ); 10950397Sobrien } 11050397Sobrien# endif /* DEBUG */ 11150397Sobrien if ( arcp -> arc_childp == childp ) { 11250397Sobrien return arcp; 11350397Sobrien } 11450397Sobrien } 11550397Sobrien return 0; 11650397Sobrien} 11750397Sobrien