AMPS:哈希表源码解读

2024-05-29 来源：小侦探旅游网

Hash表也是一种常用的数据结构，AMPS中的Hash表并不是给使用者提供一个散列函数，而是仅提供一个创建和维护Hash表这样一个结构的一组函数，针对不同的应用或者数据，由用户自己定义其要使用的散列函数，AMPS中，Hash表组成结构是如下的拉链式结构。

下面看看AMPS中对Hash操作的代码：

AMPS_Hash.h

#ifndef __HEADER_AMPS_HASH_H
#define __HEADER_AMPS_HASH_H

#ifdef __cplusplus
extern "C" {
#endif

#include "AMPS_API.h"
#include "AMPS_Defines.h"
#include "AMPS_LinkList.h"

//#define AMPS_HASH_TABLE_KEY_SIZE		1009    // Prime Nos : 1009, 11003, 11027, 50021, 50023, 100019

typedef struct _HASHTableEntry  	t_HASHTableEntry;
typedef struct _HASHTableNode       t_HASHTableNode;
typedef struct _HASHTable           t_HASHTable;
typedef struct _HASHTableUserData   t_HASHTableUserData;

typedef int(*HashTable_InsertCallback)(void* r_pvAMPSContext, void* r_pvHASHTable, void* r_pvData, t_AMPSHashTableKey* r_poHASHKey);
typedef void*(*HashTable_SearchCallback)(void* r_pvAMPSContext, void* r_pvHASHTable, t_AMPSHashTableKey* r_poHASHKey);
typedef int(*HashTable_DeleteCallback)(void* r_pvAMPSContext, void* r_pvHASHTable, t_AMPSHashTableKey* r_poHASHKey);

struct _HASHTableEntry
{
    t_AMPSDList* poDListOfHashTableNode;    //list of t_HASHTableNode
};

/*Hash表结点结构*/
struct _HASHTableNode
{
    t_AMPSSList*                poSListNodeBackPtr; /*具有相同key值的各数据节点*/
    void*						pvAMPSContext;
    t_AMPSHashTableKey			oHASHKey;
    int							nHashTableIndex;
    void*						pvData;             //Node specific pvData
};

/*Hash表结构*/
struct _HASHTable
{
    t_HASHTableEntry*       		poHASHTableEntry; /*存放各节点的值*/

    int                             nHashTableSize; /*结点个数*/

    //variable functions
    AMPS_HashTableHashCallback      pfAMPS_HashTableHashCallback; /*散列函数*/
    HashTable_InsertCallback        pfHashTable_InsertCallback;   
    HashTable_SearchCallback        pfHashTable_SearchCallback;
    HashTable_DeleteCallback        pfHashTable_DeleteCallback;
};

struct _HASHTableUserData
{
	AMPS_HashTableProcessNodeDataCallback	pfAMPS_HashTableProcessNodeDataCallback;
	AMPS_APP_HANDLE						hAMPS_APP_HANDLE;
};

void* HashTable_Create(void* r_pvAMPSContext, int r_SizeOfHashTable, AMPS_HashTableHashCallback r_pfAMPS_HashTableHashCallback);
void HashTable_Delete (void* r_pvAMPSContext, void* r_pvHASHTable);
void HashTable_DeleteAllEntries(void* r_pvAMPSContext, void* r_pvHASHTable, AMPS_HashTableProcessNodeDataCallback r_pfAMPS_HashTableProcessNodeDataCallback, AMPS_APP_HANDLE r_hAMPS_APP_HANDLE);

void HashTable_TraverseAllEntries(void* r_pvAMPSContext, void* r_pvHASHTable, AMPS_HashTableProcessNodeDataCallback r_pfAMPS_HashTableProcessNodeDataCallback, AMPS_APP_HANDLE r_hAMPS_APP_HANDLE);
void HashTable_ProcessNodeData(void* r_pvListNodeData, void* r_pvArg);

unsigned int HashTable_Main(void* r_pvAMPSContext, void* r_pvHASHTable, t_AMPSHashTableKey* r_poHASHKey);

int HashTable_Insert(void* r_pvAMPSContext, void* r_pvHASHTable, void* r_pvData, t_AMPSHashTableKey* r_poHASHKey);
int HashTable_RemoveByHandle(void* r_pvAMPSContext, void* r_pvHASHTable, int r_nHandle);
int HashTable_RemoveByKey(void* r_pvAMPSContext, void* r_pvHASHTable, t_AMPSHashTableKey* r_poHASHKey);
void* HashTable_Search(void* r_pvAMPSContext, void* r_pvHASHTable, t_AMPSHashTableKey* r_poHASHKey);
void* HashTable_LookupByHandleAndHashKey(void* r_pvAMPSContext, void* r_pvHASHTable, t_AMPSHashTableKey* r_poHASHKey, int r_nHandle);
void* HashTable_LookupByHandle(void* r_pvAMPSContext, void* r_pvHASHTable, int r_nHandle);
void* HashTable_SearchData (void* r_pvAMPSContext, t_AMPSDList* r_pDList, t_AMPSHashTableKey* r_poHASHKey);

void* HashTable_CreateAndAppendNode (void* r_pvAMPSContext, t_AMPSDList* r_poDList, void* r_pvData, t_AMPSHashTableKey* r_poHASHKey, int r_nHashTableIndex);

int HashTable_FreeNodeData (void** r_ppvHASHTableNode);
int HashTable_CompareNodeKey(void* r_pvHASHKey, void* r_pvHashTableNode);
void HashTable_FreeNodeDataEx(void* r_pvListNodeData, void* r_pvArg);

unsigned int HashTable_StringSum (void* r_pvAMPSContext, void* r_pvHASHTable, t_AMPSHashTableKey* r_poHASHKey);
unsigned int HashTable_Universal (void* r_pvAMPSContext, void* r_pvHASHTable, t_AMPSHashTableKey* r_poHASHKey);
unsigned int HashTable_HashFunc1(void* r_pvAMPSContext, void* r_pvHASHTable, t_AMPSHashTableKey* r_poHASHKey);


#ifdef __cplusplus
}
#endif

#endif //__HEADER_AMPS_HASH_H

AMPS_Hash.c

/*****************************************************************
文件名称: AMPS_Hash.c
功能描述: 拉链式存储的Hash表操作函数库

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


#include "AMPS_Core.h"
#include "AMPS_Defines.h"
#include "AMPS_MemMgt.h"
#include "AMPS_Hash.h"
#include "AMPS_LinkList.h"

/*****************************************************************
函数名称: HashTable_Create
功能描述: 建立Hash表
入参::
      void* r_pvAMPSContext AMPS应用上下文
      int r_nSizeOfHashTable Hash表总大小
      AMPS_HashTableHashCallback r_pfAMPS_HashTableHashCallback 回调函数
出参:
      
返回值:
      void* 创建的Hash表

*****************************************************************/
void* HashTable_Create(void* r_pvAMPSContext, int r_nSizeOfHashTable, AMPS_HashTableHashCallback r_pfAMPS_HashTableHashCallback)
{
    t_HASHTable* poHASHTable = NULL;
    int nCounter = 0;

    TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Entering.\n");

    poHASHTable = AMPS_InternalMalloc(sizeof (t_HASHTable));
    if (NULL == poHASHTable)
    {
        return NULL;
    }

    poHASHTable->poHASHTableEntry = AMPS_InternalMalloc(sizeof(t_HASHTableEntry) * r_nSizeOfHashTable);
    if (NULL == poHASHTable->poHASHTableEntry)
    {
        AMPS_InternalFree (poHASHTable);
        return NULL;
    }

    poHASHTable->nHashTableSize = r_nSizeOfHashTable;

    if (NULL == r_pfAMPS_HashTableHashCallback)
    {
        poHASHTable->pfAMPS_HashTableHashCallback = HashTable_HashFunc1;
    } else
    {
        poHASHTable->pfAMPS_HashTableHashCallback = r_pfAMPS_HashTableHashCallback;
    }

    /*结点存放在双向链表中*/
    for (; nCounter < poHASHTable->nHashTableSize; nCounter++)
    {
        if (NULL == DList_Init (&poHASHTable->poHASHTableEntry[nCounter].poDListOfHashTableNode))
        {
            return NULL;
        }
    }

    TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Leaving\n");

    return poHASHTable;
}

/*****************************************************************
函数名称: HashTable_Delete
功能描述: 释放Hash表
入参::
      void* r_pvAMPSContext AMPS应用上下文
      void* r_pvHASHTable Hash表句柄     
出参:
      t_AMPSDList* 操作后的链表
返回值:
      NA

*****************************************************************/
void HashTable_Delete(void* r_pvAMPSContext, void* r_pvHASHTable)
{
    t_HASHTable* poHASHTable = (t_HASHTable*)r_pvHASHTable;
    int nCounter = 0;

    TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Entering.\n");
    for (; nCounter < poHASHTable->nHashTableSize; nCounter++)
    {
        DList_Free(&poHASHTable->poHASHTableEntry[nCounter].poDListOfHashTableNode, HashTable_FreeNodeData);
    }

    AMPS_InternalFree(poHASHTable->poHASHTableEntry); 
    AMPS_InternalFree (poHASHTable);      

    TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Leaving\n");
}

/*****************************************************************
函数名称: HashTable_TraverseAllEntries
功能描述: 遍历并处理Hash表各结点
入参::
      void* r_pvAMPSContext AMPS应用上下文
      void* r_pvHASHTable Hash表句柄  
      AMPS_HashTableProcessNodeDataCallback r_pfAMPS_HashTableProcessNodeDataCallback
出参:
      t_AMPSDList* 操作后的链表
返回值:
      NA

*****************************************************************/
void HashTable_TraverseAllEntries(void* r_pvAMPSContext, void* r_pvHASHTable, AMPS_HashTableProcessNodeDataCallback r_pfAMPS_HashTableProcessNodeDataCallback, AMPS_APP_HANDLE r_hAMPS_APP_HANDLE)
{
	t_HASHTable* poHASHTable = (t_HASHTable*)r_pvHASHTable;
	int nCounter = 0;

	TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Entering.\n");

	if((NULL != r_pfAMPS_HashTableProcessNodeDataCallback) || (NULL != r_hAMPS_APP_HANDLE))
	{
		t_HASHTableUserData oHASHTableUserData;

		oHASHTableUserData.hAMPS_APP_HANDLE = r_hAMPS_APP_HANDLE;
		oHASHTableUserData.pfAMPS_HashTableProcessNodeDataCallback = r_pfAMPS_HashTableProcessNodeDataCallback;

		for (; nCounter < poHASHTable->nHashTableSize; nCounter++)
		{
			DList_Traverse(poHASHTable->poHASHTableEntry[nCounter].poDListOfHashTableNode, HashTable_ProcessNodeData, &oHASHTableUserData);
		}
	}
}

/*****************************************************************
函数名称: HashTable_ProcessNodeData
功能描述: 处理各节点
入参::
      void* r_pvListNodeData 结点数据
      void* r_pvArg 参数

出参:
      
返回值:
      NA

*****************************************************************/
void HashTable_ProcessNodeData(void* r_pvListNodeData, void* r_pvArg)
{
	t_HASHTableNode* poHASHTableNode = r_pvListNodeData;
	t_HASHTableUserData* poHASHTableUserData = r_pvArg;
	t_AMPSContext* poAMPSContext = poHASHTableNode->pvAMPSContext;

	TRACE(HASH_TRACE_ID(poAMPSContext), AMPS_TRACE_LEVEL_INFO, "Entering.\n");

	poHASHTableUserData->pfAMPS_HashTableProcessNodeDataCallback(poAMPSContext, poHASHTableUserData->hAMPS_APP_HANDLE, poHASHTableNode->pvData);

	TRACE( HASH_TRACE_ID(poAMPSContext), AMPS_TRACE_LEVEL_INFO, "Leaving\n");
}

/*****************************************************************
函数名称: HashTable_DeleteAllEntries
功能描述: 处理各节点
入参::
      void* r_pvAMPSContext 应用上下文
      void* r_pvHASHTable hash表
      AMPS_HashTableProcessNodeDataCallback r_pfAMPS_HashTableProcessNodeDataCallback
      AMPS_APP_HANDLE r_hAMPS_APP_HANDLE 应用句柄

出参:
      
返回值:
      NA

*****************************************************************/
void HashTable_DeleteAllEntries(void* r_pvAMPSContext, void* r_pvHASHTable, AMPS_HashTableProcessNodeDataCallback r_pfAMPS_HashTableProcessNodeDataCallback, AMPS_APP_HANDLE r_hAMPS_APP_HANDLE)
{
	t_HASHTable* poHASHTable = (t_HASHTable*)r_pvHASHTable;
	int nCounter = 0;

	TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Entering.\n");

	if((NULL == r_pfAMPS_HashTableProcessNodeDataCallback) || (NULL == r_hAMPS_APP_HANDLE))
	{
		for (; nCounter < poHASHTable->nHashTableSize; nCounter++)
		{
            /*释放并初始化各结点*/
			DList_Free(&poHASHTable->poHASHTableEntry[nCounter].poDListOfHashTableNode, HashTable_FreeNodeData);
			if (NULL == DList_Init (&poHASHTable->poHASHTableEntry[nCounter].poDListOfHashTableNode))
			{
				TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_ERROR,"unable to re-create node list\n"); 
				return;
			}
		}
	}
	else
	{
		t_HASHTableUserData oHASHTableUserData;

		oHASHTableUserData.hAMPS_APP_HANDLE = r_hAMPS_APP_HANDLE;
		oHASHTableUserData.pfAMPS_HashTableProcessNodeDataCallback = r_pfAMPS_HashTableProcessNodeDataCallback;

		for (; nCounter < poHASHTable->nHashTableSize; nCounter++)
		{
            /*释放前处理结点*/
			DList_FreeEx(&poHASHTable->poHASHTableEntry[nCounter].poDListOfHashTableNode, HashTable_FreeNodeDataEx, &oHASHTableUserData);
			if (NULL == DList_Init(&poHASHTable->poHASHTableEntry[nCounter].poDListOfHashTableNode))
			{
				TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_ERROR,"unable to re-create node list\n"); 
				return;
			}
		}
	}
}

/*****************************************************************
函数名称: HashTable_FreeNodeData
功能描述: 释放节点
入参::
      void** r_ppvHASHTableNode 要释放的结点


出参:
      
返回值:
      int

*****************************************************************/
int HashTable_FreeNodeData(void** r_ppvHASHTableNode)
{
    t_HASHTableNode* poHASHTableNode = (t_HASHTableNode*)(*r_ppvHASHTableNode);
    //t_AMPSContext* poAMPSContext = (t_AMPSContext*)poHASHTableNode->pvAMPSContext;

    //TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Entering.\n");

    memset(poHASHTableNode->oHASHKey.puchKey, 0, poHASHTableNode->oHASHKey.unKeyLength);
    AMPS_InternalFree(poHASHTableNode);

    //TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Leaving\n");

    return AMPS_SUCCESS;
}

/*****************************************************************
函数名称: HashTable_FreeNodeDataEx
功能描述: 释放节点
入参::
      void** r_ppvHASHTableNode 要释放的结点
      void* r_pvArg 参数

出参:
      
返回值:
      int

*****************************************************************/
void HashTable_FreeNodeDataEx(void* r_pvListNodeData, void* r_pvArg)
{
	t_HASHTableNode* poHASHTableNode = r_pvListNodeData;
	t_HASHTableUserData* poHASHTableUserData = r_pvArg;
	t_AMPSContext* poAMPSContext = poHASHTableNode->pvAMPSContext;

	TRACE(HASH_TRACE_ID(poAMPSContext), AMPS_TRACE_LEVEL_INFO, "Entering.\n");

	poHASHTableUserData->pfAMPS_HashTableProcessNodeDataCallback(poAMPSContext, poHASHTableUserData->hAMPS_APP_HANDLE, poHASHTableNode->pvData);
	AMPS_InternalFree(poHASHTableNode);

	TRACE( HASH_TRACE_ID(poAMPSContext), AMPS_TRACE_LEVEL_INFO, "Leaving\n");
}


/*****************************************************************
函数名称: HashTable_FreeNodeDataEx
功能描述: 插入结点
入参:
      void* r_pvAMPSContext AMPS应用上下文
      void* r_pvHASHTable   Hash指针
      void* r_pvData        结点内容
      t_AMPSHashTableKey* r_poHASHKey 索引值

出参:
      
返回值:
      int

*****************************************************************/
int HashTable_Insert(void* r_pvAMPSContext, void* r_pvHASHTable, void* r_pvData, t_AMPSHashTableKey* r_poHASHKey)
{
    t_AMPSContext* poAMPSContext = (t_AMPSContext*)r_pvAMPSContext;
    t_HASHTable* poHASHTable = (t_HASHTable*)r_pvHASHTable;
    void* pvHASHTableNode = NULL;
    unsigned int nHashTableIndex = 0;

    //TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Entering.\n");

    /*得到一个位置*/
    nHashTableIndex = HashTable_Main(poAMPSContext, poHASHTable, r_poHASHKey);
    if (0 > nHashTableIndex)
    {
        return AMPS_INVALID_HANDLE;
    }

    /*第一个结点*/
    if (poHASHTable->poHASHTableEntry[nHashTableIndex].poDListOfHashTableNode->poAMPSSListHead == NULL)
    {
        pvHASHTableNode = HashTable_CreateAndAppendNode (poAMPSContext, poHASHTable->poHASHTableEntry[nHashTableIndex].poDListOfHashTableNode, r_pvData, r_poHASHKey, nHashTableIndex);
        if (NULL == pvHASHTableNode)
        {
            return AMPS_INVALID_HANDLE;
        }
    } else
    {
        //DList_Search will return NULL(last poAMPSSListNext pointer) if table entry deos not exist
        if (NULL == DList_Search(poHASHTable->poHASHTableEntry[nHashTableIndex].poDListOfHashTableNode, HashTable_CompareNodeKey, r_poHASHKey))
        {
            pvHASHTableNode = HashTable_CreateAndAppendNode (poAMPSContext, poHASHTable->poHASHTableEntry[nHashTableIndex].poDListOfHashTableNode, r_pvData, r_poHASHKey, nHashTableIndex);
            if (NULL == pvHASHTableNode)
            {
                return AMPS_INVALID_HANDLE;
            }
        } else
        {
            //ERROR HANDLING
            TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_WARNING, "Entery already exist.\n");
            return AMPS_INVALID_HANDLE;
        }
    }

    //TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Leaving\n");

    return((int)pvHASHTableNode);
}

/*****************************************************************
函数名称: HashTable_CreateAndAppendNode
功能描述: 插入结点
入参:
      void* r_pvAMPSContext AMPS应用上下文
      t_AMPSDList* r_poDList, hash表中的结点链表
      void* r_pvData, 要追加的结点数据
      t_AMPSHashTableKey* r_poHASHKey 要追加的结点的k值
      int r_nHashTableIndex index

出参:
      
返回值:
      int

*****************************************************************/
void* HashTable_CreateAndAppendNode(void* r_pvAMPSContext, t_AMPSDList* r_poDList, void* r_pvData, t_AMPSHashTableKey* r_poHASHKey, int r_nHashTableIndex)
{
    //t_AMPSContext* poAMPSContext = (t_AMPSContext*)r_pvAMPSContext;
    t_AMPSSList* poSListNode = NULL;
    t_HASHTableNode* poHASHTableNode = NULL;

    //TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Entering.\n");

    /*创建结点*/
	poHASHTableNode = AMPS_InternalMalloc (sizeof(t_HASHTableNode));
    if (NULL == poHASHTableNode)
    {
        return NULL;
    }

    /*结点赋值*/
    poHASHTableNode->pvAMPSContext = r_pvAMPSContext;
    poHASHTableNode->pvData = r_pvData;
    poHASHTableNode->nHashTableIndex = r_nHashTableIndex;
    if (AMPS_HASH_TABLE_KEY_SIZE < r_poHASHKey->unKeyLength)
    {
        AMPS_InternalFree(poHASHTableNode);
        return NULL;
    }
    strncpy((char*)poHASHTableNode->oHASHKey.puchKey, (char*)r_poHASHKey->puchKey, r_poHASHKey->unKeyLength);
    poHASHTableNode->oHASHKey.unKeyLength = r_poHASHKey->unKeyLength;

    poSListNode = (t_AMPSSList*)AMPS_InternalMalloc(sizeof(t_AMPSSList));
    if (NULL == poSListNode)
    {
        memset(poHASHTableNode->oHASHKey.puchKey, 0, poHASHTableNode->oHASHKey.unKeyLength);
        AMPS_InternalFree(poHASHTableNode);
        return NULL;
    }
    poHASHTableNode->poSListNodeBackPtr = poSListNode;

    /*将结点挂在Hash中的双向链表中*/
    DList_PrependGivenNode(r_poDList, poHASHTableNode, poSListNode);

	/*if(r_poDList->uchCount > 15)
		printf("r_poDList->uchCount %d\n", r_poDList->uchCount);*/
	
    //TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Leaving\n");

    return poHASHTableNode;
}


/*****************************************************************
函数名称: HashTable_RemoveByHandle
功能描述: 删除结点
入参:
      void* r_pvAMPSContext AMPS应用上下文
      void* r_pvHASHTable
      int r_nHandle


出参:
      
返回值:
      int

*****************************************************************/
int HashTable_RemoveByHandle(void* r_pvAMPSContext, void* r_pvHASHTable, int r_nHandle)
{
    //t_AMPSContext* poAMPSContext = (t_AMPSContext*)r_pvAMPSContext;
    t_HASHTable* poHashTable = (t_HASHTable*)r_pvHASHTable;
    //这句是错的吧
    t_HASHTableNode* poHASHTableNode = (t_HASHTableNode*)r_nHandle; 
    t_AMPSSList* poSListNode = poHASHTableNode->poSListNodeBackPtr;

    //TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Entering.\n");

    if (AMPS_SUCCESS != DList_Remove(&poHashTable->poHASHTableEntry[poHASHTableNode->nHashTableIndex].poDListOfHashTableNode, poSListNode, HashTable_FreeNodeData))
    {
        return AMPS_ERROR_FAILURE;
    }

    //TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Leaving\n");

    return AMPS_SUCCESS;
}

/*****************************************************************
函数名称: HashTable_RemoveByKey
功能描述: 删除结点
入参:
      void* r_pvAMPSContext AMPS应用上下文
      void* r_pvHASHTable
      t_AMPSHashTableKey* r_poHASHKey


出参:
      
返回值:
      int

*****************************************************************/
int HashTable_RemoveByKey(void* r_pvAMPSContext, void* r_pvHASHTable, t_AMPSHashTableKey* r_poHASHKey)
{
    t_AMPSContext* poAMPSContext = (t_AMPSContext*)r_pvAMPSContext;
    t_HASHTable* poHashTable = (t_HASHTable*)r_pvHASHTable;
    t_AMPSSList* poSListNode = NULL;
    unsigned int unHashTableIndex = 0;      

    //TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Entering.\n");

    unHashTableIndex = HashTable_Main(poAMPSContext, poHashTable, r_poHASHKey);

    poSListNode = DList_Search(poHashTable->poHASHTableEntry[unHashTableIndex].poDListOfHashTableNode, HashTable_CompareNodeKey, r_poHASHKey);
    if (NULL != poSListNode)
    {
        return(DList_Remove(&poHashTable->poHASHTableEntry[unHashTableIndex].poDListOfHashTableNode, poSListNode, HashTable_FreeNodeData));
    } else
    {
        return AMPS_ERROR_FAILURE;
    }

    //TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Leaving\n");

    return AMPS_SUCCESS;
}

/*****************************************************************
函数名称: HashTable_Search
功能描述: 查找结点
入参:
      void* r_pvAMPSContext AMPS应用上下文
      void* r_pvHASHTable
      t_AMPSHashTableKey* r_poHASHKey


出参:
      
返回值:
      int

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

void* HashTable_Search(void* r_pvAMPSContext, void* r_pvHASHTable, t_AMPSHashTableKey* r_poHASHKey)
{
    t_AMPSContext* poAMPSContext = (t_AMPSContext*)r_pvAMPSContext;
    t_HASHTable* poHashTable = (t_HASHTable*)r_pvHASHTable;
    unsigned int unHashTableIndex = 0;
    t_AMPSSList* poSListNode = NULL;

    //TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Entering.\n");

    unHashTableIndex = HashTable_Main(r_pvAMPSContext, poHashTable, r_poHASHKey); //retrieve index for Node

    //Search the indexed list
    if (NULL != poHashTable->poHASHTableEntry[unHashTableIndex].poDListOfHashTableNode)
    {
        poSListNode = poHashTable->poHASHTableEntry[unHashTableIndex].poDListOfHashTableNode->poAMPSSListHead;

        if (NULL == poSListNode)
        {
            return NULL;
        }

        /*找到*/
        //if required pvData is in the first node?
        if (AMPS_SUCCESS == HashTable_CompareNodeKey (r_poHASHKey, poSListNode->pvData))
        {
            return((t_HASHTableNode*)poSListNode->pvData)->pvData;
        }
        //proceed to perform list search
        return(HashTable_SearchData (poAMPSContext, poHashTable->poHASHTableEntry[unHashTableIndex].poDListOfHashTableNode, r_poHASHKey));
    }

    //TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Leaving.\n");

    return NULL;
}


/*****************************************************************
函数名称: HashTable_LookupByHandleAndHashKey
功能描述: 查找结点(使用handle和key)
入参:
      void* r_pvAMPSContext AMPS应用上下文
      void* r_pvHASHTable
      t_AMPSHashTableKey* r_poHASHKey


出参:
      
返回值:
      int

*****************************************************************/
void* HashTable_LookupByHandleAndHashKey(void* r_pvAMPSContext, void* r_pvHASHTable, t_AMPSHashTableKey* r_poHASHKey, int r_nHandle)
{
    //t_AMPSContext* poAMPSContext = (t_AMPSContext*)r_pvAMPSContext;
    //t_HASHTable* poHashTable = (t_HASHTable*)r_pvHASHTable;
    t_HASHTableNode* poHASHTableNode = (t_HASHTableNode*)r_nHandle;

    //TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Entering.\n");

    if (AMPS_SUCCESS == HashTable_CompareNodeKey (r_poHASHKey, poHASHTableNode))
    {
        return(poHASHTableNode->pvData);
    }

    //TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Leaving.\n");

    return NULL;
}

/*****************************************************************
函数名称: HashTable_LookupByHandle
功能描述: 查找结点数据(使用handle)
入参:
      void* r_pvAMPSContext AMPS应用上下文
      void* r_pvHASHTable
      t_AMPSHashTableKey* r_poHASHKey


出参:
      
返回值:
      int

*****************************************************************/
void* HashTable_LookupByHandle(void* r_pvAMPSContext, void* r_pvHASHTable, int r_nHandle)
{
    //t_AMPSContext* poAMPSContext = (t_AMPSContext*)r_pvAMPSContext;
    //t_HASHTable* poHashTable = (t_HASHTable*)r_pvHASHTable;
    //真没有理解
    t_HASHTableNode* poHASHTableNode = (t_HASHTableNode*)r_nHandle;
    void* pvData = NULL;

    //TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Entering.\n");

    pvData = poHASHTableNode->pvData;

    //TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Leaving.\n");

    return pvData;
}

/*****************************************************************
函数名称: HashTable_CompareNodeKey
功能描述: 比较指定的key是否与结点内容匹配
入参:
      void* r_pvHASHKey
      void* r_pvHashTableNode


出参:
      
返回值:
      int

*****************************************************************/
int HashTable_CompareNodeKey(void* r_pvHASHKey, void* r_pvHashTableNode) 
{
    t_AMPSHashTableKey* poHASHKey = (t_AMPSHashTableKey*)r_pvHASHKey;
    t_HASHTableNode* poHASHTableNode = (t_HASHTableNode*)r_pvHashTableNode;

    //t_AMPSContext* poAMPSContext = (t_AMPSContext*)poHASHTableNode->pvAMPSContext;

    //TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Entering.\n");

	//if(poHASHKey->unKeyLength == poHASHTableNode->oHASHKey.unKeyLength)
	{
		if (0 == SAPI_StrnCaseCMP((char*)poHASHKey->puchKey, (char*)poHASHTableNode->oHASHKey.puchKey, poHASHKey->unKeyLength))
		{
			return AMPS_SUCCESS;
		}
	}

    //TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Leaving.\n");

    return AMPS_ERROR_FAILURE;
}

/*****************************************************************
函数名称: HashTable_SearchData
功能描述: 查找指定key值对应的数据
入参:
      void* r_pvAMPSContext 应用上下文
      t_AMPSDList* r_pDList Hash内的双链表
      t_AMPSHashTableKey*  指定的key值


出参:
      
返回值:
      int

*****************************************************************/
void* HashTable_SearchData (void* r_pvAMPSContext, t_AMPSDList* r_pDList, t_AMPSHashTableKey* r_poHASHKey)
{
    //t_AMPSContext* poAMPSContext = (t_AMPSContext*)r_pvAMPSContext;
    t_AMPSSList* poSListNode = NULL;

    //TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Entering.\n");

    poSListNode = DList_Search(r_pDList, HashTable_CompareNodeKey, r_poHASHKey);
    if (NULL != poSListNode)
    {
        if (NULL != poSListNode->pvData)
        {
            return(((t_HASHTableNode*)poSListNode->pvData)->pvData);  //return actual pvData, pvData inside t_HASHTableNode
        }
    }

    //TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Leaving.\n");

    return NULL;
}

/*****************************************************************
函数名称: HashTable_SearchData
功能描述: 获取指定key的位置
入参:
      void* r_pvAMPSContext 应用上下文
      t_AMPSDList* r_pDList Hash内的双链表
      t_AMPSHashTableKey*  指定的key值


出参:
      
返回值:
      int

*****************************************************************/
unsigned int HashTable_Main(void* r_pvAMPSContext, void* r_pvHASHTable, t_AMPSHashTableKey* r_poHASHKey)
{
    t_AMPSContext* poAMPSContext = (t_AMPSContext*)r_pvAMPSContext;
    t_HASHTable* poHashTable = (t_HASHTable*)r_pvHASHTable;

    //TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Entering.\n");

    //TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_DEBUG, "Hash Key Length = %d\n", r_poHASHKey->unKeyLength);
    //TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_DEBUG, "Hash Key = %s\n", r_poHASHKey->puchKey);

    if (NULL != poHashTable->pfAMPS_HashTableHashCallback)
    {
        /*使用hash函数得到一个位置，这个函数在hash表初始化时由用户定义*/
        return(poHashTable->pfAMPS_HashTableHashCallback (poAMPSContext, poHashTable, r_poHASHKey));
    }

    //TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Leaving.\n");

    return AMPS_ERROR_FAILURE;
}

/*****************************************************************
 下面为几个Hash散列函数举例

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

//A simple Hash Function for String keys
unsigned int HashTable_StringSum (void* r_pvAMPSContext, void* r_pvHASHTable, t_AMPSHashTableKey* r_poHASHKey)
{
    //t_AMPSContext* poAMPSContext = (t_AMPSContext*)r_pvAMPSContext;
    t_HASHTable* poHashTable = (t_HASHTable*)r_pvHASHTable;
    //Sum all the characters that make up the KEY
    unsigned int nHashTableIndex = 0;
    unsigned int unCounter = 0;
    int nSum = 0;

    //TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Entering.\n");

    for (unCounter = 0; unCounter < r_poHASHKey->unKeyLength; unCounter++)
    {
        nSum += r_poHASHKey->puchKey[unCounter];
    }
    //return the sum calculated above mod r_poHASHTable->nHashTableSize
    //ensures that the returned index lies between zero and r_poHASHTable->nHashTableSize

    nHashTableIndex = (nSum % poHashTable->nHashTableSize);

    //TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_DEBUG, "Hash Table Index = %d\n", nHashTableIndex);

    //TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Leaving.\n");

    return nHashTableIndex;
}

//Universal Hash Function for String Keys
unsigned int HashTable_Universal (void* r_pvAMPSContext, void* r_pvHASHTable, t_AMPSHashTableKey* r_poHASHKey)
{
    //t_AMPSContext* poAMPSContext = (t_AMPSContext*)r_pvAMPSContext;
    t_HASHTable* poHashTable = (t_HASHTable*)r_pvHASHTable;
    unsigned int nHashTableIndex = 0;
    int a = 31415;
    int b = 27183;

    //TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Entering.\n");

    for (nHashTableIndex = 0; nHashTableIndex < r_poHASHKey->unKeyLength; nHashTableIndex++, a = a*b % (poHashTable->nHashTableSize - 1))
    {
        nHashTableIndex = (a*nHashTableIndex + r_poHASHKey->puchKey[nHashTableIndex]) % poHashTable->nHashTableSize;
    }

    //TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_DEBUG, "Hash Table Index = %d\n", nHashTableIndex);

    //TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Leaving.\n");

    return nHashTableIndex;
}

#if !defined (HASH_Get16bits)
    #define HASH_Get16bits(cchKey) ((((unsigned int)(((const unsigned char *)(cchKey))[1])) << 8)\
                       +(unsigned int)(((const unsigned char *)(cchKey))[0]) )
#endif


unsigned int HashTable_HashFunc1(void* r_pvAMPSContext, void* r_pvHASHTable, t_AMPSHashTableKey* r_poHASHKey)
{
    t_HASHTable* poHashTable = r_pvHASHTable;
    unsigned int nHashTableIndex = r_poHASHKey->unKeyLength;
	unsigned int unKeyLength = r_poHASHKey->unKeyLength;
	const char* cchKey = (const char*)r_poHASHKey->puchKey;
	unsigned int unTemp = 0;
    int nReminder = 0;

    //TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Entering.\n");

    nReminder = unKeyLength & 3;
    unKeyLength >>= 2;

    for ( ;unKeyLength > 0; unKeyLength--)
    {
        nHashTableIndex  += HASH_Get16bits (cchKey);
        unTemp = (HASH_Get16bits (cchKey+2) << 11) ^ nHashTableIndex;
        nHashTableIndex   = (nHashTableIndex << 16) ^ unTemp;
        cchKey  += 2*sizeof(unsigned short);
        nHashTableIndex  += nHashTableIndex >> 11;
    }

    switch (nReminder)
    {
        case 3: 
			nHashTableIndex += HASH_Get16bits (cchKey);
            nHashTableIndex ^= nHashTableIndex << 16;
            nHashTableIndex ^= cchKey[sizeof (unsigned short)] << 18;
            nHashTableIndex += nHashTableIndex >> 11;
            break;
        case 2: 
			nHashTableIndex += HASH_Get16bits (cchKey);
            nHashTableIndex ^= nHashTableIndex << 11;
            nHashTableIndex += nHashTableIndex >> 17;
            break;
        case 1: 
			nHashTableIndex += *cchKey;
            nHashTableIndex ^= nHashTableIndex << 10;
            nHashTableIndex += nHashTableIndex >> 1;
    }

    nHashTableIndex ^= nHashTableIndex << 3;
    nHashTableIndex += nHashTableIndex >> 5;
    nHashTableIndex ^= nHashTableIndex << 4;
    nHashTableIndex += nHashTableIndex >> 17;
    nHashTableIndex ^= nHashTableIndex << 25;
    nHashTableIndex += nHashTableIndex >> 6;

	nHashTableIndex = (nHashTableIndex % poHashTable->nHashTableSize);

    //TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_DEBUG, "Hash Table Index = %d\n", nHashTableIndex);

    //TRACE( HASH_TRACE_ID(r_pvAMPSContext), AMPS_TRACE_LEVEL_INFO, "Leaving.\n");
    return nHashTableIndex;
}

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文

全部栏目

AMPS:哈希表源码解读