Determine External Dependencies for Single Pass Linking

Depend documents the external function module dependencies of a module to assure that single pass linking can be achieved. This code was originally implemented in Fortran on a ModComp computer that had 128K words (256K bytes) of memory and two 40 MB hard drives. Its relevance to today is that it now implements binary table lookup, in C, using a binary file and 64-bit file system calls to handle files of virtually limitless (over 16 million terabytes) size.

Depend.c

/***************************************************************************************
* Copyright (c) 1991 - 2010 Cass Tyler, PO Box 1026, Willard, NM 87063, (505) 384-5342 *
***************************************************************************************/

/******************************************************************
*                                                                 *
* File D:\Projects\Depend\Depend.c                                *
*                                                                 *
* Depend is a Quasi-Topological Sort that orders object file      *
* references so that a program can be linked in a single pass -   *
* i.e. all modules are linked in after they have already been     *
* referenced.  This prevents the linker from having to make       *
* multiple passes.                                                *
*                                                                 *
* It does this by pushing the references from each module into    *
* a table of modules and repeating for each module until no       *
* further references are added to the table.  Because the ref-    *
* erenced module is added to the list AFTER the referencing       *
* module, all referenced modules have already been resolved or    *
* are to the right of the referencing module.                     *
*                                                                 *
* The Depend.bin file is a flat file containing sorted REFTYP     *
* entries of the Modules and their external references.           *
*                                                                 *
* This program demonstrates Binary Table Lookup from a fixed      *
* entry length binary file, and uses the 64-bit functions which   *
* assure that files of virtually unlimited size can be            *
* referenced.                                                     *
*                                                                 *
* Compile from the Command Line as "CL Depend.c"                  *
*                                                                 *
******************************************************************/

#include <io.h>      /* filelength()                              */
#include <fcntl.h>   /* _O_BINARY, _O_RDONLY                      */
#include <share.h>   /* _SH_DENYNO                                */
#include <stdio.h>   /* Standard I/O Function s                   */
#include <string.h>  /* String Manipulation Functions             */
#include <process.h> /* exit()                                    */

/* Local Defines */

typedef unsigned __int64 QWORD;

typedef enum eErrTyp {

      F_NOERR,       /* No Error was Detected                     */

      F_NOFILE,      /* No File Exists                            */
      F_FILPOS,      /* File Position Error                       */
      F_UNKNOWN      /* Error other than Above                    */

} ERR;

typedef struct stRefTyp {

   char szMod [ 7 ]; /* Module Name                               */
   char szRef [ 7 ]; /* External Reference                        */

   } REFTYP;

/* Global Variables */

static int           g_hBin                     = -1;                /* The Handle to the Reference File    */

static size_t        g_cbRecSiz                 = sizeof ( REFTYP ); /* The Record Size in Bytes            */
static QWORD         g_qwFilSiz                 = 0UI64;             /* The Number of Records in the File   */

static char          g_aszTable [ 500 ] [ 7 ]   = { { '\x00' } };
static unsigned int  g_uEntries                 = 0U;

/* Open the Depend.bin File for Binary Reading */

static ERR UseBin ( void )

   {
   QWORD qwFilPos = 0UI64;

/*
 * Open Depend.bin for Shared Binary Reading
 */
   if ( ( g_hBin = _sopen ( "Depend.bin", _O_BINARY | _O_RDONLY | _O_RANDOM, _SH_DENYNO ) ) == -1 )
      return F_NOFILE;

/*
 * Position Depend.bin to the End of the File to Retrieve the File Size
 */
   if ( ( qwFilPos = _lseek ( g_hBin, 0, SEEK_END ) ) == -1 )
      return F_FILPOS;

   g_qwFilSiz = qwFilPos / g_cbRecSiz;

/*
 * Return Success!
 */
   return F_NOERR;

   }  /* static ERR UseBin ( void ) */

/* Sequentially Return the Specified Number of Records (uNumRecs) Starting at the Specifed Record Number (ixRec) */

static ERR GetBin ( QWORD ixRec, unsigned int uNumRecs, REFTYP * pstRef )

   {
   QWORD qwFilPos = 0UI64;

/*
 * Position Depend.bin to the Specified Starting Record
 */
   if ( ( qwFilPos = _lseeki64 ( g_hBin, ixRec * g_cbRecSiz, SEEK_SET ) ) == -1I64 )
      return F_FILPOS;

/*
 * Read In the Requested Number of Records
 */
   return _read ( g_hBin, pstRef, g_cbRecSiz * uNumRecs ) != -1 ? F_NOERR : F_UNKNOWN;

   }  /* static ERR GetBin ( QWORD ixRec, unsigned int uNumRecs, REFTYP * pstRef ) */

/* Find the Specifed Record in the Binary File and Return it's Position (Index) in the File */

static QWORD PosKey ( REFTYP stKey )

   {
   ERR      eErr  = F_NOERR;
   REFTYP   stRef = { { '\0' } };
   int      nComp = 0;

   __int64  ixLo  = 0I64;
   __int64  ixHi  = g_qwFilSiz - 1I64;
   __int64  ixRec = 0I64;

/*
 * Done if No Records
 */
   if ( g_qwFilSiz < 1UI64 )
      return 0UI64;

/*
 * Perform a Binary Table Lookup for the Requested Record
 */
   while ( ixLo <= ixHi )
      {
      ixRec = ( ixLo + ixHi ) / 2I64;

   /*
    * Read the Middle Record
    */
      if ( ( eErr = GetBin ( ixRec, 1U, &stRef ) ) != F_NOERR )
         {
         fprintf ( stderr, "GetBin() failed to retrieve record %u (Err=%d)!\n\a", ixRec, eErr );
         exit ( eErr );
         }

   /*
    * We are Done if We Found It!
    */
      if ( ( nComp = strcmp ( stKey.szMod, stRef.szMod ) ) == 0 )
         {
         if ( ( nComp = strcmp ( stKey.szRef, stRef.szRef ) ) == 0 )
            {
            return ixRec;
            }
         }

   /*
    * Determine the New Record Limits
    */
      if ( nComp < 0 )
         {
         ixHi = ixRec - 1I64; /* Look to the Left */
         }
      else
         {
         ixLo = ixRec + 1I64; /* Look to the Right */
         }

      }  /* End - while ( ixLo <= ixHi ) */

/*
 * We Didn't Find the Record So Return Where It Should Have Been
 */
   if ( nComp > 0 )
      ixRec++;

/*
 * Return the Index
 */
   return ixRec;

   }  /* static QWORD PosKey ( REFTYP stKey ) */

/* Release the Depend.bin File */

static ERR RelBin ( void )

   {

   return ( _close ( g_hBin ) ? F_UNKNOWN : F_NOERR );

   }  /* static ERR RelBin ( void ) */

/* Install the Module Name into the Table */

static void Install ( char szName [ 7 ] )

   {
   unsigned int ixEntry = 0U;

   for ( ixEntry = 0U; ixEntry < g_uEntries; ixEntry++ )
      if ( ! strcmp ( szName, g_aszTable [ ixEntry ] ) )
         return;

   strcpy ( g_aszTable [ g_uEntries++ ], szName );

   }  /* static void Install ( char szName [ 7 ] ) */

int main ( int argc, char * argv [], char * envp [] )

   {
   ERR            eErr     = F_NOERR;

   unsigned int   ixEntry  = 0U;
   QWORD          qwixPos  = 0UI64;

   REFTYP         stRef    = { { '\0' } };
   REFTYP         Rec      = { { '\0' } };

/*
 * Unreferenced Parameter(s)
 */
   envp;

/*
 * Assure the Module Name was Supplied
 */
   if ( argc != 2 )
      {
      fprintf ( stderr, "Usage:  Depend <Module>\n\a" );
      return F_UNKNOWN;
      }

/*
 * Open the Depend.bin Module Reference File
 */
   if ( ( eErr = UseBin() ) != F_NOERR )
      {
      fprintf ( stderr, "Unable to open Depend.bin (Err=%d)!\n\a", eErr );
      exit ( eErr );
      }

/*
 * Get and Install the Attentive Module Name
 */
   strcpy ( stRef.szMod, _strupr ( argv [ 1 ] ) );

   stRef.szRef [ 0 ] = '\0';  /* Null String Will Position to 1st Record */

   Install ( stRef.szMod );

/*
 * Look Up External References for Every Module in the Table -
 * This will Install Additional References Until All are Found
 */
   for ( ixEntry = 0; ixEntry < g_uEntries; ixEntry++ )
      {

   /*
    * Print the Module Names
    */
      fprintf ( stdout, "%-6s %s\n", g_aszTable [ 0 ], g_aszTable [ ixEntry ] );

   /*
    * Specify the Module that We are Currently Looking For
    */
      strcpy ( stRef.szMod, g_aszTable [ ixEntry ] );

      stRef.szRef[0] = '\0';     /* Null String Will Position to 1st Record */

   /*
    * Get the Position of the 1st Record in the List
    */
      qwixPos = PosKey ( stRef );

   /*
    * Retrieve All of the References to This Module and Install Them Into the Reference Table
    */
      for   (  GetBin ( qwixPos, 1, &Rec );
            !  strcmp ( stRef.szMod, Rec.szMod );
               GetBin ( ++qwixPos, 1, &Rec ) )
         {
         Install ( Rec.szRef );
         }

      }  /* End - for ( ixEntry = 0; ixEntry < g_uEntries; ixEntry++ ) */

/*
 * Release the Depend.bin Binary Cross Reference Table
 */
   if ( ( eErr = RelBin() ) != F_NOERR )
      {
      fprintf ( stderr, "Unable to close Depend.bin (Err=%d)!\n\a", eErr );
      exit ( eErr );
      }

/*
 * Return Success!
 */
   return F_NOERR;

   }  /* int main ( int argc, char * argv [], char * envp [] ) */