gpqueue

gpqueue — Priority queue implemention

Synopsis

                    GPQueue;
typedef             GPQueueHandle;
                    GPQueueNode;
void                g_pqueue_clear                      (GPQueue *pqueue);
void                g_pqueue_foreach                    (GPQueue *pqueue,
                                                         GFunc func,
                                                         gpointer user_data);
void                g_pqueue_free                       (GPQueue *pqueue);
GPtrArray *         g_pqueue_get_array                  (GPQueue *pqueue);
gboolean            g_pqueue_is_empty                   (GPQueue *pqueue);
GPQueue *           g_pqueue_new                        (GCompareDataFunc compare_func,
                                                         gpointer *compare_userdata);
gpointer            g_pqueue_peek                       (GPQueue *pqueue);
gpointer            g_pqueue_pop                        (GPQueue *pqueue);
void                g_pqueue_priority_changed           (GPQueue *pqueue,
                                                         GPQueueHandle entry);
void                g_pqueue_priority_decreased         (GPQueue *pqueue,
                                                         GPQueueHandle entry);
GPQueueHandle       g_pqueue_push                       (GPQueue *pqueue,
                                                         gpointer data);
void                g_pqueue_remove                     (GPQueue *pqueue,
                                                         GPQueueHandle entry);

Description

The GPQueue structure and its associated functions provide a sorted collection of objects. Entries can be inserted in any order and at any time, and an entry's priority can be changed after it has been inserted into the queue. Entries are supposed to be removed one at a time in order of priority with g_pqueue_pop(), but deleting entries out of order is possible.

The entries cannot be iterated over in any way other than removing them one by one in order of priority, but when doing that, this structure is far more efficient than sorted lists or balanced trees, which on the other hand do not suffer from this restriction.

You will want to be very careful with calls that use GPQueueHandle. Handles immediately become invalid when an entry is removed from a GPQueue, but the current implementation cannot detect this and will do unfortunate things to undefined memory locations if you try to use an invalid handle.

Note

Internally, GPQueue currently uses a Fibonacci heap to store the entries. This implementation detail may change.

Details

GPQueue

typedef struct _GPQueue GPQueue;

An opaque structure representing a priority queue.

Since 2.x


GPQueueHandle

typedef GPQueueNode* GPQueueHandle;

An opaque value representing one entry in a GPQueue.

Since 2.x


GPQueueNode

typedef struct _GPQueueNode GPQueueNode;


g_pqueue_clear ()

void                g_pqueue_clear                      (GPQueue *pqueue);

Removes all entries from a pqueue.

pqueue :

a GPQueue.

Since 2.x


g_pqueue_foreach ()

void                g_pqueue_foreach                    (GPQueue *pqueue,
                                                         GFunc func,
                                                         gpointer user_data);

Calls func for each element in the pqueue passing user_data to the function.

pqueue :

 a GQueue.

func :

the function to call for each element's data

user_data :

user data to pass to func

Since 2.x


g_pqueue_free ()

void                g_pqueue_free                       (GPQueue *pqueue);

Deallocates the memory used by pqueue itself, but not any memory pointed to by the data pointers of its entries.

pqueue :

a GPQueue.

Since 2.x


g_pqueue_get_array ()

GPtrArray *         g_pqueue_get_array                  (GPQueue *pqueue);

Construct a GPtrArray for the items in pqueue. This can be useful when updating the priorities of all the elements in pqueue.

pqueue :

 a GQueue.

Returns :

A GPtrArray containing a pointer to each item in pqueue

Since 2.x


g_pqueue_is_empty ()

gboolean            g_pqueue_is_empty                   (GPQueue *pqueue);

Returns TRUE if the queue is empty.

pqueue :

a GPQueue.

Returns :

TRUE if the queue is empty.

Since 2.x


g_pqueue_new ()

GPQueue *           g_pqueue_new                        (GCompareDataFunc compare_func,
                                                         gpointer *compare_userdata);

Creates a new GPQueue.

compare_func :

the GCompareDataFunc used to sort the new priority queue. This function is passed two elements of the queue and should return 0 if they are equal, a negative value if the first comes before the second, and a positive value if the second comes before the first.

compare_userdata :

user data passed to compare_func

Returns :

a new GPQueue.

Since 2.x


g_pqueue_peek ()

gpointer            g_pqueue_peek                       (GPQueue *pqueue);

Returns the topmost entry's data pointer, or NULL if the queue is empty.

If you need to tell the difference between an empty queue and a queue that happens to have a NULL pointer at the top, check if the queue is empty first.

pqueue :

a GPQueue.

Returns :

the topmost entry's data pointer, or NULL if the queue is empty.

Since 2.x


g_pqueue_pop ()

gpointer            g_pqueue_pop                        (GPQueue *pqueue);

Removes the topmost entry from a GPQueue and returns its data pointer. Calling this on an empty GPQueue is not an error, but removes nothing and returns NULL.

If you need to tell the difference between an empty queue and a queue that happens to have a NULL pointer at the top, check if the queue is empty first.

pqueue :

a GPQueue.

Returns :

the topmost entry's data pointer, or NULL if the queue was empty.

Since 2.x


g_pqueue_priority_changed ()

void                g_pqueue_priority_changed           (GPQueue *pqueue,
                                                         GPQueueHandle entry);

Notifies the GPQueue that the priority of one entry has changed. The internal representation is updated accordingly.

Make sure that entry refers to an entry that is actually part of pqueue at the time, otherwise the behavior of this function is undefined (expect crashes).

Do not attempt to change the priorities of several entries at once. Every time a single object is changed, the GPQueue needs to be updated by calling g_pqueue_priority_changed() for that object.

pqueue :

a GPQueue.

entry :

a GPQueueHandle for an entry in pqueue.

Since 2.x


g_pqueue_priority_decreased ()

void                g_pqueue_priority_decreased         (GPQueue *pqueue,
                                                         GPQueueHandle entry);

Notifies the GPQueue that the priority of one entry has decreased.

This is a special case of g_pqueue_priority_changed(). If you are absolutely sure that the new priority of entry is lower than it was before, you may call this function instead of g_pqueue_priority_changed().

Note

In the current implementation, an expensive step in g_pqueue_priority_changed() can be skipped if the new priority is known to be lower, leading to an amortized running time of O(1) instead of O(log n). Of course, if the priority is not actually lower, behavior is undefined.

pqueue :

a GPQueue.

entry :

a GPQueueHandle for an entry in pqueue.

Since 2.x


g_pqueue_push ()

GPQueueHandle       g_pqueue_push                       (GPQueue *pqueue,
                                                         gpointer data);

Inserts a new entry into a GPQueue.

The returned handle can be used in calls to g_pqueue_remove() and g_pqueue_priority_changed(). Never make such calls for entries that have already been removed from the queue. The same data can be inserted into a GPQueue more than once, but remember that in this case, g_pqueue_priority_changed() needs to be called for every handle for that object if its priority changes.

pqueue :

a GPQueue.

data :

the object to insert into the priority queue.

Returns :

a handle for the freshly inserted entry.

Since 2.x


g_pqueue_remove ()

void                g_pqueue_remove                     (GPQueue *pqueue,
                                                         GPQueueHandle entry);

Removes one entry from a GPQueue.

Make sure that entry refers to an entry that is actually part of pqueue at the time, otherwise the behavior of this function is undefined (expect crashes).

pqueue :

a GPQueue.

entry :

a GPQueueHandle for an entry in pqueue.

Since 2.x