gprof/lookup.c

   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  */
  65 nltype *
  66 nllookup(
  67 unsigned long address)
  68 {
  69     long low;
  70     long middle;
  71     long 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 (%lu) 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
 103 arctype *
 104 arclookup(
 105 nltype *parentp,
 106 nltype *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 }