?? hashlist.c
字號:
/*
* Copyright (c) 2000-2008
* Author: Weiming Zhou
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation.
*/
#include <stdlib.h>
#include "CapiGlobal.h"
#include "HashList.h"
/** 哈希鏈表的創建函數
@param UINT uBucketCount - 索引表的大小
@return HASHLIST * - 成功返回哈希表的指針，失敗返回NULL
*/
HASHLIST *HashList_Create(UINT uBucketCount)
{
HASHLIST *pHashList;
/* 假設uBucketCount最小值不能低于MINIUM_BUCKET_COUNT */
if ( uBucketCount < MINIUM_BUCKET_COUNT )
{
uBucketCount = MINIUM_BUCKET_COUNT;
}
pHashList = (HASHLIST *)malloc(sizeof(HASHLIST));
if ( pHashList != NULL)
{
/* 創建哈希鏈表里的哈希表的索引表并初始化哈希表 */
pHashList->ppBuckets = (HASHLISTNODE **)malloc(uBucketCount
* sizeof(HASHLISTNODE *));
if ( pHashList->ppBuckets == NULL )
{
free(pHashList);
return NULL;
}
memset((void *)pHashList->ppBuckets, 0,
uBucketCount * sizeof(HASHLISTNODE *));
/* 初始化哈希表里面的雙向鏈表 */
pHashList->pHead = NULL;
pHashList->pTail = NULL;
pHashList->uBucketCount = uBucketCount;
pHashList->uNodeCount = 0;
}
return pHashList;
}
/** 哈希鏈表的釋放函數
@param HASHLIST *pHashList - 哈希鏈表指針
@param DESTROYFUNC DestroyFunc - 數據釋放回調函數
@return void - 無
*/
void HashList_Destroy(HASHLIST *pHashList,
DESTROYFUNC DestroyFunc )
{
UINT uIndex;
if ( pHashList == NULL )
{
return;
}
for ( uIndex = 0; uIndex < pHashList->uBucketCount; uIndex++ )
{
HASHLISTNODE *pNode;
pNode = pHashList->ppBuckets[uIndex];
while ( pNode != NULL )
{
HASHLISTNODE *pNodeToFree;
pNodeToFree = pNode;
pNode = pNode->pBucketNext;
if ( DestroyFunc != NULL && pNodeToFree->pData != NULL )
{
(*DestroyFunc)(pNodeToFree->pData);
}
free(pNodeToFree);
}
}
free(pHashList->ppBuckets);
free(pHashList);
return;
}
/** 哈希鏈表的數據插入函數，同時插入到哈希表和鏈表中，
插入鏈表時是插入在鏈表的頭部
@param HASHLIST *pHashList - 哈希鏈表指針
@param void *pData - 要插入的數據指針
@param HASHFUNC HashFunc - 哈希函數
@return INT - CAPI_FAILED表示失敗，CAPI_SUCCESS表示成功
*/
INT HashList_InsertHead(HASHLIST *pHashList, void *pData, HASHFUNC HashFunc)
{
HASHLISTNODE *pNode;
UINT uBucketIndex;
if ( pHashList == NULL || pData == NULL )
{
return CAPI_FAILED;
}
/* 生成哈希鏈表的節點 */
pNode = (HASHLISTNODE *)malloc(sizeof(HASHLISTNODE));
if ( pNode == NULL )
{
return CAPI_FAILED;
}
pNode->pData = pData;
pNode->pBucketNext = NULL;
pNode->pListPrev = NULL;
pNode->pListNext = pHashList->pHead;
/* 插入到哈希表中 */
uBucketIndex = (*HashFunc)(pData, pHashList->uBucketCount);
if ( pHashList->ppBuckets[uBucketIndex] == NULL )
{
pHashList->ppBuckets[uBucketIndex] = pNode;
}
else
{
HASHLISTNODE *pTempNode;
pTempNode = pHashList->ppBuckets[uBucketIndex];
while ( pTempNode->pBucketNext != NULL )
{
pTempNode = pTempNode->pBucketNext;
}
pTempNode->pBucketNext = pNode;
}
/* 插入到鏈表中 */
if ( pHashList->pHead == NULL )
{
pHashList->pHead = pNode;
pHashList->pTail = pNode;
}
else
{
pNode->pListNext = pHashList->pHead;
pHashList->pHead->pListPrev = pNode;
pHashList->pHead = pNode;
}
pHashList->uNodeCount += 1;
return CAPI_SUCCESS;
}
/** 哈希鏈表的單個節點刪除函數，要同時從哈希表和鏈表中刪除
@param HASHLIST *pHashList - 哈希鏈表指針
@param void *pData - 數據指針
@param HASHFUNC HashFunc - 哈希函數
@param COMPAREFUNC CompareFunc - 數據比較函數
@param DESTROYFUNC DestroyFunc - 數據釋放函數
@return INT - CAPI_FAILED表示失敗，CAPI_SUCCESS表示成功
*/
INT HashList_Delete(HASHLIST *pHashList,
void *pData,
HASHFUNC HashFunc,
COMPAREFUNC CompareFunc,
DESTROYFUNC DestroyFunc)
{
HASHLISTNODE *pNode;
HASHLISTNODE *pPrevNode;
UINT uIndex;
if ( pHashList == NULL || HashFunc == NULL
|| CompareFunc == NULL )
{
return CAPI_FAILED;
}
uIndex = (*HashFunc)(pData, pHashList->uBucketCount);
pNode = pHashList->ppBuckets[uIndex];
pPrevNode = NULL;
while ( pNode != NULL )
{
if ( (*CompareFunc)(pNode->pData, pData ) == 0 )
{
if (pPrevNode == NULL )
{
pHashList->ppBuckets[uIndex] = pNode->pBucketNext;
}
else
{
pPrevNode->pBucketNext = pNode->pBucketNext;
}
/* 從鏈表中刪除節點 */
if ( pNode->pListPrev != NULL )
{
pNode->pListPrev->pListNext = pNode->pListNext;
}
else
{
/* pNode 是鏈表頭指針 */
pHashList->pHead = pNode->pListNext;
}
if ( pNode->pListNext != NULL )
{
pNode->pListNext->pListPrev = pNode->pListPrev;
}
else
{
/* 現在在鏈表尾部 */
pHashList->pTail = pNode;
}
if ( pNode->pData != NULL && DestroyFunc != NULL )
{
(*DestroyFunc)(pNode->pData);
}
free(pNode);
pHashList->uNodeCount -= 1;
return CAPI_SUCCESS;
}
pPrevNode = pNode;
pNode = pNode->pBucketNext;
}
return CAPI_FAILED;
}
/** 哈希鏈表的查找節點函數
@param HASHLIST *pHashList - 哈希鏈表指針
@param void *pData - 要查找的數據指針
@param HASHFUNC HashFunc - 哈希函數
@param COMPAREFUNC CompareFunc - 數據比較函數
@return HASHLISTNODE * - 成功返回查找到的哈希鏈表節點指針，
失敗返回NULL
*/
HASHLISTNODE *HashList_FindNode(HASHLIST *pHashList,
void *pData,
HASHFUNC HashFunc,
COMPAREFUNC CompareFunc)
{
HASHLISTNODE *pNode;
UINT uIndex;
if ( pHashList == NULL || HashFunc == NULL
|| CompareFunc == NULL )
{
return NULL;
}
uIndex = (*HashFunc)(pData, pHashList->uBucketCount);
pNode = pHashList->ppBuckets[uIndex];
/* try to find the key from the HashTable */
while ( pNode != NULL )
{
if ( (*CompareFunc)(pNode->pData, pData) == 0 )
{
/* 發現匹配的節點，返回節點指針 */
return pNode;
}
pNode = pNode->pBucketNext;
}
/* 沒有找到的情況下，返回NULL */
return NULL;
}
/** 哈希鏈表的查找數據函數
@param HASHLIST *pHashList - 哈希鏈表指針
@param void *pData - 要查找的數據指針
@param HASHFUNC HashFunc - 哈希函數
@param COMPAREFUNC CompareFunc - 數據比較函數
@return void * - 成功返回查找到的數據指針，失敗返回NULL
*/
void *HashList_FindData(HASHLIST *pHashList,
void *pData,
HASHFUNC HashFunc,
COMPAREFUNC CompareFunc)
{
HASHLISTNODE *pNode;
UINT uIndex;
if ( pHashList == NULL || HashFunc == NULL
|| CompareFunc == NULL )
{
return NULL;
}
uIndex = (*HashFunc)(pData, pHashList->uBucketCount);
pNode = pHashList->ppBuckets[uIndex];
/* try to find the key from the HashTable */
while ( pNode != NULL )
{
if ( (*CompareFunc)(pNode->pData, pData) == 0 )
{
/* 發現匹配的節點，返回節點指針 */
return pNode->pData;
}
pNode = pNode->pBucketNext;
}
/* 沒有找到的情況下，返回NULL */
return NULL;
}
/** 哈希鏈表的插入排序函數，用插入排序算法對哈希鏈表里的鏈表進行排序
@param HASHLIST *pHashList - 哈希鏈表指針
@param COMPAREFUNC CompareFunc - 數據比較函數
@return INT - CAPI_FAILED表示失敗，CAPI_SUCCESS表示成功
*/
INT HashList_InsertSort(HASHLIST *pHashList, COMPAREFUNC CompareFunc)
{
HASHLISTNODE *pNode;
if ( pHashList == NULL || CompareFunc == NULL )
{
return 0;
}
pNode = pHashList->pHead;
if ( pNode == NULL )
{
/* 沒有節點在鏈表中，把它當作已經排好了序 */
return 1;
}
while ( pNode->pListNext != NULL )
{
if ( (*CompareFunc)( pNode->pListNext->pData, pNode->pData ) < 0 )
{
HASHLISTNODE *pTempNode;
pTempNode = pNode->pListPrev;
while ( pTempNode != NULL )
{
if ( (*CompareFunc)( pNode->pListNext->pData,
pTempNode->pData ) >= 0 )
{
HASHLISTNODE *pCurNode;
/* 將節點彈出來 */
pCurNode = pNode->pListNext;
pNode->pListNext = pNode->pListNext->pListNext;
if ( pCurNode->pListNext != NULL )
{
pCurNode->pListNext->pListPrev = pNode;
}
/* 將節點插入到對應位置上 */
pCurNode->pListNext = pTempNode->pListNext;
pCurNode->pListPrev = pTempNode;
pTempNode->pListNext->pListPrev = pCurNode;
pTempNode->pListNext = pCurNode;
break;
}
pTempNode = pTempNode->pListPrev;
}
/* 如果所有數據都大于該節點數據，將該節點插入到鏈表頭部 */
if ( pTempNode == NULL )
{
HASHLISTNODE *pCurNode;
/* 將節點彈出來 */
pCurNode = pNode->pListNext;
pNode->pListNext = pNode->pListNext->pListNext;
if ( pCurNode->pListNext != NULL )
{
pCurNode->pListNext->pListPrev = pNode;
}
/* 將節點插入鏈表頭部 */
pCurNode->pListPrev = NULL;
pCurNode->pListNext = pHashList->pHead;
pHashList->pHead = pCurNode;
}
}
else
{
pNode = pNode->pListNext;
}
}
return 1;
}
/*
* HashString( void *str )
* Calculate the hash value of a string.
* Parameters:
* void *str, the string that need calculate.
* Return Values:
* the hash value of the string.
*/
UINT HashStr( void *str, UINT str_len, UINT numBuckets )
{
char *s;
// int i;
int hashval;
int ret;
int j;
// strupr( (char *)str );
s = (char *)str;
hashval = 0;
#if 0
for ( i = 0; i < 5 && s[i] != '\0'; i++ )
{
hashval += hashval << 3;
hashval += s[i] ;
}
#endif
j = 0;
ret = 0;
while ( *s != '\0' )
{
if ( j == 5 )
{
j = 0;
ret += hashval;
hashval = 0;
}
hashval += hashval << 3;
// hashval += tolower( (unsigned char)*s );
s++;
j++;
}
ret += hashval;
return ret % numBuckets;
}
/*
* StrCompare( )
* Compare if two string is equal.
* Return Values:
* 1 equal
* 0 not equal
*/
UINT HashStrCompare( void *str1, UINT str1_len, void *str2, UINT str2_len )
{
return stricmp( (char *)str1, (char *)str2 );
}
void HashFree(void *pData, UINT uDataLen)
{
free( pData );
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -