#include "defs.h"
#include "errors.h"
#include "mempool.h"
#include "priority_queue.h"

Include dependency graph for priority_queue.c:

Defines
#define	PRQ_comparison_fn(x) ((x)->comparison_fn)
#define	PRQ_mem_pool(x) ((x)->mem_pool)
#define	PRQ_size(x) ((x)->size)
#define	PRQ_allocated_size(x) ((x)->allocated_size)
#define	PRQ_expansion_factor(x) ((x)->expansion_factor)
#define	PRQ_get_index_fn(x) ((x)->get_index_fn)
#define	PRQ_set_index_fn(x) ((x)->set_index_fn)
#define	PRQ_heap_vector(x) ((x)->heap_vector)
Functions
void *	PRQ_Ith (PRQ *prq, INT32 i)
INT32	PRQ_Size (PRQ *prq)
static void	PRQ_Set_Ith (PRQ prq, INT32 i, void element)
static INT32	PRQ_Upheap (PRQ *prq, INT32 index)
static INT32	PRQ_Downheap (PRQ *prq, INT32 index)
void	PRQ_Initialize (PRQ prq, PRQ_COMPARISON_FUNCTION comparison_fn, PRQ_GET_INDEX_FUNCTION get_fn, PRQ_SET_INDEX_FUNCTION set_fn, MEM_POOL pool, INT32 initial_size, INT32 expansion_factor)
void *	PRQ_Delete_Top (PRQ *prq)
void *	PRQ_Top (PRQ *prq)
void	PRQ_Insert (PRQ prq, void element)
void	PRQ_Remove (PRQ prq, void element)
void	PRQ_Reset (PRQ *prq)

Define Documentation

#define PRQ_allocated_size ( x ) ((x)->allocated_size)

Definition at line 60 of file priority_queue.c.

Referenced by PRQ_Initialize(), and PRQ_Insert().

#define PRQ_comparison_fn ( x ) ((x)->comparison_fn)

======================================================================= Private field access macros =======================================================================

Definition at line 57 of file priority_queue.c.

Referenced by PRQ_Downheap(), PRQ_Initialize(), and PRQ_Upheap().

#define PRQ_expansion_factor ( x ) ((x)->expansion_factor)

Definition at line 61 of file priority_queue.c.

Referenced by PRQ_Initialize(), and PRQ_Insert().

#define PRQ_get_index_fn ( x ) ((x)->get_index_fn)

Definition at line 62 of file priority_queue.c.

Referenced by PRQ_Initialize(), and PRQ_Remove().

#define PRQ_heap_vector ( x ) ((x)->heap_vector)

Definition at line 64 of file priority_queue.c.

Referenced by PRQ_Initialize(), PRQ_Insert(), PRQ_Ith(), and PRQ_Set_Ith().

#define PRQ_mem_pool ( x ) ((x)->mem_pool)

Definition at line 58 of file priority_queue.c.

Referenced by PRQ_Initialize(), and PRQ_Insert().

#define PRQ_set_index_fn ( x ) ((x)->set_index_fn)

Definition at line 63 of file priority_queue.c.

Referenced by PRQ_Initialize(), and PRQ_Set_Ith().

#define PRQ_size ( x ) ((x)->size)

Definition at line 59 of file priority_queue.c.

Referenced by PRQ_Delete_Top(), PRQ_Downheap(), PRQ_Initialize(), PRQ_Insert(), PRQ_Remove(), PRQ_Reset(), PRQ_Size(), PRQ_Top(), and PRQ_Upheap().

Function Documentation

void* PRQ_Delete_Top ( PRQ * prq )

Definition at line 312 of file priority_queue.c.

References FmtAssert, PRQ_Downheap(), PRQ_Ith(), PRQ_Set_Ith(), and PRQ_size.

Here is the call graph for this function:

static INT32 PRQ_Downheap	(	PRQ *	prq,
		INT32	index
	)		`[static]`

Definition at line 195 of file priority_queue.c.

References FmtAssert, PRQ_comparison_fn, PRQ_Ith(), PRQ_Set_Ith(), and PRQ_size.

Referenced by PRQ_Delete_Top(), and PRQ_Remove().

Here is the call graph for this function:

void PRQ_Initialize	(	PRQ *	prq,
		PRQ_COMPARISON_FUNCTION	comparison_fn,
		PRQ_GET_INDEX_FUNCTION	get_fn,
		PRQ_SET_INDEX_FUNCTION	set_fn,
		MEM_POOL *	pool,
		INT32	initial_size,
		INT32	expansion_factor
	)

====================================================================== Interface routines ======================================================================

Definition at line 270 of file priority_queue.c.

References DevWarn(), pool, PRQ_allocated_size, PRQ_comparison_fn, PRQ_expansion_factor, PRQ_get_index_fn, PRQ_heap_vector, PRQ_mem_pool, PRQ_set_index_fn, PRQ_size, and TYPE_MEM_POOL_ALLOC_N.

Here is the call graph for this function:

void PRQ_Insert	(	PRQ *	prq,
		void *	element
	)

Definition at line 363 of file priority_queue.c.

References DevWarn(), PRQ_allocated_size, PRQ_expansion_factor, PRQ_heap_vector, PRQ_mem_pool, PRQ_Set_Ith(), PRQ_size, PRQ_Upheap(), and TYPE_MEM_POOL_REALLOC_N.

Here is the call graph for this function:

void* PRQ_Ith	(	PRQ *	prq,
		INT32	i
	)

======================================================================= Utilities for manipulating the heap =======================================================================

Definition at line 81 of file priority_queue.c.

References PRQ_heap_vector.

Referenced by PRQ_Delete_Top(), PRQ_Downheap(), PRQ_Remove(), PRQ_Top(), and PRQ_Upheap().

void PRQ_Remove	(	PRQ *	prq,
		void *	element
	)

Definition at line 403 of file priority_queue.c.

References FmtAssert, PRQ_Downheap(), PRQ_get_index_fn, PRQ_Ith(), PRQ_Set_Ith(), PRQ_size, PRQ_Upheap(), and UNDEFINED.

Here is the call graph for this function:

void PRQ_Reset ( PRQ * prq )

Definition at line 470 of file priority_queue.c.

References PRQ_size.

static void PRQ_Set_Ith	(	PRQ *	prq,
		INT32	i,
		void *	element
	)		`[static]`

Definition at line 114 of file priority_queue.c.

References NULL, PRQ_heap_vector, and PRQ_set_index_fn.

Referenced by PRQ_Delete_Top(), PRQ_Downheap(), PRQ_Insert(), PRQ_Remove(), and PRQ_Upheap().

INT32 PRQ_Size ( PRQ * prq )

Definition at line 98 of file priority_queue.c.

References PRQ_size.

void* PRQ_Top ( PRQ * prq )

Definition at line 346 of file priority_queue.c.

References FmtAssert, PRQ_Ith(), and PRQ_size.

Here is the call graph for this function:

static INT32 PRQ_Upheap	(	PRQ *	prq,
		INT32	index
	)		`[static]`

heap_Upheap

Sifts the heap_element at position 'index' in the heap (1-based) up to its appropriate position in the heap. If the heap element should not move closer to the root ("up"), it is not moved. The the new index of the heap_element is returned.

Definition at line 149 of file priority_queue.c.

References FmtAssert, PRQ_comparison_fn, PRQ_Ith(), PRQ_Set_Ith(), and PRQ_size.

Referenced by PRQ_Insert(), and PRQ_Remove().

Here is the call graph for this function:

Defines

Functions

Define Documentation

Function Documentation