pqueue_base.c File Reference

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <stdbool.h>
#include "pqueue_base.h"
#include "util.h"

Macros
#define	LF_LEFT(i)
#define	LF_RIGHT(i)
#define	LF_PARENT(i)

Functions
void *	find_equal_same_priority (pqueue_t *q, void *e, int pos)
pqueue_t *	pqueue_init (size_t n, pqueue_cmp_pri_f cmppri, pqueue_get_pri_f getpri, pqueue_get_pos_f getpos, pqueue_set_pos_f setpos, pqueue_eq_elem_f eqelem, pqueue_print_entry_f prt)
	Allocate and initialize a priority queue.
void	pqueue_free (pqueue_t *q)
size_t	pqueue_size (pqueue_t *q)
void *	pqueue_find_same_priority (pqueue_t *q, void *e)
void *	pqueue_find_equal_same_priority (pqueue_t *q, void *e)
int	pqueue_insert (pqueue_t *q, void *d)
int	pqueue_remove (pqueue_t *q, void *d)
void *	pqueue_pop (pqueue_t *q)
void	pqueue_empty_into (pqueue_t **dest, pqueue_t **src)
	Empty 'src' into 'dest'.
void *	pqueue_peek (pqueue_t *q)
void	pqueue_dump (pqueue_t *q, pqueue_print_entry_f print)
void	pqueue_print (pqueue_t *q, pqueue_print_entry_f print)
int	pqueue_is_valid (pqueue_t *q)

Macro Definition Documentation

LF_LEFT

#define LF_LEFT

(

i

)

Value:

((i) << 1)

LF_PARENT

#define LF_PARENT

(

i

)

Value:

((i) >> 1)

LF_RIGHT

#define LF_RIGHT

(

i

)

Value:

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

Function Documentation

find_equal_same_priority()

void * find_equal_same_priority	(	pqueue_t *	q,
		void *	e,
		int	pos )

pqueue_dump()

void pqueue_dump	(	pqueue_t *	q,
		pqueue_print_entry_f	print )

Dump the queue and it's internal structure.

pqueue_empty_into()

void pqueue_empty_into	(	pqueue_t **	dest,
		pqueue_t **	src )

Empty 'src' into 'dest'.

As an optimization, this function might swap 'src' and 'dest'.

Parameters

dest	The queue to fill up
src	The queue to empty

pqueue_find_equal_same_priority()

void * pqueue_find_equal_same_priority	(	pqueue_t *	q,
		void *	e )

Return an entry with the same priority (determined by cmppri) that matches the supplied entry (determined by eqelem) or NULL if there is no such entry.

Parameters

q	the queue
e	the entry to compare against

Returns

NULL if no matching event has been found, otherwise the entry

pqueue_find_same_priority()

void * pqueue_find_same_priority	(	pqueue_t *	q,
		void *	e )

Return an entry with the same priority as the specified entry or NULL if there is no such entry.

Parameters

q	the queue
e	the entry to compare against

Returns

NULL if no matching event has been found, otherwise the entry

pqueue_free()

void pqueue_free

(

pqueue_t *

q

)

free all memory used by the queue

Parameters

q

the queue

pqueue_init()

pqueue_t * pqueue_init	(	size_t	n,
		pqueue_cmp_pri_f	cmppri,
		pqueue_get_pri_f	getpri,
		pqueue_get_pos_f	getpos,
		pqueue_set_pos_f	setpos,
		pqueue_eq_elem_f	eqelem,
		pqueue_print_entry_f	prt )

Allocate and initialize a priority queue.

Parameters

n	the initial estimate of the number of queue items for which memory should be preallocated
cmppri	The callback function to run to compare two elements This callback should return -1 for 'lower', 0 for 'same', and 1 for 'higher', or vice versa if reverse priority is desired
getpri	the callback function to run to set a score to an element
getpos	the callback function to get the current element's position
setpos	the callback function to set the current element's position
eqelem	the callback function to check equivalence of entries
prt	the callback function to print an element

Returns

The handle or NULL for insufficent memory.

pqueue_insert()

int pqueue_insert	(	pqueue_t *	q,
		void *	d )

Insert an element into the queue.

Parameters

q	the queue
e	the element

Returns

0 on success

pqueue_is_valid()

int pqueue_is_valid

(

pqueue_t *

q

)

Check that the all entries are in the right order, etc.

pqueue_peek()

void * pqueue_peek

(

pqueue_t *

q

)

Access highest-ranking item without removing it.

Parameters

q

the queue

Returns

NULL on error, otherwise the entry

pqueue_pop()

void * pqueue_pop

(

pqueue_t *

q

)

Pop the highest-ranking item from the queue.

Parameters

q

the queue

Returns

NULL on error, otherwise the entry

pqueue_print()

void pqueue_print	(	pqueue_t *	q,
		pqueue_print_entry_f	print )

Print the contents of the queue.

Parameters

q	The queue.
print	The callback function to print the entry or NULL to use the default.

pqueue_remove()

int pqueue_remove	(	pqueue_t *	q,
		void *	e )

Remove an item from the queue.

Parameters

q	the queue
e	the entry

Returns

0 on success

pqueue_size()

size_t pqueue_size

(

pqueue_t *

q

)

return the size of the queue.

Parameters

q

the queue