pqueue_tag.h File Reference

Priority queue that uses tags for sorting. More...

#include "pqueue_base.h"
#include "tag.h"

Go to the source code of this file.

Data Structures
struct	pqueue_tag_element_t
	The type for an element in a priority queue that is sorted by tag. More...

Typedefs
typedef pqueue_t	pqueue_tag_t
	Type of a priority queue sorted by tags.

Functions
int	pqueue_tag_compare (pqueue_pri_t priority1, pqueue_pri_t priority2)
	Callback comparison function for the tag-based priority queue. Return -1 if the first argument is less than second, 0 if the two arguments are the same, and 1 otherwise. This function is of type pqueue_cmp_pri_f.
pqueue_tag_t *	pqueue_tag_init (size_t initial_size)
	Create a priority queue sorted by tags.
pqueue_tag_t *	pqueue_tag_init_customize (size_t initial_size, pqueue_cmp_pri_f cmppri, pqueue_eq_elem_f eqelem, pqueue_print_entry_f prt)
	Create a priority queue that stores elements with a particular payload.
void	pqueue_tag_free (pqueue_tag_t *q)
	Free all memory used by the queue including elements that are marked dynamic.
size_t	pqueue_tag_size (pqueue_tag_t *q)
	Return the size of the queue.
int	pqueue_tag_insert (pqueue_tag_t *q, pqueue_tag_element_t *d)
	Insert an element into the queue.
int	pqueue_tag_insert_tag (pqueue_tag_t *q, tag_t t)
	Insert a tag into the queue.
int	pqueue_tag_insert_if_no_match (pqueue_tag_t *q, tag_t t)
	Insert a tag into the queue if the tag is not already in the queue.
pqueue_tag_element_t *	pqueue_tag_find_with_tag (pqueue_tag_t *q, tag_t t)
	Return the first item with the specified tag or NULL if there is none.
pqueue_tag_element_t *	pqueue_tag_find_equal_same_tag (pqueue_tag_t *q, pqueue_tag_element_t *e)
	Return an item with the same tag (cmppri returns 0) that matches the supplied element (eqelem returns non-zero) or NULL if there is none.
pqueue_tag_element_t *	pqueue_tag_peek (pqueue_tag_t *q)
	Return highest-ranking item (the one with the least tag) without removing it.
tag_t	pqueue_tag_peek_tag (pqueue_tag_t *q)
	Return the least tag in the queue or FOREVER if the queue is empty.
pqueue_tag_element_t *	pqueue_tag_pop (pqueue_tag_t *q)
	Pop the least-tag element from the queue.
tag_t	pqueue_tag_pop_tag (pqueue_tag_t *q)
	Pop the least-tag element from the queue and return its tag.
void	pqueue_tag_remove (pqueue_tag_t *q, pqueue_tag_element_t *e)
	Remove an item from the queue.
void	pqueue_tag_remove_up_to (pqueue_tag_t *q, tag_t t)
	Remove items from the queue with tags up to and including the specified tag.
void	pqueue_tag_dump (pqueue_tag_t *q)

Detailed Description

Priority queue that uses tags for sorting.

Author

Byeonggil Jun

Edward A. Lee

Copyright

(c) 2023, The University of California at Berkeley License in BSD 2-clause

This file extends the pqueue infrastructure with support for queues that are sorted by tag instead of by a long long. Elements in this queue are structs of type pqueue_tag_element_t or a derived struct, as explained below. What you put onto the queue is a pointer to a tagged_element_t struct. That pointer, when cast to pqueue_pri_t, an alias for long long, also serves as the "priority" for the queue.

Typedef Documentation

pqueue_tag_t

typedef pqueue_t pqueue_tag_t

Type of a priority queue sorted by tags.

Function Documentation

pqueue_tag_compare()

int pqueue_tag_compare	(	pqueue_pri_t	priority1,
		pqueue_pri_t	priority2 )

Callback comparison function for the tag-based priority queue. Return -1 if the first argument is less than second, 0 if the two arguments are the same, and 1 otherwise. This function is of type pqueue_cmp_pri_f.

Parameters

priority1	A pointer to a pqueue_tag_element_t, cast to pqueue_pri_t.
priority2	A pointer to a pqueue_tag_element_t, cast to pqueue_pri_t.

pqueue_tag_dump()

void pqueue_tag_dump

(

pqueue_tag_t *

q

)

Dump the queue and it's internal structure.

pqueue_tag_find_equal_same_tag()

pqueue_tag_element_t * pqueue_tag_find_equal_same_tag	(	pqueue_tag_t *	q,
		pqueue_tag_element_t *	e )

Return an item with the same tag (cmppri returns 0) that matches the supplied element (eqelem returns non-zero) or NULL if there is none.

Parameters

q	The queue.
e	The element.

Returns

An entry with the specified tag or NULL if there isn't one.

pqueue_tag_find_with_tag()

pqueue_tag_element_t * pqueue_tag_find_with_tag	(	pqueue_tag_t *	q,
		tag_t	t )

Return the first item with the specified tag or NULL if there is none.

Parameters

q	The queue.
t	The tag.

Returns

An entry with the specified tag or NULL if there isn't one.

pqueue_tag_free()

void pqueue_tag_free

(

pqueue_tag_t *

q

)

Free all memory used by the queue including elements that are marked dynamic.

Parameters

q	The queue.

pqueue_tag_init()

pqueue_tag_t * pqueue_tag_init

(

size_t

initial_size

)

Create a priority queue sorted by tags.

The elements of the priority queue will be of type pqueue_tag_element_t. The caller should call pqueue_tag_free() when finished with the queue.

Returns

A dynamically allocated priority queue or NULL if memory allocation fails.

pqueue_tag_init_customize()

pqueue_tag_t * pqueue_tag_init_customize	(	size_t	initial_size,
		pqueue_cmp_pri_f	cmppri,
		pqueue_eq_elem_f	eqelem,
		pqueue_print_entry_f	prt )

Create a priority queue that stores elements with a particular payload.

Parameters

cmppri	the callback function to compare priorities
eqelem	the callback function to check equivalence of payloads.
prt	the callback function to print elements

The elements of the priority queue will be of type pqueue_tag_element_t. The caller should call pqueue_tag_free() when finished with the queue.

Returns

A dynamically allocated priority queue or NULL if memory allocation fails.

pqueue_tag_insert()

int pqueue_tag_insert	(	pqueue_tag_t *	q,
		pqueue_tag_element_t *	d )

Insert an element into the queue.

Parameters

q	The queue.
e	The element to insert.

Returns

0 on success

pqueue_tag_insert_if_no_match()

int pqueue_tag_insert_if_no_match	(	pqueue_tag_t *	q,
		tag_t	t )

Insert a tag into the queue if the tag is not already in the queue.

This automatically creates a dynamically allocated element in the queue and ensures that if the element is still on the queue when pqueue_tag_free is called, then that memory will be freed.

Parameters

q	The queue.
t	The tag to insert.

Returns

0 on success, 1 otherwise.

pqueue_tag_insert_tag()

int pqueue_tag_insert_tag	(	pqueue_tag_t *	q,
		tag_t	t )

Insert a tag into the queue.

This automatically creates a dynamically allocated element in the queue and ensures that if the element is still on the queue when pqueue_tag_free is called, then that memory will be freed.

Parameters

q	The queue.
t	The tag to insert.

Returns

0 on success

pqueue_tag_peek()

pqueue_tag_element_t * pqueue_tag_peek

(

pqueue_tag_t *

q

)

Return highest-ranking item (the one with the least tag) without removing it.

Parameters

q	The queue.

Returns

NULL on if the queue is empty, otherwise the entry.

pqueue_tag_peek_tag()

tag_t pqueue_tag_peek_tag

(

pqueue_tag_t *

q

)

Return the least tag in the queue or FOREVER if the queue is empty.

Parameters

q	The queue.

Returns

The least tag in the queue or FOREVER if the queue is empty.

pqueue_tag_pop()

pqueue_tag_element_t * pqueue_tag_pop

(

pqueue_tag_t *

q

)

Pop the least-tag element from the queue.

If the entry was dynamically allocated, then it is now up to the caller to ensure that it is freed. It will not be freed by pqueue_tag_free.

Parameters

q	The queue.

Returns

NULL on error, otherwise the entry

pqueue_tag_pop_tag()

tag_t pqueue_tag_pop_tag

(

pqueue_tag_t *

q

)

Pop the least-tag element from the queue and return its tag.

If the queue is empty, return FOREVER_TAG. This function handles freeing the element struct if it was dynamically allocated.

Parameters

q	The queue.

Returns

NULL on error, otherwise the entry

pqueue_tag_remove()

void pqueue_tag_remove	(	pqueue_tag_t *	q,
		pqueue_tag_element_t *	e )

Remove an item from the queue.

Parameters

q	The queue.
e	The entry to remove.

pqueue_tag_remove_up_to()

void pqueue_tag_remove_up_to	(	pqueue_tag_t *	q,
		tag_t	t )

Remove items from the queue with tags up to and including the specified tag.

If the specified tag is FOREVER_TAG, then all items will be removed.

Parameters

q	The queue.
t	The specified tag.

pqueue_tag_size()

size_t pqueue_tag_size

(

pqueue_tag_t *

q

)

Return the size of the queue.

Parameters

q	The queue.