/*====START_GENERATED_PROLOG======================================
 */
/*
 *   COMPONENT_NAME: odpubutils
 *
 *   CLASSES: none
 *
 *   ORIGINS: 82,27
 *
 *
 *   (C) COPYRIGHT International Business Machines Corp. 1995,1996
 *   All Rights Reserved
 *   Licensed Materials - Property of IBM
 *   US Government Users Restricted Rights - Use, duplication or
 *   disclosure restricted by GSA ADP Schedule Contract with IBM Corp.
 *   	
 *   IBM DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
 *   ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 *   PURPOSE. IN NO EVENT SHALL IBM BE LIABLE FOR ANY SPECIAL, INDIRECT OR
 *   CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
 *   USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
 *   OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE
 *   OR PERFORMANCE OF THIS SOFTWARE.
 */
/*====END_GENERATED_PROLOG========================================
 */
// @(#) 1.3 com/src/pubutils/src/HshTbl.c, odpubutils, od96nt, odnt9712d 8/21/96 09:05:55 [ 3/21/97 16:50:39 ]
/*
	File:		HshTbl.c

	Contains:	AEHshTbl from C version of Apple Event Manager.

	Owned by:	Jon Pugh

	Copyright:	© 1993 - 1995 by Apple Computer, Inc., all rights reserved.

	
*/


//#ifndef AEMDEFINES_H
//#include "AEMDefines.h"
//#endif

#include <errors.h>

#ifndef __HshTbl__
#include "HshTbl.h"
#endif

//#ifndef __AEUtil__
//#include "AEUtil.h"
//#endif

//#ifndef __AEDFWrpp__
//#include "AEDFWrpp.h"
//#endif

#ifndef __MEMORY__
#include <Memory.h>
#endif

#ifndef __STRING_H
#include <string.h>		// for memcpy
#endif

#ifndef __TOOLUTILS__
#include <ToolUtils.h>
#endif

/* Internal Details
 ---------------- 
																	  The value field when called from AEM
																	  
 																									'IsSpecial'
																				
	Hash Table Entry 								                                                  |
                                                                                                      |
	  hashed key    | Handle to list|    complete key data here     |-- user's value, variable size --|-----|
	+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+-v-+---+
	|      Tag      |    CollList   |      Key1     |      Key2     |  therefcon    :    procptr    :flag   |--> more entries              
	+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

    NOTE: This layout is fixed in this implementation. Calling NewHashTable with values in KeySize 
	      that do not conform to this description will not have the expected results. However, the
		  value can be a variable size.
		  
    1) Each entry may have a collision list associated with it. This is simply a linked list of
	Table Entries, which only exists if more than one key hashes to the same Tag.
	
	2) If the intial entry is emptied by RemoveKeyEntry, and there is a list, the DATA of the first
	list entry is moved into the table, the Handle that originally pointed to that list entry is
	disposed.
	
	3) Removal of a list entry is simply implemented by handle adjustment, and disposal of the original
	handle.
	
	4) Addition of a list entry is always at the head of the list, stack fashion.
	
	5) FindAnEntry notes, implied from the foregoing :
	  a) If there is a collision list, a pointer to an available slot will NEVER be returned
	     by FindAnEntry (kFoundKey or kNoSlot are the only returns in this case).
	  b) Two handles are also returned : 1 references the entry itself, the other references the entry
	     preceding it in the list.  If the current entry is the intial table entry, both are null.
		 Similarly, if the return is kNoSlot, both handles are null. If the entry is the first
		 in the list, the handle to the previous entry is null.
*/
		 /*
		 *    The header of a hash table 
		 *
		 */
#if defined(powerc) || defined (__powerc)
#pragma options align=mac68k
#endif
typedef struct TableInfoRec {
		 long	HashMask,	 			// Long mask to select the offset bits - set to KeySize -1.
		 		HashTableSize,			// physical size of the table.
		 		HashNumUsed, 			// not used in this implementation - number of entries in use
		 		HashEntrySize,			// size of an entry.
		 		HashNumExtra;			// not used  - # extra entries at end of table 
		 short	HashMagnitude,			// not used  - # bits in hash index
		 		HashFullPercent,		// not used  - grow table when more than this percent used
		 	  	HashPercentUsed,		// not used  - current percent used
		 		HValueOffset,			//offset to the value within an entry.
		 		HashKeySize,			//size of a key
		 		HashValueSize;			//size of a data value.
		 Boolean InSysHeap;				// is it in the system memory
	 }TableInfoRec,  * TableInfoPtr,  ** TableInfoHdl;
#if defined(powerc) || defined(__powerc)
#pragma options align=reset
#endif

	 
#define HeaderSize	sizeof(TableInfoRec)
		 /*
		 *
		 *   An Entry in the Table
		 *
		 */
typedef struct TableEntry  * TableEntryPtr;
typedef TableEntryPtr  * TableEntryHdl;

#if defined(powerc) || defined (__powerc)
#pragma options align=mac68k
#endif
typedef struct TableEntry {
			long			Tag;
			TableEntryHdl	CollList;     // if there are collisions, search this list
			KeyRec			theKey;
			handlerRec		theValue;
        }TableEntry;

#if defined(powerc) || defined(__powerc)
#pragma options align=reset
#endif
	   /*
	   *   Defines
	   *
	   */
#define BitsInLong (sizeof(long) * 8)  // used in InLineHash (c version)

#define  kEmptySlot	0L
       /* 1 of these 3 will be returned by FindAnEntry */
#define kFoundKey	 0		//found theKey, am returning a pointer to its' slot
#define kFoundSlot	 1		//didn't find theKey; returning a pointer to available slot
#define kNoSlot		 -1		//didn't find theKey; returning a pointer to CollList field of TableEntry

#define KeysNotEqual(x,y) ((x.firstKey != y.firstKey) || (x.secondKey != y.secondKey) )


/* Note that a collision indicates that there are 2(or more) entries xharing a Tag(hash) value, with different
   key values.
*/
#define collision(x) ((currEntry->Tag != x) \
					|| (KeysNotEqual((*(KeyRecPtr)srchKey),(*(KeyRecPtr)&currEntry->theKey))))

//------------------------ Prototypes of internal routines ---------------------------------

unsigned long InLineHash(KeyPtr srchKey);  // for PPC,  in C; 68K in assembler
				  
TableEntryPtr PointInTable(HHand Hash,KeyPtr srchKey, long  * theHashValue);

OSErr SrchCollLst(TableEntryHdl theList, long theTag, KeyPtr srchKey, HEntryPtr  * theEntry,
                  TableEntryHdl  * currHdl, TableEntryHdl  * PredHdl);

OSErr FindAnEntry(KeyPtr srchKey, HEntryPtr  * theEntry, HHand Hash,
				 TableEntryHdl  * theHdl, TableEntryHdl  * preHdl);

//--------------------------- internal routines -----------------------------------------------

//  C version of InLineHash

unsigned long int InLineHash(KeyPtr theKey)
{

   unsigned long  int * ulongPtr = (unsigned long  int *)theKey;
   unsigned long  int  workingLong = *ulongPtr;      // a key is 2 longs, we deal w/ them one at a time

 // Rotate left by 5
   workingLong = (workingLong >> 5) | (workingLong << (BitsInLong - 5)) + *ulongPtr;
   workingLong = (workingLong >> 5) | (workingLong << (BitsInLong - 5)) + *ulongPtr;
   workingLong = (workingLong >> 5) | (workingLong << (BitsInLong - 5)) + *(ulongPtr++);
   
   workingLong += *ulongPtr;
   
 // Rotate right by 5

   workingLong = (workingLong << 5) | (workingLong >> (BitsInLong - 5)) + *ulongPtr;
   workingLong = (workingLong << 5) | (workingLong >> (BitsInLong - 5)) + *ulongPtr;
   workingLong = (workingLong << 5) | (workingLong >> (BitsInLong - 5)) + *ulongPtr;

//   Multiply least significant word by 0xB33D, and store the product as long
   workingLong = (unsigned long  int)(LoWord(workingLong) * (unsigned short int)0XB33D);

//   set the most significant bit - insures no Tag will ever = 0
    BitSet((char  *) &workingLong,31L);
    return workingLong;
  }

// -------------------------------------------------------------------------------------------


		   /*
			PointInTable	Derive a pointer to a table entry
			-----------
			   Entry:	Hash    - Pointer to Handle to the hash table
						srchKey  - The key to be indexed
						
			   Exit:	returns - Pointer to the table entry , and :
						   theHashValue	- set to the hashed value of srchKey
		   */
TableEntryPtr PointInTable(HHand Hash,KeyPtr srchKey, long  * theHashValue)
   { long		theIndex;
     void  * hshDeRefPtr;
     if (Hash != NULL)
	   {
	     hshDeRefPtr = DEREF_OF(Hash);
		 *theHashValue = InLineHash(srchKey);                 // compute the hash value for the key.
		 theIndex = (*theHashValue & ((TableInfoPtr)hshDeRefPtr)->HashMask);	// mask down to the index bits.
		 theIndex *= ((TableInfoPtr)hshDeRefPtr)->HashEntrySize;	            // multiply by the entry size
		 CLEAR_REF_OF(Hash);
		 return (TableEntryPtr)((Ptr)hshDeRefPtr + HeaderSize + theIndex);
	   }
	 else
	    return NULL;
   }	/* PointInTable */
//-------------------------------------------------------------------------------------------
		   /*
			SrchCollLst		Search for the matching entry in the collision list.
			-----------
			   Entry:	theList - Handle to the collision list
			            theTag  - Hashed value to search for
						srchKey  - The key to search for
						
			   Exit:	result is 1 of :
						   kFoundKey	found srchKey, am returning a pointer to its' slot
						   kNoSlot		didn't find srchKey; theEntry is undefined
					    theEntry -  pointer as indicated above
						currHdl  -  Handle associated with theEntry
						PredHdl  -  Handle to entry before theEntry
		   */
OSErr SrchCollLst(TableEntryHdl theList, long theTag, KeyPtr srchKey, HEntryPtr  * theEntry,
                  TableEntryHdl  * currHdl, TableEntryHdl  * PredHdl)
   {
	 TableEntryPtr  currEntry;
	 OSErr	theReturn = kNoSlot;

     *currHdl  = theList;
	 currEntry  = (TableEntryPtr)DEREF_OF(*currHdl);
	 if (currEntry != NULL)
	  {
		theReturn = kFoundKey;     //let's be optimistic
		while (collision(theTag))
		  {
			if (currEntry->CollList == NULL)
			  {
				theReturn = kNoSlot;        // forget it
				 break;
			   }
			else
			 {
			  CLEAR_REF_OF(*currHdl);       //unlock the last one used
			  *PredHdl    = *currHdl;  // retain this handle as predecessor
			  *currHdl    = currEntry->CollList;
			  currEntry  = (TableEntryPtr)DEREF_OF(*currHdl);
			 }
		   }		/* while (collision(theTag)) */
		if (theReturn != kNoSlot)			//MUST, therefore, be kFoundKey
		   *theEntry = (HEntryPtr)currEntry;
	    }	        /* (currEntry != NULL) */
     CLEAR_REF_OF(*currHdl);       //drop deref the last one used
     return theReturn;
   }	/* SrchCollLst */
   
// ---------------------------------------------------------------------------------

// Dispose the hash table, the only tricky stuff is to get rid of all the collision lists first

OSErr  DisposeHashTable(HHand *Hash, MemProcs MemHooks)

   {
	   	TableInfoPtr		tblDeRefPtr;
	   	TableEntryPtr 	tblEntryPtr, tableEnd;
	   	TableEntryHdl	collisionList, tempEntry;


		if (*Hash != NULL)
			{
	    	HLOCK(*Hash);
			tblDeRefPtr = (TableInfoPtr)DEREF_OF(*Hash);
			tblEntryPtr = (TableEntryPtr)((Ptr)(tblDeRefPtr) + sizeof(TableInfoRec)); // start search here
			tableEnd = (TableEntryPtr)((Ptr)(tblDeRefPtr) + tblDeRefPtr->HashTableSize); // and end search here
			while (tblEntryPtr < tableEnd)
				{ // go through all the entry and look for the collision list
				collisionList=tblEntryPtr->CollList;
				while (collisionList != NULL)
					{
					tempEntry = ((TableEntryPtr)DEREF_OF(collisionList))->CollList; // next item in the collision list
					CLEAR_REF_OF(collisionList);
					DISPOSEHANDLE (collisionList);
					collisionList = tempEntry; // continue with next item in the collision list
					}
				// now go and look at the next entery
				tblEntryPtr = (TableEntryPtr)((Ptr)tblEntryPtr + tblDeRefPtr->HashEntrySize);
				}
			HUNLOCK(*Hash);
			DISPOSEHANDLE (*Hash);
			*Hash = NULL; // After we have disposed it, table does not exist
			}
		return noErr;
	}    // DisposeHashTable
//-------------------------------------------------------------------------------------------


		   /*
			FindAnEntry		Search for the matching entry.
			-----------
			   Entry:	srchKey - Pointer to the Key.
			            Hash - Pointer to HashTable handle
						
			   Exit:	return: 1 of :
						   kFoundKey	found srchKey, am returning a pointer to its' slot
						   kFoundSlot	didn't find srchKey; returning a pointer to available slot
						   kNoSlot		didn't find srchKey; returning pointer to TableEntry
					    theEntry -  pointer as indicated above
						theHdl   -  Handle associated with theEntry (NULL if initial table entry)
						PreHdl   -  Handle to entry before theEntry (NULL if table entry OR 1st list entry)
		   */
OSErr FindAnEntry(KeyPtr srchKey, HEntryPtr  * theEntry,HHand Hash,
                 TableEntryHdl  * theHdl, TableEntryHdl  * preHdl)
  {
	 TableEntryPtr  currEntry, 
	 				startEntry; 
	 OSErr	theReturn;
	 long 	theHashValue;
           
	 currEntry = startEntry = PointInTable(Hash, srchKey, &theHashValue);
	 *theHdl   = *preHdl = NULL;  		 //No handle to the entry, nor it's list predecessor
	 theReturn = kFoundKey;     		//let's be optimistic
	 if (currEntry->Tag == kEmptySlot)
	   theReturn = kFoundSlot;     		//an available slot to use
	 else
	   if (collision(theHashValue))
	     if (currEntry->CollList == NULL)
		   theReturn = kNoSlot;
		 else
	       theReturn = SrchCollLst(currEntry->CollList,theHashValue, srchKey, (HEntryPtr  * )&currEntry,
		                            theHdl, preHdl);

	 if (theReturn == kNoSlot)    /* return the ptr to the TableEntry indicated by theIndex */
	   {
	    *theEntry = (HEntryPtr)startEntry;   /* point to the TableEntry */
	    *theHdl   = *preHdl = NULL;   //No handle to the entry, nor it's list predecessor
		}
	 else
	    *theEntry = (HEntryPtr)currEntry;

     return theReturn;      // points to the correct one, a useable one, or CollList field of TableEntry
  }	/* FindAnEntry */
// ---------------------------------------------------------------------------------


// ------------------------Externally-available Functions ---------------------------

         /*
            GetKeyValue - Find the hashed entry.
			-----------
			   Entry:	Hash		- the hash table to search
			            Key			- Pointer to the Key.
						
			   Exit:	Returns an error if not found.
					    Value - memory pointed to is filled with the Value field of the entry.
         */
OSErr  GetKeyValue(HHand Hash, MemProcs MemHooks,KeyPtr Key, HEntryPtr Value)
   {
		OSErr			theReturn;
		HEntryPtr		theEntry;
		Ptr				EntryVal;  //the value in the table entry
	    TableEntryHdl	dummy = NULL;
		void  *		hshDeRefPtr;

        theReturn =  FindAnEntry(Key, &theEntry, Hash, &dummy, &dummy);
		if (theReturn == kFoundKey)
		   {
		      theReturn = noErr;
			  hshDeRefPtr = (TableInfoPtr)DEREF_OF(Hash);
		   	  EntryVal = (theEntry + ((TableInfoPtr)hshDeRefPtr)->HValueOffset);

/*
		      for (i = 0; i < ((TableInfoPtr)hshDeRefPtr)->HashValueSize; i++,((char  *)Value)++,EntryVal++)
		         *Value = *EntryVal;
*/
			  memcpy((void *)Value, (void *)EntryVal, ((TableInfoPtr)hshDeRefPtr)->HashValueSize);
             CLEAR_REF_OF(Hash);
		   }		/* (theReturn == kFoundKey) */
		else
		   theReturn = ErrNotFound;

		return theReturn;
   }		/* GetKeyValue */
// ---------------------------------------------------------------------------------

/*
CheckKey - Find the hashed entry.
-----------
Entry:	Hash	- the hash table to search
Key	- Pointer to the Key.

Exit:	Returns an error if not found.
Value - memory pointed to is filled with the Value field of the entry.
*/
Boolean CheckKey(HHand Hash, MemProcs MemHooks, KeyPtr Key) 
{
HEntryPtr	theEntry;
TableEntryHdl	dummy = NULL;

return ((FindAnEntry(Key, &theEntry, Hash, &dummy, &dummy)) == kFoundKey);
}	/* CheckKey */

// --------------------------------------------------------------------------------- 
// Get the index th entry from the hash table, the order we use here is we go through the table
// and down the collison list if possible, so the order would be like 1, 2, 2a, 2b, 3, 4, 4a, 4b
// where the alphabet subscript is on the collision list

// if we ever need to speed it up, a simple way is to remember the entry for the last GetIndexedEntry call


OSErr  GetIndexedEntry(HHand Hash, MemProcs MemHooks, long Index, KeyPtr Key, HEntryPtr Value)

   {
	   OSErr			err;
	   long 			itemsFound;
	   TableInfoPtr		tblDeRefPtr;
	   TableEntryPtr 	tblEntryPtr, tableEnd;
	   TableEntryHdl	collisionList, tempEntry;
	   Ptr				aPtr;
	   
		err = ErrEndOfTable; // assume we reach the end of the table
		if (++Index <= 0) return err; // also change from 0 origin to 1 origin
		itemsFound = 0; // we have found nothing yet
		tblDeRefPtr = (TableInfoPtr)DEREF_OF(Hash);
		tblEntryPtr = (TableEntryPtr)((Ptr)(tblDeRefPtr) + sizeof(TableInfoRec)); // start search here
		tableEnd = (TableEntryPtr)((Ptr)(tblDeRefPtr) + tblDeRefPtr->HashTableSize); // and end search here
		collisionList = NULL; // we are not in any collision yet
		
		while (tblEntryPtr < tableEnd)
			{
			if (collisionList != NULL)
				{ // we are in the middle of marching through the collision list
				if (++itemsFound == Index)
					{ // we found it in the collisionList, copy the key and value
					tblEntryPtr = (TableEntryPtr)DEREF_OF(collisionList);
					memcpy(Key, (Ptr)(&(tblEntryPtr->theKey)), tblDeRefPtr->HashKeySize);
					memcpy(Value, (Ptr)(tblEntryPtr)+tblDeRefPtr->HValueOffset, tblDeRefPtr->HashValueSize);
					CLEAR_REF_OF(collisionList);
					err = noErr;
					break;
					}
				else
					{ // access the next item in the collision list
					tempEntry = ((TableEntryPtr)DEREF_OF(collisionList))->CollList;
					CLEAR_REF_OF(collisionList);
					collisionList = tempEntry;
					}
				}
			else if (tblEntryPtr->Tag == kEmptySlot)
				/* tblEntryPtr++; // keep marching until we find an non-empty slot */
                tblEntryPtr = (TableEntryPtr)((Ptr)tblEntryPtr + tblDeRefPtr->HashEntrySize);   //will work even if TableEntry not same size as specified by struct
			else
				{ // we found another entry
				if (++itemsFound == Index)
					{ 
					aPtr = (Ptr)&(tblEntryPtr->theKey);
					memcpy(Key, (Ptr)(&(tblEntryPtr->theKey)), tblDeRefPtr->HashKeySize);
					memcpy(Value, (Ptr)(tblEntryPtr)+tblDeRefPtr->HValueOffset, tblDeRefPtr->HashValueSize);
					err = noErr;
					break;
					}
				else
					{
					collisionList = tblEntryPtr->CollList; // we may march down the collision list next
					tblEntryPtr++;
					}
				}
			}
		CLEAR_REF_OF(Hash);
		return err;
	}
			
			
		
		

// ---------------------------------------------------------------------------------
		/*
			 NewHashTable - Creates a new hash table and returns the handle.
			 -----------
			   Entry:	NumEntries		- Initial # of entries to establish
			            KeySize,
						ValueSize   - Sizes for these fields
						SysHeap     - Should the System heap be used; if not, goes in App heap
			   Exit:	Returns an error if failure.
					    Table - pointer to the handle to the hashtable.
		*/
OSErr  NewHashTable(long NumEntries,short KeySize, short ValueSize,MemProcs MemHooks,
									Boolean SysHeap, HHand  * Table)
   {
	   long		TableSize;
	   OSErr	theReturn = noErr;
	   TableEntryPtr theEntry;
	   long i;
	   TableInfoPtr	tblDeRefPtr;
	   long		entrySize;
	   
	   							//calculate the size of one entry, round up to even number
	   entrySize = (sizeof(long) + sizeof(TableEntryHdl) + KeySize + ValueSize + 1) & -2;
								//calculate the table size, and add header size
       TableSize = (NumEntries * entrySize) + HeaderSize;
								// create the hash table.
		if (SysHeap)     // don't store the handle in applications heap
		   *Table = NEWHANDLESYS(TableSize);
		else                  // DO store the handle in an app's AppRec
           *Table = NEWHANDLE(TableSize);
								// Set up the header with all of our information.
        if (*Table != NULL)
		  {
		   tblDeRefPtr =(TableInfoPtr)DEREF_OF(*Table);
		   tblDeRefPtr->HashMask		= NumEntries-1;
		   tblDeRefPtr->HashTableSize	= TableSize;
		   tblDeRefPtr->HashNumUsed		= 0;                  //not used in this implementation
		   tblDeRefPtr->HashEntrySize	= entrySize; // hash + collision + key + value
		   tblDeRefPtr->HashNumExtra	= 0;                  //not used in this implementation
		   tblDeRefPtr->HashMagnitude	= 0;                  //not used in this implementation
		   tblDeRefPtr->HashFullPercent	= 0;              //not used in this implementation
		   tblDeRefPtr->HashPercentUsed	= 0;              //not used in this implementation
		   tblDeRefPtr->HValueOffset	= sizeof(long) + sizeof(TableEntryHdl) + KeySize;  //the Tag + collison + theKey
		   tblDeRefPtr->HashKeySize		= KeySize;      // This BETTER be sizeof(KeyRec)
		   tblDeRefPtr->HashValueSize	= ValueSize;    // This BETTER be >= sizeof(handlerRec)
		   tblDeRefPtr->InSysHeap		= SysHeap;    	// added so we don't need param in ReplaceEntry etc
							
           theEntry = (TableEntryPtr)((Ptr)tblDeRefPtr + HeaderSize);  //point to first actual entry
		   for (i = 0; i < NumEntries; i++, theEntry=(TableEntryPtr)((Ptr)theEntry+entrySize))
		     {
			    theEntry->Tag										= kEmptySlot;
			    theEntry->CollList						  			= NULL;
		/* Somewhat bizarre initialization values used for ease of debugging */
				if (KeySize >= sizeof(KeyRec))
					{ // only do this is the key size is big enough to do it
					(*(KeyRecPtr)&(theEntry->theKey)).firstKey		 = 0x0FFFFFFFF;
					(*(KeyRecPtr)&(theEntry->theKey)).secondKey		 = 0x0AAAAAAAA;
					}
				if (ValueSize >= sizeof(handlerRec))
					{ // only do this is the value size is big enough to do it
					(*(handlerRec *)&(theEntry->theValue)).theRefCon = 0x0BBBBBBBB;
					(*(handlerRec *)&(theEntry->theValue)).theProc	 = (UniversalProcPtr) 0x0CCCCCCCC;
					(*(handlerRec *)&(theEntry->theValue)).IsSpecial = false;
					}
			 }	/* for */
           CLEAR_REF_OF(*Table);
		  }	  	/* (*Table != NULL) */
        else
		  theReturn = ErrNoHashTable;
		  
	  return theReturn;
   }	/* NewHashTable */

// ---------------------------------------------------------------------------------
		/*
			 RemoveKeyEntry - Returns an error if entry not found.
			 --------------
			   Entry:	Hash		- the hash table to search
			            Key			- Pointer to the Key.
						
			   Exit:	Returns an error if not found.
		*/
OSErr  RemoveKeyEntry(HHand Hash, MemProcs MemHooks,KeyPtr Key)
   {
		OSErr			theReturn = noErr;
		long			dummy;
		HEntryPtr		theEntry,
				 		tblEntry;
		register short	i;
        TableEntryHdl  	theHdl,
		               	preHdl;
		TableEntryPtr   theHdlDeRefPtr;
		TableEntryPtr   preHdlDeRefPtr;
		TableEntryPtr   lstDeRefPtr;
		
		TableInfoPtr	tableDeRefPtr;
		long			entrySize;
		Boolean			InSys;
		Ptr				entryChars;

		tableDeRefPtr = (TableInfoPtr)DEREF_OF(Hash);
		entrySize = tableDeRefPtr->HashEntrySize;
		InSys = tableDeRefPtr->InSysHeap;
		CLEAR_REF_OF(Hash);

        if (FindAnEntry(Key, &theEntry, Hash, &theHdl, &preHdl) == kFoundKey)
		   if (theHdl == NULL)             // this is the initial table entry
			  {	
				 if (((TableEntryPtr)theEntry)->CollList != NULL)
					{			         // There's a collision list, move values from it's 1st entry			  
					  lstDeRefPtr = (TableEntryPtr)DEREF_OF(((TableEntryPtr)theEntry)->CollList);
					  

/*					  for (i = 0; i < entrySize; i++, ((char  *)theEntry)++,((Ptr)lstDeRefPtr)++ )
			             *((Ptr)theEntry) = *((Ptr)lstDeRefPtr);
*/
					  memcpy((void *)theEntry, (void *)lstDeRefPtr, entrySize);

#if WINDOWS /*  11/6   RETAIN TILL DECIDE WHAT TO DO ABOUT SYSTEM HEAP */
                        // don't want to us myGlobalFree if this is in the system heap
					 if(InSys)
					   {
					     HUNLOCK(((TableEntryPtr)theEntry)->CollList);
						 GlobalFree((HGLOBAL)((TableEntryPtr)theEntry)->CollList);
					   }
					 else
#endif
					  DISPOSEHANDLE (((TableEntryPtr)theEntry)->CollList);
					}	/* (((TableEntryPtr)theEntry)->CollList != NULL) i.e. there's a collision list */
				  else			             // this has no collision list
					{ 						//clear this entry, and set Tag to indicate it's available
/*
					  for (i = 0; i < entrySize; i++, ((char  *)theEntry)++)
						 *((Ptr)theEntry) = (char)0;
*/
					  entryChars = theEntry;
					  for (i = 0; i < entrySize; i++, entryChars++)
						 *entryChars = (char)0;
					  ((TableEntryPtr)theEntry)->Tag = kEmptySlot;
					}
			  }			/* (theHdl = NULL) i.e initial table entry */
		   else            // this is a list entry
			  {
				 theHdlDeRefPtr = (TableEntryPtr)DEREF_OF(theHdl);
				 if (preHdl == NULL)           //first list entry
				    {		  				 //pesky - have to re-index initial table entry
					   tblEntry = (HEntryPtr)PointInTable(Hash, Key, &dummy);
					  ((TableEntryPtr)tblEntry)->CollList = theHdlDeRefPtr->CollList;
					 }
				 else                         // there are others in the list
				   {
				      preHdlDeRefPtr = (TableEntryPtr)DEREF_OF(preHdl);
					  preHdlDeRefPtr->CollList = theHdlDeRefPtr->CollList;
				      CLEAR_REF_OF(preHdl);
				   }
#if WINDOWS /*  11/6   RETAIN TILL DECIDE WHAT TO DO ABOUT SYSTEM HEAP */
				   // don't want to us myGlobalFree if this is in the system heap
				if(InSys)
				  {
					HUNLOCK(((TableEntryPtr)theEntry)->CollList);
					GlobalFree((HGLOBAL)((TableEntryPtr)theEntry)->CollList);
				  }
				else
#endif
				 DISPOSEHANDLE (theHdl);
			  }			/* list entry */
		else           // FindAnEntry failed
		   theReturn = ErrNotFound;

		return theReturn;
   }		/* RemoveKeyEntry */
// ---------------------------------------------------------------------------------

         /*
            ReplaceEntry - Replace the fields of an existent entry OR add a new one.
			------------
			   Entry:	Hash		- the hash table to search
			            Key			- Pointer to the Key to add.
					    Value       - pointer to value to add.
						
			   Exit:	Returns ErrAlreadyExists if unable to replace or create a new one - unlikely.
         */
		 
OSErr  ReplaceEntry(HHand Hash, MemProcs MemHooks,KeyPtr Key,HEntryPtr Value)
   {
		OSErr			theReturn;
		TableEntryPtr	theEntry;
		TableEntryHdl   NewEntryHdl;
		TableEntryHdl	* OldCollLstPtr = NULL;
	    TableEntryHdl	preHdl, currHdl;
	    TableInfoPtr	tblDeRefPtr;
		Boolean			InSys;

        theReturn =  FindAnEntry(Key, (HEntryPtr  *)&theEntry, Hash, &currHdl, &preHdl);
		                     //First, lock Hash, so theEntry will remain valid
	    HLOCK(Hash);
		tblDeRefPtr = (TableInfoPtr)DEREF_OF (Hash);
		
		if (theReturn == kNoSlot)        // Must create a new entry
		   { 
			  InSys = tblDeRefPtr->InSysHeap;
/*  11/6   RETAIN TILL DECIDE WHAT TO DO ABOUT SYSTEM HEAP */
			  if(InSys)
                  NewEntryHdl = (TableEntryHdl)NEWHANDLESYS (tblDeRefPtr->HashEntrySize);
              else
                NewEntryHdl = (TableEntryHdl)NEWHANDLE (tblDeRefPtr->HashEntrySize);
		      if (NewEntryHdl == NULL)
			      theReturn = memFullErr;
			   else
			     {		 //retain a ptr to CollList field, for linking new entry into head of list
				   OldCollLstPtr = &theEntry->CollList;
			       theEntry = (TableEntryPtr)DEREF_OF(NewEntryHdl);
			      }
		   }	/* Creating a new entry */
		 if (theReturn != memFullErr)           /* Move the data in */
		   {
			  theEntry->Tag = InLineHash(Key);    // compute the hash value for the key.
			  (*(KeyRecPtr)&theEntry->theKey).firstKey  = ((KeyRecPtr)Key)->firstKey;
			  (*(KeyRecPtr)&theEntry->theKey).secondKey = ((KeyRecPtr)Key)->secondKey;

			  memcpy(((Ptr)theEntry)+tblDeRefPtr->HValueOffset, Value, tblDeRefPtr->HashValueSize);

              if (OldCollLstPtr!= NULL)       //Added a new list item - hook it in at head of list
			    {
			        theEntry->CollList = *OldCollLstPtr; 				 //point to previous head of list
					*OldCollLstPtr = NewEntryHdl;         				//hook in as new head of list
				    CLEAR_REF_OF(NewEntryHdl);
			     }
			  theReturn = noErr;
			  CLEAR_REF_OF(currHdl);
		   }		/* (theReturn != memFullErr) */
	    HUNLOCK(Hash);
		return theReturn;
   }	/* ReplaceEntry */
// ---------------------------------------------------------------------------------

