ra.c

基于h323协议的软phone

/***********************************************************************
        Copyright (c) 2002 RADVISION Ltd.
************************************************************************
NOTICE:
This document contains information that is confidential and proprietary
to RADVISION Ltd.. No part of this document may be reproduced in any
form whatsoever without written prior approval by RADVISION Ltd..

RADVISION Ltd. reserve the right to revise this publication and make
changes without obligation to notify any person of such revisions or
changes.
***********************************************************************/


/*
  ra.c

  Fixed size array implementation.


  Format:

  +----------+------------+----------------+
  |  header  | bit vector | array of data  |
  +----------+------------+----------------+
  (raHeader)               (sizeofElement*maxNodes)


  Vacant element search is done in O(1) by linking all vacant nodes
  (link is inside the data).
  no need for vacant and data pointer (saving a lot of space).

  Note: element size >= sizeof(vacantNode).
  Bit vector: bit i=0 iff element i is free.

  */

#include "rvstdio.h"
#include "rvmemory.h"
#include "copybits.h"
#include "ra.h"


#ifdef __cplusplus
extern "C" {
#endif



#if defined(RV_RA_SUPPORT_WORKING_SET)

/* Maximum number of elements that RA will use for its working set */
#define RA_MAX_WORKING_SET_SIZE (50)

#endif  /* defined(RV_RA_SUPPORT_WORKING_SET) */



#define BIT_VECTOR(ra)      ((RvUint8 *)(ra) + sizeof(raHeader))

#define BIT_VECTOR_SIZE(n)   ( RvRoundToSize((n + 7) / 8 , RV_ALIGN_SIZE) )

/* Convert an element's pointer into its index in the array */
#define ELEM_INDEX(ra, ptr)   ( ((int)((char *)ptr - ra->arrayLocation)) / ra->sizeofElement )


/* This structure holds the linked-list of vacant elements within the array.
 * It is implemented inside the elements themselves, since when they're not used,
 * their content can be used for that purpose instead.
 */
typedef struct vacantNode_tag vacantNode;
struct vacantNode_tag
{
    void*       unused; /* This unused pointer is here to protect the first parameter people
                           will put in structs inside RA even when the element is vacant.
                           It is used by EMA. */
#if defined(RV_RA_SUPPORT_WORKING_SET)
    vacantNode* prev; /* Pointer to the previous vacant element. NULL if this one is the first */
#endif
    vacantNode* next; /* Pointer to the next vacant element. NULL if this one is the last */
    int         nodeIndex; /* Current node's index. This is used for faster calculation of the
                              raAdd() function. */
};



/************************************************************************
 *
 *                           Private functions
 *
 ************************************************************************/


/************************************************************************
 * raGetAllocationSize
 * purpose: Return the allocation size of an RA object
 * input  : elemSize            - Size of elements in the RA in bytes
 *          maxNumOfElements    - Number of elements in RA
 * output : none
 * return : Allocation size
 ************************************************************************/
static int
raGetAllocationSize(int elemSize, int maxNumOfElements)
{
    int roundSize = RvRoundToSize(sizeof(vacantNode), RV_ALIGN_SIZE);

    return
        sizeof(raHeader) +
        BIT_VECTOR_SIZE(maxNumOfElements) +
        (maxNumOfElements * RvMax(roundSize, elemSize));
}


/************************************************************************
 * raBuild
 * purpose: Build the actual RA from a given allocated memory block
 * input  : buffer              - Buffer of allocated RA memory block
 *          elemSize            - Size of elements in the RA in bytes
 *          maxNumOfElements    - Number of elements in RA
 *          threadSafe          - RV_TRUE to make raAdd,raDelete thread-safe
 *          name                - Name of RA (used in log messages)
 * output : none
 * return : Pointer to the modified header
 ************************************************************************/
static raHeader *
raBuild(
    IN char*        buffer,
    IN int          elemSize,
    IN int          maxNumOfElements,
    IN RvBool       threadSafe,
    IN const char*  name)
{
    raHeader *ra;

    /* Clear the buffer */
    memset(buffer, 0, (RvSize_t)raGetAllocationSize(elemSize, maxNumOfElements));

    /* Set the header information */
    ra = (raHeader *)buffer;

    if (threadSafe)
    {
        if (RvLockConstruct(&ra->lock) != RV_OK)
            return NULL;
    }
    ra->threadSafe = threadSafe;

    ra->maxNumOfElements = maxNumOfElements;
    ra->arrayLocation = (RvUint8*)ra + BIT_VECTOR_SIZE(maxNumOfElements) + sizeof(raHeader);
    ra->curNumOfElements = 0;
    ra->sizeofElement    = elemSize;
    ra->maxUsage         = 0;
    strncpy(ra->name, name, sizeof(ra->name));
    ra->name[sizeof(ra->name)-1] = '\0';

#if defined(RV_RA_SUPPORT_WORKING_SET)
    /* Caculate a default size for our working-set */
    if ( maxNumOfElements > (RA_MAX_WORKING_SET_SIZE * 2) )
        ra->workingSetSize = RA_MAX_WORKING_SET_SIZE;
    else
        ra->workingSetSize = maxNumOfElements / 2;
#endif  /* defined(RV_RA_SUPPORT_WORKING_SET) */

    raClear((HRA)ra);   /* init vacant list and pointers */

    return ra;
}







/************************************************************************
*
*                           Public functions
*
************************************************************************/


/************************************************************************
 * raConstruct
 * purpose: Create an RA object
 * input  : elemSize            - Size of elements in the RA in bytes
 *          maxNumOfElements    - Number of elements in RA
 *          threadSafe          - RV_TRUE to make raAdd,raDelete thread-safe
 *          name                - Name of RA (used in log messages)
 * output : none
 * return : Handle to RA constructed on success
 *          NULL on failure
 ************************************************************************/
HRA raConstruct(
    IN int          elemSize,
    IN int          maxNumOfElements,
    IN RvBool       threadSafe,
    IN const char*  name)
{
    raHeader*   ra;
    int         size;
    void*       ptr=NULL;

    /* Make sure the size is at least 4 bytes per element and aligned on 32bits */
    size = RvRoundToSize(RvMax(elemSize, sizeof(vacantNode)), RV_ALIGN_SIZE);

    /* Allocate the amount of memory necessary */
    if(RvMemoryAlloc(NULL, (void**)&ptr, (RvSize_t)raGetAllocationSize(size, maxNumOfElements)) != RV_OK)
        return NULL;

    /* Build the RA header and elements properly */
    ra = raBuild((char *)ptr, size, maxNumOfElements, threadSafe, name);
    if (ra == NULL)
    {
        /* Error building this RA */
        RvMemoryFree(ptr);
        return NULL;
    }

    RvLogSourceConstruct(RvLogGet(), &ra->log, RV_LOG_LIBCODE_ASN1, "RA", "R Array");

#ifdef RV_RA_DEBUG
    RvLogDebug(&ra->log,
        (&ra->log, "raConstruct (%s): %d elements of size %d (total of %d)", name, maxNumOfElements, size, maxNumOfElements*size));
#endif

    return (HRA)ra;
}


/************************************************************************
* raDestruct
* purpose: Free an RA object, deallocating all of its used memory
* input  : raH     - Handle of the RA object
* output : none
* return : none
************************************************************************/
void raDestruct(HRA raH)
{
    if (raH != NULL)
    {
        raHeader* ra = (raHeader*) raH;

        if (ra->threadSafe)
            RvLockDestruct(&ra->lock);

        RvLogSourceDestruct(RvLogGet(), &ra->log);
        RvMemoryFree((raHeader*)raH);
    }
}


/************************************************************************
 * raClear
 * purpose: Clean an RA object from any used elements, bringing it back
 *          to the point it was when raConstruct() was called.
 * input  : raH     - Handle of the RA object
 * output : none
 * return : none
 ************************************************************************/
void
raClear(HRA raH)
{
    raHeader*   ra = (raHeader *)raH;
    vacantNode* lastNode;
    vacantNode* curNode;
    vacantNode* prevNode;
    char*       nextNode;
    int i;

    if (ra == NULL)
        return;

    if (ra->threadSafe)
        RvLockGet(&ra->lock);

    ra->curNumOfElements = 0;
    ra->maxUsage = 0;

    curNode = (vacantNode *)RV_RA_ELEM_DATA(ra, 0);
    lastNode = (vacantNode *)RV_RA_ELEM_DATA(ra, ra->maxNumOfElements-1);

    /* Set the first vacant element pointers to first elements in array */
    if (ra->maxNumOfElements > 0)
        ra->firstVacantElement = (RAElement)curNode;
    else
        ra->firstVacantElement = NULL;

#if defined(RV_RA_SUPPORT_WORKING_SET)
    ra->workingSetDistance = ra->workingSetSize;

    /* Set the working set element by the size of the working set we're using */
    ra->workingSetElement = (RAElement)RV_RA_ELEM_DATA(ra, ra->workingSetSize);
#else
    ra->lastVacantElement = (RAElement)lastNode;
#endif


    /* Set each element to point at the next element as the next free element */
    prevNode = NULL;
    for (i = 0; i < ra->maxNumOfElements; i++)
    {
        nextNode = ((char *)curNode) + ra->sizeofElement;
#if defined(RV_RA_SUPPORT_WORKING_SET)
        curNode->prev = prevNode;
#endif
        curNode->next = (vacantNode *)nextNode;
        curNode->nodeIndex = i;

        prevNode = curNode;
        curNode = (vacantNode *)nextNode;
    }

    /* Make sure last element points to NULL */
    lastNode->next = NULL;

    /* Make sure the bits vector shows all elements as free */
    memset(BIT_VECTOR(ra), 0, BIT_VECTOR_SIZE(ra->maxNumOfElements));

    if (ra->threadSafe)
        RvLockRelease(&ra->lock);
}


/************************************************************************
 * raSetCompareFunc
 * purpose: Set the compare function to use in raFind()
 * input  : raH     - Handle of the RA object
 *          func    - Compare function to use
 * output : none
 * return : none
 ************************************************************************/
void raSetCompareFunc(IN HRA raH, IN RAECompare func)
{
    raHeader *ra = (raHeader *)raH;
    ra->compare = func;
}


/************************************************************************
 * raSetPrintFunc
 * purpose: Set the print function to use in raPrint()
 * input  : raH     - Handle of the RA object
 *          func    - Print function to use
 * output : none
 * return : none
 ************************************************************************/
void raSetPrintFunc(IN HRA raH, IN RAEFunc func)
{
    raHeader *ra = (raHeader *)raH;
    ra->print = func;
}


/************************************************************************
 * raGetPrintFunc
 * purpose: Set the print function to use in raPrint()
 * input  : raH     - Handle of the RA object
 * output : none
 * return : Print function used by RA (given by raSetPrintFunc)
 ************************************************************************/
RAEFunc raGetPrintFunc(IN HRA raH)
{
    return ((raHeader *)raH)->print;
}


/************************************************************************
 * raAdd
 * purpose: Allocate an element in RA for use, without initializing its
 *          value.
 * input  : raH         - Handle of the RA object
 * output : pOutElem    - Pointer to the element added.
 *                        If given as NULL, it will not be set
 * return : Negative value on failure
 *          Non-negative value representing the location of the added
 *          element.
 ************************************************************************/
int raAdd(IN HRA raH, OUT RAElement *pOutElem)
{
    raHeader *ra = (raHeader *)raH;
    RAElement allocatedElement;
    int vLocation;

    if (ra->threadSafe)
        RvLockGet(&ra->lock);

    /* See if there's any place in this RA */
    if (ra->firstVacantElement == NULL)
    {
        RvLogError(&ra->log,
            (&ra->log, "raAdd (%s): Array full (%d elements)", ra->name, ra->maxNumOfElements));
        RvPrintf("raAdd (%s): Array full (%d elements)\n", ra->name, ra->maxNumOfElements);
        if (pOutElem != NULL) *pOutElem = NULL;
        if (ra->threadSafe)
            RvLockRelease(&ra->lock);
        return RV_ERROR_UNKNOWN;
    }

    allocatedElement = ra->firstVacantElement;

    /* Get the element from list of vacant elements and fix that list */
    ra->firstVacantElement = (RAElement)((vacantNode *)allocatedElement)->next;

#if defined(RV_RA_SUPPORT_WORKING_SET)
    if (((vacantNode *)ra->workingSetElement)->next != NULL)
        ra->workingSetElement = (RAElement)(((vacantNode *)ra->workingSetElement)->next);
    else
        ra->workingSetDistance--;

    /* Let's see what we have to do with our free list */
    if (ra->firstVacantElement == NULL)
    {
        /* No more free elements - update the working set information */
        ra->workingSetElement = NULL;
        ra->workingSetDistance = 0;
    }
    else
    {
        /* Since we chopped off the head of the free list - we should set the new head
           of the free list as the first element: i.e - prev=NULL */
        ((vacantNode *)ra->firstVacantElement)->prev = NULL;
    }
#else
    if (ra->firstVacantElement == NULL)
        ra->lastVacantElement = NULL;
#endif

    /* Get the index of this element and set in the bit vector */
    vLocation = ((vacantNode *)allocatedElement)->nodeIndex;
    setBitTrue(BIT_VECTOR(ra), vLocation); /* make it occupied */

    /* Set statistical information */
    ra->curNumOfElements++;
    if (ra->curNumOfElements > ra->maxUsage)
        ra->maxUsage=ra->curNumOfElements;

    RvLogInfo(&ra->log,
        (&ra->log, "raAdd (%s): %d current elements, Added 0x%p, location %d", ra->name, ra->curNumOfElements, allocatedElement, vLocation));

    if (ra->threadSafe)
        RvLockRelease(&ra->lock);

    /* Return the location */
    if (pOutElem != NULL)
        *pOutElem = allocatedElement;
    return vLocation;
}