VCC PRIORITY QUEUE NATIVE IMPL

[Courageous]

This is a visual c++ implementation of a heap-priority queue.
It is 5-6 times faster than the equivalent python, as tested
doing heapsort. This priority queue implements "lowest is best"
priority, so all pops always retrieve the lowest item in the
queue.

This is my second implementation of a python C extension, and
I believe it is correct, however there exists some small chance
I've messed up something with references, as I'm fairly new at
this.

Hope someone finds this useful,

C/


//////////////////////////////////////////////////////////////////////
//  Pqueue.c -- pque and pque cursor object types for python
//////////////////////////////////////////////////////////////////////

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <Python.h>

//////////////////////////////////////////////////////////////////////
//  FORWARD DECLARES AND THE LIKE:
//////////////////////////////////////////////////////////////////////

static                 char            msg[256];
staticforward          PyTypeObject    PqueueObjectType;

//////////////////////////////////////////////////////////////////////
//  INTERNAL DATA TYPES:
//////////////////////////////////////////////////////////////////////

typedef struct __PqueueNode     PqueueNode;
typedef struct __PqueueNode
{
    double        priority;
    PyObject*     object;
}
PqueueNode;

//////////////////////////////////////////////////////////////////////
//  EXTERNAL DATA TYPES / PYTHON OBJECTS:
//////////////////////////////////////////////////////////////////////

typedef struct __Pqueue
{
    PyObject_HEAD

    PqueueNode**   heap;        // the heap array
    long           len;         // current length
    long           alloclen;    // allocated length
}
Pqueue;

//////////////////////////////////////////////////////////////////////

static void            PqueueObjectDestroy (Pqueue* self);
static PyObject*       PqueueObjectGetattr (Pqueue* self, char* name);
static int             PqueueSeqLen        (Pqueue* self);

//####################################################################
//  PQUEUE METHODS
//####################################################################

static PyObject* PqueuePush ( Pqueue* pque, PyObject* args )
{
    PqueueNode*    newnode;
    PqueueNode*    temp;
    PyObject*      object;
    double         pri;

    PqueueNode**   heap;
    long           pos;

    if (!PyArg_ParseTuple(args,"dO", &pri, &object)) 
    {
        PyErr_SetString(PyExc_ValueError, "attempt to push onto pque without an object to push");
        return NULL;
    }

    Py_INCREF ( object );

    newnode                       = (PqueueNode*) malloc ( sizeof(PqueueNode) );
    newnode->object               = object;
    newnode->priority             = pri;

    pos                           = pque->len+1;
    heap                          = pque->heap;
    heap[pos]                     = newnode;
    pque->len++;

    //sprintf(msg,"print \"pushing node pos= %d pri= %f\"", pos, pri);
    //PyRun_SimpleString(msg);

    while (heap[pos/2]->priority > heap[pos]->priority)
    {
        temp = heap[pos/2];
        heap[pos/2] = heap[pos];
        heap[pos] = temp;
        pos /= 2;
    }
    
    Py_INCREF(Py_None);
    return Py_None;
}

static PyObject* PqueuePop ( Pqueue* pque, PyObject* args )
{
    PqueueNode**   heap;
    PqueueNode*    popnode;
    PqueueNode*    temp;
    PyObject*      retval;
    long           pos;
    long           len;
    double         pri;
    long           j;

    if (pque->len == 0)
    {
        Py_INCREF(Py_None);
        return Py_None;
    }

    heap           = pque->heap;
    popnode        = heap[1];
    retval         = popnode->object;
    len            = pque->len;
    pri            = popnode->priority;
    pos            = 1;
    j              = 2;

    if (len>1)
    {
        heap[1]=heap[len];
        len--;

        while ( pos <= len/2 )
        {
            if ( j<len && heap[j]->priority > heap[j+1]->priority) j++;
            if ( heap[pos]->priority <= heap[j]->priority) break;

            temp       = heap[pos];
            heap[pos]  = heap[j];
            heap[j]    = temp;

            pos = j;
            j = pos*2;
        }
    }

    pque->len--;
    free((char*)popnode);
    //Py_INCREF(retval);
    return retval;
}

    ////  PqueuePeek()  --  return the value of the tail item, but don't pop

static PyObject* PqueuePeek ( Pqueue* pque, PyObject* args )
{
    if (pque->len == 0)
    {
        Py_INCREF(Py_None);
        return Py_None;
    }

    Py_INCREF(pque->heap[1]->object);
    return pque->heap[1]->object;
}

static PyObject* PqueueDump ( Pqueue* pque, PyObject* args )
{
    int i;
    for (i=0;i<pque->len+1;i++)
    {
        sprintf(msg,"print \"node %f\"", pque->heap[i]->priority);
        PyRun_SimpleString(msg);
    }

    Py_INCREF(Py_None);
    return Py_None;
}

//####################################################################
//  MODULE HOOKUPS
//####################################################################

    ////  Primary instance object CONSTRUCTOR

static PyObject* PqueueCreate ( PyObject* module, PyObject* args )
{
    Pqueue* pque                  = PyObject_NEW (Pqueue,&PqueueObjectType);
    PqueueNode* sentinel          = (PqueueNode*) malloc ( sizeof(PqueueNode));
    long initialsize              = 1000;

    PyArg_ParseTuple(args,"i", &initialsize);  // failure okay
    sprintf(msg,"print \"new pque size is %d\"", initialsize);
    PyRun_SimpleString(msg);

    // we always make room for a sentinel

    pque->heap                    = (PqueueNode**) malloc ( (initialsize+2) * sizeof(PqueueNode*) );
    sentinel->priority            = -1;
    pque->heap[0]                 = sentinel;
    pque->len                     = 0;
    pque->alloclen                = initialsize;

    return pque;
}

    ////  Pqueue object method hookup

static char PqueuePushDoc[]=      
    "p.push(priority,object) -- pushes an object onto the queue with the designated priority; always
returns None";
static char PqueuePopDoc[]=      
    "p.pop() -- pops the highest priority object off the priority queue; returns None if no object
is present.";
static char PqueuePeekDoc[]=      
    "p.peek() -- returns the object at the head of the pque, leaving it in the pque; returns None if
no object is present.";

static struct PyMethodDef PqueueObjectMethods[]=
{
    { "push",        (PyCFunction)PqueuePush,     1, PqueuePushDoc },
    { "pop",         (PyCFunction)PqueuePop,      0, PqueuePopDoc },
    { "peek",        (PyCFunction)PqueuePeek,     0, PqueuePeekDoc },
    { "dump",        (PyCFunction)PqueueDump,     0, PqueuePeekDoc },
    { NULL, NULL }
};

static PySequenceMethods PqueueSequenceMethods=
{
    (inquiry)            PqueueSeqLen,   // len(p)
    (binaryfunc)         0,              // concat
    (intargfunc)         0,              // ?
    (intargfunc)         0,              // p[i]
    (intintargfunc)      0,              // p[i:j]
    (intobjargproc)      0,              // p[i]=v
    (intintobjargproc)   0,              // p[i:j]=v
};

    ////  Pqueue object python type

static PyTypeObject PqueueObjectType = 
{
    PyObject_HEAD_INIT(0)                // mandatory init
    0,                                   // ?
    "pqueue",                             // object name
    sizeof(Pqueue),                       // record size
    0,                                   // ?
    (destructor)                         PqueueObjectDestroy,
    0,                                   // print
    (getattrfunc)                        PqueueObjectGetattr,
    0,                                   //PqueueObjectSetattr,
    0,                                   // compare
    0,                                   //PqueueObjectRepr,
    0,                                   // number
                                         &PqueueSequenceMethods,
    0,                                   // mapping
    0,                                   // hash
    0,                                   // call
    0                                    // str
};

    ////  Our module-level methods; there's just one:

static char PqueueCreateDoc[] =
    "create() -- creates a priority queue object";

static PyMethodDef PqueueModuleMethods[]=
{
    {"create",        PqueueCreate,          1, PqueueCreateDoc},
    {NULL, NULL }
};

//####################################################################
//  PQUEUE PRIMARY METHODS
//####################################################################

static void PqueueObjectDestroy (Pqueue* self)
{
    int i;

    free((char*)self->heap[0]);     // free the sentinel
    for (i=1;i<self->len+1;i++)  // from sentinel to end
    {
        Py_DECREF ( self->heap[i]->object );
        free((char*)self->heap[i]);
    }

    PyMem_DEL (self);
}

static PyObject* PqueueObjectGetattr ( Pqueue* self, char* name)
{
    return Py_FindMethod(PqueueObjectMethods,(PyObject*)self, name);
}

static int PqueueSeqLen (Pqueue* self)
{
    return self->len;
}

//####################################################################
//  GLUE
//####################################################################

void _declspec(dllexport) initpqueue()
{
    Py_InitModule("pqueue", PqueueModuleMethods);
}

//////////////////////////////////////////////////////////////////////
//  END
//////////////////////////////////////////////////////////////////////