rvpqueue.c

基于h323协议的软phone

/***********************************************************************
Filename   : rvpqueue.c
Description: utility for a Binary Heap Priority Queue
************************************************************************
        Copyright (c) 2001 RADVISION Inc. and RADVISION Ltd.
************************************************************************
NOTICE:
This document contains information that is confidential and proprietary
to RADVISION Inc. and RADVISION Ltd.. No part of this document may be
reproduced in any form whatsoever without written prior approval by
RADVISION Inc. or RADVISION Ltd..

RADVISION Inc. and RADVISION Ltd. reserve the right to revise this
publication and make changes without obligation to notify any person of
such revisions or changes.
***********************************************************************/
#include "rvpqueue.h"
#include <string.h>

/* Basic Priority Queue using a Binary Heap. User is responsible for locking */
/* if Priority Queue is to be shared. */

static RvSize_t RvPQueueNewSize(RvPQueue *pqueue, RvSize_t newsize);

/* The callbacks structure must be completely filled in. A duplicate */
/* of the callbacks structure will be made so that the user doesn't have */
/* to keep their own copy of that structure. Note that the memalloc callback */
/* will be called to allocate the starting array. See header file for qtype */
/* options. */
RvPQueue *RvPQueueConstruct(RvPQueue *pqueue, RvInt qtype, RvSize_t startsize, RvPQueueFuncs *callbacks)
{
#if defined(RV_NULLCHECK)
    if((pqueue == NULL) || (callbacks == NULL) ||
       (callbacks->memalloc == NULL) || (callbacks->memfree == NULL) ||
       (callbacks->itemcmp == NULL) || (callbacks->newindex == NULL))
        return NULL;
#endif
#if defined(RV_RANGECHECK)
    if((qtype != RV_PQUEUE_TYPE_FIXED) && (qtype != RV_PQUEUE_TYPE_EXPANDING) &&
       (qtype != RV_PQUEUE_TYPE_DYNAMIC))
        return NULL;
    if(startsize < 2)
        return NULL;
#endif

    pqueue->qtype = qtype;
    pqueue->startsize = startsize;
    pqueue->cursize = startsize;
    pqueue->numitems = 0;

    /* Copy callbacks */
    memcpy(&pqueue->callbacks, callbacks, sizeof(*callbacks));

    /* Allocate starting array (allocate extra because index 0 is unused for speed purposes) */
    pqueue->heap = NULL;
    pqueue->heap = (void **)callbacks->memalloc((RvSize_t)&pqueue->heap[startsize + 1], callbacks->memallocdata);
    if(pqueue->heap == NULL)
        return NULL;

    return pqueue;
}

/* Any items still in the heap are assumed to be removed. */
void RvPQueueDestruct(RvPQueue *pqueue)
{
#if defined(RV_NULLCHECK)
    if(pqueue == NULL)
        return;
#endif

    pqueue->callbacks.memfree(pqueue->heap, pqueue->callbacks.memfreedata);
}

/* Put new item into a Priority Queue. */
void *RvPQueuePut(RvPQueue *pqueue, void *newitem)
{
    RvSize_t newsize;
    RvSize_t index, parent;

#if defined(RV_NULLCHECK)
    if((pqueue == NULL) || (newitem == NULL))
        return NULL;
#endif

    /* Deal with running out of space in the heap array. */
    if(pqueue->numitems >= pqueue->cursize) {
        if(pqueue->qtype == RV_PQUEUE_TYPE_FIXED)
            return NULL; /* Fixed size, just return error */

        /* Calculate and allocate space, remember array index 0 is unused. */
        newsize = pqueue->cursize * 2;
        if(RvPQueueNewSize(pqueue, newsize) != newsize)
            return NULL; /* No more space available */
    }

    /* Insert new item in heap, start trying at end. */
    pqueue->numitems += 1;
    index = pqueue->numitems;
    while(index > 1) {
        parent = index / 2;
        if(pqueue->callbacks.itemcmp(newitem, pqueue->heap[parent]) == RV_FALSE)
            break; /* New item is not higher priority than parent so stop. */

        /* Move parent down heap and tell item that it has moved. */
        pqueue->heap[index] = pqueue->heap[parent];
        pqueue->callbacks.newindex(pqueue->heap[index], index);

        index = parent;
    }

    /* Store new item in proper spot and tell the item its position. */
    pqueue->heap[index] = newitem;
    pqueue->callbacks.newindex(newitem, index);

    return newitem;
}

/* Get highest priority item from Priority Queue. */
void *RvPQueueGet(RvPQueue *pqueue)
{
    /* Simply remove the highest value item in the heap. */
    return RvPQueueRemove(pqueue, 1);
}


/* Return highest priority item but don't remove it. */
void *RvPQueuePeek(RvPQueue *pqueue)
{
#if defined(RV_NULLCHECK)
    if(pqueue == NULL)
        return NULL;
#endif

    if(pqueue->numitems == 0)
        return NULL; /* empty */

    /* First item is the needed item. */
    return pqueue->heap[1];
}

/* Return the number of items in the priority queue. */
RvSize_t RvPQueueNumItems(RvPQueue *pqueue)
{
#if defined(RV_NULLCHECK)
    if(pqueue == NULL)
        return 0;
#endif

    return pqueue->numitems;
}

/* Get size of priority queue. */
RvSize_t RvPQueueSize(RvPQueue *pqueue)
{
#if defined(RV_NULLCHECK)
    if(pqueue == NULL)
        return 0;
#endif

    return pqueue->cursize;
}

/* Force a change of the priority queue size. Can not change */
/* the size smaller than the number of items in it. DYNAMIC */
/* queues will not reduce below this value (same as startsize) */
/* Returns new size (or old size if it couldn't be changed. */
RvSize_t RvPQueueChangeSize(RvPQueue *pqueue, RvSize_t newsize)
{
    RvSize_t result;

#if defined(RV_NULLCHECK)
    if(pqueue == NULL)
        return 0;
#endif

    if((newsize < 2) || (newsize < pqueue->numitems))
        return pqueue->cursize;

    result = RvPQueueNewSize(pqueue, newsize);
    if(result == newsize)
        pqueue->startsize = newsize; /* DYNAMIC hard floor */

    return result;
}


/* Clear the priority Queue */
void RvPQueueClear(RvPQueue *pqueue)
{
#if defined(RV_NULLCHECK)
    if(pqueue == NULL)
        return;
#endif

    pqueue->numitems = 0;

    /* If shrinking is allowed, shrink back to starting size. */
    if(pqueue->qtype == RV_PQUEUE_TYPE_DYNAMIC)
        RvPQueueNewSize(pqueue, pqueue->startsize);
}

/* Remove an item. The index for the item is the one provided by the newindex callback. */
/* Returns the item removed. */
void *RvPQueueRemove(RvPQueue *pqueue, RvSize_t itemindex)
{
    void *result, *lastitem;
    RvSize_t index, child, otherchild, lastnonleaf;
    RvSize_t newsize;

#if defined(RV_NULLCHECK)
    if(pqueue == NULL)
        return NULL;
#endif
#if defined(RV_RANGECHECK)
    if(itemindex == 0)
        return NULL;
#endif

    if(pqueue->numitems == 0)
        return NULL; /* empty */

    /* Make a copy of the needed item since that's the return value. */
    result = pqueue->heap[itemindex];

    /* The last item in the heap will be re-inserted from the deleted position. */
    lastitem = pqueue->heap[pqueue->numitems];
    pqueue->numitems -= 1;
    lastnonleaf = pqueue->numitems / 2;
    index = itemindex;
    while(index <= lastnonleaf) {
        child = index * 2;      /* left child */
        otherchild = child + 1; /* right child */
        if(child != pqueue->numitems) {
            /* Only check second child if it exists, ie first child is not last item in heap. */
            if(pqueue->callbacks.itemcmp(pqueue->heap[otherchild], pqueue->heap[child]) == RV_TRUE)
                child = otherchild; /* Use other (right) child if its higher priority. */
        }

        /* Compare re-inserted item with highest child. */
        if(pqueue->callbacks.itemcmp(pqueue->heap[child], lastitem) == RV_FALSE)
            break; /* Child isn't higher, we're done. */

        /* Move child up heap and tell item that it has moved. */
        pqueue->heap[index] = pqueue->heap[child];
        pqueue->callbacks.newindex(pqueue->heap[child], index);

        index = child;
    }

    /* Store re-inserted item in proper spot and tell the item its position. */
    pqueue->heap[index] = lastitem;
    pqueue->callbacks.newindex(lastitem, index);

    /* If shrinking is allowed, do it when needed. */