Priority Queues


Overview

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.

Function Documentation

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

Parameters:
nitems maximum number of elements (at least 2) in queue
ppq the newly created u_u_pq_t object as a result argument
Return values:
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 
)
Parameters:
pq an u_pq_t object
pkey if non-NULL, it will store the priority of the top element
Returns:
the evicted element value
Note:
If performed on an empty queue the result is unpredictable.

Definition at line 226 of file srcs/toolbox/pqueue.c.

int u_pq_empty ( u_pq_t pq  ) 
Parameters:
pq queue handler
Returns:
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

Parameters:
pq a previously allocated u_pq_t object
Returns:
nothing

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  ) 
Parameters:
pq queue handler
Returns:
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 
)
Parameters:
pq an u_pq_t object
pkey if non-NULL, it will store the priority of the top element
Returns:
the element value
Note:
If performed on an empty queue the result is unpredictable.

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

Parameters:
pq an u_pq_t object
key the priority tag for ptr
val the element to be pushed into q
Return values:
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().


←Products
© 2005-2012 - KoanLogic S.r.l. - All rights reserved