pqueue_base.h File Reference

#include <stddef.h>

Go to the source code of this file.

Data Structures
struct	pqueue_t

Typedefs
typedef unsigned long long	pqueue_pri_t
typedef pqueue_pri_t(*	pqueue_get_pri_f) (void *a)
typedef int(*	pqueue_cmp_pri_f) (pqueue_pri_t next, pqueue_pri_t curr)
typedef int(*	pqueue_eq_elem_f) (void *next, void *curr)
typedef size_t(*	pqueue_get_pos_f) (void *a)
typedef void(*	pqueue_set_pos_f) (void *a, size_t pos)
typedef void(*	pqueue_print_entry_f) (void *a)
typedef struct pqueue_t	pqueue_t

Functions
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)
int	pqueue_insert (pqueue_t *q, void *d)
void	pqueue_change_priority (pqueue_t *q, pqueue_pri_t new_pri, void *d)
void *	pqueue_pop (pqueue_t *q)
void	pqueue_empty_into (pqueue_t **dest, pqueue_t **src)
	Empty 'src' into 'dest'.
void *	pqueue_find_same_priority (pqueue_t *q, void *e)
void *	pqueue_find_equal_same_priority (pqueue_t *q, void *e)
int	pqueue_remove (pqueue_t *q, void *e)
void *	pqueue_peek (pqueue_t *q)
void	pqueue_print (pqueue_t *q, pqueue_print_entry_f print)
void	pqueue_dump (pqueue_t *q, pqueue_print_entry_f print)
int	pqueue_is_valid (pqueue_t *q)

Typedef Documentation

pqueue_cmp_pri_f

typedef int(* pqueue_cmp_pri_f) (pqueue_pri_t next, pqueue_pri_t curr)

Callback to compare two priorities.

pqueue_eq_elem_f

typedef int(* pqueue_eq_elem_f) (void *next, void *curr)

Callback to determine whether two elements are equivalent.

pqueue_get_pos_f

typedef size_t(* pqueue_get_pos_f) (void *a)

Callback functions to get the position of an element.

pqueue_get_pri_f

typedef pqueue_pri_t(* pqueue_get_pri_f) (void *a)

Callback to get the priority of an element.

pqueue_pri_t

typedef unsigned long long pqueue_pri_t

Priority data type.

pqueue_print_entry_f

typedef void(* pqueue_print_entry_f) (void *a)

Debug callback function to print a entry.

pqueue_set_pos_f

typedef void(* pqueue_set_pos_f) (void *a, size_t pos)

Callback functions to set the position of an element.

pqueue_t

typedef struct pqueue_t pqueue_t

The priority queue handle.

Function Documentation

pqueue_change_priority()

void pqueue_change_priority	(	pqueue_t *	q,
		pqueue_pri_t	new_pri,
		void *	d )

Move an existing entry to a different priority.

Parameters

q	the queue
new_pri	the new priority
d	the entry

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