gprof/lookup.c

   1 /*
   2  * Copyright (c) 1983 Regents of the University of California.
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms are permitted
   6  * provided that: (1) source distributions retain this entire copyright
   7  * notice and comment, and (2) distributions including binaries display
   8  * the following acknowledgement:  ``This product includes software
   9  * developed by the University of California, Berkeley and its contributors''
  10  * in the documentation or other materials provided with the distribution
  11  * and in all advertising materials mentioning features or use of this
  12  * software. Neither the name of the University nor the names of its
  13  * contributors may be used to endorse or promote products derived
  14  * from this software without specific prior written permission.
  15  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
  16  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  17  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  18  */
  19
  20 #ifndef lint
  21 static char sccsid[] = "@(#)lookup.c    5.4 (Berkeley) 6/1/90";
  22 #endif /* not lint */
  23
  24 #include "gprof.h"
  25
  26     /*
  27      *  look up an address in a sorted-by-address namelist
  28      *      this deals with misses by mapping them to the next lower
  29      *      entry point.
  30      */
  31 #ifdef DEBUG
  32 nltype *dbg_nllookup();
  33 #endif
  34
  35 nltype *
  36 nllookup( address )
  37     unsigned long       address;
  38 {
  39     register long       low;
  40     register long       middle;
  41     register long       high;
  42 #   ifdef DEBUG
  43         register int    probes;
  44
  45         probes = 0;
  46 #   endif DEBUG
  47     for ( low = 0 , high = nname - 1 ; low != high ; ) {
  48 #       ifdef DEBUG
  49             probes += 1;
  50 #       endif DEBUG
  51         middle = ( high + low ) >> 1;
  52         if ( nl[ middle ].value <= address && nl[ middle+1 ].value > address ) {
  53 #           ifdef DEBUG
  54                 if ( debug & LOOKUPDEBUG ) {
  55                     printf( "[nllookup] %d (%d) probes\n" , probes , nname-1 );
  56                 }
  57 #           endif DEBUG
  58             return &nl[ middle ];
  59         }
  60         if ( nl[ middle ].value > address ) {
  61             high = middle;
  62         } else {
  63             low = middle + 1;
  64         }
  65     }
  66     if(nl[middle+1].value <= address) {
  67 #           ifdef DEBUG
  68       if (debug & LOOKUPDEBUG ) {
  69         printf("[nllookup] %d (%d) probes, fall off\n", probes, nname-1);
  70       }
  71 #           endif
  72       return &nl[middle+1];
  73     }
  74     fprintf( stderr , "[nllookup] binary search fails???\n" );
  75 #ifdef DEBUG
  76     dbg_nllookup(address);
  77 #endif
  78     return 0;
  79 }
  80
  81 #ifdef DEBUG
  82 nltype *
  83 dbg_nllookup( address )
  84     unsigned long       address;
  85 {
  86     register long       low;
  87     register long       middle;
  88     register long       high;
  89     fprintf(stderr,"[nllookup] address 0x%x\n",address);
  90
  91     for ( low = 0 , high = nname - 1 ; low != high ; ) {
  92
  93       middle = ( high + low ) >> 1;
  94       fprintf(stderr, "[nllookup] low 0x%x middle 0x%x high 0x%x nl[m] 0x%x nl[m+1] 0x%x\n",
  95               low,middle,high,nl[middle].value,nl[middle+1].value);
  96       if ( nl[ middle ].value <= address && nl[ middle+1 ].value > address) {
  97         return &nl[ middle ];
  98       }
  99       if ( nl[ middle ].value > address ) {
 100         high = middle;
 101       } else {
 102         low = middle + 1;
 103       }
 104     }
 105     fprintf( stderr , "[nllookup] binary search fails???\n" );
 106     return 0;
 107 }
 108 #endif DEBUG
 109
 110 arctype *
 111 arclookup( parentp , childp )
 112     nltype      *parentp;
 113     nltype      *childp;
 114 {
 115     arctype     *arcp;
 116
 117     if ( parentp == 0 || childp == 0 ) {
 118         printf( "[arclookup] parentp == 0 || childp == 0\n" );
 119         return 0;
 120     }
 121 #   ifdef DEBUG
 122         if ( debug & LOOKUPDEBUG ) {
 123             printf( "[arclookup] parent %s child %s\n" ,
 124                     parentp -> name , childp -> name );
 125         }
 126 #   endif DEBUG
 127     for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) {
 128 #       ifdef DEBUG
 129             if ( debug & LOOKUPDEBUG ) {
 130                 printf( "[arclookup]\t arc_parent %s arc_child %s\n" ,
 131                         arcp -> arc_parentp -> name ,
 132                         arcp -> arc_childp -> name );
 133             }
 134 #       endif DEBUG
 135         if ( arcp -> arc_childp == childp ) {
 136             return arcp;
 137         }
 138     }
 139     return 0;
 140 }