rvpqueue.c

基于h323协议的软phone

    if((pqueue->qtype == RV_PQUEUE_TYPE_DYNAMIC) && (pqueue->numitems <= (pqueue->cursize / 4))) {
        newsize = pqueue->cursize / 2;

        /* Don't shrink beneath original starting size. */
        if(newsize >= pqueue->startsize)
            RvPQueueNewSize(pqueue, newsize);
    }

    return result;
}

/* Change the heap size to newsize. Returns the new size */
/* (or old one if it couldn't do it). Doesn't do any error */
/* checking so make sure newsize is valid. */
static RvSize_t RvPQueueNewSize(RvPQueue *pqueue, RvSize_t newsize)
{
    void *newptr;

    /* Remember that array index 0 is not used. */
    newptr = pqueue->callbacks.memalloc((RvSize_t)((RvInt8 *)&pqueue->heap[newsize + 1] - (RvInt8 *)pqueue->heap), pqueue->callbacks.memallocdata);
    if(newptr == NULL)
        return pqueue->cursize; /* No memory available so don't bother. */

    /* Copy existing heap to new space, remember array index 0 is unused. */
    memcpy(newptr, pqueue->heap, (RvSize_t)((RvInt8 *)&pqueue->heap[pqueue->numitems + 1] - (RvInt8 *)pqueue->heap));

    /* Get rid of old memory and set heap. */
    pqueue->callbacks.memfree(pqueue->heap, pqueue->callbacks.memfreedata);
    pqueue->cursize = newsize;
    pqueue->heap = (void **)newptr;

    return pqueue->cursize;
}

#if defined(RV_TEST_CODE)
#include "rv64ascii.h"
#include "rvstdio.h"
#include <stdlib.h>
typedef struct {
    RvInt64 value;
    RvSize_t index;
} RvPQueueTestStruct;

static volatile int callbackprint = 0;
static volatile int memcallbackprint = 0;

/* Set GETMEMORY & FREEMEMORY to function that will allocate memory */
#if (RV_OS_TYPE == RV_OS_TYPE_NUCLEUS) /* Shouldn't use this here but its a test */
#define FREEMEMORY(_x) NU_Deallocate_Memory((_x))
#define GETMEMORY(_x) NU_getmemory((_x))
#include <nucleus.h>
extern NU_MEMORY_POOL System_Memory;
static void *NU_getmemory(RvSize_t n)
{
    int status;
    void *ptr;

    status = NU_Allocate_Memory(&System_Memory, &ptr, n, NU_NO_SUSPEND);
    if(status != NU_SUCCESS) return NULL;
    return ptr;
}
#elif (RV_OS_TYPE == RV_OS_TYPE_OSE) /* Shouldn't use this here but its a test */
#define GETMEMORY(_x) heap_alloc_shared((_x), (__FILE__), (__LINE__))
#define FREEMEMORY(_x) heap_free_shared((_x))
#include "ose.h"
#include "heapapi.h"
#else
#define GETMEMORY(_x) malloc((_x))
#define FREEMEMORY(_x) free((_x))
#endif

static void *RvPQueueTestMemAlloc(RvSize_t size, void *data)
{
    void *result;

    result = (void *)GETMEMORY(size);
    if(memcallbackprint != 0)
        RvPrintf("Memory Allocation (Size = %u, data = %p) = %p\n", size, data, result);
    return result;
}

static void RvPQueueTestMemFree(void *ptr, void *data)
{
    if(memcallbackprint != 0)
        RvPrintf("Memory Free (Ptr = %p, data = %p)\n", ptr, data);
    FREEMEMORY(ptr);
}

static RvBool RvPQueueTestItemCmp(void *ptr1, void *ptr2)
{
    RvPQueueTestStruct *item1, *item2;
    RvChar s1[RV_64TOASCII_BUFSIZE], s2[RV_64TOASCII_BUFSIZE];

    item1 = (RvPQueueTestStruct *)ptr1;
    item2 = (RvPQueueTestStruct *)ptr2;
    if(callbackprint != 0) {
        Rv64toA(s1, item1->value);
        Rv64toA(s2, item2->value);
        RvPrintf("ItemCmp: Ptr1(%p) = %s, Ptr2(%p) = %s\n", ptr1, s1, ptr2, s2);
    }
    if(item1->value < item2->value)
        return RV_TRUE; /* ptr1 is higher priority than ptr2 */
    return RV_FALSE;
}

static void RvPQueueTestNewIndex(void *item, RvSize_t index)
{
    RvPQueueTestStruct *itemptr;

    itemptr = (RvPQueueTestStruct *)item;
    if(callbackprint != 0)
        RvPrintf("NewIndex: %p = %u\n", item, index);
    itemptr->index = index;
}

static void RvPQueueTestPQ(RvInt qtype, RvSize_t startsize)
{
    RvPQueueFuncs callbacks;
    RvPQueue pqueue, *pqueueresult;
    RvPQueueTestStruct *item, newitem;
    RvSize_t arraysize, i, newsize;
    RvPQueueTestStruct *itemarray;
    RvChar s64[RV_64TOASCII_BUFSIZE];
    RvInt64 lastvalue;

    RvPrintf("++++Testing Priority Queue++++\n");

    callbacks.memalloc = RvPQueueTestMemAlloc;
    callbacks.memfree = RvPQueueTestMemFree;
    callbacks.itemcmp = RvPQueueTestItemCmp;
    callbacks.newindex = RvPQueueTestNewIndex;
    callbacks.memallocdata = NULL;
    callbacks.memfreedata = NULL;
    RvPrintf("Constructing with startsize * 2 (%u)...\n", (startsize * 2));
    pqueueresult = RvPQueueConstruct(&pqueue, qtype, (startsize * 2), &callbacks);
    if(pqueueresult == NULL) {
        RvPrintf("RvPQueueConstruct: ERROR\n");
        RvPrintf("++++Priority Queue Test Aborted++++\n");
        return;
    } else RvPrintf("RvPQueueConstruct: OK\n");
    RvPrintf("RvPQueueNumItems = %u, RvPQueueSize = %u\n", RvPQueueNumItems(&pqueue), RvPQueueSize(&pqueue));

    RvPrintf("RvPQueueGet: ");
    item = (RvPQueueTestStruct *)RvPQueueGet(&pqueue);
    if(item == NULL) {
        RvPrintf("OK, nothing on queue.\n");
    } else RvPrintf("ERROR!\n");

    RvPrintf("RvPQueuePut: ");
    item = (RvPQueueTestStruct *)RvPQueuePut(&pqueue, &newitem);
    if(item == &newitem) {
        RvPrintf("OK.\n");
    } else RvPrintf("ERROR!\n");
    RvPrintf("RvPQueueNumItems = %u, RvPQueueSize = %u\n", RvPQueueNumItems(&pqueue), RvPQueueSize(&pqueue));

    RvPrintf("RvPQueueChangeSize(%u): ", (startsize / 4));
    newsize = RvPQueueChangeSize(&pqueue, (startsize / 4));
    if(newsize != (startsize / 4)) {
        RvPrintf("ERROR, size is %u.\n", newsize);
    } else RvPrintf("OK.\n");
    RvPrintf("RvPQueueNumItems = %u, RvPQueueSize = %u\n", RvPQueueNumItems(&pqueue), RvPQueueSize(&pqueue));

    RvPrintf("RvPQueuePeek: ");
    item = (RvPQueueTestStruct *)RvPQueuePeek(&pqueue);
    if(item == &newitem) {
        RvPrintf("OK.\n");
    } else RvPrintf("ERROR!\n");
    RvPrintf("RvPQueueNumItems = %u, RvPQueueSize = %u\n", RvPQueueNumItems(&pqueue), RvPQueueSize(&pqueue));

    RvPrintf("RvPQueueChangeSize(%u): ", startsize);
    newsize = RvPQueueChangeSize(&pqueue, startsize);
    if(newsize != startsize) {
        RvPrintf("ERROR, size is %u.\n", newsize);
    } else RvPrintf("OK.\n");
    RvPrintf("RvPQueueNumItems = %u, RvPQueueSize = %u\n", RvPQueueNumItems(&pqueue), RvPQueueSize(&pqueue));

    RvPrintf("RvPQueueClear.\n");
    RvPQueueClear(&pqueue);
    RvPrintf("RvPQueueNumItems = %u, RvPQueueSize = %u\n", RvPQueueNumItems(&pqueue), RvPQueueSize(&pqueue));

    arraysize = startsize * 3;
    itemarray = NULL;
    itemarray = (RvPQueueTestStruct *)GETMEMORY((RvSize_t)((RvInt8 *)&itemarray[arraysize] - (RvInt8 *)&itemarray[0]));
    for(i = 0; i < arraysize; i++) {
        itemarray[i].value = Rv64Multiply((RvInt64)rand(), (RvInt64)rand());
        itemarray[i].index = 0;
    }

    RvPrintf("Putting %d items on Priority Queue...\n", arraysize);
    for(i = 0; i <  arraysize; i++) {
        if(RvPQueuePut(&pqueue, &itemarray[i]) == NULL)
            RvPrintf("ERROR! Bad Put: #%d\n", i);
    }
    RvPrintf("RvPQueueNumItems = %u, RvPQueueSize = %u\n", RvPQueueNumItems(&pqueue), RvPQueueSize(&pqueue));

    Rv64toA(s64, itemarray[0].value);
    RvPrintf("Removing item (value = %s, index = %u)...\n", s64, itemarray[0].index);
    item = RvPQueueRemove(&pqueue, itemarray[0].index);
    if(item == &itemarray[0]) {
        RvPrintf("RvPQueueRemove OK.\n");
    } else RvPrintf("RvPQueueRemove ERROR!.\n");
    RvPrintf("RvPQueueNumItems = %u, RvPQueueSize = %u\n", RvPQueueNumItems(&pqueue), RvPQueueSize(&pqueue));

    RvPrintf("Getting items...\n");
    i = 0;
    lastvalue = RvInt64Const(0);
    while(RvPQueueNumItems(&pqueue) > 0) {
        i++;
        item = RvPQueueGet(&pqueue);
        Rv64toA(s64, item->value);
        RvPrintf("Got: %s\n", s64);
        if(lastvalue > item->value) {
            RvPrintf("ERROR. Priority sequence wrong.\n");
            break;
        }
        lastvalue = item->value;
    }
    RvPrintf("Retrieved %u items from queue.\n", i);
    RvPrintf("RvPQueueNumItems = %u, RvPQueueSize = %u\n", RvPQueueNumItems(&pqueue), RvPQueueSize(&pqueue));

    RvPrintf("RvPQueueDestruct...\n");
    RvPQueueDestruct(&pqueue);

    FREEMEMORY(itemarray);
    RvPrintf("++++Priority Queue test completed++++\n");
}

void RvPQueueTest(void)
{
    RvPrintf("Starting test of Rvpqueue.\n");

    callbackprint = 1;
    memcallbackprint = 1;

    RvPrintf("Testing PQueue Type: FIXED (15)\n");
    RvPQueueTestPQ(RV_PQUEUE_TYPE_FIXED, 15);

    callbackprint = 0;

    RvPrintf("Testing PQueue Type: EXPANDING (100)\n");
    RvPQueueTestPQ(RV_PQUEUE_TYPE_EXPANDING, 100);

    RvPrintf("Testing PQueue Type: DYNAMIC (100)\n");
    RvPQueueTestPQ(RV_PQUEUE_TYPE_DYNAMIC, 100);

    RvPrintf("Testing PQueue Type: DYNAMIC (3) ... size reduction should fail.\n");
    RvPQueueTestPQ(RV_PQUEUE_TYPE_DYNAMIC, 3);

    memcallbackprint = 0;
}

#endif /* RV_TEST_CODE */