11590Srgrimes/* 21590Srgrimes * Copyright (c) 1983, 1993 31590Srgrimes * The Regents of the University of California. All rights reserved. 41590Srgrimes * 51590Srgrimes * Redistribution and use in source and binary forms, with or without 61590Srgrimes * modification, are permitted provided that the following conditions 71590Srgrimes * are met: 81590Srgrimes * 1. Redistributions of source code must retain the above copyright 91590Srgrimes * notice, this list of conditions and the following disclaimer. 101590Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 111590Srgrimes * notice, this list of conditions and the following disclaimer in the 121590Srgrimes * documentation and/or other materials provided with the distribution. 131590Srgrimes * 4. Neither the name of the University nor the names of its contributors 141590Srgrimes * may be used to endorse or promote products derived from this software 151590Srgrimes * without specific prior written permission. 161590Srgrimes * 171590Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 181590Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 191590Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 201590Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 211590Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 221590Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 231590Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 241590Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 251590Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 261590Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 271590Srgrimes * SUCH DAMAGE. 281590Srgrimes */ 291590Srgrimes 30105243Scharnier#if 0 311590Srgrimes#ifndef lint 321590Srgrimesstatic char sccsid[] = "@(#)lookup.c 8.1 (Berkeley) 6/6/93"; 33105243Scharnier#endif /* not lint */ 3497631Swollman#endif 35105243Scharnier 3699112Sobrien#include <sys/cdefs.h> 3799112Sobrien__FBSDID("$FreeBSD$"); 381590Srgrimes 391590Srgrimes#include "gprof.h" 401590Srgrimes 411590Srgrimes /* 421590Srgrimes * look up an address in a sorted-by-address namelist 438874Srgrimes * this deals with misses by mapping them to the next lower 441590Srgrimes * entry point. 451590Srgrimes */ 461590Srgrimesnltype * 47246783Scharniernllookup(unsigned long address) 481590Srgrimes{ 491590Srgrimes register long low; 501590Srgrimes register long middle; 511590Srgrimes register long high; 521590Srgrimes# ifdef DEBUG 531590Srgrimes register int probes; 541590Srgrimes 551590Srgrimes probes = 0; 5697631Swollman# endif /* DEBUG */ 571590Srgrimes for ( low = 0 , high = nname - 1 ; low != high ; ) { 581590Srgrimes# ifdef DEBUG 591590Srgrimes probes += 1; 6097631Swollman# endif /* DEBUG */ 611590Srgrimes middle = ( high + low ) >> 1; 621590Srgrimes if ( nl[ middle ].value <= address && nl[ middle+1 ].value > address ) { 631590Srgrimes# ifdef DEBUG 641590Srgrimes if ( debug & LOOKUPDEBUG ) { 651590Srgrimes printf( "[nllookup] %d (%d) probes\n" , probes , nname-1 ); 661590Srgrimes } 6797631Swollman# endif /* DEBUG */ 68235975Sgber#if defined(__arm__) 69235975Sgber if (nl[middle].name[0] == '$' && 70235975Sgber nl[middle-1].value == nl[middle].value) 71235975Sgber middle--; 72235975Sgber#endif 73235975Sgber 741590Srgrimes return &nl[ middle ]; 751590Srgrimes } 761590Srgrimes if ( nl[ middle ].value > address ) { 771590Srgrimes high = middle; 781590Srgrimes } else { 791590Srgrimes low = middle + 1; 801590Srgrimes } 811590Srgrimes } 821590Srgrimes# ifdef DEBUG 831590Srgrimes if ( debug & LOOKUPDEBUG ) { 841590Srgrimes fprintf( stderr , "[nllookup] (%d) binary search fails\n" , 851590Srgrimes nname-1 ); 861590Srgrimes } 8797631Swollman# endif /* DEBUG */ 881590Srgrimes return 0; 891590Srgrimes} 901590Srgrimes 911590Srgrimesarctype * 92246783Scharnierarclookup(nltype *parentp, nltype *childp) 931590Srgrimes{ 941590Srgrimes arctype *arcp; 951590Srgrimes 961590Srgrimes if ( parentp == 0 || childp == 0 ) { 971590Srgrimes fprintf( stderr, "[arclookup] parentp == 0 || childp == 0\n" ); 981590Srgrimes return 0; 991590Srgrimes } 1001590Srgrimes# ifdef DEBUG 1011590Srgrimes if ( debug & LOOKUPDEBUG ) { 1021590Srgrimes printf( "[arclookup] parent %s child %s\n" , 1031590Srgrimes parentp -> name , childp -> name ); 1041590Srgrimes } 10597631Swollman# endif /* DEBUG */ 1061590Srgrimes for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) { 1071590Srgrimes# ifdef DEBUG 1081590Srgrimes if ( debug & LOOKUPDEBUG ) { 1091590Srgrimes printf( "[arclookup]\t arc_parent %s arc_child %s\n" , 1101590Srgrimes arcp -> arc_parentp -> name , 1111590Srgrimes arcp -> arc_childp -> name ); 1121590Srgrimes } 11397631Swollman# endif /* DEBUG */ 1141590Srgrimes if ( arcp -> arc_childp == childp ) { 1151590Srgrimes return arcp; 1161590Srgrimes } 1171590Srgrimes } 1181590Srgrimes return 0; 1191590Srgrimes} 120