
/***************************************************************************
**
**    $Header:   D:/EPSLDV1/SRC/LOG/HASHTBL.H__   1.8   20 Jun 1996 09:27:44   ZJRD  $
**
**    $Log:   D:/EPSLDV1/SRC/LOG/HASHTBL.H__  $
** 
**    Rev 1.8   20 Jun 1996 09:27:44   ZJRD
** EasyPack/SLD Version 1.20a
** 
**    Rev 1.6   10 Jun 1996 10:22:22   ZJRD
** EasyPack/SLD Version 1.20
** 
**    Rev 1.4   29 May 1996 09:33:04   ZJRD
** No change.
** 
**    Rev 1.3   16 May 1996 09:05:10   ZJRD
** No change.
** 
**    Rev 1.2   10 May 1996 09:14:02   ZJRD
** No change.
** 
**    Rev 1.1   02 May 1996 10:24:34   ZJRD
** EasyPack/SLD Version 1.92
** 
**    Rev 1.31   18 Apr 1996 12:53:52   Shirley
** No change.
** 
**    Rev 1.30   12 Apr 1996 10:40:42   Shirley
** EasyPack/SLD Version 1.90
** 
**    Rev 1.28   15 Feb 1996 08:54:12   Shirley
** No change.
** 
**    Rev 1.27   12 Feb 1996 14:09:30   Shirley
** No change.
** 
**    Rev 1.26   06 Feb 1996 15:35:52   Shirley
** No change.
** 
**    Rev 1.25   06 Feb 1996 13:50:10   Shirley
** No change.
** 
**    Rev 1.24   01 Feb 1996 10:14:38   Shirley
** No change.
** 
**    Rev 1.23   26 Jan 1996 09:20:32   Shirley
** No change.
** 
**    Rev 1.22   25 Jan 1996 13:20:26   Shirley
** No change.
** 
**    Rev 1.21   24 Jan 1996 10:37:44   Shirley
** No change.
** 
**    Rev 1.20   23 Jan 1996 11:23:12   Shirley
** No change.
** 
**    Rev 1.19   18 Jan 1996 10:12:40   Shirley
** No change.
** 
**    Rev 1.18   15 Jan 1996 16:15:38   Shirley
** No change.
** 
**    Rev 1.17   04 Jan 1996 11:09:24   Shirley
** No change.
** 
**    Rev 1.16   30 Nov 1995 09:10:58   Shirley
** No change.
** 
**    Rev 1.15   28 Nov 1995 15:30:06   Shirley
** No change.
** 
**    Rev 1.14   21 Nov 1995 11:19:40   Shirley
** No change.
** 
**    Rev 1.13   13 Nov 1995 09:22:22   Shirley
** No change.
** 
**    Rev 1.12   12 Nov 1995 11:33:58   Shirley
** No change.
** 
**    Rev 1.11   08 Nov 1995 16:34:26   Shirley
** No change.
** 
**    Rev 1.10   08 Nov 1995 12:44:20   Shirley
** No change.
** 
**    Rev 1.9   02 Nov 1995 10:05:48   Shirley
** No change.
** 
**    Rev 1.8   27 Oct 1995 16:47:20   Shirley
** No change.
** 
**    Rev 1.7   27 Oct 1995 13:45:12   Shirley
** No change.
** 
**    Rev 1.6   25 Oct 1995 14:26:32   Shirley
** No change.
** 
**    Rev 1.5   18 Oct 1995 14:49:26   Shirley
** No change.
** 
**    Rev 1.4   13 Oct 1995 13:23:46   Shirley
** No change.
** 
**    Rev 1.3   29 Sep 1995 09:50:32   Shirley
** No change.
** 
**    Rev 1.2   20 Sep 1995 10:55:02   Shirley
** No change.
** 
**    Rev 1.1   15 Sep 1995 09:44:56   Shirley
** No change.
** 
**    Rev 1.0   07 Sep 1995 09:55:52   Shirley
** Initial revision.
**
****************************************************************************/

/*----------------------------------------------------------------------------
** 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
**
** $Log$
** 
** $Header:   D:/EPSLDV1/SRC/LOG/HASHTBL.H__   1.8   20 Jun 1996 09:27:44   ZJRD  $
**
** Copyright (C) 1995 Microtek International.  All rights reserved.
**
**--------------------------------------------------------------------------*/
#ifndef _HASHTBL_

                       /****************************
                        *                          *
                        *   INCLUDE FILES          *
                        *                          *
                        ****************************/
#include "memmanag.h"
#include "symutil.h"

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

};

#define _HASHTBL_
#endif
/******************************** E O F *************************************/
