/*----------------------------------------------------------------------------
** Name: byadrtbl.cpp
**
** Title: By-Address Sorted Table
**
** Purpose:
**  Create and manage the table that holds all (global) symbols by their
**  their address.  Each base structure points to one of these tables.  After
**  symbols are loaded, the SortTable function is called to sort the table.
**  Methods provided are:
**       PutU32 (MemPool)
**       SortTable
**       SearchForAddr - search for an address to match a symbol's addr range
**
**  Base class = MemPool
**
** Status: PRELIMINARY | CODED
**
** $Log:   S:/tbird/arcppc/symbol/byadrtbl.cpv  $
** 
**    Rev 1.2   12 Mar 1997 14:47:28   hera
** No change.
** 
**    Rev 1.1   03 Mar 1997 15:47:24   hera
** 
**    Rev 1.0   07 Sep 1995 11:16:30   gene
** Initial revision.
** 
**    Rev 1.17   24 Sep 1993 10:30:56   nghia
** Fixed boundary condition bug for the SearchForAddress() routine.
** 
**    Rev 1.16   06 Aug 1992 22:02:50   brucea
** Fixed: bug in SearchForAddr in area of bottom <= 0 test
** 
**    Rev 1.15   06 Aug 1992 15:19:42   brucea
** Added: more checks for bottom <= 0 so UAE doesn't occur when accessing
**    an index that doesn't exist
** 
**    Rev 1.14   06 Aug 1992 10:11:30   brucea
** Changed access to .typeIndex.symType to use &0xF
** Changed: search loop in ::SearchForAddr to compare to <= or >= values
**    to handle all boundary conditions
** 
**    Rev 1.13   25 Jul 1992 16:34:36   brucea
** Reduced size of initial table size
** Modified: ByAddressTableGetNext - added tableSize output parameter in order
**    to be able to display the allocated size of each by-address table
** 
**    Rev 1.12   19 Jul 1992 21:54:46   brucea
** Added to search algorithm searching for public label (usually extern
**    functions with only a start address).  Uses the address of next label - 1
** 
**    Rev 1.11   10 Jul 1992 19:04:28   brucea
** Added: ByAddressTableGetNext to be able to walk the base tables in order to
**    display the number of symbols in each one
** 
** 
**    Rev 1.10   24 Jun 1992 18:06:36   brucea
** Changed: SortAllByAddressTables to EXPORT
** 
**    Rev 1.9   11 May 1992 17:53:44   brucea
** Fixed: algorithm problem in ByAddressTable::SearchForAddr where the binary
**    search failed but a match still existed.  Solution is to search backward
**    after the binary failure until reaching a module.  If no match, then report
**    no match.  This fixes PPR5531.
** 
**    Rev 1.8   12 Mar 1992 22:08:26   brucea
** Changed: end address points to last byte of range; modified ::SearchForAddr
**   to compare only > to reflect this.
** 
**    Rev 1.7   27 Feb 1992 22:39:00   brucea
** Fixed: bug in binary search in ByAddressTable::SearchForAddr
** 
**    Rev 1.6   16 Dec 1991 16:22:06   brucea
** Modified AddressCompare: added a terciary sort on symbol type if both
**    the start and end addresses are the same.
** 
**    Rev 1.5   29 Nov 1991 19:58:42   brucea
** changed LOGICAL_ADDR_TYPE to OFFSET_ADDR_TYPE
** changed search algorithm to test for top <= bottom from
**   old top == bottom
** changed begin and endInfo to beginAddrInfo, etc
** NULL to NULL_SYMBOL
** 
**    Rev 1.4   15 Nov 1991 13:48:42   john
** The structure of COMMON_SYMBOL_HEADER was changed to allow
** better packing of variable start/end address info.  The changes
** made here reflect the changes made in the structure.
** 
**    Rev 1.3   06 Nov 1991 14:42:58   brucea
** Fixed bugs in SearchForAddr
** Added ER_TOO_MANY_SYMBOLS error if > 0xFFFF symbols being sorted
**   in SortTable
** 
**    Rev 1.2   01 Nov 1991 11:00:22   brucea
** Added #ifndef _BASETBL_
** Added extern BaseIndexTable bit; // base index table and
**       extern MemPool st;         // symbol table
** Implemented ByAddressTable::SearchForAddr
** Modified AddressCompare to do secondary compare on end address
** Added SortAllByAddressTables
** 
**    Rev 1.1   14 Oct 1991 10:33:28   brucea
** removed _DLL_, added symmgr.h include
** 
**    Rev 1.0   11 Sep 1991 09:08:32   brucea
** Initial revision.
**
** $Header:   S:/tbird/arcppc/symbol/byadrtbl.cpv   1.2   12 Mar 1997 14:47:28   hera  $
**
** Copyright (C) 1991 Microtek International.  All rights reserved.
**
**--------------------------------------------------------------------------*/

                       /****************************
                        *                          *
                        *       INCLUDE FILES      *
                        *                          *
                        ****************************/

#ifndef _BASETBL_
#include "basetbl.h"
#endif

#ifndef _BYADRTBL_
#include "byadrtbl.h"
#endif

#ifndef __STDLIB_H
#include <stdlib.h>
#endif

#ifndef _SYMERROR_
#include "symerror.h"
#endif

#ifndef _SYMMGR_
#include "symmgr.h"
#endif

                       /****************************
                        *                          *
                        *        DEFINITIONS       *
                        *                          *
                        ****************************/

#define BYADDRTABLE_INIT_SIZE      (4L * 64L)
#define BYADDRTABLE_EXPANSION_SIZE (4L * 1024L)

                       /****************************
                        *                          *
                        *        EXTERNALS         *
                        *                          *
                        ****************************/

extern BaseIndexTable bit; // base index table
extern MemPool st;         // symbol table

                       /****************************
                        *                          *
                        *     EXECUTABLE CODE      *
                        *                          *
                        ****************************/

//-----------------------------------------------------
//member functions for ByAddressTable
//-----------------------------------------------------


ByAddressTable::ByAddressTable():MemPool()  {   // constructor
   initialSize = BYADDRTABLE_INIT_SIZE;
   expandSize  = BYADDRTABLE_EXPANSION_SIZE;
};  // end of ByAddressTable constructor


//-----------------------------------------------------------------------
// SearchForAddr
//
// Purpose:
//    Searches for a symbol with 1) the closest start address less than the
//    requested address and 2) (second priority) has the smallest end address
//    that still contains the requested address.
//
// Input parameters:
//    requestedAddr: address to search for; has already been converted to
//                   logical
//
// Output parameters:
//    symbolInfo:
//       structure consisting of the offset to the symbol found and the
//       absolute difference between the requested address and starting addr
//
// Assumptions:
//    The table is sorted by (primary key) start address AND (secondary key)
//    end address.  This means that if the start address is equal, the smaller
//    end address is closer to the beginning of the table than a larger end
//    address.
//
// Notes:
//    First do a binary search on by-address table
//    Next, search backward to see if a symbol has a smaller end address that
//    still contains requested addr.
//    Finally, search forward for a start address that is closer to the
//    requested address without being larger.
//
//    Algorithm for SYM_PUBLIC_LABEL types:
//       Since public labels are only single addresses, the search algorithm
//       treats them similar to line numbers in that the next item in the
//       table, if also a public label, represents the end address (minus 1)
//       of the previous symbol.  This is used to see if the requested address
//       matches.
//       if symbol is SYM_PUBLIC_LABEL
//       if startAddr == endAddr  // special condition required.  Means that
//                               // the public label only has a single addr
//       if next symbol is SYM_PUBLIC_LABEL
//       if requested address < next symbol start address then match occurred
//-----------------------------------------------------------------------
RETCODE
ByAddressTable::SearchForAddr(OFFSET_ADDR_TYPE requestedAddr,
                              SYMBOL_INFO_TYPE& symbolInfo)  {

   BOOLEAN found;
   // represent element pointers, not physical table indexes; (not * 4 yet)
   S32 bottom, middle, top, topTop;
   COMMON_SYMBOL_HEADER *symbolPtr;
   COMMON_SYMBOL_HEADER *symbolNextPtr;
   TABLE_OFFSET         localSymbolOffset, localNextSymbolOffset;
   U32                  localStartAddr;
                                // used to see if new addr range unsuitable

   bottom = 0;
   if (0 == (topTop = top = GetSymbolCount()))
      return ER_BYADDRTABLE_EMPTY;

   top -= 1;  // table starts at 0
   // NOTES: 09/21/93 - Nghia
   // Prevent going off the end of table
   topTop = top;
   found = FALSE;

   while (top >= bottom) { // works for top < 0
      middle = (top + bottom) / 2;
      localSymbolOffset = GetOffset(middle);   // compensates for sizeof
                                               // TABLE_OFFSET
      symbolPtr =
         (COMMON_SYMBOL_HEADER *)st.GetHugeDataPtr(localSymbolOffset);

      // test for requestedAddr < *middle start addr
      if (requestedAddr < (symbolPtr->beginAddrInfo.startAddr))  {
         top = middle - 1;
         // NOTE: if requestedAddr = 0 and no symbol matched, the last time
         //through this loop, top to become negative.

      // test for requestedAddr > *middle end addr
      // NOTE: compare is > because the end address points to the last
      //   valid address in the range,
      // i.e. endAddr-startAddr=sizeof symbol
      } else if (requestedAddr > (symbolPtr->endAddrInfo.endAddr))  {
         // test for public label and treat next symbol as end address
         // if also a public label
         if ((symbolPtr->typeIndex.symType & 0xF) != SYM_PUBLIC_LABEL) {
            bottom = middle + 1;
         } else {
            // get start address of next symbol in table
            // compensates for sizeof TABLE_OFFSET
            localNextSymbolOffset = GetOffset(middle + 1);
            symbolNextPtr = (COMMON_SYMBOL_HEADER *)
               st.GetHugeDataPtr(localNextSymbolOffset);
            // NOTES: 09/21/93 - Nghia
            // When middle == top == bottom then IT WILL CRASH AND BURN.
            // Therefore topTop MUST BE top to prevent this.
            // giant AND condition to pass the public label test
            if ((middle < topTop) &&                  // test for end of table

                (symbolPtr->endAddrInfo.endAddr ==    // test for legit public
                 symbolPtr->beginAddrInfo.startAddr) &&
                                        // test for next symbol = public label
                ((symbolNextPtr->typeIndex.symType & 0xF) == 
                 SYM_PUBLIC_LABEL) &&

                (requestedAddr < (symbolNextPtr->beginAddrInfo.startAddr)))  {
               found = TRUE;
               break;
            } else {
            bottom = middle + 1;
            }  // end of final if for requested addr < next symbol addr
         } // end of test for public label
      } else { // a match was found
         found = TRUE;
         break;
      }
   }  // end of while

   if (!found) {
      // there is a condition where it fails but a match still exists -
      // the case occurs when a module has a start address less than a
      // block address whose start address is less than requested.  This
      // sends the direction toward top which fails.  The match exists
      // with the enclosing module.
      // SOLUTION: search back looking for match and stop on first module
      // found or beginning of table, whichever is first.
      if (middle <= 0L)
         return ER_ADDRESS_NOT_FOUND;
      while ((--middle) >= 0L) {
         localSymbolOffset = GetOffset(middle);   // compensates for sizeof
                                                  // TABLE_OFFSET
         symbolPtr =
            (COMMON_SYMBOL_HEADER *)st.GetHugeDataPtr(localSymbolOffset);

         // test for requestedAddr in range of symbol
         if ((requestedAddr >= (symbolPtr->beginAddrInfo.startAddr)) &&
             (requestedAddr <= (symbolPtr->endAddrInfo.endAddr)))  {
             break;
         }
         // quit search if module found that does not contain requested addr
         if (SYM_MODULE == ((symbolPtr->typeIndex.symType) & 0xF)) {
            return ER_ADDRESS_NOT_FOUND;
         }
      }
   }

   // save start address of found symbol; save the latest found symbol
   localStartAddr = symbolPtr->beginAddrInfo.startAddr;
   symbolInfo.symbolOffset = localSymbolOffset;
   symbolInfo.delta = requestedAddr - localStartAddr;

   // now search linearly for closest match when multiple symbols contain
   // the requested address.  The rule is to return the symbol that:
   // 1) has the largest start address that is still <= requested address
   //    (i.e. start-to-requested delta is minimized)
   // 2) (secondary) has the smallest end address that still contains req addr
   // 3) (terciary) if multiple start-end addresses are equal, return first
   //    one in list; they are sorted by symbol type

   // First go backward until the start address is less than the initial
   // matched symbol.  Look for symbol with smaller end address that still
   // contains requested addr

   // bottom is the moving index; middle holds the point where the binary
   // search ended

   bottom = middle;
   if (bottom < 0) {
      return ER_ADDRESS_NOT_FOUND;
   }
   while (TRUE)  {
      // reusing <bottom> to save local variable space
      bottom = bottom - 1;
      if (bottom < 0)   // leave loop when first entry has been
         break;          // processed or starting value bogus
      localSymbolOffset = GetOffset(bottom);
      symbolPtr =
         (COMMON_SYMBOL_HEADER *)st.GetHugeDataPtr(localSymbolOffset);

      // stop backward search if start address is less than previously found
      // start address (also tests for greater than, but should never occur)
      if (localStartAddr != (symbolPtr->beginAddrInfo.startAddr)) {
         break;
      }
      // stop backward search if symbol end address is less than requested
      // address, since symbols are secondary sorted by end address
      if (requestedAddr >= (symbolPtr->endAddrInfo.endAddr)) {
         break;
      }
      // save new (and closer or equal end address) symbol offset
      symbolInfo.symbolOffset = localSymbolOffset;

      // don't need to save start-to-requested delta because it not changed
      // when searching backwards
   }  // end while

   // now scan forward for a symbol with a start address closer to requested
   // address
   bottom = middle;  // point back to symbol found with binary search
   if (bottom < 0) {
      return ER_ADDRESS_NOT_FOUND;
   }
   // must re-establish localStartAddr;
      symbolPtr =
         (COMMON_SYMBOL_HEADER *)st.GetHugeDataPtr(GetOffset(bottom));
      localStartAddr = symbolPtr->beginAddrInfo.startAddr;

   while (TRUE)  {
      if (bottom >= top) break;  // leave loop if last entry has been
                                 // processed
      // reusing <bottom> to save space
      bottom = bottom + 1;
      localSymbolOffset = GetOffset(bottom);
      symbolPtr =
         (COMMON_SYMBOL_HEADER *)st.GetHugeDataPtr(localSymbolOffset);

      // Forward search rules:
      //    1) skip over those with start addresses equal to found start
      //       address, since the end address will always be equal or larger
      //       (because they are secondary sorted by end address where < is
      //       closer to the beginning)
      //    2) if start address is closer to found start address but still <,
      //       record this as new found symbol then continue loop

      // skip over equals ;
      if ((symbolPtr->beginAddrInfo.startAddr) == localStartAddr) {
         continue;
      } else {
         // went beyond, quit ;
         if ((symbolPtr->beginAddrInfo.startAddr) > requestedAddr) {
            break;
         }
      }
      // check end address for inclusion of <requestedAddr> and skip if not
      // Do not update localStartAddr since we don't want the == compare to
      //   block out the next symbol from the comparison
      if (requestedAddr >= (symbolPtr->endAddrInfo.endAddr))  {
         continue;
      }
      // select this symbol as a closer symbol match
      symbolInfo.symbolOffset = localSymbolOffset;
      symbolInfo.delta = requestedAddr - (symbolPtr->beginAddrInfo.startAddr);

      // save context for next compare
      localStartAddr = symbolPtr->beginAddrInfo.startAddr;
   }  // end while
   return SUCCESS;
}  // end of SearchForAddr


//-----------------------------------------------------------------------
// SortTable
//
// Purpose: Sorts the offsets to symbols by the start address of each symbol
//
// Input parameter: NONE
//
// Return value: NONE
//
// Errors:
//    returns ER_BYADDRTABLE_EMPTY if no items in the table; this should
//    never occur since the call to SortTable should never be made if the
//    the dirty flag is not set - i.e. no symbols are put into table.
//------------------------------------------------------------------------
RETCODE ByAddressTable::SortTable(void)  {

   U32 tmp;
   RETCODE retCode = SUCCESS;

   tmp = GetSymbolCount();
   if (tmp == 0) {
      return ER_BYADDRTABLE_EMPTY;
   } else {
      if (tmp > 0xFFFFL)  {
         retCode = ER_TOO_MANY_SYMBOLS;
      }
      qsort(GetHugeDataPtr(0L),     // starting address
            (U16)tmp,               // number of symbols to sort
            sizeof(TABLE_OFFSET),   // size of each symbol offset
            AddressCompare
            // function pointer to compare routine
           );
   }  // end of else
   return retCode;
}  // end of ByAddressTable::SortTable


//-----------------------------------------------------------------------
// AddressCompare
//
// Purpose: 
//    Compares two symbol start addresses and returns < or >.  If =,
//    compares the end addresses and returns <, > depending on that compare.
//    If both start and end addresses are equal, sort is done by symbol type.
//    The precedence is:
//       SYM_LABEL < SYM_BLOCK < SYM_FUNCTION < SYM_MODULE
//
// Input params:
//    *first, *second: pointers to symbol offsets
//
// Output parameter:
//    return val: -1 -> first < second
//                 0 -> first = second
//                 1 -> first > second
//-----------------------------------------------------------------------
int AddressCompare(const void _FAR *first,
                   const void _FAR *second)
   {
   register TABLE_OFFSET first_val, second_val;
   register COMMON_SYMBOL_HEADER * firstPtr;
   register COMMON_SYMBOL_HEADER * secondPtr;

   // must first get huge ptr to symbol
   firstPtr = (COMMON_SYMBOL_HEADER *)
              st.GetHugeDataPtr(*((TABLE_OFFSET *)first));
   secondPtr = (COMMON_SYMBOL_HEADER *)
               st.GetHugeDataPtr(*((TABLE_OFFSET *)second));

   first_val = firstPtr->beginAddrInfo.startAddr;
   second_val = secondPtr->beginAddrInfo.startAddr;

   if (first_val < second_val) {
      return -1;
   } else if (first_val == second_val) {
      first_val = firstPtr->endAddrInfo.endAddr;
      second_val = secondPtr->endAddrInfo.endAddr;

      if (first_val < second_val)  {
         return -1;
      } else if (first_val == second_val) {
         // compare symbol types with the following precedence:
         //   SYM_LABEL < SYM_BLOCK < SYM_FUNCTION < SYM_MODULE <= all others
         // NOTE: as the enum is defined in symblsvr.h, the ordering of these
         // names is exactly opposite: i.e. by enum value,
         //   SYM_MODULE < SYM_FUNCTION etc.  Therefore, numeric comparison
         // will be used
         if (((firstPtr->typeIndex.symType) & 0xF) >
             ((secondPtr->typeIndex.symType) & 0xF)) {
            return -1;
         } else {
            return 1;
         }
      } else {
         return 1;
      }
   } else {
      return 1;
   }
}  // end of AddressCompare


//-----------------------------------------------------------------------
// SortAllByAddressTables
//
// Purpose: Sorts all by-address tables which have the dirty flag set
//
// Input parameter: NONE
//
// Return value: NONE
//
// Errors:
//    returns any error generated by SortTable call
//------------------------------------------------------------------------
RETCODE EXPORT
SortAllByAddressTables(void)
   {
   TABLE_OFFSET  tableOffset, byAddrTableOffset;
   BaseSymbol    *basePtr;       // ptr to Base object
   ByAddressTable *byAddrTablePtr;  // ptr to ByAddressTable object
   RETCODE       retCode, tmp;

   retCode = SUCCESS;
   tableOffset = bit.GetRootBaseSymbolOffset();
   while (tableOffset != NULL_SYMBOL) {
      basePtr = (BaseSymbol *)st.GetHugeDataPtr(tableOffset);
      if (basePtr->GetAddrTableDirty())  {
         byAddrTableOffset = basePtr->GetByAddressTableOffset();
         byAddrTablePtr =
            (ByAddressTable *)st.GetHugeDataPtr(byAddrTableOffset);
         if ((tmp = (byAddrTablePtr->SortTable())) != SUCCESS)
            retCode = tmp;
         else
            basePtr->SetAddrTableDirty(FALSE);
      }
      // get link to next base object
      tableOffset = basePtr->GetNextBaseOffset();
   }  // end of while
   return retCode;
} // end of SortAllByAddressTables


//-----------------------------------------------------------------------
// ByAddressTableGetNext
//
// Purpose:
//   Iterator to walk the bases and return the name and symbol count
//
// Input parameters:
//    startLoop: TRUE ==> starts the interation
//              FALSE ==> must be set after first access
//
// Output parameters:
//    loopPtr: call by reference; must be returned when startLoop FALSE
//    baseName: string of base name
//    entryCount: reference var returning number of symbols in this base
//
// Return: GOOD when baseName and entryCount are valid;
//         ER_SYM_LOOP_COMPLETE means end; params not valid
//-----------------------------------------------------------------------
RETCODE
ByAddressTableGetNext(BOOLEAN       startLoop,
                      TABLE_OFFSET& loopPtr,
                      LPSTR         baseName,
                      U32&          entryCount,
                      U32&          tableSize)  {

   TABLE_OFFSET   byAddrTableOffset, namePtr;
   BaseSymbol     *basePtr;       // ptr to Base object
   ByAddressTable *byAddrTablePtr;  // ptr to ByAddressTable object

   if (startLoop) {  // indicates start of loop
      loopPtr = bit.GetRootBaseSymbolOffset();
   }
   if (loopPtr == NULL_SYMBOL) {
      return ER_SYM_LOOP_COMPLETE;
   }

   // get base name
   basePtr = (BaseSymbol *)st.GetHugeDataPtr(loopPtr);
   namePtr = basePtr->GetBaseNameOffset();
   st.GetString(namePtr,(LPU8)baseName);

   // get base symbol count
   byAddrTableOffset = basePtr->GetByAddressTableOffset();
   byAddrTablePtr = (ByAddressTable *)st.GetHugeDataPtr(byAddrTableOffset);
   entryCount = byAddrTablePtr->GetSymbolCount();
   tableSize =  byAddrTablePtr->GetTableSize();

   // return link to next base object
   loopPtr = basePtr->GetNextBaseOffset();

   return GOOD;
} // end of ByAddressTableGetNext

/******************************** E O F *************************************/