1124524Sume/*- 266776Skris * SPDX-License-Identifier: BSD-3-Clause 355163Sshin * 455163Sshin * Copyright (c) 1983, 1993 555163Sshin * The Regents of the University of California. All rights reserved. 662632Skris * 755163Sshin * Redistribution and use in source and binary forms, with or without 855163Sshin * modification, are permitted provided that the following conditions 955163Sshin * are met: 1055163Sshin * 1. Redistributions of source code must retain the above copyright 1155163Sshin * notice, this list of conditions and the following disclaimer. 1255163Sshin * 2. Redistributions in binary form must reproduce the above copyright 1355163Sshin * notice, this list of conditions and the following disclaimer in the 1455163Sshin * documentation and/or other materials provided with the distribution. 1555163Sshin * 3. Neither the name of the University nor the names of its contributors 1655163Sshin * may be used to endorse or promote products derived from this software 1755163Sshin * without specific prior written permission. 1862632Skris * 1955163Sshin * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 2055163Sshin * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 2155163Sshin * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 2255163Sshin * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 2355163Sshin * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 2455163Sshin * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 2555163Sshin * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 2655163Sshin * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 2755163Sshin * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 2855163Sshin * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 2955163Sshin * SUCH DAMAGE. 3055163Sshin */ 3155163Sshin 3255163Sshin#include <sys/cdefs.h> 3355163Sshin#include "gprof.h" 3455163Sshin 3555163Sshin /* 3655163Sshin * look up an address in a sorted-by-address namelist 3755163Sshin * this deals with misses by mapping them to the next lower 3866776Skris * entry point. 3955163Sshin */ 4055163Sshinnltype * 4155163Sshinnllookup(unsigned long address) 4255163Sshin{ 4355163Sshin register long low; 4455163Sshin register long middle; 4555163Sshin register long high; 46118787Sume# ifdef DEBUG 4755163Sshin register int probes; 4855163Sshin 4955163Sshin probes = 0; 5055163Sshin# endif /* DEBUG */ 5155163Sshin for ( low = 0 , high = nname - 1 ; low != high ; ) { 5255163Sshin# ifdef DEBUG 5355163Sshin probes += 1; 5455163Sshin# endif /* DEBUG */ 5555163Sshin middle = ( high + low ) >> 1; 5655163Sshin if ( nl[ middle ].value <= address && nl[ middle+1 ].value > address ) { 5755163Sshin# ifdef DEBUG 5855163Sshin if ( debug & LOOKUPDEBUG ) { 5955163Sshin printf( "[nllookup] %d (%d) probes\n" , probes , nname-1 ); 6062632Skris } 6155163Sshin# endif /* DEBUG */ 6255163Sshin#if defined(__arm__) 6362632Skris if (nl[middle].name[0] == '$' && 6455163Sshin nl[middle-1].value == nl[middle].value) 6555163Sshin middle--; 66118998Sume#endif 67118998Sume 6855163Sshin return &nl[ middle ]; 6955163Sshin } 70124524Sume if ( nl[ middle ].value > address ) { 7155163Sshin high = middle; 7262632Skris } else { 7355163Sshin low = middle + 1; 7455163Sshin } 7555163Sshin } 7655163Sshin# ifdef DEBUG 7755163Sshin if ( debug & LOOKUPDEBUG ) { 7855163Sshin fprintf( stderr , "[nllookup] (%d) binary search fails\n" , 7955163Sshin nname-1 ); 8055163Sshin } 8162632Skris# endif /* DEBUG */ 8255163Sshin return 0; 83119027Sume} 8455163Sshin 8555163Sshinarctype * 86118660Sumearclookup(nltype *parentp, nltype *childp) 87118664Sume{ 8855163Sshin arctype *arcp; 8955163Sshin 9055163Sshin if ( parentp == 0 || childp == 0 ) { 9155163Sshin fprintf( stderr, "[arclookup] parentp == 0 || childp == 0\n" ); 92118664Sume return 0; 93118660Sume } 94118664Sume# ifdef DEBUG 9555163Sshin if ( debug & LOOKUPDEBUG ) { 9655163Sshin printf( "[arclookup] parent %s child %s\n" , 9755163Sshin parentp -> name , childp -> name ); 98118660Sume } 9955163Sshin# endif /* DEBUG */ 10062632Skris for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) { 10162632Skris# ifdef DEBUG 102118660Sume if ( debug & LOOKUPDEBUG ) { 103118664Sume printf( "[arclookup]\t arc_parent %s arc_child %s\n" , 10455163Sshin arcp -> arc_parentp -> name , 10555163Sshin arcp -> arc_childp -> name ); 10655163Sshin } 10762632Skris# endif /* DEBUG */ 108118664Sume if ( arcp -> arc_childp == childp ) { 10955163Sshin return arcp; 11062632Skris } 11162632Skris } 112118660Sume return 0; 113118664Sume} 11455163Sshin