/*----------------------------------------------------------------------------
** 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/mt2_186/symbol/byadrtbl.cpv  $
** 
**    Rev 1.4   12 Feb 1998 12:18:20   Judy
** 
**    Rev 1.3   22 Jul 1997 10:10:12   Judy
** 
**    Rev 1.2   18 Apr 1997 09:29:00   Judy
** 
**    Rev 1.1   26 Feb 1997 11:42:24   Judy
** 
**    Rev 1.2   14 Jan 1997 15:30:32   Judy
** No change.
** 
**    Rev 1.1   25 Sep 1996 10:11:42   hera
** 
**    Rev 1.0   14 Jun 1996 16:41:54   Judy
** Initial revision.
** 
**    Rev 1.22   17 Aug 1994 19:01:46   brucea
** Changed after-binary-lookup search loops to fix infinite loop bug
** 
**    Rev 1.21   04 Aug 1994 18:25:24   brucea
** Added to ::SearchForAddr code which, when the binary search symbol found is
** a public and FilterPublics is true, scans previous then next in the sorted
** list for a symbol that is not a public and is still in the requested range.
** 
**    Rev 1.20   03 Aug 1994 11:51:12   brucea
** Reduced expansion table size to 256 (was 4K)
** Modified SearchForAddr function call to include FilterPublics for search criteria
** Added IsPublicType function to support previous change.  This code needs
**    more changes to work properly.
** 
**    Rev 1.19   14 Jul 1994 01:49:00   brucea
** Removed EXPORT from CreateAllAddrRanges
** 
**    Rev 1.18   20 Jun 1994 10:02:06   nghia
** Added CreateAddressRange() and CreateAllAddressRanges for pulbic lables.
** 
**    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/mt2_186/symbol/byadrtbl.cpv   1.4   12 Feb 1998 12:18:20   Judy  $
**
** 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 * 64L)

BOOLEAN IsPublicType(COMMON_SYMBOL_HEADER *symbolPtr);

                       /****************************
                        *                          *
                        *        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
//    FilterPublics: global indicating whether to skip over publics in lookup
//                   or not.  Used for module lookup so that publics with no
//                   parentage are not found
//
// 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,
                              U16              segment,
                              BOOLEAN          FilterPublics,
                              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;

   //Hera 5/14/97 for multiple code segment
   middle = top;
   while (top >= bottom) {
      localSymbolOffset = GetOffset(top);
      symbolPtr = (COMMON_SYMBOL_HEADER *)st.GetHugeDataPtr(localSymbolOffset);
      if (((symbolPtr->typeIndex.symType & 0xF) == SYM_FUNCTION/*Hera*/) ||
          ((symbolPtr->typeIndex.symType & 0xF) == SYM_BLOCK)) { /* <Winky 9/1/97> */
	 if (segment == symbolPtr->segment[0]) {
	    if (symbolPtr->beginAddrInfo.startAddr <= requestedAddr &&
	       requestedAddr <= symbolPtr->endAddrInfo.endAddr) {
	       localStartAddr = symbolPtr->beginAddrInfo.startAddr;
	       found = TRUE;
	       middle = top;
	       break;
	    }
	 }
      }
      else if ((symbolPtr->typeIndex.symType & 0xF) == SYM_MODULE) {
	 int index;
	 for (index = 0; index < symbolPtr->segNum; index++) {
            if (segment == symbolPtr->segment[index]) {
	       if (symbolPtr->beginAddr[index] <= requestedAddr &&
	          requestedAddr <= symbolPtr->endAddr[index]) {
		  localStartAddr = symbolPtr->beginAddr[index];
		  found = TRUE;
		  middle = top;
		  break;
	       }
	    }
	 }
      }
      top--;
   }
   if (found) {
      localSymbolOffset = GetOffset(middle);
      symbolInfo.symbolOffset = localSymbolOffset;
      symbolInfo.delta = requestedAddr - localStartAddr;
      return SUCCESS;
   }
   top = middle;
   //Hera
   //Hera 4/7/97
   while (top >= bottom) {
      middle = ((top + bottom) / 2);
      localSymbolOffset = GetOffset(middle);  
      symbolPtr =
	 (COMMON_SYMBOL_HEADER *)st.GetHugeDataPtr(localSymbolOffset);

      if (requestedAddr < (symbolPtr->beginAddrInfo.startAddr)) {
	 top = middle - 1;
      }
      else
	 break;
   }
   while (requestedAddr >= (symbolPtr->beginAddrInfo.startAddr)
      && ++middle <= topTop) {
      localSymbolOffset = GetOffset(middle);
      symbolPtr =
	 (COMMON_SYMBOL_HEADER *)st.GetHugeDataPtr(localSymbolOffset);
   }
   localSymbolOffset = GetOffset(--middle);
   symbolPtr =
	 (COMMON_SYMBOL_HEADER *)st.GetHugeDataPtr(localSymbolOffset);

   if (requestedAddr <= (symbolPtr->endAddrInfo.endAddr))  {
      found = TRUE;
   }
   //Hera

   // valid variables:
   //    middle - abstract offset into byadrtbl of match
   //    localSymbolOffset - physical offset into byadrtbl - compensated for
   //                        sizeof each element in table
   //    symbolPtr - pointer to matching symbol
   
   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.
      while (TRUE) {
         middle--;  // move back one
         if (middle < 0L)
            return ER_ADDRESS_NOT_FOUND;
         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 does not contain requested addr
         if (SYM_MODULE == ((symbolPtr->typeIndex.symType) & 0xF)) {
            return ER_ADDRESS_NOT_FOUND;
         }
      }
   }
   // valid variables:
   //    middle - abstract offset into byadrtbl of match
   //    localSymbolOffset - physical offset into byadrtbl - compensated for
   //                        sizeof each element in table
   //    symbolPtr - pointer to matching symbol
   //    topTop - last element in byadrtbl
      
   // if FilterPublics is true, want to make sure that the found symbol is
   // not a public.  If it is, search back, then forward, for a symbol
   // that contains the requested address range and is not a public.
   if (FilterPublics) {
      S32 tmpMiddle = middle;  // save for searching down
      // first back up looking for a non-public address match
      found = FALSE;
      while (TRUE)  {
         if (middle < 0L)
            return ER_ADDRESS_NOT_FOUND;
         localSymbolOffset = GetOffset(middle);   // compensates for sizeof
                                                  // TABLE_OFFSET
         symbolPtr =
            (COMMON_SYMBOL_HEADER *)st.GetHugeDataPtr(localSymbolOffset);

         if (!(IsPublicType(symbolPtr)) &&
                  // test for requestedAddr in range of symbol
            (requestedAddr >= (symbolPtr->beginAddrInfo.startAddr)) &&
            (requestedAddr <= (symbolPtr->endAddrInfo.endAddr)))  {
            found = TRUE;
            break;  // leave while loop since non-public match found
         }
         middle--;  // move back one
      }

      if (!found) {
         // now search down for non-public match
         middle = tmpMiddle;
         // already checked tmpMiddle; move down one
         while ((middle++) <= topTop) {
            localSymbolOffset = GetOffset(middle);   // compensates for sizeof
                                                     // TABLE_OFFSET
            symbolPtr =
               (COMMON_SYMBOL_HEADER *)st.GetHugeDataPtr(localSymbolOffset);

            if (!(IsPublicType(symbolPtr)) &&
                // test for requestedAddr in range of symbol
                (requestedAddr >= (symbolPtr->beginAddrInfo.startAddr)) &&
                (requestedAddr <= (symbolPtr->endAddrInfo.endAddr)))  {
               found = TRUE;
               break;  // leave while loop since non-public match found
            }
         }  // end of while
      }
      if (!found)
         return ER_ADDRESS_NOT_FOUND;
   }  // end of if (FilterPublics)
   
   // valid variables:
   //    middle - abstract offset into byadrtbl of match
   //    localSymbolOffset - physical offset into byadrtbl - compensated for
   //                        sizeof each element in table
   //    symbolPtr - pointer to matching symbol
   
   // 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
   // 4) if FilterPublics is TRUE, then skip over public types

   // 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);

      if ((FilterPublics) &&
         (IsPublicType(symbolPtr)))
         break;     // skip over publics
      
      // 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:
      //    0) skip over if FilterPublics TRUE and symbol is public
      //    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

      if ((FilterPublics) &&
         (IsPublicType(symbolPtr)))
         break;     // skip over publics
      
      // skip over equals ;
      if ((symbolPtr->beginAddrInfo.startAddr) == localStartAddr) {
         continue;
      } else {
	 // went beyond, quit ;
         //**Hera 09/24/96**/
         if ((symbolPtr->beginAddrInfo.startAddr) >= requestedAddr) {
	    break;
	 //**Hera**/
         }
      }
      // 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/sizeof(TABLE_OFFSET)))  {
         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

//-----------------------------------------------------------------------
// CreateAddrRanges
//
// Purpose: create address ranges of the specified label type.
//    Algotrithm:
//    Walk the ByAddressTable {
//        while (currentItem != NULL) {
//           if (currentItem->type == type) {
//              nextItem = currentItem->next;   
//              if (nextItem->type == type)
//                 currentItem->endAddr = nextItem->startAddr - 1;
//              currentItem = nextItem;
//           } else  
//              currentItem = currentItem->next;
//        }        
//
//------------------------------------------------------------------------
RETCODE ByAddressTable::CreateAddrRanges(SYM_TYPE_TYPE labelType)  {
   S32 top, bottom;
 
   top = 0L;
   // Only if base have more than 1 symbol 
   if ((bottom = GetSymbolCount()) > 1) {
      TABLE_OFFSET current, next = 0L;
      COMMON_SYMBOL_HEADER *symbolPtr, *symbolNextPtr;
      
      while (top < bottom)  {
         current = GetOffset(top++);
         symbolPtr = (COMMON_SYMBOL_HEADER *)st.GetHugeDataPtr(current);
         // if match current symbol type - continue on adjacent symbols
         while (((symbolPtr->typeIndex.symType & 0xF) == labelType) &&
             (top < bottom)) {
            next = GetOffset(top++);
            symbolNextPtr = (COMMON_SYMBOL_HEADER *)st.GetHugeDataPtr(next);
            if (symbolNextPtr &&
               ((symbolNextPtr->typeIndex.symType & 0xF) == labelType)) {
               // assign end address range of symbol = the start of the
               // next symbol
               symbolPtr->endAddrInfo.endAddr =
                  (symbolNextPtr->beginAddrInfo.startAddr - 1);
               symbolPtr = symbolNextPtr;
            }           
         }  // while
      } // while
   }  // end of else
   return SUCCESS;
   
}  // end of ByAddressTable::CreateAddrRanges

//-----------------------------------------------------------------------
// 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

//-----------------------------------------------------------------------
// CreateAllAddrRanges
//
// Purpose: Creates address range for all labels of the specified type.
//------------------------------------------------------------------------
RETCODE CreateAllAddrRanges(SYM_TYPE_TYPE labelType) {
   TABLE_OFFSET  tableOffset, byAddrTableOffset;
   BaseSymbol    *basePtr;       // ptr to Base object
   ByAddressTable *byAddrTablePtr;  // ptr to ByAddressTable object

   tableOffset = bit.GetRootBaseSymbolOffset();
   while (tableOffset != NULL_SYMBOL) {
      basePtr = (BaseSymbol *)st.GetHugeDataPtr(tableOffset);
      BASE_TYPE baseType = (BASE_TYPE)(basePtr->GetBaseType() & 0xF);
      // check for sorted CODE and CODE_DATA bases only 
      if (!(basePtr->GetAddrTableDirty()) &&
          ((baseType == BASE_CODE) || (baseType == BASE_CODE_DATA))) {
         // retrieve the ByAddressTable pointer
         byAddrTableOffset = basePtr->GetByAddressTableOffset();
         byAddrTablePtr =
            (ByAddressTable *)st.GetHugeDataPtr(byAddrTableOffset);
         // create address range for this table
         byAddrTablePtr->CreateAddrRanges(labelType);
      }
      // get link to next base object
      tableOffset = basePtr->GetNextBaseOffset();
   }  // end of while
   return SUCCESS;
} // end of CreateAllAddressRanges

//-----------------------------------------------------------------------
// IsPublicType
//
// Purpose: returns TRUE if symbol pointed to by symPtr is any of the
//          three public types
//------------------------------------------------------------------------
BOOLEAN IsPublicType(COMMON_SYMBOL_HEADER *symPtr) {

   switch (((symPtr->typeIndex.symType) & 0xF)) {
      case SYM_PUBLIC_VAR:
      case SYM_PUBLIC_LABEL:
      case SYM_PUBLIC_UNKNOWN:
         return TRUE;

      default:
         return FALSE;
   }
}  // end of IsPublicType


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