1/* 2 * Copyright (c) 1999 Apple Computer, Inc. All rights reserved. 3 * 4 * @APPLE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. Please obtain a copy of the License at 10 * http://www.opensource.apple.com/apsl/ and read it before using this 11 * file. 12 * 13 * The Original Code and all software distributed under the License are 14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 18 * Please see the License for the specific language governing rights and 19 * limitations under the License. 20 * 21 * @APPLE_LICENSE_HEADER_END@ 22 */ 23/* $OpenBSD: lookup.c,v 1.2 1996/06/26 05:33:53 deraadt Exp $ */ 24/* $NetBSD: lookup.c,v 1.5 1995/04/19 07:16:06 cgd Exp $ */ 25 26/* 27 * Copyright (c) 1983, 1993 28 * The Regents of the University of California. All rights reserved. 29 * 30 * Redistribution and use in source and binary forms, with or without 31 * modification, are permitted provided that the following conditions 32 * are met: 33 * 1. Redistributions of source code must retain the above copyright 34 * notice, this list of conditions and the following disclaimer. 35 * 2. Redistributions in binary form must reproduce the above copyright 36 * notice, this list of conditions and the following disclaimer in the 37 * documentation and/or other materials provided with the distribution. 38 * 3. All advertising materials mentioning features or use of this software 39 * must display the following acknowledgement: 40 * This product includes software developed by the University of 41 * California, Berkeley and its contributors. 42 * 4. Neither the name of the University nor the names of its contributors 43 * may be used to endorse or promote products derived from this software 44 * without specific prior written permission. 45 * 46 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 47 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 48 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 49 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 50 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 51 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 52 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 53 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 54 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 55 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 56 * SUCH DAMAGE. 57 */ 58#include "gprof.h" 59 60/* 61 * look up an address in a sorted-by-address namelist 62 * this deals with misses by mapping them to the next lower 63 * entry point. 64 */ 65nltype * 66nllookup( 67uint64_t address) 68{ 69 int32_t low; 70 int32_t middle; 71 int32_t high; 72 73#ifdef DEBUG 74 int probes; 75 76 probes = 0; 77#endif 78 for(low = 0, high = nname; low != high ; ){ 79#ifdef DEBUG 80 probes += 1; 81#endif 82 middle = (high + low) >> 1; 83 if(nl[middle].value <= address && nl[middle+1].value > address){ 84#ifdef DEBUG 85 if(debug & LOOKUPDEBUG){ 86 printf("[nllookup] %d (%u) probes\n", probes, nname-1); 87 } 88#endif 89 return(&nl[middle]); 90 } 91 if(nl[middle].value > address){ 92 high = middle; 93 } 94 else{ 95 low = middle + 1; 96 } 97 } 98 fprintf(stderr, "[nllookup] binary search fails for address 0x%x\n", 99 (unsigned int)address ); 100 return(NULL); 101} 102 103arctype * 104arclookup( 105nltype *parentp, 106nltype *childp) 107{ 108 arctype *arcp; 109 110 if(parentp == 0 || childp == 0){ 111 printf("[arclookup] parentp == 0 || childp == 0\n"); 112 return(NULL); 113 } 114#ifdef DEBUG 115 if(debug & LOOKUPDEBUG){ 116 printf("[arclookup] parent %s child %s\n", 117 parentp->name, childp->name); 118 } 119#endif 120 for(arcp = parentp->children; arcp ; arcp = arcp->arc_childlist){ 121#ifdef DEBUG 122 if(debug & LOOKUPDEBUG){ 123 printf("[arclookup]\t arc_parent %s arc_child %s\n", 124 arcp->arc_parentp->name, 125 arcp->arc_childp->name); 126 } 127#endif 128 if(arcp->arc_childp == childp){ 129 return(arcp); 130 } 131 } 132 return(NULL); 133} 134