High-performance Priority Queue / Heap for glib

[Maik Zumstrull-2]

Needing a fast priority queue for an internal project recently and
noticing that glib doesn't have one, I wrote it myself. I'd be
interested in submitting the code, and I'd be willing to do the
necessary cleanup and documentation work on it.

It's a pretty straight-forward implementation of a Fibonacci Heap
<http://en.wikipedia.org/wiki/Fibonacci_heap>, with a forest of trees
of circular double-linked lists as the underlying data structure (which
is not as nasty as that sounds).

According to my quick mailing list search, a Heap-based priority queue
was submitted in 2003, but not accepted. Let me address the comments in
<http://mail.gnome.org/archives/gtk-devel-list/2003-March/msg00006.html>.

| - Does it offer significant (big-o) performance
|   benefits for a common operation, or allow some
|   operation that would be really hard to code without
|   the data structure?

All operations can be done with existing glib data structures, but
there is a significant performance benefit. Please refer to
<http://en.wikipedia.org/wiki/Fibonacci_heap#Summary_of_running_times>.

Glib includes linked lists and balanced trees, of course; a simple heap
was submitted in 2003. As you can see, all three structures are easily
beaten by this approach, dropping performance to O(1) for most
operations and retaining O(log n) performance in the other cases.

| - Would it be useful to a significant fraction of
|   applications?

I don't think I can estimate the need. Personally, I was working with
graph algorithms related to partitioning and path finding, where a good
priority queue has a significant impact. In other areas where a
priority queue is needed, presumably people are simply using glib's
trees or lists now, accepting the performance penalty, which wouldn't
matter in most applications.


My implementation, ~300 lines of code, is fairly self-contained. It
introduces one new data structure (to be renamed for inclusion):

struct s_FQueue {
        gpointer data;
        gint priority;

        gint degree;
        gboolean marked;

        struct s_FQueue *parent;
        struct s_FQueue *prev;
        struct s_FQueue *next;
        struct s_FQueue *firstchild;
};

typedef struct s_FQueue FQueue;

The glib slice allocator is used to create and drop these elements.
There are no significant dependencies on glib functionality otherwise.

Memory management follows the semantics used by glib's linked lists: a
simple NULL pointer represents an empty queue, and FQueue elements are
created and deleted implicitly as items are added to and removed from
the queue. The implementation doesn't at all care about the data
pointer, so filling it with GINT_TO_POINTER wrapped gints instead of
actual pointers is okay.

The element's priorities have to be expressed as gints, the use of a
comparison function is not supported as an alternative. Elements are
returned by the queue in ascending order of the priority value. No
guarantees are made regarding the iteration order for elements with the
same priority. The priority of an entry can be changed after insertion
by a function call, but the priority field must not be directly written.

The user is expected to keep one FQueue *q variable for the queue, then
pass its address to most of the API calls. The pointer is rewritten by
each call as necessary to always point to the FQueue element currently
at the front of the queue (or NULL for an empty queue). The GList style
syntax q = some_api_call(q, ...); for rewriting the pointer is not used
because of the special needs of the insert call (see below). This could
be inverted to use GList-style syntax everywhere, and an FQueue** in
the insert call only.

This is the proposed / currently implemented API:

#define fqueue_isempty(fq) (gboolean)(fq == NULL)

Obvious.

FQueue* fqueue_insert (FQueue **fq, gpointer data, gint priority);

Inserts "data" into the list with a priority value of "priority". An
FQueue element is implicitly allocated. The fq pointer is rewritten to
point to the front of the queue. The *returned* pointer points to the
newly allocated element. Do NOT put that into your queue variable, but
keep the pointer around somewhere if you intend to make
change_priority or delete calls on this element. The returned pointer
can be ignored if you don't plan to change any priorities and don't
plan to remove elements other than by pop()-ing them.

gpointer fqueue_peek (FQueue *fq);

Returns the value of the data pointer of the element with the lowest
priority value, without removing it from the queue. NULL is returned
for an empty queue, so if you need to differentiate between an empty
queue and an element with a NULL data pointer, check for that first.

gpointer fqueue_pop (FQueue **fq);

Returns the value of the data pointer of the element with the lowest
priority value, removing it from the queue. The FQueue element is
implicitly deallocated. Do not attempt to make change_priority or delete
calls on that element after this, it's gone! NULL is returned for an
empty queue.

void fqueue_delete (FQueue **fq, FQueue *elem);

Deletes the queue element pointed to by elem from the queue, rewriting
the main queue pointer if necessary.

void fqueue_change_priority (FQueue **fq, FQueue *elem, gint newpriority);

Changes the priority of the queue element pointed to by elem to
newpriority, rewriting the main queue pointer if necessary.

void fqueue_merge (FQueue **fqa, FQueue **fqb);

Merges two priority queues into one. fqb will be NULL after this call
and fqa contains one queue with all elements of both queues. No memory
needs to be allocated or deallocated, neither explicitly nor implicitly.

void fqueue_free (FQueue *fq);

Rarely needed. If you fill up a queue and then pop() all the elements,
all the memory will be deallocated already. If, for some reason, you
want to get rid of a queue before it's empty, this call is for you. Of
course, calling this on an already empty queue doesn't hurt, it's just
unnecessary.


Any comments? If you're at all interested, what exactly would be
expected of the code for inclusion?
_______________________________________________
gtk-devel-list mailing list
gtk-devel-list@...
http://mail.gnome.org/mailman/listinfo/gtk-devel-list

[Ben Pfaff]

Maik Zumstrull <maik.zumstrull@...> writes:

[about a Fibonacci heap implementation]

> | - Does it offer significant (big-o) performance
> |   benefits for a common operation, or allow some
> |   operation that would be really hard to code without
> |   the data structure?
>
> All operations can be done with existing glib data structures, but
> there is a significant performance benefit. Please refer to
> <http://en.wikipedia.org/wiki/Fibonacci_heap#Summary_of_running_times>.
>
> Glib includes linked lists and balanced trees, of course; a simple heap
> was submitted in 2003. As you can see, all three structures are easily
> beaten by this approach, dropping performance to O(1) for most
> operations and retaining O(log n) performance in the other cases.

The big-O of a Fibonacci heap is better than that of a balanced
tree or a binary heap, but how is the actual performance?  When
you benchmark your Fibonacci heap against balanced trees or
binary heaps for realistic test cases, is there an actual
improvement in runtime?

The reason that I ask is this paragraph in the chapter on
Fibonacci heaps in Cormen, Leiserson, and Rivest, _Introduction
to Algorithms_:

        From a practical point of view, however, the constant
        factors and programming complexity of Fibonacci heaps
        make them less desirable than ordinary binary (or k-ary)
        heaps for most applications.  Thus, Fibonacci heaps are
        predominantly of theoretical interest.

I observed this effect in practice myself a few years ago, when I
compared the performance of otherwise identical code using a
binary heap and a Fibonacci heap (see page 51 of
http://benpfaff.org/uniformity/uniformity-2001.04.27.pdf).  But I
didn't make much of an attempt to optimize my heaps, and maybe
you did a better implementation.
--
Ben Pfaff
http://benpfaff.org

_______________________________________________
gtk-devel-list mailing list
gtk-devel-list@...
http://mail.gnome.org/mailman/listinfo/gtk-devel-list

[Maik Zumstrull-2]

Ben Pfaff wrote:

> Maik Zumstrull <maik.zumstrull@...> writes:

> The big-O of a Fibonacci heap is better than that of a balanced
> tree or a binary heap, but how is the actual performance?  When
> you benchmark your Fibonacci heap against balanced trees or
> binary heaps for realistic test cases, is there an actual
> improvement in runtime?

To be perfectly honest, I hadn't run any direct benchmarks before and
just assumed a Fibonacci Heap would be faster. I have done so now.

First, the results of my synthetic benchmarks:

Running Test "Insert all, then pop all":
         n      TQueue     FQueue
      5000      0.006s     0.004s
     50000      0.137s     0.070s
    500000      2.202s     1.148s
Running Test "Insert, then pop, randomized":
         n      TQueue     FQueue
      5000      0.006s     0.003s
     50000      0.102s     0.048s
    500000      1.649s     0.803s
Running Test "Insert, change, pop, randomized":
         n      TQueue     FQueue
      5000      0.011s     0.004s
     50000      0.147s     0.055s
    500000      2.455s     0.874s

"FQueue" (FibonacciQueue) is my implementation, "TQueue" (TreeQueue) is
a thin abstraction to provide a priority queue API on top of GSequence.
I looked at GTree first, but it provides no clean way to get the
minimal element of the tree as far as I can see. You'd have to call
g_tree_foreach and abort in the first callback. GSequence seems more
appropriate.

All tests involve inserting n elements with random priorities into
the structure. In the first test, there are n inserts followed by n
pops. In the second test, a random number of inserts is followed by a
random number of pops until n inserts have happened in total, then the
queue is poped until empty. The third test is similar, but between
inserting and poping a random number of elements have their priority
randomly changed in each cycle. Each test is run 10 times, the
numbers listed are averages over that.

Being faster by a factor of about 2-4 is not stellar, but not too
shabby either. Two other things to note: FQueue is much faster for the
randomized tests; this is probably because until you pop, FQueue is
simply a linked list. The structural compression into trees happens
during poping, and would take quite a while if the root list is 500000
elements long at that time. Secondly, FQueue barely cares about
change_priority calls, while TQueue almost doubles its runtime. I guess
that's the difference between O(1) and O(log n) right there.

For a real-world perspective, I forked the graph processing application
I mentioned and switched from FQueue to TQueue. This increases the
runtime for real input data by about 30% -- FQueue is somewhat faster,
though not as much as I expected it to be.

> The reason that I ask is this paragraph in the chapter on
> Fibonacci heaps in Cormen, Leiserson, and Rivest, _Introduction
> to Algorithms_:
>
>         From a practical point of view, however, the constant
>         factors and programming complexity of Fibonacci heaps
>         make them less desirable than ordinary binary (or k-ary)
>         heaps for most applications.  Thus, Fibonacci heaps are
>         predominantly of theoretical interest.

I'm not sure what "programming complexity" he's talking about. The
forest data structure involves some mildly annoying pointer-fiddling,
but it's not exceptionally challenging. Other than that, he might be
right about the relation between binary- and Fibonacci-heaps. I haven't
tested against the former, my primary goal was to be faster than lists
and trees, and I went with what I thought to be the best algorithm for
the job. Maybe I've let the theory deceive me.
_______________________________________________
gtk-devel-list mailing list
gtk-devel-list@...
http://mail.gnome.org/mailman/listinfo/gtk-devel-list

[Behdad Esfahbod-3]

Maik Zumstrull wrote:
> Needing a fast priority queue for an internal project recently and
> noticing that glib doesn't have one, I wrote it myself. I'd be
> interested in submitting the code, and I'd be willing to do the
> necessary cleanup and documentation work on it.

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.

behdad

> It's a pretty straight-forward implementation of a Fibonacci Heap
> <http://en.wikipedia.org/wiki/Fibonacci_heap>, with a forest of trees
> of circular double-linked lists as the underlying data structure (which
> is not as nasty as that sounds).
>
> According to my quick mailing list search, a Heap-based priority queue
> was submitted in 2003, but not accepted. Let me address the comments in
> <http://mail.gnome.org/archives/gtk-devel-list/2003-March/msg00006.html>.
>
> | - Does it offer significant (big-o) performance
> |   benefits for a common operation, or allow some
> |   operation that would be really hard to code without
> |   the data structure?
>
> All operations can be done with existing glib data structures, but
> there is a significant performance benefit. Please refer to
> <http://en.wikipedia.org/wiki/Fibonacci_heap#Summary_of_running_times>.
>
> Glib includes linked lists and balanced trees, of course; a simple heap
> was submitted in 2003. As you can see, all three structures are easily
> beaten by this approach, dropping performance to O(1) for most
> operations and retaining O(log n) performance in the other cases.
>
> | - Would it be useful to a significant fraction of
> |   applications?
>
> I don't think I can estimate the need. Personally, I was working with
> graph algorithms related to partitioning and path finding, where a good
> priority queue has a significant impact. In other areas where a
> priority queue is needed, presumably people are simply using glib's
> trees or lists now, accepting the performance penalty, which wouldn't
> matter in most applications.
>
>
> My implementation, ~300 lines of code, is fairly self-contained. It
> introduces one new data structure (to be renamed for inclusion):
>
> struct s_FQueue {
>         gpointer data;
>         gint priority;
>
>         gint degree;
>         gboolean marked;
>
>         struct s_FQueue *parent;
>         struct s_FQueue *prev;
>         struct s_FQueue *next;
>         struct s_FQueue *firstchild;
> };
>
> typedef struct s_FQueue FQueue;
>
> The glib slice allocator is used to create and drop these elements.
> There are no significant dependencies on glib functionality otherwise.
>
> Memory management follows the semantics used by glib's linked lists: a
> simple NULL pointer represents an empty queue, and FQueue elements are
> created and deleted implicitly as items are added to and removed from
> the queue. The implementation doesn't at all care about the data
> pointer, so filling it with GINT_TO_POINTER wrapped gints instead of
> actual pointers is okay.
>
> The element's priorities have to be expressed as gints, the use of a
> comparison function is not supported as an alternative. Elements are
> returned by the queue in ascending order of the priority value. No
> guarantees are made regarding the iteration order for elements with the
> same priority. The priority of an entry can be changed after insertion
> by a function call, but the priority field must not be directly written.
>
> The user is expected to keep one FQueue *q variable for the queue, then
> pass its address to most of the API calls. The pointer is rewritten by
> each call as necessary to always point to the FQueue element currently
> at the front of the queue (or NULL for an empty queue). The GList style
> syntax q = some_api_call(q, ...); for rewriting the pointer is not used
> because of the special needs of the insert call (see below). This could
> be inverted to use GList-style syntax everywhere, and an FQueue** in
> the insert call only.
>
> This is the proposed / currently implemented API:
>
> #define fqueue_isempty(fq) (gboolean)(fq == NULL)
>
> Obvious.
>
> FQueue* fqueue_insert (FQueue **fq, gpointer data, gint priority);
>
> Inserts "data" into the list with a priority value of "priority". An
> FQueue element is implicitly allocated. The fq pointer is rewritten to
> point to the front of the queue. The *returned* pointer points to the
> newly allocated element. Do NOT put that into your queue variable, but
> keep the pointer around somewhere if you intend to make
> change_priority or delete calls on this element. The returned pointer
> can be ignored if you don't plan to change any priorities and don't
> plan to remove elements other than by pop()-ing them.
>
> gpointer fqueue_peek (FQueue *fq);
>
> Returns the value of the data pointer of the element with the lowest
> priority value, without removing it from the queue. NULL is returned
> for an empty queue, so if you need to differentiate between an empty
> queue and an element with a NULL data pointer, check for that first.
>
> gpointer fqueue_pop (FQueue **fq);
>
> Returns the value of the data pointer of the element with the lowest
> priority value, removing it from the queue. The FQueue element is
> implicitly deallocated. Do not attempt to make change_priority or delete
> calls on that element after this, it's gone! NULL is returned for an
> empty queue.
>
> void fqueue_delete (FQueue **fq, FQueue *elem);
>
> Deletes the queue element pointed to by elem from the queue, rewriting
> the main queue pointer if necessary.
>
> void fqueue_change_priority (FQueue **fq, FQueue *elem, gint newpriority);
>
> Changes the priority of the queue element pointed to by elem to
> newpriority, rewriting the main queue pointer if necessary.
>
> void fqueue_merge (FQueue **fqa, FQueue **fqb);
>
> Merges two priority queues into one. fqb will be NULL after this call
> and fqa contains one queue with all elements of both queues. No memory
> needs to be allocated or deallocated, neither explicitly nor implicitly.
>
> void fqueue_free (FQueue *fq);
>
> Rarely needed. If you fill up a queue and then pop() all the elements,
> all the memory will be deallocated already. If, for some reason, you
> want to get rid of a queue before it's empty, this call is for you. Of
> course, calling this on an already empty queue doesn't hurt, it's just
> unnecessary.
>
>
> Any comments? If you're at all interested, what exactly would be
> expected of the code for inclusion?
> _______________________________________________
> gtk-devel-list mailing list
> gtk-devel-list@...
> http://mail.gnome.org/mailman/listinfo/gtk-devel-list
>

_______________________________________________
gtk-devel-list mailing list
gtk-devel-list@...
http://mail.gnome.org/mailman/listinfo/gtk-devel-list

[Maik Zumstrull-2]

Behdad Esfahbod wrote:

> Maik Zumstrull wrote:
> > Needing a fast priority queue for an internal project recently and
> > noticing that glib doesn't have one, I wrote it myself. I'd be
> > interested in submitting the code, and I'd be willing to do the
> > necessary cleanup and documentation work on it.
>
> 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.
_______________________________________________
gtk-devel-list mailing list
gtk-devel-list@...
http://mail.gnome.org/mailman/listinfo/gtk-devel-list

[Maik Zumstrull-2]

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
[glib-2.19.10-priorityqueue.diff]

---

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

---

_______________________________________________
gtk-devel-list mailing list
gtk-devel-list@...
http://mail.gnome.org/mailman/listinfo/gtk-devel-list

[Behdad Esfahbod-3]

Hi Maik,

I suggest you open a bug on http://bugzilla.gnome.org/ and attach your latest
patch there.  I like to comment on the patch, but don't want to take more of
your time until the glib maintainers show interest in merging this.

Cheers,
behdad

On 03/10/2009 03:53 PM, Maik Zumstrull wrote:

> 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
>
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> gtk-devel-list mailing list
> gtk-devel-list@...
> http://mail.gnome.org/mailman/listinfo/gtk-devel-list

_______________________________________________
gtk-devel-list mailing list
gtk-devel-list@...
http://mail.gnome.org/mailman/listinfo/gtk-devel-list

[Maik Zumstrull-2]

Behdad Esfahbod wrote:

> I suggest you open a bug on http://bugzilla.gnome.org/ and attach
> your latest patch there.

I created the bug (<http://bugzilla.gnome.org/show_bug.cgi?id=575074>),
but I am unable to attach the patch:

| Internal Error
|
| Bugzilla has suffered an internal error. Please save this page and
| send it to bugmaster@... with details of what you were doing at
| the time this message appeared.
|
| URL: http://bugzilla.gnome.org/attachment.cgi
|
| undef error - Undefined subroutine Fh::slice at
| data/template/template/en/default/global/hidden-fields.html.tmpl
| line 58
_______________________________________________
gtk-devel-list mailing list
gtk-devel-list@...
http://mail.gnome.org/mailman/listinfo/gtk-devel-list

[Maik Zumstrull-2]

Maik Zumstrull wrote:

> Behdad Esfahbod wrote:
>
> > I suggest you open a bug on http://bugzilla.gnome.org/ and attach
> > your latest patch there.
>
> I created the bug
> (<http://bugzilla.gnome.org/show_bug.cgi?id=575074>), but I am unable
> to attach the patch:

Worked on fifth-or-so attempt, must have been a temporary server glitch.
_______________________________________________
gtk-devel-list mailing list
gtk-devel-list@...
http://mail.gnome.org/mailman/listinfo/gtk-devel-list

[Olav Vitters]

On Thu, Mar 12, 2009 at 01:56:05PM +0100, Maik Zumstrull wrote:
> Worked on fifth-or-so attempt, must have been a temporary server glitch.

You likely have a (transparent) proxy with multiple IP addresses. Don't
limit the login to your IP address when logging in.

--
Regards,
Olav
_______________________________________________
gtk-devel-list mailing list
gtk-devel-list@...
http://mail.gnome.org/mailman/listinfo/gtk-devel-list

[Peter Clifton-2]

On Tue, 2009-03-10 at 20:53 +0100, Maik Zumstrull wrote:

> 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.

Hi,

Forgive my ignorance if this is a fundamentally stupid question.. but
would it still be a priority queue if rather than assigning an integer
priority when adding an element, the queue was set up with a callback
function - such that the user's implementation can compare the priority
of two items in the queue?

I'm looking at implementing a computational geometry algorithm (based on
Bentley-Ottmann) (and I've not got much experience in that field). The
priority function required is the x-coordinate of some points, but with
a tie-break on the y-coordinate in the case where the x-coordinates
match.

Without constraining the bounds of my coordinates, or performing some
separate coordinate -> priority mapping step (hard, since new coords are
generated as the algorithm progresses), this doesn't seem to be possible
with your implementation.

Any thoughts?

Best regards,

Peter Clifton


_______________________________________________
gtk-devel-list mailing list
gtk-devel-list@...
http://mail.gnome.org/mailman/listinfo/gtk-devel-list