hash.c

基于h323协议的软phone

#ifdef __cplusplus
extern "C" {
#endif



/*
***********************************************************************************

NOTICE:
This document contains information that is proprietary to RADVISION LTD..
No part of this publication may be reproduced in any form whatsoever without
written prior approval by RADVISION LTD..

RADVISION LTD. reserves the right to revise this publication and make changes
without obligation to notify any person of such revisions or changes.

***********************************************************************************
*/

/*
  ohash.c

  Irina S.
  20 Jan. 1998

  Opened hash table implementation


  Notes:
  Hash function is provided by the user.
  Hash function parameters may be duplicated in the hash table.
  Each table element holds list id. New collided parameter is
  positioned in the list corresponding to parameter key.
  Duplicated parameters following each other in the corresponding list.
  The hash size is the first prime number above the supplied hashSize.

  */


#include <string.h>
#include "rvmemory.h"
#include "ra.h"
#include "hash.h"
#include "intutils.h"


/************************************************************************
 * hashStruct structure
 * Structure holding a HASH object
 * hash             - Hash function used
 * compare          - Comparison function used
 * numKeys          - Size of the hash table (number of keys supported)
 * userKeySize      - Size of the keys inside the hash table
 * userElemSize     - Size of the elements inside the hash table
 * alignedKeySize   - Size of the keys inside the hash table, aligned to 32bits
 * numElements      - Number of elements that can be stored inside the hash
 * curSize          - Current number of occupied elements
 * keys             - List of keys (the hash table)
 *                    This array holds pointers to the elements
 * elements         - Table of stored elements (RA)
 *                    See hashListElement to see the value itself
 ************************************************************************/
typedef struct
{
    hashFunc        hash;
    hashCompareFunc compare;
    RvUint32        numKeys;
    RvUint32        userKeySize;
    RvUint32        userElemSize;
    RvUint32        alignedKeySize;
    RvUint32        numElements;
    RvUint32        curSize;
    RAElement*      keys;
    HRA             elements;
} hashStruct;


/************************************************************************
 * hashListElement struct
 * This structure will be included in any user element and serve for
 * pointing to the next and prev elements in the list of elements that
 * were mapped to the same entry (collision/key)
 * next     - Pointer to the next user element with the same key value
 * prev     - Pointer to the previous user element with the same key value
 * entryNum - The entry location of the key value in the hash table
 *
 * Note: Inside the elements RA, the information stored in each element
 *       is the list element, the key and the data in their written order.
 ************************************************************************/
typedef struct hashListElement_tag hashListElement;
struct hashListElement_tag
{
    hashListElement*    next;
    hashListElement*    prev;
    int                 entryNum;
};




/************************************************************************
 * Default hashing function.
 * input  : param       - Pointer to the element to hash
 *          paramSize   - Size of the element to hash in bytes
 *                        When this value <=0, then 'param' is considered
 *                        to be NULL terminated.
 *          hashSize    - Size of the hash table used for the hash
 *                        function's return value
 * return : Hash result
 ************************************************************************/
RvUint32 hashstr(
    IN void*    param,
    IN int      paramSize,
    IN int      hashSize)
{
    RvUint32 hash=0;
    char* ptr = (char *)param;

    if (paramSize <= 0)
    {
        /* string is null terminated */
        while (*ptr) hash = hash << 1 ^ *ptr++;
    }
    else
    {
        while (paramSize-- > 0 && *ptr) hash = hash << 1 ^ *ptr++;
    }

    return (hash % hashSize);
}


/************************************************************************
 * Default comparison function. Checks byte-by-byte.
 * input  : key1, key2  - Keys to compare
 *          keySize     - Size of each key
 * return : RV_TRUE if elements are the same
 *          RV_FALSE otherwise
 ************************************************************************/
RvBool hashDefaultCompare(IN void *key1, IN void* key2, IN RvUint32 keySize)
{
    return (memcmp(key1, key2, keySize) == 0);
}



/************************************************************************
 * hashConstruct
 * purpose: Create a HASH object, holding a hash table of keys and the
 *          actual data in an array
 * input  : numOfKeys       - Size of hash table.
 *                            This is the amount of keys available for use
 *                            It should be greater than the number of
 *                            elements in the table
 *          numOfElems      - Number of elements that will be stored
 *                            in the hash table
 *          hashFunc        - Hash function used on the data
 *          compareFunc     - Comparison function used on the keys
 *          keySize         - Size of the keys
 *          elemSize        - Size of the elements
 *          name            - Name of HASH (used in log messages)
 * output : none
 * return : Handle to RA constructed on success
 *          NULL on failure
 ************************************************************************/
HHASH
hashConstruct(
    IN  int             numOfKeys,
    IN  int             numOfElems,
    IN  hashFunc        hashFunc,
    IN  hashCompareFunc compareFunc,
    IN  int             keySize,
    IN  int             elemSize,
    IN  const char*     name)
{
    hashStruct* hash;
    RvUint32    actualKeySize;

    /* Calculate the actual size of the hash table = number of keys */
    actualKeySize = intFirstPrime(numOfKeys);

    /* Allocate the HASH object and the hash table itself
     * We make sure to leave it empty to the hash table will be filled with NULL
     * pointers.
     */
    RvMemoryAlloc(NULL, (void**)&hash, sizeof(hashStruct)+actualKeySize*sizeof(RAElement));
    memset(hash, 0, sizeof(hashStruct)+actualKeySize*sizeof(RAElement));

    /* Set the HASH object struct */
    hash->hash = hashFunc;
    hash->compare = compareFunc;
    hash->numKeys = actualKeySize;
    hash->userKeySize = keySize;
    hash->userElemSize = elemSize;
    hash->alignedKeySize = RvRoundToSize(keySize, RV_ALIGN_SIZE);
    hash->numElements = numOfElems;
    hash->curSize = 0;
    hash->keys = (RAElement*)((RvUint8*)hash + sizeof(hashStruct));

    /* Construct the elements RA */
    hash->elements =
        raConstruct((int)(elemSize + hash->alignedKeySize + sizeof(hashListElement)), numOfElems, RV_FALSE, name);
    if (hash->elements == NULL)
    {
        RvMemoryFree(hash);
        return NULL;
    }

    return (HHASH)hash;
}


/************************************************************************
 * hashDestruct
 * purpose: Delete a HASH object, freeing all of the taken memory
 * input  : hHash   - HASH object handle
 * output : none
 * return : Non negative value on succes
 *          Negative value on failure
 ************************************************************************/
int
hashDestruct(
    IN  HHASH hHash)
{
    hashStruct* hash = (hashStruct *)hHash;

    if (!hash) return RV_ERROR_UNKNOWN;
    raDestruct(hash->elements);
    RvMemoryFree(hash);

    return 0;
}


/************************************************************************
 * hashAdd
 * purpose: Add a new element to the hash table.
 *          This function will not add the element if an element with the
 *          same key already exists if asked
 * input  : hHash               - HASH object handle
 *          key                 - Pointer to the key
 *          userElem            - Pointer to the element to store
 *          searchBeforeInsert  - Check for the same key inside the HASH or not
 * output : none
 * return : Pointer to the element's location in the hash table on success
 *          NULL on failure
 ************************************************************************/
void*
hashAdd(
     IN  HHASH  hHash,
     IN  void*  key,
     IN  void*  userElem,
     IN  RvBool   searchBeforeInsert)
{
    hashStruct* hash = (hashStruct *)hHash;
    hashListElement* newElem;
    RvUint32 keyValue;

    /* See if such an element exists */
    if (searchBeforeInsert)
    {
        newElem = (hashListElement*)hashFind(hHash, key);
        if (newElem != NULL) return newElem;