pqueue.c File Reference

Implementation of a priority queue by using a binary heap. More...

#include "common.h"
#include "pqueue.h"

Include dependency graph for pqueue.c:

Go to the source code of this file.

Defines
#define	PQ_PARENT_INDEX(i)   ((i)>>1)
#define	PQ_FIRST_ENTRY   (1)
#define	PQ_LEFT_CHILD_INDEX(i)   ((i)<<1)
#define	PQ_RIGHT_CHILD_INDEX(i)   (((i)<<1)+1)
#define	PGetRating(elem)   ((elem).rating)
Functions
void	PQueueInitialise (priorityQueue_t *pq, uint32_t maxElements)
	initialise the priority queue with a maximum size of maxelements.
void	PQueuePush (priorityQueue_t *pq, pos4_t item, priorityQueueRating_t r)
void	PQueueFree (priorityQueue_t *pq)
	free up memory for pqueue
void	PQueuePop (priorityQueue_t *pq, pos4_t item)
	remove the first node from the pqueue and provide a pointer to it

---

Detailed Description

Implementation of a priority queue by using a binary heap.

Note:

Manage a priority queue as a heap - the heap is implemented as an array.

Definition in file pqueue.c.

---

Define Documentation

#define PGetRating

(

elem

)

((elem).rating)

Definition at line 32 of file pqueue.c.

#define PQ_FIRST_ENTRY   (1)

Definition at line 27 of file pqueue.c.

Referenced by PQueuePop(), and PQueuePush().

#define PQ_LEFT_CHILD_INDEX

(

i

)

((i)<<1)

Definition at line 30 of file pqueue.c.

Referenced by PQueuePop().

#define PQ_PARENT_INDEX

(

i

)

((i)>>1)

Definition at line 26 of file pqueue.c.

Referenced by PQueuePush().

#define PQ_RIGHT_CHILD_INDEX

(

i

)

(((i)<<1)+1)

Definition at line 31 of file pqueue.c.

---

Function Documentation

void PQueueFree

(

priorityQueue_t *

pq

)

free up memory for pqueue

Definition at line 87 of file pqueue.c.

References priorityQueue_s::elements.

Referenced by Grid_MoveCalc().

void PQueueInitialise	(	priorityQueue_t *	pq,
		uint32_t	maxElements
	)

initialise the priority queue with a maximum size of maxelements.

Definition at line 38 of file pqueue.c.

References priorityQueue_s::currentSize, priorityQueue_s::elements, priorityQueue_s::maxSize, and Sys_Error().

Referenced by Grid_MoveCalc().

void PQueuePop	(	priorityQueue_t *	pq,
		pos4_t	item
	)

remove the first node from the pqueue and provide a pointer to it

Definition at line 95 of file pqueue.c.

References priorityQueue_s::currentSize, priorityQueue_s::elements, i, priorityQueueElement_s::item, PQ_FIRST_ENTRY, PQ_LEFT_CHILD_INDEX, PQueueIsEmpty, and priorityQueueElement_s::rating.

Referenced by Grid_MoveCalc().

void PQueuePush	(	priorityQueue_t *	pq,
		pos4_t	item,
		priorityQueueRating_t	r
	)

Definition at line 49 of file pqueue.c.

References priorityQueue_s::currentSize, priorityQueue_s::elements, i, priorityQueueElement_s::item, priorityQueue_s::maxSize, PQ_FIRST_ENTRY, PQ_PARENT_INDEX, and priorityQueueElement_s::rating.

Referenced by Grid_MoveCalc(), and Grid_SetMoveData().