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 nltype *
  32 nllookup( address )
  33     unsigned long       address;
  34 {
  35     register long       low;
  36     register long       middle;
  37     register long       high;
  38 #   ifdef DEBUG
  39         register int    probes;
  40
  41         probes = 0;
  42 #   endif DEBUG
  43     for ( low = 0 , high = nname - 1 ; low != high ; ) {
  44 #       ifdef DEBUG
  45             probes += 1;
  46 #       endif DEBUG
  47         middle = ( high + low ) >> 1;
  48         if ( nl[ middle ].value <= address && nl[ middle+1 ].value > address ) {
  49 #           ifdef DEBUG
  50                 if ( debug & LOOKUPDEBUG ) {
  51                     printf( "[nllookup] %d (%d) probes\n" , probes , nname-1 );
  52                 }
  53 #           endif DEBUG
  54             return &nl[ middle ];
  55         }
  56         if ( nl[ middle ].value > address ) {
  57             high = middle;
  58         } else {
  59             low = middle + 1;
  60         }
  61     }
  62     fprintf( stderr , "[nllookup] binary search fails???\n" );
  63     return 0;
  64 }
  65
  66 arctype *
  67 arclookup( parentp , childp )
  68     nltype      *parentp;
  69     nltype      *childp;
  70 {
  71     arctype     *arcp;
  72
  73     if ( parentp == 0 || childp == 0 ) {
  74         fprintf( "[arclookup] parentp == 0 || childp == 0\n" );
  75         return 0;
  76     }
  77 #   ifdef DEBUG
  78         if ( debug & LOOKUPDEBUG ) {
  79             printf( "[arclookup] parent %s child %s\n" ,
  80                     parentp -> name , childp -> name );
  81         }
  82 #   endif DEBUG
  83     for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) {
  84 #       ifdef DEBUG
  85             if ( debug & LOOKUPDEBUG ) {
  86                 printf( "[arclookup]\t arc_parent %s arc_child %s\n" ,
  87                         arcp -> arc_parentp -> name ,
  88                         arcp -> arc_childp -> name );
  89             }
  90 #       endif DEBUG
  91         if ( arcp -> arc_childp == childp ) {
  92             return arcp;
  93         }
  94     }
  95     return 0;
  96 }