|
/* Priority
queue functions.
[ ... ]
static void
trickle_up (int index, struct
pqueue *queue)
{
void *tmp;
/* Save current node as tmp
node. */
tmp = queue->array[index];
/* Continue until the node reaches
top or the place where the parent
node should be upper than
the tmp node. */
while (index > 0 &&
(*queue->cmp) (tmp,
queue->array[PARENT_OF (index)]) < 0)
{
/* actually trickle up */
queue->array[index] =
queue->array[PARENT_OF (index)];
if (queue->update != NULL)
(*queue->update) (queue->array[index] , index);
index = PARENT_OF (index);
}
/* Restore the tmp node to appropriate
place. */
queue->array[index] = tmp;
if (queue->update != NULL) (*queue->update)
(tmp , index);
}
void
trickle_down (int index,
struct pqueue *queue)
{
void *tmp;
int which;
/* Save current node as tmp node. */
tmp = queue->array[index];
/* Continue until the node have at
least one (left) child. */
while (HAVE_CHILD (index, queue))
{
/* If right child exists,
and if the right child is more proper
to be moved upper. */
if (RIGHT_OF (index) <
queue->size &&
(*queue->cmp)
(queue->array[LEFT_OF (index)],
queue->array[RIGHT_OF
(index)]) > 0)
which = RIGHT_OF (index);
else
which = LEFT_OF (index);
/* If the tmp node should
be upper than the child, break. */
if ((*queue->cmp)
(queue->array[which], tmp) > 0)
break;
/* Actually trickle down
the tmp node. */
queue->array[index] =
queue->array[which];
if (queue->update != NULL)
(*queue->update) (queue->array[index] , index);
index = which;
}
/* Restore the tmp node to appropriate
place. */
queue->array[index] = tmp;
if (queue->update != NULL)
(*queue->update) (tmp , index);
}
struct pqueue *
pqueue_create ()
{
struct pqueue *queue;
queue =
(struct pqueue *) malloc (sizeof (struct pqueue));
memset (queue, 0, sizeof (struct
pqueue));
queue->array = (void **)
malloc (DATA_SIZE *
PQUEUE_INIT_ARRAYSIZE);
memset (queue->array, 0, DATA_SIZE
* PQUEUE_INIT_ARRAYSIZE);
queue->array_size =
PQUEUE_INIT_ARRAYSIZE;
/* by default we want nothing to happen
when a node changes */
queue->update = NULL ;
return queue;
}
[ ... ]
void
pqueue_enqueue (void *data, struct
pqueue *queue)
{
if (queue->size + 2 >=
queue->array_size && ! pqueue_expand (queue))
return;
queue->array[queue->size] = data;
if (queue->update != NULL) (*queue->update) (data ,queue->size);
trickle_up (queue->size, queue);
queue->size ++;
}
void *
pqueue_dequeue (struct pqueue
*queue)
{
void *data = queue->array[0];
if (queue->update != NULL) (*queue->update) (data , -2);
queue->array[0] = queue->array[--queue->size];
trickle_down (0, queue);
return data;
}
|
