/*                                 LIBRARY.C                               */

/*+-------------------------------------------------------------------------+
  |                                                                         |
  |                            process_libraries                            |
  |                                                                         |
  +-------------------------------------------------------------------------+*/
void process_libraries()
BeginDeclarations
file_info_ptr                          current_lib_file_info;
EndDeclarations
BeginCode
 library_processing_start_time = Now;
 While library_request_count Exceeds 0
  BeginWhile
   TraverseList(lib_file_list, current_lib_file_info)
    BeginTraverse
     process_library(current_lib_file_info);
    EndTraverse;
  EndWhile;
 write_temp_file(0, Null, 0, 0, 0);
 file_close_for_write();
 return;
EndCode

/*+-------------------------------------------------------------------------+
  |                                                                         |
  |                            process_library                              |
  |                                                                         |
  +-------------------------------------------------------------------------+*/
void process_library(file_info_ptr lib_file)
BeginDeclarations
#define Lib_file                       (*lib_file)
bit_32                                 pos;
public_entry_ptr                       pub;
#define Pub                            (*pub)
EndDeclarations
BeginCode
 While Lib_file.request_count Exceeds 0
  BeginWhile
   file_open_for_read(lib_file);
   Lib_file.pass_count++;
   TraverseList(Lib_file.external_list, pub)
    BeginTraverse
     LoopIf((Pub.type_entry IsNot public_in_library) OrIf
            (Not Pub.Library.requested));
     pos = Bit_32(Pub.Library.page) * Bit_32(Lib_file.page_size);
     file_position(pos);
     Lib_file.module_count++;
     obj_tmodule();
     If Pub.type_entry IsNot internal
      Then
       linker_error(12, "Library directory error:\n"
                        "\tLibrary:  \"%Fs\"\n"
                        "\t Module:  \"%Fs\"\n"
                        "\t Offset:  %lu\n"
                        "\t  Error:  Above module did not resolve \"%Fs\"\n"
                        "\t          when the library directory indicated it "
                                     "would.\n",
                        Lib_file.filename,
                        (*tmodule_name).symbol,
                        pos,
                        Pub.symbol);
      EndIf;
    EndTraverse;
   file_close_for_read();
  EndWhile;
 return;
EndCode
#undef Lib_file
#undef Pub

/*+-------------------------------------------------------------------------+
  |                                                                         |
  |                       process_library_directories                       |
  |                                                                         |
  +-------------------------------------------------------------------------+*/
void process_library_directories()
BeginDeclarations
file_info_ptr                          current_lib_file_info;
EndDeclarations
BeginCode
 library_directory_start_time = Now;
 public_sort_array = (public_entry_ptr_array)
                       allocate_memory
                        (Addr(dynamic_pool),
                         Bit_32(sizeof(public_entry_ptr)) *
                          Bit_32(MAX_PUBLICS_IN_LIBRARY));
 TraverseList(lib_file_list, current_lib_file_info)
  BeginTraverse
   process_library_directory(current_lib_file_info);
  EndTraverse;
 release_pool(Addr(dynamic_pool));
 return;
EndCode

/*+-------------------------------------------------------------------------+
  |                                                                         |
  |                        process_library_directory                        |
  |                                                                         |
  +-------------------------------------------------------------------------+*/
void process_library_directory(file_info_ptr lib_file)
BeginDeclarations
#define Lib_file                       (*lib_file)
bit_16                                 entry_number;
bit_16                                 current_block;
library_directory_ptr                  directory_page;
#define Directory_page                 (*directory_page)
library_file_header_ptr                lib_hdr;
#define Lib_hdr                        (*lib_hdr)
bit_16                                 n_directory_blocks;
public_entry_ptr                       pub;
#define Pub                            (*pub)
public_entry_ptr_array                 public_array;
library_symbol_entry_ptr               symbol;
bit_16                                 symbol_count;
bit_16                                 symbol_index;
#define Symbol                         (*symbol)
bit_16                                *symbol_in_page;
#define Symbol_in_page                 (*symbol_in_page)
EndDeclarations
BeginCode
 lib_hdr = (library_file_header_ptr) object_file_element;
 file_open_for_read(lib_file);
 file_IO_limit(sizeof(library_file_header_type));
 file_read(object_file_element, sizeof(library_file_header_type));
 If Lib_hdr.flag IsNot 0xF0
  Then
   linker_error(4,"File \"%Fs\" is not in LIB file format.\n"
                  "\tThis file has been ignored.\n",
                  (*lib_file).filename);
   Delete lib_file FromList lib_file_list EndDelete;
   file_close_for_read();
   return;
  EndIf;
 Lib_file.page_size            = Lib_hdr.page_size + 3;
 Lib_file.request_count        = 0;
 First(Lib_file.external_list) =
 Last(Lib_file.external_list)  = Null;
 n_directory_blocks            = Lib_hdr.n_directory_blocks;
 file_position(Lib_hdr.directory_position);
 file_IO_limit(0);
 symbol_count = 0;
 public_array = public_sort_array;
 For current_block=0;
     current_block LessThan  n_directory_blocks;
     current_block++
  BeginFor
   file_read(object_file_element, 512);
   directory_page = (library_directory_ptr) object_file_element;
   For entry_number=0; entry_number LessThan 37; entry_number++
    BeginFor
     symbol_index =
      Directory_page.offset_to_symbol[entry_number] ShiftedLeft 1;
     LoopIf(symbol_index IsZero);
     symbol = (library_symbol_entry_ptr)
              Addr(Directory_page.offset_to_symbol[symbol_index]);
     symbol_in_page = (bit_16 *)
                      Addr(Symbol.symbol[Symbol.length_of_symbol]);
     If case_ignore.val
      Then
       far_to_lower(Symbol.symbol, Symbol.length_of_symbol);
      EndIf;
     pub = lookup_public(Symbol.length_of_symbol, Symbol.symbol, 0);
/*+-------------------------------------------------------------------------+
  |                                                                         |
  | The Microsoft linker does not seem to concern itself with the ambiguity |
  | which occurs when more than one library contains a module resolving an  |
  | external reference.  It just seems to take the module from the first    |
  | library which can resolve the external.  This linker behaves in the     |
  | same manner except it will log when it ignores a module in a library.   |
  |                                                                         |
  +-------------------------------------------------------------------------+*/
     If Pub.type_entry IsNot unused
      Then  /* Log the ambiguity. */
       linker_error(4,"The symbol \"%Fs\" is defined in the libraries\n"
                      "\t\"%Fs\" and \"%Fs\".\n"
                      "\tThe latter has been ignored.\n",
                      Pub.symbol,
                      (*Pub.Library.lib_file).filename, Lib_file.filename);
      Else
       Pub.type_entry        = public_in_library;
       Pub.Library.page      = Symbol_in_page;
       Pub.Library.lib_file  = lib_file;
       Pub.Library.requested = False;
       If symbol_count NotLessThan MAX_PUBLICS_IN_LIBRARY
        Then
         linker_error(8,"Limitation of not more than %u public symbols in "
                        "a library\n"
                        "\texceeded for library \"%Fs\".\n",
                        MAX_PUBLICS_IN_LIBRARY,
                        Lib_file.filename);
        EndIf;
       *public_array++ = pub;
       symbol_count++;
      EndIf;
    EndFor;
  EndFor;
 file_close_for_read();
 If symbol_count Exceeds 0
  Then
   sort_directory(0, symbol_count-1);
   public_array = public_sort_array;
   For entry_number=0; entry_number LessThan symbol_count; entry_number++
    BeginFor
     Insert *public_array++ AtEnd InList Lib_file.external_list EndInsert;
    EndFor;
  EndIf;
 return;
EndCode
#undef Pub
#undef Lib_file
#undef Lib_hdr
#undef Library_page
#undef Symbol
#undef Symbol_in_page

/*+-------------------------------------------------------------------------+
  |                                                                         |
  |                              sort_directory                             |
  |                                                                         |
  +-------------------------------------------------------------------------+

Well, there is always much ado concerning the best sort method for a
particular application.  What is used here is a simple "quick sort".
See Knuth, "Searching and Sorting", page 114 for a description of the
algorithm.  What is really important here is why we are sorting.  After
the OBJ modules are processed, we must scan the libraries to see what
modules from the library must be included.  If the symbols in the
symbol table are in ascending module order, then we will include modules
from the library in ascending order.  This may not seem too important
at first glance, but consider that the library will be heavily buffered
and we can reduce I/O overhead by processing modules in the same buffer.
We may not get all the modules in one pass (a module at the end of the
library could require a module at the beginning of the library).  However,
experience has shown that all modules from a library can usually be
included in less than three passes.  The linker statistics will show
the number of passes for and modules included from each library.  If
you want to test this theory, just comment out the sort in the
procedure "process_library_directory" and compare the number of passes
before and after.

Now, all this could be avoided if the librarian had placed the modules
in the library in some sort of an approximation of a topologically
sorted order.  (A true topological sort is not usually possible because
relational loops are not all that infrequent.)  However, if modules with
relational loops were placed close to each other, it is very likely
that the I/O buffering could cause the library to be fully processed in
one pass.  This would improve performance, but it would not insure that
a library could be processed in exactly one pass.

Consider the case where a relational loop occurs with modules which are
not in the same library (this case forces multiple passes).  E.G.,
suppose module A1 in library A requires module B1 in library B.  Further,
suppose module B1 in turn requires module A2 back in library A.  When
processing library A (the first time), we have no way of knowing we also
need A2 until after we process B1 in library B.  We then have to go back
to library A and pick up A2.  The more this happens, the longer the link
time.*/
void sort_directory(bit_16 left, bit_16 right)
BeginDeclarations
bit_16                                 i;
bit_16                                 j;
public_entry_ptr                       temp;
EndDeclarations
BeginCode
 If left NotLessThan right
  Then
   return;
  EndIf;
 i = left;
 j = right;
 While i LessThan j
  BeginWhile
   While i LessThan j
    BeginWhile
     If (*public_sort_array[i]).Library.page GreaterThan
        (*public_sort_array[j]).Library.page
      Then
       temp                 = public_sort_array[i];
       public_sort_array[i] = public_sort_array[j];
       public_sort_array[j] = temp;
       ExitLoop;
      EndIf;
     j--;
    EndWhile;
   While i LessThan j
    BeginWhile
     If (*public_sort_array[i]).Library.page GreaterThan
        (*public_sort_array[j]).Library.page
      Then
       temp                 = public_sort_array[i];
       public_sort_array[i] = public_sort_array[j];
       public_sort_array[j] = temp;
       ExitLoop;
      EndIf;
     i++;
    EndWhile;
  EndWhile;
  If i Exceeds 0
   Then
    sort_directory(left, i-1);
   EndIf;
 sort_directory(i+1,  right);
 return;
EndCode
