home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / gnu / djgpp / src / binutils.2 / gprof / lookup.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-05-30  |  3.8 KB  |  141 lines
  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. }
  141.