/*
 * 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 "BinTree.h"
#include "RBTree.h"
#include "HashRBTree.h"


/**	哈希紅黑樹的節(jié)點(diǎn)創(chuàng)建函數(shù)

	@param	void *pData - 數(shù)據(jù)指針	
	@return	static HASHRBTREENODE * - 成功返回創(chuàng)建的節(jié)點(diǎn)指針，失敗返回NULL	
*/
static HASHRBTREENODE *HashRBTreeNode_Create( void *pData )
{
    HASHRBTREENODE *pNewNode;

    pNewNode = (HASHRBTREENODE *)malloc(sizeof(HASHRBTREENODE));
    if ( pNewNode != NULL )
    {
        RBTREENODE     *pTreeNode;

        pTreeNode = &(pNewNode->TreeNode);

        pTreeNode->pLeft = NULL;
        pTreeNode->pRight = NULL;
        pTreeNode->nMagic = RBTREE_COLOR_RED;
        pTreeNode->pData = pData;
        pTreeNode->pParent = NULL;

        pNewNode->pNext = NULL;
    }
    return pNewNode;
}

/**	哈希紅黑樹的創(chuàng)建函數(shù)

	@param	UINT uBucketNum - 哈希表的bucket數(shù)量	
	@return	HASHRBTREE * - 成功返回哈希紅黑樹指針，失敗返回NULL。	
*/
HASHRBTREE *HashRBTree_Create(UINT uBucketCount)
{
    HASHRBTREE  *pHashRBTree;

    if ( uBucketCount == 0 )
    {
        return NULL;
    }

    pHashRBTree = (HASHRBTREE *)malloc( sizeof(HASHRBTREE) );
    if ( pHashRBTree != NULL )
    {
        pHashRBTree->ppBucket = (HASHRBTREENODE **)malloc( uBucketCount 
            * sizeof(HASHRBTREENODE *) );
        if ( pHashRBTree->ppBucket != NULL )
        {
            pHashRBTree->pTree = RBTree_Create();
            if ( pHashRBTree->pTree == NULL )
            {
                free( pHashRBTree->ppBucket );
                free( pHashRBTree );
                pHashRBTree = NULL;
            }
            else
            {
                memset(pHashRBTree->ppBucket, 0, uBucketCount * sizeof(HASHRBTREENODE *));
                pHashRBTree->uBucketCount = uBucketCount;
            }
        }
        else
        {
            free( pHashRBTree );
            pHashRBTree = NULL;
        }
    }
    return pHashRBTree;
}

/**	哈希紅黑樹的釋放函數(shù)

	@param	HASHRBTREE *pHashRBTree - 哈希紅黑樹指針	
	@param	DESTROYFUNC DestroyFunc - 數(shù)據(jù)釋放函數(shù)	
	@return	void - 無	
*/
void HashRBTree_Destroy(HASHRBTREE *pHashRBTree, DESTROYFUNC DestroyFunc)
{
    /* 哈希紅黑樹中，我們只要按紅黑樹的釋放方法將所有節(jié)點(diǎn)釋放即可 */
    if ( pHashRBTree != NULL && pHashRBTree->pTree != NULL )
    {
        RBTree_Destroy( pHashRBTree->pTree, DestroyFunc );

        /* 釋放哈希表時(shí)，由于節(jié)點(diǎn)已經(jīng)被釋放了, 因此不需要釋放節(jié)點(diǎn) */
        free(pHashRBTree->ppBucket);
        free(pHashRBTree);
    }
}


/**	哈希紅黑樹的插入函數(shù)

	@param	HASHRBTREE *pHashRBTree - 哈希紅黑樹指針	
	@param	void *pData - 數(shù)據(jù)指針	
	@param	HASHFUNC HashFunc - 哈希函數(shù)	
	@param	COMPAREFUNC CompareFunc - 數(shù)據(jù)比較函數(shù)	
	@param	DESTROYFUNC DestroyFunc - 數(shù)據(jù)釋放函數(shù)	
	@return	INT - CAPI_FAILED表示失敗，CAPI_SUCCESS表示成功。	
*/
INT HashRBTree_Insert(HASHRBTREE *pHashRBTree, void *pData, HASHFUNC HashFunc,
                      COMPAREFUNC CompareFunc, DESTROYFUNC DestroyFunc)
{
    UINT        uIndex;

    INT nRet = CAPI_FAILED;
    if ( pHashRBTree != NULL )
    {
        HASHRBTREENODE  *pNewNode;

        pNewNode = (HASHRBTREENODE *)HashRBTreeNode_Create( pData );
        if ( pNewNode == NULL )
        {
            return CAPI_FAILED;
        }

        /* 先將節(jié)點(diǎn)插入到紅黑樹中 */
        nRet = RBTree_Inter_Insert(pHashRBTree->pTree, 
            (RBTREENODE *)pNewNode, CompareFunc);
        if ( nRet == CAPI_SUCCESS )
        {
            HASHRBTREENODE  *pNode;

            /* 在紅黑樹中插入成功后，再將其插入到哈希表中 */
            uIndex = (*HashFunc)( pData, pHashRBTree->uBucketCount );
            pNode = (HASHRBTREENODE *)(pHashRBTree->ppBucket[uIndex]);

	        /* 在哈希表中查找對(duì)應(yīng)節(jié)點(diǎn) */
            while ( pNode != NULL )
            {
                if ( (*CompareFunc)( (pNode->TreeNode).pData, pData) == 0 )
                {
			        /* 哈希表中存在相同數(shù)據(jù)的節(jié)點(diǎn)，將節(jié)點(diǎn)的數(shù)據(jù)用新的數(shù)據(jù)覆蓋 */
                    (*DestroyFunc)( (pNode->TreeNode).pData );
                    (pNode->TreeNode).pData = pData;

                    return nRet;
		        }
                pNode = pNode->pNext;
	        }

            /* 將新生成的節(jié)點(diǎn)插入到BUCKET的頭部 */
            pNode = (HASHRBTREENODE *)pHashRBTree->ppBucket[uIndex];
            pNewNode->pNext = pNode;
            pHashRBTree->ppBucket[uIndex] = (HASHRBTREENODE *)pNewNode;
        }
    }

    return nRet;
}

/**	哈希紅黑樹的刪除函數(shù)

	@param	HASHRBTREE *pHashRBTree - 哈希紅黑樹指針	
	@param	void *pData - 數(shù)據(jù)指針	
	@param	HASHFUNC HashFunc - 哈希函數(shù)	
	@param	COMPAREFUNC CompareFunc - 數(shù)據(jù)比較函數(shù)	
	@param	DESTROYFUNC DestroyFunc - 數(shù)據(jù)釋放函數(shù)	
	@return	INT - 成功返回CAPI_SUCCESS, 失敗返回CAPI_FAILED	
*/
INT HashRBTree_Delete(HASHRBTREE *pHashRBTree, void *pData, 
                      HASHFUNC HashFunc, 
                      COMPAREFUNC CompareFunc,
                      DESTROYFUNC DestroyFunc)
{
    UINT    uIndex;
    HASHRBTREENODE  *pNode;
    HASHRBTREENODE  *pPrevNode;

    uIndex = (*HashFunc)( pData, pHashRBTree->uBucketCount );
    pNode = (HASHRBTREENODE *)(pHashRBTree->ppBucket[uIndex]);
    pPrevNode = pNode;

    /* 在哈希表中刪除對(duì)應(yīng)的節(jié)點(diǎn)，注意這里因?yàn)檫€要在紅黑樹中刪除對(duì)應(yīng)數(shù)據(jù)的節(jié)點(diǎn)，
     * 因此節(jié)點(diǎn)內(nèi)存必須在刪除紅黑樹時(shí)才能釋放.
     */
    while ( pNode != NULL )
    {
        if ( (*CompareFunc)( (pNode->TreeNode).pData, pData ) == 0 )
        {
            if ( pPrevNode == pNode )
            {
                pHashRBTree->ppBucket[uIndex] = pNode->pNext;
            }
            else
            {
                pPrevNode->pNext = pNode->pNext;
            }

            break;
        }

        pPrevNode = pNode;
        pNode = pNode->pNext;
    }    

    /* 在紅黑樹中將對(duì)應(yīng)節(jié)點(diǎn)刪除 */
    return RBTree_Delete(pHashRBTree->pTree, pData, CompareFunc, DestroyFunc);
}

/**	哈希紅黑樹的按紅黑樹查找方法進(jìn)行查找的函數(shù)

	@param	HASHRBTREE *pHashRBTree - 哈希紅黑樹指針	
	@param	void *pData - 要查找的數(shù)據(jù)	
	@param	HASHFUNC HashFunc - 哈希函數(shù)	
	@param	COMPAREFUNC CompareFunc - 數(shù)據(jù)比較函數(shù)	
	@return	void * - 成功返回查找到的數(shù)據(jù)指針，失敗返回NULL	
*/
void * HashRBTree_HashFind(HASHRBTREE *pHashRBTree, void *pData, 
                       HASHFUNC HashFunc, COMPAREFUNC CompareFunc )
{
	UINT			    uIndex;
	HASHRBTREENODE *	pNode;

    /* 參數(shù)校驗(yàn) */
	if ( pHashRBTree == NULL || pData == NULL 
        || HashFunc == NULL || CompareFunc == NULL )
	{
		return NULL;
	}

	uIndex = (*HashFunc)( pData, pHashRBTree->uBucketCount );
	pNode = (HASHRBTREENODE *)(pHashRBTree->ppBucket[uIndex]);
	
	/* 在哈希表沖突鏈中進(jìn)行查找 */
	while ( pNode != NULL )
	{
		if ( (*CompareFunc)( (pNode->TreeNode).pData, pData) == 0 )
		{
			/* 找到了對(duì)應(yīng)的數(shù)據(jù)，返回找到的數(shù)據(jù)指針 */
			return (pNode->TreeNode).pData;
		}
		pNode = pNode->pNext;
	}

    return NULL;
}


/**	哈希紅黑樹的按紅黑樹查找方法進(jìn)行查找的函數(shù)

	@param	HASHRBTREE *pHashRBTree - 哈希紅黑樹指針	
	@param	void *pData - 要查找的數(shù)據(jù)	
	@param	COMPAREFUNC CompareFunc - 數(shù)據(jù)比較函數(shù)	
	@return	void * - 成功返回查找到的數(shù)據(jù)指針，失敗返回NULL	
*/
void * HashRBTree_TreeFind(HASHRBTREE *pHashRBTree, void *pData, 
                           COMPAREFUNC CompareFunc )
{
    return RBTree_Find(pHashRBTree->pTree, pData, CompareFunc);
}


/**	哈希紅黑樹的逐個(gè)節(jié)點(diǎn)遍歷初始化函數(shù)

	@param	HASHRBTREE *pHashRBTree - 哈希紅黑樹指針	
	@return	void - 無	
*/
void HashRBTree_EnumBegin(HASHRBTREE *pHashRBTree)
{
    RBTree_EnumBegin(pHashRBTree->pTree);
}


/**	哈希紅黑樹的逐個(gè)節(jié)點(diǎn)遍歷函數(shù)，按照紅黑樹的遍歷方法進(jìn)行遍歷

	@param	HASHRBTREE *pHashRBTree - 哈希紅黑樹指針	
	@return	void * - 數(shù)據(jù)指針	
*/
void *HashRBTree_EnumNext(HASHRBTREE *pHashRBTree)
{
    return RBTree_EnumNext(pHashRBTree->pTree);
}