/*
 * 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 <stdio.h>
#include <stdlib.h>
#include "CapiGlobal.h"
#include "Queue.h"


/**	隊列的創(chuàng)建函數(shù)

	@param	UINT uMaxCount - 隊列里的最大數(shù)據(jù)個數(shù)	
	@return	QUEUE * - 成功時返回創(chuàng)建的隊列指針，失敗返回NULL	
*/
QUEUE *	Queue_Create(UINT uMaxCount)
{
    QUEUE *pQueue;
    
    if ( uMaxCount < 2 ) /* 環(huán)形隊列大小必須大于等于2才能插入元素 */
    {
        return NULL;
    }
    
    pQueue = (QUEUE *)malloc(sizeof(struct QUEUE_st));
    if ( pQueue != NULL )
    {
        pQueue->ppData = (void **)malloc(uMaxCount * sizeof(void *));
        if ( pQueue->ppData != NULL )
        {
            /* memset( pQueue->ppData, 0, uMaxCount * sizeof(void *)); */
            pQueue->ppData[0] = NULL;
            pQueue->uMaxCount = uMaxCount;

            pQueue->uHead = 0;
            pQueue->uTail = 0;
        }
        else
        {
            free( pQueue );
            pQueue = NULL;
        }
    }
    return pQueue;
}


/**	隊列的釋放函數(shù)，將隊列中剩余數(shù)據(jù)全部釋放掉及將隊列釋放掉

	@param	QUEUE *pQueue - 隊列指針	
	@param	DESTROYFUNC DestroyFunc - 數(shù)據(jù)釋放回調(diào)函數(shù)	
	@return	void - 無	
*/
void Queue_Destroy( QUEUE *pQueue, DESTROYFUNC DestroyFunc )
{
    UINT    i;
    
    if ( pQueue == NULL )
    {
        return;
    }

    if ( DestroyFunc != NULL )
    {
        if ( pQueue->uHead < pQueue->uTail )
        {
            for ( i = 0; i < pQueue->uTail; i++ )
            {
                (*DestroyFunc)( pQueue->ppData[i] );
            }
            for ( i = pQueue->uHead; i < pQueue->uMaxCount; i++ )
            {
                (*DestroyFunc)( pQueue->ppData[i] );
            }
        }
        else
        {
            for ( i = pQueue->uHead; i < pQueue->uTail; i++ )
            {
                (*DestroyFunc)( pQueue->ppData[i] );
            }
        }
    }

    free( pQueue->ppData );
    free( pQueue );
}


/**	插入數(shù)據(jù)到隊列的尾部的函數(shù)
	如果隊列已滿會自動將隊列空間擴大一倍再插入

	@param	QUEUE *pQueue - 隊列指針	
	@param	void *pData - 要插入的數(shù)據(jù)指針	
	@return	INT - CAPI_FAILED表示隊列已滿，申請不到內(nèi)存將隊列再擴大，插入失敗。
                  CAPI_SUCCESS表示插入成功
*/
INT Queue_InsertTail( QUEUE *pQueue, void *pData )
{
    UINT    uTailNext;

    /* 求出尾部位置的下一個位置 */
    if ( pQueue->uTail == pQueue->uMaxCount - 1 )
    {
        /* 當(dāng)?shù)搅藬?shù)組的最尾部時，下一個要從數(shù)組頭部重新計算 */
        uTailNext = 0;
    }
    else
    {
        uTailNext = pQueue->uTail + 1;
    }

    if ( uTailNext != pQueue->uHead ) /* 隊列未滿的情況 */
    {
        
        pQueue->ppData[pQueue->uTail] = pData;
        pQueue->uTail = uTailNext;
    }
    else /* 隊列為滿的情況 */
    {
		/* 將隊列空間擴大一倍 */       
		void **ppData = (void **)malloc(pQueue->uMaxCount * 2 * sizeof(void *)); 

		if ( ppData == NULL )
		{
			return CAPI_FAILED;
		}
		if ( pQueue->uHead > pQueue->uTail )
		{
			UINT i;
			/* 復(fù)制uHead和隊列最尾部間的數(shù)據(jù) */
			for ( i = pQueue->uHead; i < pQueue->uMaxCount; i++)
			{
				ppData[i] = pQueue->ppData[i];
			}
			/* 復(fù)制從0到uTail間的數(shù)據(jù) */
			for ( i = 0; i < pQueue->uTail; i++)
			{
				ppData[i + pQueue->uMaxCount] = pQueue->ppData[i];
			}
			pQueue->uTail += pQueue->uMaxCount;
		}
		else
		{
			UINT i;
			/* 復(fù)制從uHead到uTail間的數(shù)據(jù) */
			for ( i = pQueue->uHead; i < pQueue->uTail; i++)
			{
				ppData[i] = pQueue->ppData[i];
			}
		}
		/* 將輸入插入新分配的隊列空間中 */
        ppData[pQueue->uTail] = pData;
		pQueue->uTail += 1;
		
		pQueue->uMaxCount *= 2;
		free(pQueue->ppData);
		pQueue->ppData = ppData;
    }

	return CAPI_SUCCESS;
}


/**	隊列的彈出頭部數(shù)據(jù)函數(shù)

	@param	QUEUE *pQueue - 隊列指針	
	@return	void * - NULL表示隊列為空，否則返回彈出的頭部數(shù)據(jù)指針	
*/
void * Queue_PopHead(QUEUE *pQueue)
{
    UINT    uHead;

    uHead = pQueue->uHead;

    if ( uHead != pQueue->uTail )
    {
        /* 頭部和尾部沒有重合表示隊列不為空的情況 */
        if ( uHead == pQueue->uMaxCount - 1 )
        {
            pQueue->uHead = 0;
        }
        else
        {
            pQueue->uHead += 1;
        }

		return pQueue->ppData[uHead];
    }
	else
	{
		return NULL;
	}
}