lookup.c revision 246783
1107553Sdes/* 2107553Sdes * Copyright (c) 1983, 1993 3124244Sdes * The Regents of the University of California. All rights reserved. 499059Sdes * 599059Sdes * Redistribution and use in source and binary forms, with or without 6124244Sdes * modification, are permitted provided that the following conditions 7124244Sdes * are met: 8124244Sdes * 1. Redistributions of source code must retain the above copyright 9124244Sdes * notice, this list of conditions and the following disclaimer. 10124244Sdes * 2. Redistributions in binary form must reproduce the above copyright 11124244Sdes * notice, this list of conditions and the following disclaimer in the 12124244Sdes * documentation and/or other materials provided with the distribution. 13124244Sdes * 4. Neither the name of the University nor the names of its contributors 14124244Sdes * may be used to endorse or promote products derived from this software 15124244Sdes * without specific prior written permission. 16124244Sdes * 17124244Sdes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 18124244Sdes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19124244Sdes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20124244Sdes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 21124244Sdes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 22124244Sdes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 23124244Sdes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 24124244Sdes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 25124244Sdes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 26124244Sdes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 27124244Sdes * SUCH DAMAGE. 28124244Sdes */ 29124244Sdes 3099059Sdes#if 0 3199059Sdes#ifndef lint 3299059Sdesstatic char sccsid[] = "@(#)lookup.c 8.1 (Berkeley) 6/6/93"; 3399059Sdes#endif /* not lint */ 3499059Sdes#endif 3599059Sdes 3699059Sdes#include <sys/cdefs.h> 37124244Sdes__FBSDID("$FreeBSD: head/usr.bin/gprof/lookup.c 246783 2013-02-14 08:16:03Z charnier $"); 38124244Sdes 39124244Sdes#include "gprof.h" 40124244Sdes 41124244Sdes /* 42124244Sdes * look up an address in a sorted-by-address namelist 43124244Sdes * this deals with misses by mapping them to the next lower 44124244Sdes * entry point. 45124244Sdes */ 4699059Sdesnltype * 4799059Sdesnllookup(unsigned long address) 4899059Sdes{ 49124244Sdes register long low; 5099059Sdes register long middle; 5199059Sdes register long high; 5299059Sdes# ifdef DEBUG 5399059Sdes register int probes; 5499059Sdes 5599059Sdes probes = 0; 5699059Sdes# endif /* DEBUG */ 5799059Sdes for ( low = 0 , high = nname - 1 ; low != high ; ) { 5899059Sdes# ifdef DEBUG 5999059Sdes probes += 1; 6099059Sdes# endif /* DEBUG */ 6199059Sdes middle = ( high + low ) >> 1; 6299059Sdes if ( nl[ middle ].value <= address && nl[ middle+1 ].value > address ) { 6399059Sdes# ifdef DEBUG 6499059Sdes if ( debug & LOOKUPDEBUG ) { 6599059Sdes printf( "[nllookup] %d (%d) probes\n" , probes , nname-1 ); 6699059Sdes } 6799059Sdes# endif /* DEBUG */ 6899059Sdes#if defined(__arm__) 6999059Sdes if (nl[middle].name[0] == '$' && 7099059Sdes nl[middle-1].value == nl[middle].value) 7199059Sdes middle--; 7299059Sdes#endif 7399059Sdes 7499059Sdes return &nl[ middle ]; 7599059Sdes } 7699059Sdes if ( nl[ middle ].value > address ) { 7799059Sdes high = middle; 7899059Sdes } else { 7999059Sdes low = middle + 1; 8099059Sdes } 8199059Sdes } 8299059Sdes# ifdef DEBUG 8399059Sdes if ( debug & LOOKUPDEBUG ) { 8499059Sdes fprintf( stderr , "[nllookup] (%d) binary search fails\n" , 8599059Sdes nname-1 ); 8699059Sdes } 8799059Sdes# endif /* DEBUG */ 8899059Sdes return 0; 8999059Sdes} 9099059Sdes 9199059Sdesarctype * 9299059Sdesarclookup(nltype *parentp, nltype *childp) 9399059Sdes{ 9499059Sdes arctype *arcp; 9599059Sdes 9699059Sdes if ( parentp == 0 || childp == 0 ) { 9799059Sdes fprintf( stderr, "[arclookup] parentp == 0 || childp == 0\n" ); 9899059Sdes return 0; 9999059Sdes } 10099059Sdes# ifdef DEBUG 10199059Sdes if ( debug & LOOKUPDEBUG ) { 10299059Sdes printf( "[arclookup] parent %s child %s\n" , 10399059Sdes parentp -> name , childp -> name ); 10499059Sdes } 10599059Sdes# endif /* DEBUG */ 10699059Sdes for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) { 10799059Sdes# ifdef DEBUG 10899059Sdes if ( debug & LOOKUPDEBUG ) { 10999059Sdes printf( "[arclookup]\t arc_parent %s arc_child %s\n" , 11099059Sdes arcp -> arc_parentp -> name , 11199059Sdes arcp -> arc_childp -> name ); 11299059Sdes } 11399059Sdes# endif /* DEBUG */ 11499059Sdes if ( arcp -> arc_childp == childp ) { 11599059Sdes return arcp; 11699059Sdes } 11799059Sdes } 11899059Sdes return 0; 11999059Sdes} 12099059Sdes