hashlib.c

大名鼎鼎的嵌入式操作系统vxworks的完整的源代码

    return (hashTblDestroy (hashId, FALSE));	/* terminate the hash table */
    }

/*******************************************************************************
*
* hashTblDestroy - destroy a hash table
*
* This routine destroys the specified hash table and optionally frees the
* associated memory.  The hash table is marked as invalid.
*
* RETURNS: OK, or ERROR if hashId is invalid.
*/

STATUS hashTblDestroy
    (
    HASH_ID hashId,             /* id of hash table to destroy */
    BOOL    dealloc             /* deallocate associated memory */
    )
    {
    if (OBJ_VERIFY (hashId, hashClassId) != OK)
	return (ERROR);				/* invalid hash id */

    objCoreTerminate (&hashId->objCore);	/* terminate core */

    if (dealloc)
	return (objFree (hashClassId, (char *) hashId));

    return (OK);
    }

/*******************************************************************************
*
* hashTblPut - put a hash node into the specified hash table
*
* This routine puts the specified hash node in the specified hash table.
* Identical nodes will be kept in FIFO order in the hash table.
*
* RETURNS: OK, or ERROR if hashId is invalid.
*
* SEE ALSO: hashTblRemove()
*/

STATUS hashTblPut
    (
    HASH_ID     hashId,         /* id of hash table in which to put node */
    HASH_NODE   *pHashNode      /* pointer to hash node to put in hash table */
    )
    {
    int		index;

    if (OBJ_VERIFY (hashId, hashClassId) != OK)
	return (ERROR);				/* invalid hash id */

    /* invoke hash table's hashing routine to get index into table */

    index = (* hashId->keyRtn) (hashId->elements, pHashNode, hashId->keyArg);

    /* add hash node to head of linked list */

    sllPutAtHead (&hashId->pHashTbl [index], pHashNode);

    return (OK);
    }

/*******************************************************************************
*
* hashTblFind - find a hash node that matches the specified key
*
* This routine finds the hash node that matches the specified key.
*
* RETURNS: pointer to HASH_NODE, or NULL if no matching hash node is found.
*/

HASH_NODE *hashTblFind
    (
    FAST HASH_ID hashId,        /* id of hash table from which to find node */
    HASH_NODE    *pMatchNode,   /* pointer to hash node to match */
    int          keyCmpArg      /* parameter to be passed to key comparator */
    )
    {
    FAST HASH_NODE *pHNode;
    int	            ix;

    if (OBJ_VERIFY (hashId, hashClassId) != OK)
	return (NULL);				/* invalid hash node */

    /* invoke hash table's hashing routine to get index into table */

    ix = (* hashId->keyRtn) (hashId->elements, pMatchNode, hashId->keyArg);

    /* search linked list for above hash index and return matching hash node */

    pHNode = (HASH_NODE *) SLL_FIRST (&hashId->pHashTbl [ix]);

    while ((pHNode != NULL) &&
	   !((* hashId->keyCmpRtn) (pMatchNode, pHNode, keyCmpArg)))
	pHNode = (HASH_NODE *) SLL_NEXT (pHNode);

    return (pHNode);
    }

/*******************************************************************************
*
* hashTblRemove - remove a hash node from a hash table
*
* This routine removes the hash node that matches the specified key.
*
* RETURNS: OK, or ERROR if hashId is invalid or no matching hash node is found.
*/

STATUS hashTblRemove
    (
    HASH_ID     hashId,         /* id of hash table to to remove node from */
    HASH_NODE   *pHashNode      /* pointer to hash node to remove */
    )
    {
    HASH_NODE *pPrevNode;
    int	      ix;

    if (OBJ_VERIFY (hashId, hashClassId) != OK)
	return (ERROR);					/* invalid hash node */

    /* invoke hash table's hashing routine to get index into table */

    ix = (* hashId->keyRtn) (hashId->elements, pHashNode, hashId->keyArg);

    pPrevNode = sllPrevious (&hashId->pHashTbl [ix], pHashNode);

    sllRemove (&hashId->pHashTbl [ix], pHashNode, pPrevNode);

    return (OK);
    }

/*******************************************************************************
*
* hashTblEach - call a routine for each node in a hash table
*
* This routine calls a user-supplied routine once for each node in the
* hash table.  The routine should be declared as follows:
* .CS
*  BOOL routine (pNode, arg)
*      HASH_NODE *pNode;	/@ pointer to a hash table node     @/
*      int	  arg;		/@ arbitrary user-supplied argument @/
* .CE
* The user-supplied routine should return TRUE if hashTblEach() is to
* continue calling it with the remaining nodes, or FALSE if it is done and
* hashTblEach() can exit.
*
* RETURNS: NULL if traversed whole hash table, or pointer to HASH_NODE that
*          hashTblEach ended with.
*/

HASH_NODE *hashTblEach
    (
    HASH_ID     hashId,         /* hash table to call routine for */
    FUNCPTR     routine,        /* the routine to call for each hash node */
    int         routineArg      /* arbitrary user-supplied argument */
    )
    {
    FAST int  ix;
    HASH_NODE *pNode = NULL;

    if (OBJ_VERIFY (hashId, hashClassId) != OK)
	return (NULL);				/* invalid hash id */

    for (ix = 0; (ix < hashId->elements) && (pNode == NULL); ix++)
	pNode = (HASH_NODE *)sllEach (&hashId->pHashTbl[ix],routine,routineArg);

    return (pNode);		/* return node we ended with */
    }

/*******************************************************************************
*
* hashFuncIterScale - interative scaling hashing function for strings
*
* This hashing function interprets the key as a pointer to a null terminated
* string.  A seed of 13 or 27 appears to work well.  It calculates the hash as
* follows:
*
* .CS
*
*  for (tkey = pHNode->string; *tkey != '\0'; tkey++)
*	hash = hash * seed + (unsigned int) *tkey;
*
*  hash &= (elements - 1);
*
* .CE
*
* RETURNS: integer between 0 and (elements - 1)
*/

int hashFuncIterScale
    (
    int                 elements,       /* number of elements in hash table */
    H_NODE_STRING       *pHNode,        /* pointer to string keyed hash node */
    int                 seed            /* seed to be used as scalar */
    )
    {
    FAST char	*tkey;
    FAST int	hash = 0;

    /* Compute string signature (sparse 32-bit hash value) */

    for (tkey = pHNode->string; *tkey != '\0'; tkey++)
	hash = hash * seed + (unsigned int) *tkey;

    return (hash & (elements - 1));	/* mask hash to (0, elements - 1) */
    }

/*******************************************************************************
*
* hashFuncModulo - hashing function using remainder technique
*
* This hashing function interprets the key as a 32 bit quantity and applies the
* standard hashing function: h (k) = K mod D.  Where D is the passed divisor.
* The result of the hash function is masked to the appropriate number of bits
* to ensure the hash is not greater than (elements - 1).
*
* RETURNS: integer between 0 and (elements - 1)
*/

int hashFuncModulo
    (
    int         elements,       /* number of elements in hash table */
    H_NODE_INT  *pHNode,        /* pointer to integer keyed hash node */
    int         divisor         /* divisor */
    )
    {
    FAST int	hash;

    hash = pHNode->key % divisor;		/* modulo hashing function */

    return (hash & (elements - 1));		/* mask hash to (0,elements-1)*/
    }

/*******************************************************************************
*
* hashFuncMultiply - multiplicative hashing function
*
* This hashing function interprets the key as a unsigned integer quantity and
* applies the standard hashing function: h (k) = leading N bits of (B * K).
* Where N is the appropriate number of bits such that the hash is not greater
* than (elements - 1).  The overflow of B * K is discarded.  The value of B is
* passed as an argument.  The choice of B is similar to that of the seed to a
* linear congruential random number generator.  Namely, B's value should take
* on a large number (roughly 9 digits base 10) and end in ...x21 where x is an
* even number.  (Don't ask... it involves statistics mumbo jumbo)
*
* RETURNS: integer between 0 and (elements - 1)
*/

int hashFuncMultiply
    (
    int         elements,       /* number of elements in hash table */
    H_NODE_INT  *pHNode,        /* pointer to integer keyed hash node */
    int         multiplier      /* multiplier */
    )
    {
    FAST int	hash;

    hash = pHNode->key * multiplier;		/* multiplicative hash func */

    hash = hash >> (33 - ffsMsb (elements));	/* take only the leading bits */

    return (hash & (elements - 1));		/* mask hash to (0,elements-1)*/
    }

/*******************************************************************************
*
* hashKeyCmp - compare keys as 32 bit identifiers
*
* This routine compares hash node keys as 32 bit identifiers.
* The argument keyCmpArg is unneeded by this comparator.
*
* RETURNS: TRUE if keys match or, FALSE if keys do not match.
*
*ARGSUSED
*/

BOOL hashKeyCmp
    (
    H_NODE_INT  *pMatchHNode,   /* hash node to match */
    H_NODE_INT  *pHNode,        /* hash node in table to compare to */
    int         keyCmpArg       /* argument ingnored */
    )
    {
    if (pMatchHNode->key == pHNode->key)	/* simple comparison */
	return (TRUE);
    else
	return (FALSE);
    }

/*******************************************************************************
*
* hashKeyStrCmp - compare keys based on strings they point to
*
* This routine compares keys based on the strings they point to.  The strings
* must be null terminated.  The routine strcmp() is used to compare keys.
* The argument keyCmpArg is unneeded by this comparator.
*
* RETURNS: TRUE if keys match or, FALSE if keys do not match.
*
*ARGSUSED
*/

BOOL hashKeyStrCmp
    (
    H_NODE_STRING       *pMatchHNode,   /* hash node to match */
    H_NODE_STRING       *pHNode,        /* hash node in table to compare to */
    int                 keyCmpArg       /* argument ingnored */
    )
    {
    if (strcmp (pMatchHNode->string, pHNode->string) == 0)
	return (TRUE);
    else
	return (FALSE);
    }