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;
+}
+
