Re: High-performance Priority Queue / Heap for glib

[Maik Zumstrull <maik zumstrull rz uni-karlsruhe de>]

Maik Zumstrull wrote:

> Behdad Esfahbod wrote:

> > I agree that having a priority queue in glib would be useful.
> > However, the API should use an opaque structure and be agnostic of
> > the actual implementation.
> 
> I'm going to rethink the API and package the thing as a patch against
> 2.19.10 sources. Maybe the discussion will pick up a little when
> there's actual code on the table. Thanks for the feedback so far.

Okay, here it is. I haven't extensively tested this for correctness or
performance yet, but it basically works. The API is documented and
should allow different implementations, I think. It's similar to what I
suggested before, but I dropped merge(). I'm not sure every kind of
underlying implementation could provide that efficiently. Also,
priority queues and single entries of priority queues are syntactically
different types now, but in reality the same thing with my
implementation.

% diffstat glib-2.19.10-priorityqueue.diff 
 docs/reference/glib/glib-docs.sgml            |    2 
 docs/reference/glib/glib-sections.txt         |   17 
 docs/reference/glib/tmpl/priority_queues.sgml |  156 +++++++++
 glib/Makefile.am                              |    1 
 glib/glib.h                                   |    1 
 glib/glib.symbols                             |   14 
 glib/gpqueue.c                                |  445 ++++++++++++++++++++++++++
 glib/gpqueue.h                                |   63 +++
 tests/Makefile.am                             |    2 
 tests/priorityqueue-test.c                    |  170 +++++++++
 10 files changed, 871 insertions(+)

It applies to glib-2.19.10, and building with
./autogen.sh --enable-gtk-doc && make && make check
seems to work fine. I hope I've integrated it into the build system
correctly in all places.

Please review.


Thanks,

Maik Zumstrull

diff -X diffignore -ruN glib-2.19.10/docs/reference/glib/glib-docs.sgml glib-2.19.10.local/docs/reference/glib/glib-docs.sgml
--- glib-2.19.10/docs/reference/glib/glib-docs.sgml	2009-03-02 07:02:41.000000000 +0100
+++ glib-2.19.10.local/docs/reference/glib/glib-docs.sgml	2009-03-09 18:16:35.804036418 +0100
@@ -36,6 +36,7 @@
 <!ENTITY glib-Doubly-Linked-Lists SYSTEM "xml/linked_lists_double.xml">
 <!ENTITY glib-Singly-Linked-Lists SYSTEM "xml/linked_lists_single.xml">
 <!ENTITY glib-Double-ended-Queues SYSTEM "xml/queue.xml">
+<!ENTITY glib-Priority-Queues SYSTEM "xml/priority_queues.xml">
 <!ENTITY glib-Sequences SYSTEM "xml/sequence.xml">
 <!ENTITY glib-Trash-Stacks SYSTEM "xml/trash_stack.xml">
 <!ENTITY glib-Hash-Tables SYSTEM "xml/hash_tables.xml">
@@ -180,6 +181,7 @@
     &glib-Doubly-Linked-Lists;
     &glib-Singly-Linked-Lists;
     &glib-Double-ended-Queues;
+    &glib-Priority-Queues;
     &glib-Sequences;
     &glib-Trash-Stacks;
     &glib-Hash-Tables;
diff -X diffignore -ruN glib-2.19.10/docs/reference/glib/glib-sections.txt glib-2.19.10.local/docs/reference/glib/glib-sections.txt
--- glib-2.19.10/docs/reference/glib/glib-sections.txt	2009-03-02 07:19:08.000000000 +0100
+++ glib-2.19.10.local/docs/reference/glib/glib-sections.txt	2009-03-09 18:11:23.308036369 +0100
@@ -1939,6 +1939,23 @@
 </SECTION>
 
 <SECTION>
+<TITLE>Priority Queues</TITLE>
+<FILE>priority_queues</FILE>
+
+GPQueue
+GPQueueHandle
+g_pqueue_insert
+g_pqueue_top
+g_pqueue_top_extended
+g_pqueue_delete_top
+g_pqueue_pop
+g_pqueue_pop_extended
+g_pqueue_delete
+g_pqueue_change_priority
+g_pqueue_destroy
+</SECTION>
+
+<SECTION>
 <TITLE>Sequences</TITLE>
 <FILE>sequence</FILE>
 
diff -X diffignore -ruN glib-2.19.10/docs/reference/glib/tmpl/priority_queues.sgml glib-2.19.10.local/docs/reference/glib/tmpl/priority_queues.sgml
--- glib-2.19.10/docs/reference/glib/tmpl/priority_queues.sgml	1970-01-01 01:00:00.000000000 +0100
+++ glib-2.19.10.local/docs/reference/glib/tmpl/priority_queues.sgml	2009-03-10 15:53:51.431915573 +0100
@@ -0,0 +1,156 @@
+<!-- ##### SECTION Title ##### -->
+Priority Queues
+
+<!-- ##### SECTION Short_Description ##### -->
+a collection of data entries with associated priority values that returns
+entries one by one in order of priority
+
+<!-- ##### SECTION Long_Description ##### -->
+<para>
+The #GPQueue structure and its associated functions provide a sorted collection
+of data/priority pairs. 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. Any entry can be deleted at any time if you still have its
+#GPQueueHandle, but entries are supposed to be removed one at a time in order
+of priority with g_pqueue_pop().
+</para>
+<para>
+The entries <emphasis>cannot</emphasis> 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.
+</para>
+<para>
+Most of the functions for #GPQueue work like #GList functions, that is,
+you assign the result to your queue variable, and the
+exception to the rule are g_pqueue_pop() and g_pqueue_pop_extended(),
+which take a pointer to your queue variable instead:
+<informalexample><programlisting>
+GPQueue *q = NULL; /* Empty queue */
+...
+q = g_pqueue_do_something(q, ...);
+...
+gpointer data = g_pqueue_pop(&amp;q);
+...
+g_pqueue_destroy(q);
+</programlisting></informalexample>
+</para>
+<para>
+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.
+Avoid calls to g_pqueue_delete() and g_pqueue_change_priority() if you can,
+and if you need them, make sure to keep track of your handles' validity.
+</para>
+
+<!-- ##### SECTION See_Also ##### -->
+<para>
+
+</para>
+
+<!-- ##### SECTION Stability_Level ##### -->
+
+
+<!-- ##### STRUCT GPQueue ##### -->
+<para>
+
+</para>
+
+
+<!-- ##### TYPEDEF GPQueueHandle ##### -->
+<para>
+
+</para>
+
+
+<!-- ##### FUNCTION g_pqueue_insert ##### -->
+<para>
+
+</para>
+
+ pqueue: 
+ data: 
+ priority: 
+ handle: 
+ Returns: 
+
+
+<!-- ##### FUNCTION g_pqueue_top ##### -->
+<para>
+
+</para>
+
+ pqueue: 
+ Returns: 
+
+
+<!-- ##### FUNCTION g_pqueue_top_extended ##### -->
+<para>
+
+</para>
+
+ pqueue: 
+ data: 
+ priority: 
+ Returns: 
+
+
+<!-- ##### FUNCTION g_pqueue_delete_top ##### -->
+<para>
+
+</para>
+
+ pqueue: 
+ Returns: 
+
+
+<!-- ##### FUNCTION g_pqueue_pop ##### -->
+<para>
+
+</para>
+
+ pqueue: 
+ Returns: 
+
+
+<!-- ##### FUNCTION g_pqueue_pop_extended ##### -->
+<para>
+
+</para>
+
+ pqueue: 
+ data: 
+ priority: 
+ Returns: 
+
+
+<!-- ##### FUNCTION g_pqueue_delete ##### -->
+<para>
+
+</para>
+
+ pqueue: 
+ entry: 
+ Returns: 
+
+
+<!-- ##### FUNCTION g_pqueue_change_priority ##### -->
+<para>
+
+</para>
+
+ pqueue: 
+ entry: 
+ priority: 
+ Returns: 
+
+
+<!-- ##### FUNCTION g_pqueue_destroy ##### -->
+<para>
+
+</para>
+
+ pqueue: 
+
+
diff -X diffignore -ruN glib-2.19.10/glib/glib.h glib-2.19.10.local/glib/glib.h
--- glib-2.19.10/glib/glib.h	2009-03-02 07:02:42.000000000 +0100
+++ glib-2.19.10.local/glib/glib.h	2009-03-09 14:32:20.136037017 +0100
@@ -61,6 +61,7 @@
 #include <glib/gpattern.h>
 #include <glib/gpoll.h>
 #include <glib/gprimes.h>
+#include <glib/gpqueue.h>
 #include <glib/gqsort.h>
 #include <glib/gquark.h>
 #include <glib/gqueue.h>
diff -X diffignore -ruN glib-2.19.10/glib/glib.symbols glib-2.19.10.local/glib/glib.symbols
--- glib-2.19.10/glib/glib.symbols	2009-03-02 07:02:42.000000000 +0100
+++ glib-2.19.10.local/glib/glib.symbols	2009-03-10 15:25:47.439914916 +0100
@@ -852,6 +852,20 @@
 #endif
 #endif
 
+#if IN_HEADER(__G_PQUEUE_H__)
+#if IN_FILE(__G_PQUEUE_C__)
+g_pqueue_change_priority
+g_pqueue_delete
+g_pqueue_delete_top
+g_pqueue_destroy
+g_pqueue_insert
+g_pqueue_pop
+g_pqueue_pop_extended
+g_pqueue_top
+g_pqueue_top_extended
+#endif
+#endif
+
 #if IN_HEADER(__G_PRIMES_H__)
 #if IN_FILE(__G_PRIMES_C__)
 g_spaced_primes_closest G_GNUC_CONST
diff -X diffignore -ruN glib-2.19.10/glib/gpqueue.c glib-2.19.10.local/glib/gpqueue.c
--- glib-2.19.10/glib/gpqueue.c	1970-01-01 01:00:00.000000000 +0100
+++ glib-2.19.10.local/glib/gpqueue.c	2009-03-10 19:43:28.150914142 +0100
@@ -0,0 +1,445 @@
+#include "config.h"
+#include "glib.h"
+#include "galias.h"
+
+struct _GPQueue {
+	struct _GPQueue *next;
+	struct _GPQueue *prev;
+	struct _GPQueue *parent;
+	struct _GPQueue *child;
+
+	gpointer data;
+	gint priority;
+	gint degree;
+	gboolean marked;
+};
+
+/*
+static void
+structure_dump (GPQueue *pqueue, gint indent)
+{
+	if (pqueue == NULL) return;
+	g_debug("%*s%p %d", indent, "", pqueue, pqueue->priority);
+	structure_dump(pqueue->child, indent + 2);
+	pqueue->prev->next = NULL;
+	structure_dump(pqueue->next, indent);
+	pqueue->prev->next = pqueue;
+}
+*/
+
+static inline void
+g_pqueue_remove (GPQueue *src)
+{
+	src->prev->next = src->next;
+	src->next->prev = src->prev;
+	src->next = src;
+	src->prev = src;
+}
+
+static inline void
+g_pqueue_insert_before (GPQueue *dest, GPQueue *src)
+{
+	GPQueue *prev = dest->prev;
+	dest->prev = src->prev;
+	src->prev->next = dest;
+	src->prev = prev;
+	prev->next = src;
+}
+
+static inline void
+g_pqueue_insert_after (GPQueue *dest, GPQueue *src)
+{
+	GPQueue *next = dest->next;
+	dest->next = src;
+	src->prev->next = next;
+	next->prev = src->prev;
+	src->prev = dest;
+}
+
+ /**
+  * g_pqueue_insert:
+  * @pqueue: an existing GPQueue or %NULL to begin with an empty queue.
+  * @data: a pointer to something associated with this queue entry.
+  *   %NULL or the use of GINT_TO_POINTER() is acceptable. The same @data can
+  *   be inserted into a GPQueue more than once, with different or identical
+  *   priorities.
+  * @priority: the priority for this entry. Entries are returned from the queue
+  *   in <emphasis>ascending</emphasis> order of priority.
+  * @handle: if not %NULL, a handle for the freshly inserted entry
+  *   will be returned into this. This handle can be used in calls to
+  *   g_pqueue_delete() and g_pqueue_change_priority(). Never make such calls
+  *   for entries that have already been removed from the queue.
+  * 
+  * Inserts a new entry into a #GPQueue.
+  * 
+  * Return value: The altered priority queue.
+  **/
+GPQueue*
+g_pqueue_insert (GPQueue *pqueue, gpointer data, gint priority, GPQueueHandle *handle)
+{
+	GPQueue *e = g_slice_new(GPQueue);
+
+	e->next = e;
+	e->prev = e;
+	e->parent = NULL;
+	e->child = NULL;
+	e->data = data;
+	e->priority = priority;
+	e->degree = 0;
+	e->marked = FALSE;
+
+	if (handle != NULL) *handle = e;
+
+	if (pqueue != NULL) {
+		g_pqueue_insert_before(pqueue, e);
+		if (e->priority < pqueue->priority)
+			return e;
+		else
+			return pqueue;
+	} else {
+		return e;
+	}
+}
+
+/**
+ * g_pqueue_top:
+ * @pqueue: a #GPQueue.
+ * 
+ * Returns the topmost entry's data pointer.
+ * 
+ * If you need to tell the difference between an empty queue and a queue
+ * that happens to have a %NULL pointer at the top, use g_pqueue_top_extended()
+ * or check if the queue is empty first.
+ * 
+ * Return value: the topmost entry's data pointer.
+ **/
+gpointer
+g_pqueue_top (GPQueue *pqueue)
+{
+	return (pqueue != NULL) ? (pqueue->data) : (NULL);
+}
+
+/**
+ * g_pqueue_top_extended:
+ * @pqueue: a #GPQueue.
+ * @data: where to write the data pointer.
+ * @priority: where to write the priority value.
+ * 
+ * If the queue is empty, writes %NULL into * data if @data is not %NULL
+ * and returns %FALSE.
+ * 
+ * If the queue is not empty, writes the topmost entry's data pointer
+ * and priority value into * data and * priority unless they are %NULL
+ * and returns %TRUE.
+ * 
+ * Return value: %TRUE if the queue is not empty, %FALSE if it is.
+ **/
+gboolean
+g_pqueue_top_extended (GPQueue *pqueue, gpointer *data, gint *priority)
+{
+	if (pqueue == NULL) {
+		if (data != NULL) *data = NULL;
+		return FALSE;
+	} else {
+		if (data != NULL) *data = pqueue->data;
+		if (priority != NULL) *priority = pqueue->priority;
+		return TRUE;
+	}
+}
+
+static GPQueue*
+g_pqueue_make_child (GPQueue *a, GPQueue *b)
+{
+	g_pqueue_remove(b);
+	if (a->child != NULL) {
+		g_pqueue_insert_before(a->child, b);
+		a->degree += 1;
+	} else {
+		a->child = b;
+		a->degree = 1;
+	}
+	b->parent = a;
+	return a;
+}
+
+static inline GPQueue*
+g_pqueue_join_trees (GPQueue *a, GPQueue *b)
+{
+	if (b->priority < a->priority)
+		return g_pqueue_make_child(b, a);
+	return g_pqueue_make_child(a, b);
+}
+
+static GPQueue*
+g_pqueue_fix_rootlist (GPQueue* pqueue)
+{
+	/* We need to iterate over the circular list we are given and do
+	 * several things:
+	 * - Make sure all the elements are unmarked
+	 * - Make sure to return the element in the list with smallest
+	 *   priority value
+	 * - Find elements of identical degree and join them into trees
+	 * The last point is irrelevant for correctness, but essential
+	 * for performance. If we did not do this, our data structure would
+	 * degrade into an unsorted linked list.
+	 */
+
+	const gsize degnode_size = (8 * sizeof(gpointer) + 1) * sizeof(gpointer);
+	GPQueue **degnode = g_slice_alloc0(degnode_size);
+
+	GPQueue sentinel;
+	sentinel.next = &sentinel;
+	sentinel.prev = &sentinel;
+	g_pqueue_insert_before(pqueue, &sentinel);
+
+	GPQueue *current = pqueue;
+	while (current != &sentinel) {
+		current->marked = FALSE;
+		current->parent = NULL;
+		gint d = current->degree;
+		if (degnode[d] == NULL) {
+			degnode[d] = current;
+			current = current->next;
+		} else {
+			if (degnode[d] != current) {
+				current = g_pqueue_join_trees(degnode[d], current);
+				degnode[d] = NULL;
+			} else {
+				current = current->next;
+			}
+		}
+	}
+
+	current = sentinel.next;
+	GPQueue *minimum = current;
+	while (current != &sentinel) {
+		if (current->priority < minimum->priority) minimum = current;
+		current = current->next;
+	}
+
+	g_pqueue_remove(&sentinel);
+
+	g_slice_free1(degnode_size, degnode);
+
+	return minimum;
+}
+
+static GPQueue*
+g_pqueue_delete_root (GPQueue *pqueue, GPQueue *root)
+{
+	/* Step one:
+	 * If root has any children, pull them up to root level.
+	 * At this time, we only deal with their next/prev pointers,
+	 * further changes are made later in g_pqueue_fix_rootlist().
+	 */
+	if (root->child) {
+		g_pqueue_insert_after(root, root->child);
+		root->child = NULL;
+		root->degree = 0;
+	}
+
+	/* Step two:
+	 * Cut root out of the list.
+	 */
+	if (root->next != root) {
+		pqueue = root->next;
+		g_pqueue_remove(root);
+		/* Step three:
+		 * Clean up the remaining list.
+		 */
+		pqueue = g_pqueue_fix_rootlist(pqueue);
+	} else {
+		pqueue = NULL;
+	}
+
+	g_slice_free(GPQueue, root);
+	return pqueue;
+}
+
+/**
+ * g_pqueue_delete_top:
+ * @pqueue: a #GPQueue.
+ * 
+ * Deletes the topmost entry from a #GPQueue and returns the altered queue.
+ * 
+ * Return value: the altered #GPQueue.
+ **/
+GPQueue*
+g_pqueue_delete_top (GPQueue *pqueue)
+{
+	if (pqueue == NULL) return NULL;
+	return g_pqueue_delete_root(pqueue, pqueue);
+}
+
+/**
+ * g_pqueue_pop:
+ * @pqueue: a <emphasis>pointer</emphasis> to a #GPQueue.
+ * 
+ * Deletes the topmost entry from a #GPQueue and returns its data pointer.
+ * The altered queue is written back to * pqueue 
+ * 
+ * If you also need to know the elements priority value or be able to tell
+ * the difference between an empty #GPQueue and one that happens to have an
+ * entry with a %NULL data pointer at the top, use g_pqueue_pop_extended()
+ * instead.
+ * 
+ * Return value: the topmost entry's data pointer.
+ **/
+gpointer
+g_pqueue_pop (GPQueue **pqueue)
+{
+	if (*pqueue == NULL) return NULL;
+	gpointer data = (*pqueue)->data;
+	*pqueue = g_pqueue_delete_root(*pqueue, *pqueue);
+	return data;
+}
+
+/**
+ * g_pqueue_pop_extended:
+ * @pqueue: a <emphasis>pointer to a</emphasis> #GPQueue.
+ * @data: unless this is %NULL, the topmost entry's data pointer or %NULL
+ *   will be written here.
+ * @priority: if this is not %NULL and the queue is not empty, the topmost
+ *   entry's priority value will be written here.
+ * 
+ * Deletes the topmost entry from a #GPQueue and returns (by reference) both
+ * its data pointer and its priority value.
+ * The altered queue is written back to * pqueue 
+ * 
+ * Return value: %TRUE if the queue was not empty, %FALSE if it was.
+ **/
+gboolean
+g_pqueue_pop_extended (GPQueue **pqueue, gpointer *data, gint *priority)
+{
+	if (*pqueue == NULL) {
+		if (data != NULL) *data = NULL;
+		return FALSE;
+	}
+
+	if (data != NULL) *data = (*pqueue)->data;
+	if (priority != NULL) *priority = (*pqueue)->priority;
+	*pqueue = g_pqueue_delete_top(*pqueue);
+	return TRUE;
+}
+
+static inline GPQueue*
+g_pqueue_make_root (GPQueue *pqueue, GPQueue *entry)
+{
+	GPQueue *parent = entry->parent;
+	entry->parent = NULL;
+	entry->marked = FALSE;
+	if (parent != NULL) {
+		if (entry->next != entry) {
+			if (parent->child == entry) parent->child = entry->next;
+			g_pqueue_remove(entry);
+			parent->degree -= 1;
+		} else {
+			parent->child = NULL;
+			parent->degree = 0;
+		}
+		g_pqueue_insert_before(pqueue, entry);
+	}
+	if (entry->priority < pqueue->priority) return entry;
+	else return pqueue;
+}
+
+static GPQueue*
+g_pqueue_cut_tree (GPQueue *pqueue, GPQueue *entry)
+{
+	GPQueue *current = entry;
+	while ((current != NULL) && (current->parent != NULL)) {
+		GPQueue *parent = current->parent;
+		pqueue = g_pqueue_make_root(pqueue, entry);
+		if (parent->marked) {
+			current = parent;
+		} else {
+			parent->marked = TRUE;
+			current = NULL;
+		}
+	}
+	if (entry->priority < pqueue->priority) return entry;
+	else return pqueue;
+}
+
+/**
+ * g_pqueue_delete:
+ * @pqueue: a #GPQueue.
+ * @entry: a #GPQueueHandle for an entry in @pqueue.
+ * 
+ * Deletes one entry in a #GPQueue and returns the altered queue.
+ * 
+ * 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).
+ * 
+ * Return value: the altered #GPQueue.
+ **/
+GPQueue*
+g_pqueue_delete (GPQueue* pqueue, GPQueueHandle entry)
+{
+	pqueue = g_pqueue_cut_tree(pqueue, entry);
+	pqueue = g_pqueue_delete_root(pqueue, entry);
+	return pqueue;
+}
+
+/**
+ * g_pqueue_change_priority:
+ * @pqueue: a #GPQueue.
+ * @entry: a #GPQueueHandle for an entry in @pqueue.
+ * @priority: the new priority value for @entry.
+ * 
+ * Changes the priority of one entry in a #GPQueue
+ * and returns the altered queue.
+ * 
+ * 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).
+ * 
+ * Return value: the altered #GPQueue.
+ **/
+GPQueue*
+g_pqueue_change_priority (GPQueue* pqueue, GPQueueHandle entry, gint priority)
+{
+	if (entry->priority == priority) return pqueue;
+
+	gint oldpriority = entry->priority;
+	entry->priority = priority;
+
+	pqueue = g_pqueue_cut_tree(pqueue, entry);
+
+	if (priority > oldpriority) {
+		if (entry->child) {
+			g_pqueue_insert_after(entry, entry->child);
+			entry->child = NULL;
+			entry->degree = 0;
+		}
+		pqueue = g_pqueue_fix_rootlist(pqueue);
+	}
+
+	return pqueue;
+}
+
+/**
+ * g_pqueue_destroy:
+ * @pqueue: a #GPQueue.
+ * 
+ * Deallocates the memory used by @pqueue itself, but not any memory pointed
+ * to by the entries' data pointers.
+ * 
+ * This is unnecessary for empty queues, which are just a %NULL pointer,
+ * but can be used if you ever want to get rid of a #GPQueue before you have
+ * removed all the entries.
+ **/
+void
+g_pqueue_destroy (GPQueue* pqueue)
+{
+	if (pqueue == NULL) return;
+	g_pqueue_destroy(pqueue->child);
+	pqueue->prev->next = NULL;
+	g_pqueue_destroy(pqueue->next);
+	g_slice_free(GPQueue, pqueue);
+}
+
+#define __G_PQUEUE_C__
+#include "galiasdef.c"
+
diff -X diffignore -ruN glib-2.19.10/glib/gpqueue.h glib-2.19.10.local/glib/gpqueue.h
--- glib-2.19.10/glib/gpqueue.h	1970-01-01 01:00:00.000000000 +0100
+++ glib-2.19.10.local/glib/gpqueue.h	2009-03-09 19:33:47.588035881 +0100
@@ -0,0 +1,63 @@
+#if defined(G_DISABLE_SINGLE_INCLUDES) && !defined (__GLIB_H_INSIDE__) && !defined (GLIB_COMPILATION)
+#error "Only <glib.h> can be included directly."
+#endif
+
+#ifndef __G_PQUEUE_H__
+#define __G_PQUEUE_H__
+
+G_BEGIN_DECLS
+
+/**
+ * GPQueue:
+ * 
+ * An opaque structure representing a priority queue.
+ **/
+typedef struct _GPQueue GPQueue;
+
+/**
+ * GPQueueHandle:
+ * 
+ * An opaque value representing one entry in a #GPQueue.
+ * 
+ * DO NOT RELY on the fact that a #GPQueue and a #GPQueueHandle are
+ * essentially the same thing at this time, this may change along with the
+ * underlying implementation in future releases.
+ **/
+typedef GPQueue* GPQueueHandle;
+
+GPQueue*	g_pqueue_insert			(GPQueue *pqueue,
+						 gpointer data,
+						 gint priority,
+						 GPQueueHandle *handle)
+						G_GNUC_WARN_UNUSED_RESULT;
+
+gpointer	g_pqueue_top			(GPQueue *pqueue);
+
+gboolean	g_pqueue_top_extended		(GPQueue *pqueue,
+						 gpointer *data,
+						 gint *priority);
+
+GPQueue*	g_pqueue_delete_top		(GPQueue *pqueue)
+						G_GNUC_WARN_UNUSED_RESULT;
+
+gpointer	g_pqueue_pop			(GPQueue **pqueue);
+
+gboolean	g_pqueue_pop_extended		(GPQueue **pqueue,
+						 gpointer *data,
+						 gint *priority);
+
+GPQueue*	g_pqueue_delete			(GPQueue* pqueue,
+						 GPQueueHandle entry)
+						G_GNUC_WARN_UNUSED_RESULT;
+
+GPQueue*	g_pqueue_change_priority	(GPQueue* pqueue,
+						 GPQueueHandle entry,
+						 gint priority)
+						G_GNUC_WARN_UNUSED_RESULT;
+
+void		g_pqueue_destroy		(GPQueue* pqueue);
+
+G_END_DECLS
+
+#endif /* __G_PQUEUE_H__ */
+
diff -X diffignore -ruN glib-2.19.10/glib/Makefile.am glib-2.19.10.local/glib/Makefile.am
--- glib-2.19.10/glib/Makefile.am	2009-03-02 07:02:42.000000000 +0100
+++ glib-2.19.10.local/glib/Makefile.am	2009-03-09 13:49:07.128035706 +0100
@@ -131,6 +131,7 @@
 	gpattern.c		\
 	gpoll.c			\
 	gprimes.c		\
+	gpqueue.c		\
 	gqsort.c		\
 	gqueue.c		\
 	grel.c			\
diff -X diffignore -ruN glib-2.19.10/tests/Makefile.am glib-2.19.10.local/tests/Makefile.am
--- glib-2.19.10/tests/Makefile.am	2009-03-02 07:02:41.000000000 +0100
+++ glib-2.19.10.local/tests/Makefile.am	2009-03-10 16:26:34.350916275 +0100
@@ -121,6 +121,7 @@
 	patterntest				\
 	queue-test				\
 	asyncqueue-test				\
+	priorityqueue-test			\
 	qsort-test				\
 	relation-test				\
 	sequence-test				\
@@ -185,6 +186,7 @@
 onceinit_LDADD = $(thread_ldadd)
 queue_test_LDADD = $(progs_ldadd)
 asyncqueue_test_LDADD = $(thread_ldadd)
+priorityqueue_test_LDADD = $(progs_ldadd)
 qsort_test_LDADD = $(progs_ldadd)
 relation_test_LDADD = $(progs_ldadd)
 sequence_test_LDADD = $(progs_ldadd)
diff -X diffignore -ruN glib-2.19.10/tests/priorityqueue-test.c glib-2.19.10.local/tests/priorityqueue-test.c
--- glib-2.19.10/tests/priorityqueue-test.c	1970-01-01 01:00:00.000000000 +0100
+++ glib-2.19.10.local/tests/priorityqueue-test.c	2009-03-10 20:19:24.111915228 +0100
@@ -0,0 +1,170 @@
+#undef G_DISABLE_ASSERT
+
+#include <stdlib.h>
+#include <glib.h>
+
+#define NTESTS 15000
+#define MIN_P 0
+#define MAX_P 9999
+
+GPQueue *q = NULL;
+gint count = 0;
+
+gint priority[NTESTS];
+GPQueueHandle handles[NTESTS];
+gint last_priority = MIN_P - 1;
+gint returned[NTESTS];
+
+static inline gint
+randp (void)
+{
+	return g_random_int_range(MIN_P, MAX_P + 1);
+}
+
+static void
+generate (void)
+{
+	gint i;
+	for (i = 0; i < NTESTS; i++)
+		priority[i] = randp();
+}
+
+static void
+reset (void)
+{
+	gint i;
+	count = 0;
+	last_priority = -1;
+	for (i = 0; i < NTESTS; i++) returned[i] = 0;
+}
+
+static void
+push_n (gint n)
+{
+	while (n > 0) {
+		q = g_pqueue_insert(q, GINT_TO_POINTER(count), priority[count], handles + count);
+		count++;
+		n--;
+	}
+	last_priority = -1;
+}
+
+static gboolean
+pop_one (void)
+{
+	gpointer entry_data;
+	gint entry_priority;
+	gboolean was_not_empty =
+		g_pqueue_pop_extended(&q, &entry_data, &entry_priority);
+	if (was_not_empty) {
+		returned[GPOINTER_TO_INT(entry_data)] += 1;
+		handles[GPOINTER_TO_INT(entry_data)] = NULL;
+		if (entry_priority < last_priority)
+			g_error("GPQueue returned entries in the wrong order");
+		if (entry_priority != priority[GPOINTER_TO_INT(entry_data)])
+			g_error("Entry returned with a different priority");
+		last_priority = entry_priority;
+	}
+	return was_not_empty;
+}
+
+static void
+pop_all (void)
+{
+	while (pop_one()) {}
+}
+
+static void
+pop_n (gint n)
+{
+	while (n > 0) { pop_one(); n--; }
+}
+
+static void
+change_priorities (gint n)
+{
+	while (n > 0) {
+		gint k = g_random_int_range(0, count);
+		if (handles[k] != NULL) {
+			gint p = randp();
+			priority[k] = p;
+			q = g_pqueue_change_priority(q, handles[k], p);
+			n--;
+		}
+	}
+	last_priority = -1;
+}
+
+static void
+delete_entries (gint n)
+{
+	while (n > 0) {
+		gint k = g_random_int_range(0, count);
+		if (handles[k] != NULL) {
+			q = g_pqueue_delete(q, handles[k]);
+			handles[k] = NULL;
+			returned[k] += 1;
+			n--;
+		}
+	}
+}
+
+static void
+verify (void)
+{
+	gint i;
+	for (i = 0; i < NTESTS; i++)
+		if (returned[i] != 1)
+			g_error("Entry %d returned %d times instead of exactly once", i, returned[i]);
+}
+
+int
+main (int argc, char **argv)
+{
+	generate();
+	reset();
+	push_n(NTESTS);
+	pop_all();
+	verify();
+
+	generate();
+	reset();
+	push_n(NTESTS / 4);
+	pop_n(NTESTS / 4);
+	push_n(NTESTS / 4);
+	pop_n(NTESTS / 4);
+	push_n(NTESTS / 2);
+	pop_all();
+	verify();
+
+	generate();
+	reset();
+	push_n(NTESTS);
+	pop_n(NTESTS / 10);
+	change_priorities(NTESTS / 10);
+	pop_n(NTESTS / 10);
+	change_priorities(NTESTS / 10);
+	pop_n(NTESTS / 10);
+	change_priorities(NTESTS / 10);
+	pop_all();
+	verify();
+
+	generate();
+	reset();
+	push_n(NTESTS / 2);
+	change_priorities(NTESTS / 10);
+	pop_n(NTESTS / 10);
+	delete_entries(NTESTS / 10);
+	push_n(NTESTS / 4);
+	change_priorities(NTESTS / 10);
+	pop_n(NTESTS / 10);
+	change_priorities(NTESTS / 10);
+	pop_n(NTESTS / 10);
+	push_n(NTESTS / 4);
+	change_priorities(NTESTS / 10);
+	pop_all();
+	verify();
+
+	return EXIT_SUCCESS;
+}
+