/* hashLib.c - generic hashing library *//* Copyright 1990-1993 Wind River Systems, Inc. */#include "copyright_wrs.h"/*modification history--------------------01l,12feb93,kdl  changed hashLibInit() to handle multiple invocations.01k,04jul92,jcf  scalable/ANSI/cleanup effort.01j,26may92,rrr  the tree shuffle01i,19nov91,rrr  shut up some ansi warnings.01h,04oct91,rrr  passed through the ansification filter                  -changed functions to ansi style		  -changed includes to have absolute path from h/		  -changed VOID to void		  -changed copyright notice01g,01oct90,jcf   fixed hashTblEach() to traverse table correctly.01f,28sep90,jcf   documentation.01e,17jul90,dnw   changed call to objAlloc() to objAllocExtra()01d,05jul90,jcf   documentation.01c,23jun90,jcf   changed ffs to ffsMsb.01b,22apr90,jcf   removed hashTblShow to indepent show routine library.01a,17nov89,jcf   written.*//*DESCRIPTIONThis subroutine library supports the creation and maintenance of achained hash table.  Hash tables efficiently store hash nodes for fast access.They are frequently used for symbol tables, or other name to identifierfunctions.  A chained hash table is an array of singly linked list heads,with one list head per element of the hash table.  During creation a hash tableis passed two user-definable functions, the hashing function, and the hash nodecomparator.HASH NODESA hash node is a structure used for chaining nodes together in the table.The defined structure HASH_NODE is not complete because it contains no fieldfor the key for referencing, and no place to store data.  The user completesthe hash node by including a HASH_NODE in a structure containing the necessarykey and data fields.  This flexibility allows hash tables to better suitvarying data representations of the key and data fields.  The hashing functionand the hash node comparator determine the full hash node representation.  Referto the defined structures H_NODE_INT and H_NODE_STRING for examples of thegeneral purpose hash nodes used by the hashing functions and hash nodecomparators defined in this library.HASHING FUNCTIONSOne function, called the hashing function, controls the distribution of nodesin the table.  This library provides a number of standard hashing functions,but applications can specify their own.  Desirable properties of a hashingfunction are that they execute quickly, and evenly distribute the nodesthroughout the table.  The worst hashing function imaginable would be:h(k) = 0.  This function would put all nodes in list associated with thezero element in the hash table.  Most hashing functions find their originin random number generators.Hashing functions must return an index between zero and (elements - 1).  Theytake the following form:.CSint hashFuncXXX (elements, pHashNode, keyArg)    int		elements;	/@ number of elements in hash table        @/    HASH_NODE	*pHashNode;	/@ hash node to pass through hash function @/    int		keyArg;		/@ optional argument to hash function      @/.CEHASH NODE COMPARATOR FUNCTIONSThe second function required is a key comparator.  Different hash tables maychoose to compare hash nodes in different ways.  For example, the hash nodecould contain a key which is a pointer to a string, or simply an integer.The comparator compares the hash node on the basis of some criteria, andreturns a boolean as to the nodes equivalence.  Additionally, the keycomparator can use the keyCmpArg for additional information to the comparator.The keyCmpArg is passed from all the hashLib functions which use the thecomparator.  The keyCmpArg is usually not needed except for advancedhash table queurying.symLib is a good example of the utilization of the keyCmpArg parameter.symLib hashes the name of the symbol.  It finds the id based on thename using hashTblFind(), but for the purposes of putting and removingsymbols from the symbol's hash table, an additional comparison restrictionapplies.  Symbols have types, and while symbols of equivalent names can exist,no symbols of equivalent name and type can exist.  So symLib utilizes thekeyCmpArg as a flag to denote the which operation being performed on the hashtable: symbol name matching, or complete symbol name and type matching.Key comparator functions must return a boolean.  They take the following form:.CSint hashKeyCmpXXX (pMatchNode, pHashNode, keyCmpArg)    HASH_NODE	*pMatchNode;	/@ hash node to match                        @/    HASH_NODE	*pHashNode;	/@ hash node in table being compared to      @/    int		keyCmpArg;	/@ parameter passed to hashTblFind (2)       @/.CEHASHING COLLISIONSHashing collisions occur when the hashing function returns the same index whengiven two unique keys.  This is unavoidable in cases where there are more nodesin the hash table then there are elements in the hash table.  In a chainedhash table, collisions are resolved by treating each element of the table asthe head of a linked list.  Nodes are simply added to appropriate listregardless of other nodes already in the list.  The list is not sorted, butnew nodes are added at the head of the list because newer entries are usuallysearched for before older entries.  When nodes are removed or searched for,the list is traversed from the head until a match is found.STRUCTURE.CS   HASH_HEAD 0           HASH_NODE         HASH_NODE   ---------             --------          --------   | head--------------->| next----------->| next---------   |       |             |......|          |......|      |   | tail------          | key  |          | key  |      |   |       |  |          | data |          | data |      v   ---------  |          --------          --------     ---              |                             ^            -              |                             |              -------------------------------   HASH_HEAD 1           HASH_NODE   ---------             --------   | head--------------->| next---------   |       |             |......|      |   | tail------          | key  |      |   |       |  |          | data |      v   ---------  |          --------     ---              |           ^            -              |           |              -------------    ...    ...   HASH_HEAD N   ---------   | head-----------------   |       |             |   | tail---------       |   |       |     |       v   ---------    ---     ---		 -	 -.CECAVEATSHash tables must have a number of elements equal to a power of two.INCLUDE FILE: hashLib.h*/#include "vxWorks.h"#include "errno.h"#include "hashLib.h"#include "string.h"#include "private/classLibP.h"#include "private/objLibP.h"IMPORT int ffsMsb (int bitfield);/* locals */LOCAL OBJ_CLASS hashClass;LOCAL BOOL	hashLibInstalled = FALSE;  /* protect from multiple inits *//* globals */CLASS_ID hashClassId = &hashClass;/********************************************************************************* hashLibInit - initialize hash table library** This routine initializes the hash table package.*/STATUS hashLibInit (void)    {    if (!hashLibInstalled &&(classInit (hashClassId, sizeof (HASH_TBL), 		       	     		OFFSET(HASH_TBL,objCore),		       	     		(FUNCPTR) hashTblCreate, 					(FUNCPTR) hashTblInit,		       	     		(FUNCPTR) hashTblDestroy) == OK))	{	hashLibInstalled = TRUE;	}	    return ((hashLibInstalled) ? OK : ERROR);    }/********************************************************************************* hashTblCreate - create a hash table** This rountine creates a hash table 2^sizeLog2 number of elements.  The hash* table is carved from the system memory pool via malloc (2).  To accomidate* the list structures associated with the table, the actual amout of memory* alocated will be roughly eight times the number of elements requested.* Additionallly, two routines must be specified to dictate the behavior of the* hashing table.  The first routine is the hashing function.** The hashing function's role is to disperse the hash nodes added to the table* as evenly throughout the table as possible.  The hashing function receives as* its parameters; the number of elements in the table, a pointer to the* HASH_NODE structure, and finally the keyArg parameter passed to this* routine.  The keyArg may be used to seed the hashing function.  The hash* function returns an index between 0 and (elements - 1).  Standard hashing* functions are available in this library.** The keyCmpRtn parameter specifies the other function required by the hash* table.  This routine tests for equivalence of two HASH_NODES.  It returns a* boolean, TRUE if the keys match, and FALSE if they differ.  As an example,* a hash node may contain a HASH_NODE followed by a key which is an unsigned* integer identifiers, or a pointer to a string, depending on the application.* Standard hash node comparators are available in this library.** RETURNS: HASH_ID, or NULL if hash table could not be created.** SEE ALSO: hashFuncIterScale(), hashFuncModulo(), hashFuncMultiply()* 	    hashKeyCmp(), hashKeyStrCmp()*/HASH_ID hashTblCreate    (    int         sizeLog2,       /* number of elements in hash table log 2 */    FUNCPTR     keyCmpRtn,      /* function to test keys for equivalence */    FUNCPTR     keyRtn,         /* hashing function to generate hash from key */    int         keyArg          /* argument to hashing function */    )    {    unsigned extra  = (1 << sizeLog2) * sizeof (SL_LIST);    HASH_ID hashId;    SL_LIST *pList;    hashId  = (HASH_ID) objAllocExtra (hashClassId, extra, (void **) &pList);    if (hashId != NULL)	hashTblInit (hashId, pList, sizeLog2, keyCmpRtn, keyRtn, keyArg);    return (hashId);				/* return the hash id */    }/********************************************************************************* hashTblInit - initialize a hash table** This routine initializes a hash table.** RETURNS: OK*/STATUS hashTblInit    (    HASH_TBL    *pHashTbl,      /* pointer to hash table to initialize */    SL_LIST     *pTblMem,       /* pointer to memory of sizeLog2 SL_LISTs */    int         sizeLog2,       /* number of elements in hash table log 2 */    FUNCPTR     keyCmpRtn,      /* function to test keys for equivalence */    FUNCPTR     keyRtn,         /* hashing function to generate hash from key */    int         keyArg          /* argument to hashing function */    )    {    FAST int ix;    pHashTbl->elements	= 1 << sizeLog2;	/* store number of elements */    pHashTbl->keyCmpRtn	= keyCmpRtn;		/* store comparator routine */    pHashTbl->keyRtn	= keyRtn;		/* store hashing function */    pHashTbl->keyArg	= keyArg;		/* store hashing function arg */    pHashTbl->pHashTbl	= pTblMem;    /* initialize all of the linked list heads in the table */    for (ix = 0; ix < pHashTbl->elements; ix++)	sllInit (&pHashTbl->pHashTbl [ix]);    objCoreInit (&pHashTbl->objCore, hashClassId);	/* initialize core */    return (OK);    }/********************************************************************************* hashTblDelete - delete a hash table** This routine deletes the specified hash table and frees the* associated memory.  The hash table is marked as invalid.** RETURNS: OK, or ERROR if hashId is invalid.*/STATUS hashTblDelete    (    HASH_ID hashId              /* id of hash table to delete */    )    {    return (hashTblDestroy (hashId, TRUE));	/* delete the hash table */    }/********************************************************************************* hashTblTerminate - terminate a hash table** This routine terminates the specified hash table.  The hash table is marked* as invalid.** RETURNS: OK, or ERROR if hashId is invalid.*/STATUS hashTblTerminate    (    HASH_ID hashId              /* id of hash table to terminate */    )    {