/*----------------------------------------------------------------------------
** Name: hashtbl.h
**
** Title: Hash Table
**
** Purpose:
**  Define the interface for the by-name Hash Table routines; generic routines
**  to put and get a string.
**
** Status: PRELIMINARY | CODED
**
** $Log:   S:/tbird/mt2_68k/symbol/hashtbl.h_v  $
** 
**    Rev 1.0   13 Feb 1997 09:06:10   gene
** Initial revision.
** 
**    Rev 1.0   07 Sep 1995 11:16:34   gene
** Initial revision.
** 
**    Rev 1.4   06 Nov 1992 07:15:04   brucea
** Cosmetic changes
** 
**    Rev 1.3   09 Dec 1991 09:17:46   john
** Added member function to free the allocated memory for the 
** name hash table.
** 
**    Rev 1.2   18 Nov 1991 15:19:46   brucea
** Added #include symutil.h
** 
**    Rev 1.1   31 Oct 1991 14:27:36   john
** Found an error in how the hashtable stores names.  The offset to
** the name was stored directly, but this did not give access to
** the symbol.  Now the symbol offset is stored, and the hashtable
** searches for a name by looking into the symbol.
** 
**    Rev 1.0   05 Sep 1991 11:05:28   brucea
** Initial revision.
**
** $Header:   S:/tbird/mt2_68k/symbol/hashtbl.h_v   1.0   13 Feb 1997 09:06:10   gene  $
**
** Copyright (C) 1991 Microtek International.  All rights reserved.
**
**--------------------------------------------------------------------------*/

#define _HASHTBL_

#ifndef _MEMMANAG_
#include "memmanag.h"
#endif

#ifndef _SYMUTIL_
#include "symutil.h"
#endif

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

                  /*********************************************
                   *                                           *
                   *   MEMBER FUNCTION PROTOTYPES AND INLINES  *
                   *                                           *
                   *********************************************/
typedef enum {MISSES_STATE, RATIO_STATE} EXTEND_HASH_STATE_TYPE;

class HashTable : public Table {

private:

   U32 hashTableSize;         // size set up for hash elements; depends on
                              // algorithm, but must not be evenly divisible
                              // by the incremental search size
   U32 entryCount;            // number of entries in the table
   U32 totalPutMisses;        // accumulated count of PutName misses
   U32 totalGetMisses;        // accumulated count of LookupName misses
   U8  maxPutMisses;          // largest number of misses for one PutName
   U8  maxGetMisses;          // largest number of misses for one LookupName
   EXTEND_HASH_STATE_TYPE extendHashState;
                              // what algorithm to use for determining
                              // when to extend hash table
   U32 constRatio;            // calculated constant whenever hashTableSize
                              // increases; compared to entryCount to know
                              // when to extend table size

public:

//---------------------------------------------------------------------------
// HashTable
// Purpose:
//    Initialize hash table variables to default values.
//    Does not create the table or fix up the size (SetHashTableSize)
//      because a constructor cannot return a parameter, and there can
//      be an out-of-memory error resulting from creation of table.
//---------------------------------------------------------------------------
HashTable();    // constructor


//---------------------------------------------------------------------------
// HashTable
//
// Purpose:
//    Initialize hash table variables.  Caller specifies initial sizes.
//    Does not create the table or fix up the size (SetHashTableSize)
//      because a constructor cannot return a parameter, and there can
//      be an out-of-memory error resulting from creation of table.
//
// Input parameters:
//    initSize: initial size of table to allocate
//    expSize:  size to increase the table by when it is too small
//---------------------------------------------------------------------------
HashTable(U32 initSize, U32 expSize);     // parameterized constructor


//---------------------------------------------------------------------------
// GetEntryCount
//
// Purpose:
//    FOR TESTING.
//    Return the value of the variable holding the entries put into the
//    hash table so far.
//---------------------------------------------------------------------------
U32 GetEntryCount() { return entryCount; };


//---------------------------------------------------------------------------
// GetHashTableSize
//
// Purpose:
//    FOR TESTING.
//    Return the value of the variable holding the accessible size of the
//    table
//---------------------------------------------------------------------------
U32 GetHashTableSize() { return hashTableSize; };


//---------------------------------------------------------------------------
// GetMaxGetMisses
//
// Purpose:
//    FOR TESTING.
//    Return the value of the variable holding the maximum number of Get
//    misses.
//---------------------------------------------------------------------------
U8 GetMaxGetMisses() { return maxGetMisses; };


//---------------------------------------------------------------------------
// GetMaxPutMisses
//
// Purpose:
//    FOR TESTING.
//    Return the value of the variable holding the maximum number of Put
//    misses.
//---------------------------------------------------------------------------
U8 GetMaxPutMisses() { return maxPutMisses; };


//---------------------------------------------------------------------------
// GetTotalGetMisses
//
// Purpose:
//    FOR TESTING.
//    Return the value of the variable holding the total number of Get misses
//---------------------------------------------------------------------------
U32 GetTotalGetMisses() { return totalGetMisses; };


//---------------------------------------------------------------------------
// GetTotalPutMisses
//
// Purpose:
//    FOR TESTING.
//    Return the value of the variable holding the total number of Put misses
//---------------------------------------------------------------------------
U32 GetTotalPutMisses() { return totalPutMisses; };


//---------------------------------------------------------------------------
// LookupName
//
// Purpose:
//    Retrieve offset of name in symbol table given the name string.
//
// Input parameters:
//    name: long pointer to string.  Must be null terminated.
//
// Output parameters:
//    symOffset:
//       offset into symbol table of symbol holding matching name.
//       Returns NULL if the name is not found.
//    misses: number of missed lookups for that name
//
// Error: Reports ER_STRING_LENGTH_0 if string is length 0
//------------------------------------------------------------------------
RETCODE LookupName(LPSTR lpName, TABLE_OFFSET& symOffset, U8& misses);


//---------------------------------------------------------------------------
// ObliterateTable
//
// Purpose:
//    Unlocks, then frees the table to Windows memory.
//---------------------------------------------------------------------------
VOID ObliterateTable(VOID);


//---------------------------------------------------------------------------
// PrintStats
//
// Purpose:
//    FOR TESTING.
//    Print out statistics on misses to entry ratios and others
//---------------------------------------------------------------------------
VOID PrintStats(VOID);


//---------------------------------------------------------------------------
// PutName
//
// Purpose:
//    Places pointer to symbol into table based on hashing name
//
// Input parameters:
//    symOffset:
//       offset into symbol table where symbol containing name is
//
// Output parameters:
//    duplicateName:
//       TRUE if duplicate name already exists
//       FALSE if name successfully put into table
//       Note that the string has already been put in symbol table (st);
//         if name duplicated, may want to reclaim st memory
//
// Error:
//    Reports ER_MEM_OUT_OF_MEMORY if table cannot be extended
//------------------------------------------------------------------------
RETCODE PutName(TABLE_OFFSET symOffset,
                BOOLEAN& duplicateName);


//---------------------------------------------------------------------------
// SetHashTableSize
//
// Purpose:
//    Calculates the proper size of hash table so sequential search (after
//    miss) will cause all locations to be searched.
//------------------------------------------------------------------------
VOID SetHashTableSize(VOID);


private:

//---------------------------------------------------------------------------
// ExtendHashTable
//
// Purpose:
//    Extend the size of the hash table, rehash all names, Free the old table
//------------------------------------------------------------------------
RETCODE ExtendHashTable(void);


//---------------------------------------------------------------------------
// HashFunc
//
// Purpose:
//    Calculate a hash index from the name;  the name is represented
//    by a byte length followed by characters.
//
// Input parameters:
//    name: huge pointer to string.
//
// Output parameters:
//    hash index is returned
//
// Error: None
//------------------------------------------------------------------------
U32 HashFunc(HPU8 name);


//---------------------------------------------------------------------------
// HashFuncString
//
// Purpose:
//    Calculate a hash index from a string and its length.
//
// Input parameters:
//    name: long pointer to string.
//    length: length of string
//
// Output parameters:
//    hash index is returned
//
// Error: None
//------------------------------------------------------------------------
U32 HashFuncString(LPSTR name, U8 length);

};
/******************************** E O F *************************************/