The Priority Queues module implements a fixed length priority queue using a heap. Elements (together with their associated numerical priority) are pushed to the queue via (u_pq_push) until free slots are available.
The top element can be evicted (u_pq_delmax) or just peeked at (u_pq_peekmax). Eviction and insertion are performed in O(lg(N)) where N is the queue cardinality.
The following example describes the use of a priority queue to efficiently extract the bottom 10 out of 10 million random values:
{ enum { EMAX = 10 }; size_t i; double key, keymax = DBL_MAX; u_pq_t *pq = NULL; srandom((unsigned long) getpid()); con_err_if (u_pq_create(EMAX, &pq)); // fill the pqueue for (i = 0; i < EMAX; i++) con_err_if (u_pq_push(pq, (double) random(), NULL)); // del-push cycle for (i = EMAX; i < 10000000; i++) { (void) u_pq_peekmax(pq, &keymax); if (keymax > (key = (double) random())) { (void) u_pq_delmax(pq, NULL); con_err_if (u_pq_push(pq, key, NULL)); } } // print results for (i = 0; !u_pq_empty(pq); i++) { (void) u_pq_delmax(pq, &key); u_con("%zu: %.0lf", EMAX - i, key); } }
Typedefs | |
typedef struct u_pq_s | u_pq_t |
The priority queue handler. | |
Functions | |
int | u_pq_create (size_t nitems, u_pq_t **ppq) |
Create a new priority queue. | |
int | u_pq_push (u_pq_t *pq, double key, const void *val) |
Push an element with the given priority. | |
void * | u_pq_delmax (u_pq_t *pq, double *pkey) |
Evict the top element from the supplied queue. | |
void * | u_pq_peekmax (u_pq_t *pq, double *pkey) |
Return the top element without evicting it. | |
int | u_pq_empty (u_pq_t *pq) |
Tell if a the supplied queue is empty. | |
int | u_pq_full (u_pq_t *pq) |
Tell if a the supplied queue is full. | |
void | u_pq_free (u_pq_t *pq) |
Dispose the queue. |
int u_pq_create | ( | size_t | nitems, | |
u_pq_t ** | ppq | |||
) |
Create a new u_u_pq_t object with nitems
elements and return its reference as a result value at *ppq
nitems | maximum number of elements (at least 2) in queue | |
ppq | the newly created u_u_pq_t object as a result argument |
0 | on success | |
~0 | on failure |
Definition at line 89 of file srcs/toolbox/pqueue.c.
References u_calloc(), u_pq_free(), and u_zalloc().
void * u_pq_delmax | ( | u_pq_t * | pq, | |
double * | pkey | |||
) |
pq | an u_pq_t object | |
pkey | if non-NULL, it will store the priority of the top element |
Definition at line 226 of file srcs/toolbox/pqueue.c.
int u_pq_empty | ( | u_pq_t * | pq | ) |
pq | queue handler |
0
when there is some element in pq
, non-zero otherwise. Definition at line 120 of file srcs/toolbox/pqueue.c.
void u_pq_free | ( | u_pq_t * | pq | ) |
Dispose the supplied u_pq_t object q
pq | a previously allocated u_pq_t object |
Definition at line 146 of file srcs/toolbox/pqueue.c.
References u_free().
Referenced by u_pq_create().
int u_pq_full | ( | u_pq_t * | pq | ) |
pq | queue handler |
0
when there is no room left in pq
, non-zero otherwise. Definition at line 132 of file srcs/toolbox/pqueue.c.
Referenced by u_pq_push().
void * u_pq_peekmax | ( | u_pq_t * | pq, | |
double * | pkey | |||
) |
pq | an u_pq_t object | |
pkey | if non-NULL, it will store the priority of the top element |
Definition at line 206 of file srcs/toolbox/pqueue.c.
int u_pq_push | ( | u_pq_t * | pq, | |
double | key, | |||
const void * | val | |||
) |
Push the element val
into the u_pq_t object pq
with the given priority key
pq | an u_pq_t object | |
key | the priority tag for ptr | |
val | the element to be pushed into q |
0 | on success | |
-1 | on failure | |
-2 | if the insertion can't proceed because the queue is full |
Definition at line 171 of file srcs/toolbox/pqueue.c.
References u_pq_full().