pqueue.cpp File Reference

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

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

Include dependency graph for pqueue.cpp:

Go to the source code of this file.

Macros
#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. More...
void	PQueuePush (priorityQueue_t *pq, const pos4_t item, priorityQueueRating_t r)
void	PQueueFree (priorityQueue_t *pq)
	free up memory for pqueue More...
void	PQueuePop (priorityQueue_t *pq, pos4_t item)
	remove the first node from the pqueue and provide a pointer to it More...

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.cpp.

Macro Definition Documentation

PGetRating

#define PGetRating

(

elem

)

((elem).rating)

Definition at line 30 of file pqueue.cpp.

PQ_FIRST_ENTRY

#define PQ_FIRST_ENTRY   (1)

Definition at line 25 of file pqueue.cpp.

Referenced by PQueuePop(), and PQueuePush().

PQ_LEFT_CHILD_INDEX

#define PQ_LEFT_CHILD_INDEX

(

i

)

((i)<<1)

Definition at line 28 of file pqueue.cpp.

Referenced by PQueuePop().

PQ_PARENT_INDEX

#define PQ_PARENT_INDEX

(

i

)

((i)>>1)

Definition at line 24 of file pqueue.cpp.

Referenced by PQueuePush().

PQ_RIGHT_CHILD_INDEX

#define PQ_RIGHT_CHILD_INDEX

(

i

)

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

Definition at line 29 of file pqueue.cpp.

Function Documentation

PQueueFree()

void PQueueFree

(

priorityQueue_t *

pq

)

free up memory for pqueue

Definition at line 83 of file pqueue.cpp.

References priorityQueue_t::elements, and Mem_Free.

Referenced by Grid_CalcPathing(), and Grid_FindPath().

PQueueInitialise()

void PQueueInitialise	(	priorityQueue_t *	pq,
		uint32_t	maxElements
	)

initialise the priority queue with a maximum size of maxelements.

Definition at line 36 of file pqueue.cpp.

References priorityQueue_t::currentSize, priorityQueue_t::elements, priorityQueue_t::maxSize, Mem_AllocTypeN, and Sys_Error().

Referenced by Grid_CalcPathing(), and Grid_FindPath().

PQueuePop()

void PQueuePop	(	priorityQueue_t *	pq,
		pos4_t	item
	)

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

Definition at line 91 of file pqueue.cpp.

References priorityQueue_t::currentSize, priorityQueue_t::elements, i, priorityQueueElement_t::item, PQ_FIRST_ENTRY, PQ_LEFT_CHILD_INDEX, PQueueIsEmpty, and priorityQueueElement_t::rating.

Referenced by Grid_CalcPathing(), and Grid_FindPath().

PQueuePush()

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

Definition at line 47 of file pqueue.cpp.

References priorityQueue_t::currentSize, priorityQueue_t::elements, i, priorityQueueElement_t::item, priorityQueue_t::maxSize, Mem_ReAlloc, PQ_FIRST_ENTRY, PQ_PARENT_INDEX, and priorityQueueElement_t::rating.

Referenced by Grid_CalcPathing(), and Grid_FindPath().