lookup.c revision 99112
1145132Sanholt/* 2145132Sanholt * Copyright (c) 1983, 1993 3145132Sanholt * The Regents of the University of California. All rights reserved. 4145132Sanholt * 5145132Sanholt * Redistribution and use in source and binary forms, with or without 6145132Sanholt * modification, are permitted provided that the following conditions 7145132Sanholt * are met: 8145132Sanholt * 1. Redistributions of source code must retain the above copyright 9145132Sanholt * notice, this list of conditions and the following disclaimer. 10145132Sanholt * 2. Redistributions in binary form must reproduce the above copyright 11145132Sanholt * notice, this list of conditions and the following disclaimer in the 12145132Sanholt * documentation and/or other materials provided with the distribution. 13145132Sanholt * 3. All advertising materials mentioning features or use of this software 14145132Sanholt * must display the following acknowledgement: 15145132Sanholt * This product includes software developed by the University of 16145132Sanholt * California, Berkeley and its contributors. 17145132Sanholt * 4. Neither the name of the University nor the names of its contributors 18145132Sanholt * may be used to endorse or promote products derived from this software 19145132Sanholt * without specific prior written permission. 20145132Sanholt * 21145132Sanholt * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 22145132Sanholt * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 23145132Sanholt * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 24145132Sanholt * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 25145132Sanholt * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 26145132Sanholt * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 27145132Sanholt * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 28145132Sanholt * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 29145132Sanholt * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 30145132Sanholt * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 31152909Sanholt * SUCH DAMAGE. 32152909Sanholt */ 33152909Sanholt 34182080Srnoland#ifndef lint 35182080Srnoland#if 0 36182080Srnolandstatic char sccsid[] = "@(#)lookup.c 8.1 (Berkeley) 6/6/93"; 37182080Srnoland#endif 38182080Srnolandstatic const char rcsid[] = 39145132Sanholt "$FreeBSD: head/usr.bin/gprof/lookup.c 99112 2002-06-30 05:25:07Z obrien $"; 40145132Sanholt#endif /* not lint */ 41145132Sanholt#include <sys/cdefs.h> 42145132Sanholt__FBSDID("$FreeBSD: head/usr.bin/gprof/lookup.c 99112 2002-06-30 05:25:07Z obrien $"); 43145132Sanholt 44145132Sanholt#include "gprof.h" 45145132Sanholt 46145132Sanholt /* 47182080Srnoland * look up an address in a sorted-by-address namelist 48182080Srnoland * this deals with misses by mapping them to the next lower 49145132Sanholt * entry point. 50183573Srnoland */ 51145132Sanholtnltype * 52182080Srnolandnllookup( address ) 53182080Srnoland unsigned long address; 54182080Srnoland{ 55145132Sanholt register long low; 56182080Srnoland register long middle; 57145132Sanholt register long high; 58145132Sanholt# ifdef DEBUG 59145132Sanholt register int probes; 60145132Sanholt 61145132Sanholt probes = 0; 62145132Sanholt# endif /* DEBUG */ 63145132Sanholt for ( low = 0 , high = nname - 1 ; low != high ; ) { 64182080Srnoland# ifdef DEBUG 65182080Srnoland probes += 1; 66145132Sanholt# endif /* DEBUG */ 67183573Srnoland middle = ( high + low ) >> 1; 68145132Sanholt if ( nl[ middle ].value <= address && nl[ middle+1 ].value > address ) { 69145132Sanholt# ifdef DEBUG 70145132Sanholt if ( debug & LOOKUPDEBUG ) { 71145132Sanholt printf( "[nllookup] %d (%d) probes\n" , probes , nname-1 ); 72182080Srnoland } 73182080Srnoland# endif /* DEBUG */ 74145132Sanholt return &nl[ middle ]; 75183833Srnoland } 76145132Sanholt if ( nl[ middle ].value > address ) { 77182080Srnoland high = middle; 78145132Sanholt } else { 79182080Srnoland low = middle + 1; 80183833Srnoland } 81182080Srnoland } 82145132Sanholt# ifdef DEBUG 83182080Srnoland if ( debug & LOOKUPDEBUG ) { 84145132Sanholt fprintf( stderr , "[nllookup] (%d) binary search fails\n" , 85145132Sanholt nname-1 ); 86145132Sanholt } 87145132Sanholt# endif /* DEBUG */ 88145132Sanholt return 0; 89145132Sanholt} 90183833Srnoland 91182080Srnolandarctype * 92145132Sanholtarclookup( parentp , childp ) 93145132Sanholt nltype *parentp; 94145132Sanholt nltype *childp; 95145132Sanholt{ 96145132Sanholt arctype *arcp; 97145132Sanholt 98145132Sanholt if ( parentp == 0 || childp == 0 ) { 99145132Sanholt fprintf( stderr, "[arclookup] parentp == 0 || childp == 0\n" ); 100183833Srnoland return 0; 101182080Srnoland } 102145132Sanholt# ifdef DEBUG 103145132Sanholt if ( debug & LOOKUPDEBUG ) { 104145132Sanholt printf( "[arclookup] parent %s child %s\n" , 105145132Sanholt parentp -> name , childp -> name ); 106145132Sanholt } 107145132Sanholt# endif /* DEBUG */ 108182080Srnoland for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) { 109145132Sanholt# ifdef DEBUG 110145132Sanholt if ( debug & LOOKUPDEBUG ) { 111182080Srnoland printf( "[arclookup]\t arc_parent %s arc_child %s\n" , 112145132Sanholt arcp -> arc_parentp -> name , 113145132Sanholt arcp -> arc_childp -> name ); 114145132Sanholt } 115145132Sanholt# endif /* DEBUG */ 116145132Sanholt if ( arcp -> arc_childp == childp ) { 117145132Sanholt return arcp; 118145132Sanholt } 119145132Sanholt } 120182080Srnoland return 0; 121145132Sanholt} 122145132Sanholt