GNOME Bugzilla – Bug 107082
Priority queue for glib
Last modified: 2018-05-23 23:13:25 UTC
I have implemented a simple array-based priority queue for glib. I submit it for your consideration for incorporation into future versions of glib. I know that there are problems with this first version, please let me know. In particular, I believe that the documentation is supposed to be embedded in the code somehow, but I'm not clear how this is done. In the absence of any explanation to the contrary, I'm just going to paste the diffs into this browser window: The three new files are located below the diffs: ? docs/reference/glib/tmpl/priority_queues.sgml ? glib/gpriq.c ? glib/gpriq.h Index: ChangeLog =================================================================== RCS file: /cvs/gnome/glib/ChangeLog,v retrieving revision 1.1286 diff -u -r1.1286 ChangeLog --- ChangeLog 26 Feb 2003 00:12:41 -0000 1.1286 +++ ChangeLog 26 Feb 2003 00:50:57 -0000 @@ -1,3 +1,15 @@ +2003-02-26 Robert Graham Merkel <rgmerk@mira.net> + + * glib/gpriq.{ch}: new files implementing a simple priority + queue for glib. + + * glib/glib.h: include gpriq.h + + * glib/Makefile.am: build gpriq.o + + * glib/docs/reference/glib/tmpl/priority_queues.sgml: documentation + for the priority queue. + 2003-02-26 Matthias Clasen <maclas@gmx.de> * glib/gstrfuncs.c (g_strdup_vprintf): Use g_strndup, not Index: docs/reference/glib/tmpl/glib-unused.sgml =================================================================== RCS file: /cvs/gnome/glib/docs/reference/glib/tmpl/glib-unused.sgml,v retrieving revision 1.34 diff -u -r1.34 glib-unused.sgml --- docs/reference/glib/tmpl/glib-unused.sgml 26 May 2002 22:46:24 -0000 1.34 +++ docs/reference/glib/tmpl/glib-unused.sgml 26 Feb 2003 00:50:57 -0000 @@ -1,3 +1,49 @@ +<!-- ##### SECTION ./tmpl/priority_queues.sgml:Long_Description ##### --> +<para> +The #GPriq structure and its associated functions provide a collection +of key/value pairs designed for insertion in any order and in-order +removal. For these operations, it is faster than #GTree and has +a simpler interface. +</para> +<para> +To create a new #GPriq use g_priq_new(). +</para> +<para> +To insert a key/value pair into a #GPriq use g_priq_insert(). +</para> +<para> +To check the smallest entry. in a #GPriq, use g_priq_minimum(), or g_priq_minimum_extended(). +To check it and remove it from the queue, use g_priq_remove() or g_priq_remove_extended() +</para> +<para> +To find out the number of items in a #GTree, use g_priq_nnodes(). +</para> +<para> +To traverse a #GPriq, calling a function for each node visited in the +traversal, use g_tree_foreach(). You can either to a fast traversal (in +arbitrary order) or a (slower) in-order traversal. +</para> +<para> +To destroy a #GPriq, use g_priq_destroy(). +</para> + + +<!-- ##### SECTION ./tmpl/priority_queues.sgml:See_Also ##### --> +<para> +#GTree +</para> + + +<!-- ##### SECTION ./tmpl/priority_queues.sgml:Short_Description ##### --> +A data structure optimized for inserting items in any order, +and removing them one by one in sorted order, from the smallest +to the largest. + + +<!-- ##### SECTION ./tmpl/priority_queues.sgml:Title ##### --> +Priority Queues + + <!-- ##### ENUM GChannelError ##### --> <para> @@ -100,6 +146,13 @@ @G_MATCH_EXACT: a pattern matching exactly one string. @G_MATCH_LAST: +<!-- ##### STRUCT GPriq ##### --> +<para> +The <structname>GPriq</structname> struct is an opaque data structure representing a +min-priority queue. It should be accessed only by using the following functions. +</para> + + <!-- ##### USER_FUNCTION GWarningFunc ##### --> <para> Specifies the type of function passed to g_set_warning_handler(). @@ -277,6 +330,79 @@ </para> @mem: the memory to check. + +<!-- ##### FUNCTION g_priq_destroy ##### --> +<para> +Destroy a #GPriq, freeing all memory allocated for it. +If key and/or value destructors were specified using g_priq_new_full() +when the queue was created, those destructors will be called on each +key and/or value respectively. The items will not be destroyed in +an arbitrary order. If not, the programmer is responsible +for deallocating that memory, if required. +</para> + +@priq: The the #Gpriq to be destroyed. + +<!-- ##### FUNCTION g_priq_foreach ##### --> +<para> +Apply a function to each key/value pair in a #GPriq. This +can either be performed in arbitrary order (faster) or in +order (slower and requires a temporary copy of the priority +queue to be made internally). +</para> + +@priq: The #GPriq to traverse. +@inorder: If TRUE, the traversal will be in-order. If FALSE, it +will be in arbitrary order. +@traverse_func: the function to apply to each key-value pair +@user_data: pointer to data to be supplied to each invocation of traverse_func. + +<!-- ##### FUNCTION g_priq_insert ##### --> +<para> +Insert a new key/value pair into a #GPriq. +</para> + +@priq: The #GPriq in which to insert the pair. +@key: The key. +@value: The corresponding data. + +<!-- ##### FUNCTION g_priq_new ##### --> +<para> +Create a new #GPriq. +</para> + +@key_compare_func: Key comparison function. +@Returns: A pointer to the newly allocated #GPriq. + +<!-- ##### FUNCTION g_priq_new_full ##### --> +<para> +Create a new #Gpriq, not only with a comparison function that takes user-supplied data, +but with keys and/or values destroyed by a user-supplied function when they are removed from the +queue or the queue is destroyed. +</para> + +@key_compare_func: The key comparison function. +@key_compare_data: data supplied to the key function each time it is called +@key_destroy_func: a function to destroy keys +@value_destroy_func: a function to destroy data items. +@Returns: A pointer to the newly allocated #GPriq. + +<!-- ##### FUNCTION g_priq_new_with_data ##### --> +<para> +Create a new #Gpriq, with a comparison function that takes additional user-supplied data. +</para> + +@key_compare_func: key comparison function. +@key_compare_data: data supplied to the key comparison function each time that it is used. +@Returns: A pointer to the newly allocated #GPriq. + +<!-- ##### FUNCTION g_priq_nnodes ##### --> +<para> +Count the number of entries in a #GPriq +</para> + +@priq: The #GPriq to count the number of nodes in. +@Returns: The number of nodes in the #GPriq. <!-- ##### FUNCTION g_scanner_stat_mode ##### --> <para> Index: glib/Makefile.am =================================================================== RCS file: /cvs/gnome/glib/glib/Makefile.am,v retrieving revision 1.105 diff -u -r1.105 Makefile.am --- glib/Makefile.am 14 Feb 2003 15:08:45 -0000 1.105 +++ glib/Makefile.am 26 Feb 2003 00:50:57 -0000 @@ -67,6 +67,7 @@ gnode.c \ gpattern.c \ gprimes.c \ + gpriq.c \ gqsort.c \ gqueue.c \ grel.c \ @@ -133,6 +134,7 @@ gnode.h \ gpattern.h \ gprimes.h \ + gpriq.h \ gqsort.h \ gquark.h \ gqueue.h \ Index: glib/glib.h =================================================================== RCS file: /cvs/gnome/glib/glib/glib.h,v retrieving revision 1.218 diff -u -r1.218 glib.h --- glib/glib.h 5 Nov 2001 01:47:31 -0000 1.218 +++ glib/glib.h 26 Feb 2003 00:50:57 -0000 @@ -51,6 +51,7 @@ #include <glib/gnode.h> #include <glib/gpattern.h> #include <glib/gprimes.h> +#include <glib/gpriq.h> #include <glib/gqsort.h> #include <glib/gquark.h> #include <glib/gqueue.h> ********************************************************************* /* GLIB - Library of useful routines for C programming * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public * License as published by the Free Software Foundation; either * version 2 of the License, or (at your option) any later version. * * This library is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this library; if not, write to the * Free Software Foundation, Inc., 59 Temple Place - Suite 330, * Boston, MA 02111-1307, USA. */ /* * Modified by the GLib Team and others 1997-2000. See the AUTHORS * file for a list of people on the GLib Team. See the ChangeLog * files for a list of changes. These files are distributed with * GLib at ftp://ftp.gtk.org/pub/gtk/. */ #include <glib.h> #define g_heaparray_index(h, i) g_array_index(h, HeapEntry, i) typedef struct _HeapEntry HeapEntry; struct _HeapEntry { gpointer key; gpointer data; }; struct _GPriq { GCompareDataFunc key_compare; gboolean key_compare_func_data_p; /* if FALSE, key_compare is a GCompareFunc */ gpointer key_comp_data; GDestroyNotify key_destroy; /* pointer to a function that destroys keys */ GDestroyNotify data_destroy; /* pointer to a function that destroys destroy data */ GArray *heap; }; static inline guint parent (guint index) { return index / 2; } static inline guint left (guint index) { return index * 2; } static inline guint right (guint index) { return (index * 2) + 1; } static inline gint compare (GPriq * priq, const HeapEntry * a, const HeapEntry * b) { if (priq->key_compare_func_data_p) { return (priq->key_compare) (a->key, b->key, priq->key_comp_data); } else { return ((GCompareFunc) (priq->key_compare)) (a->key, b->key); } } static inline void upheap (GPriq * priq, guint index) { HeapEntry he = g_heaparray_index (priq->heap, index); while (index > 1 && compare (priq, &(g_array_index (priq->heap, HeapEntry, parent (index))), &he) > 0) { g_heaparray_index (priq->heap, index) = g_heaparray_index (priq->heap, parent (index)); index = parent (index); } g_heaparray_index (priq->heap, index) = he; return; } static inline void downheap (GPriq * priq, guint index) { guint child; HeapEntry he = g_heaparray_index (priq->heap, index); while (index <= (priq->heap->len - 1) / 2) { if (left (index) < (priq->heap->len - 1) && (compare (priq, &(g_heaparray_index (priq->heap, left (index))), &(g_heaparray_index (priq->heap, right (index)))) > 0)) { child = right (index); } else { child = left (index); } if (compare (priq, &he, &(g_heaparray_index (priq->heap, child))) <= 0) { break; } g_heaparray_index (priq->heap, index) = g_heaparray_index (priq->heap, child); index = child; } g_heaparray_index (priq->heap, index) = he; return; } static inline GPriq * g_priq_new_full_real (GCompareDataFunc key_compare_func, gboolean key_compare_func_has_data, gpointer key_compare_data, GDestroyNotify key_destroy_func, GDestroyNotify data_destroy_func) { HeapEntry he = { NULL, NULL }; GPriq *priq; g_return_val_if_fail (key_compare_func != NULL, NULL); priq = g_new (GPriq, 1); priq->key_compare = key_compare_func; priq->key_compare_func_data_p = key_compare_func_has_data; priq->key_comp_data = key_compare_data; priq->key_destroy = key_destroy_func; priq->data_destroy = data_destroy_func; priq->heap = g_array_new (FALSE, FALSE, sizeof (HeapEntry)); g_array_append_val (priq->heap, he); return priq; } static inline void traverse_fast (GPriq * priq, GTraverseFunc traverse_func, gpointer user_data) { int i; HeapEntry *he; for (i = 1; i < priq->heap->len; i++) { he = &g_heaparray_index (priq->heap, i); if (traverse_func (he->key, he->data, user_data)) { break; } } return; } /* * creating a quickie heap for doing an inorder traversal * no copying of data, so we don't want to destroy it on * g_priq_remove */ static inline GPriq * duplicate_no_destructors (GPriq * priq) { int i; GPriq *dup = g_new (GPriq, 1); dup->key_compare = priq->key_compare; dup->key_comp_data = priq->key_comp_data; dup->key_compare_func_data_p = priq->key_compare_func_data_p; dup->key_destroy = NULL; dup->data_destroy = NULL; dup->heap = g_array_sized_new (FALSE, FALSE, sizeof (HeapEntry), priq->heap->len); for (i = 0; i < priq->heap->len; i++) { g_array_append_val (dup->heap, g_heaparray_index (priq->heap, i)); } return dup; } static inline void traverse_inorder (GPriq * priq, GTraverseFunc traverse_func, gpointer user_data) { int i; gpointer key, data; GPriq *copy = duplicate_no_destructors (priq); for (i = g_priq_nnodes (copy); i > 0; i--) { g_priq_remove_extended (copy, &key, &data); if (traverse_func (key, data, user_data)) { break; } } g_priq_destroy (copy); } GPriq * g_priq_new (GCompareFunc key_compare_func) { return g_priq_new_full_real ((GCompareDataFunc) key_compare_func, FALSE, NULL, NULL, NULL); } GPriq * g_priq_new_with_data (GCompareDataFunc key_compare_func, gpointer key_compare_data) { return g_priq_new_full_real (key_compare_func, TRUE, key_compare_data, NULL, NULL); } GPriq * g_priq_new_full (GCompareDataFunc key_compare_func, gpointer key_compare_data, GDestroyNotify key_destroy, GDestroyNotify data_destroy) { return g_priq_new_full_real (key_compare_func, TRUE, key_compare_data, key_destroy, data_destroy); } gint g_priq_nnodes (GPriq * priq) { g_return_val_if_fail (priq, 0); return (priq->heap->len) - 1; } void g_priq_destroy (GPriq * priq) { int i; if (priq->key_destroy) { for (i = 1; i < priq->heap->len; i++) { (priq->key_destroy) ((g_array_index (priq->heap, HeapEntry, i)). key); } } if (priq->data_destroy) { for (i = 1; i < priq->heap->len; i++) { (priq->data_destroy) ((g_array_index (priq->heap, HeapEntry, i)). data); } } g_array_free (priq->heap, FALSE); return; } gpointer g_priq_minimum (GPriq * priq) { g_return_val_if_fail (priq->heap->len > 1, NULL); return (g_heaparray_index (priq->heap, 1)).data; } void g_priq_minimum_extended (GPriq * priq, gpointer * key, gpointer * value) { *key = NULL; *value = NULL; g_return_if_fail (priq->heap->len > 1); HeapEntry *he = &(g_heaparray_index (priq->heap, 1)); *key = he->key; *value = he->data; return; } void g_priq_remove_extended (GPriq * priq, gpointer * key, gpointer * value) { HeapEntry min; *key = NULL; *value = NULL; g_return_if_fail (priq->heap->len > 1); min = g_heaparray_index (priq->heap, 1); g_heaparray_index (priq->heap, 1) = g_heaparray_index (priq->heap, priq->heap->len - 1); g_array_remove_index (priq->heap, priq->heap->len - 1); downheap (priq, 1); *key = min.key; *value = min.data; return; } gpointer g_priq_remove (GPriq * priq) { gpointer key, data; g_priq_remove_extended (priq, &key, &data); if (priq->key_destroy) { (priq->key_destroy) (key); } return data; } void g_priq_insert (GPriq * priq, gpointer key, gpointer data) { HeapEntry he; he.key = key; he.data = data; g_return_if_fail (priq); g_array_append_val (priq->heap, he); upheap (priq, priq->heap->len - 1); return; } void g_priq_foreach (GPriq * priq, gboolean inorder, GTraverseFunc traverse_func, gpointer user_data) { g_return_if_fail (priq && traverse_func); if (inorder) { traverse_inorder (priq, traverse_func, user_data); } { traverse_fast (priq, traverse_func, user_data); } return; } ************************************************************** #ifndef __G_PRIQ_H__ #define __G_PRIQ_H__ #include <glib/gtypes.h> #include <glib/gtree.h> G_BEGIN_DECLS typedef struct _GPriq GPriq; GPriq *g_priq_new (GCompareFunc key_compare_func); GPriq *g_priq_new_with_data (GCompareDataFunc key_compare_func, gpointer key_compare_data); GPriq *g_priq_new_full (GCompareDataFunc key_compare_func, gpointer key_compare_data, GDestroyNotify key_destroy_func, GDestroyNotify data_destroy_func); gint g_priq_nnodes (GPriq * priq); void g_priq_destroy (GPriq * priq); void g_priq_insert (GPriq * priq, gpointer key, gpointer value); gpointer g_priq_minimum (GPriq * priq); void g_priq_minimum_extended (GPriq * priq, gpointer * key, gpointer * value); gpointer g_priq_remove (GPriq * priq); void g_priq_remove_extended (GPriq * priq, gpointer * key, gpointer * value); void g_priq_foreach (GPriq * priq, gboolean inorder, GTraverseFunc traverse_func, gpointer user_data); G_END_DECLS #endif /* __G_PRIQ_H__ */ ************************************************************** <!-- ##### SECTION Title ##### --> Priority Queues <!-- ##### SECTION Short_Description ##### --> A data structure optimized for inserting items in any order, and removing them one by one in sorted order, from the smallest to the largest. <!-- ##### SECTION Long_Description ##### --> <para> The #GPriq structure and its associated functions provide a collection of key/value pairs designed for insertion in any order and in-order removal. For these operations, it is faster than #GTree and has a simpler interface. </para> <para> To create a new #GPriq use g_priq_new(). </para> <para> To insert a key/value pair into a #GPriq use g_priq_insert(). </para> <para> To check the smallest entry. in a #GPriq, use g_priq_minimum(), or g_priq_minimum_extended(). To check it and remove it from the queue, use g_priq_remove() or g_priq_remove_extended() </para> <para> To find out the number of items in a #GTree, use g_priq_nnodes(). </para> <para> To traverse a #GPriq, calling a function for each node visited in the traversal, use g_tree_foreach(). You can either to a fast traversal (in arbitrary order) or a (slower) in-order traversal. </para> <para> To destroy a #GPriq, use g_priq_destroy(). </para> <!-- ##### SECTION See_Also ##### --> <para> #GTree </para> <!-- ##### STRUCT GPriq ##### --> <para> The <structname>GPriq</structname> struct is an opaque data structure representing a min-priority queue. It should be accessed only by using the following functions. </para> <!-- ##### FUNCTION g_priq_new ##### --> <para> Create a new #GPriq. </para> @key_compare_func: Key comparison function. @Returns: A pointer to the newly allocated #GPriq. <!-- ##### FUNCTION g_priq_new_with_data ##### --> <para> Create a new #Gpriq, with a comparison function that takes additional user-supplied data. </para> @key_compare_func: key comparison function. @key_compare_data: data supplied to the key comparison function each time that it is used. @Returns: A pointer to the newly allocated #GPriq. <!-- ##### FUNCTION g_priq_new_full ##### --> <para> Create a new #Gpriq, not only with a comparison function that takes user-supplied data, but with keys and/or values destroyed by a user-supplied function when they are removed from the queue or the queue is destroyed. </para> @key_compare_func: The key comparison function. @key_compare_data: data supplied to the key function each time it is called @key_destroy_func: a function to destroy keys @value_destroy_func: a function to destroy data items. @Returns: A pointer to the newly allocated #GPriq. <!-- ##### FUNCTION g_priq_insert ##### --> <para> Insert a new key/value pair into a #GPriq. </para> @priq: The #GPriq in which to insert the pair. @key: The key. @value: The corresponding data. <!-- ##### FUNCTION g_priq_nnodes ##### --> <para> Count the number of entries in a #GPriq </para> @priq: The #GPriq to count the number of nodes in. @Returns: The number of nodes in the #GPriq. <!-- ##### FUNCTION g_tree_lookup_extended ##### --> @tree: @lookup_key: @orig_key: @value: @Returns: <!-- ##### FUNCTION g_priq_foreach ##### --> <para> Apply a function to each key/value pair in a #GPriq. This can either be performed in arbitrary order (faster) or in order (slower and requires a temporary copy of the priority queue to be made internally). </para> @priq: The #GPriq to traverse. @inorder: If TRUE, the traversal will be in-order. If FALSE, it will be in arbitrary order. @traverse_func: the function to apply to each key-value pair @user_data: pointer to data to be supplied to each invocation of traverse_func. <!-- ##### FUNCTION g_tree_traverse ##### --> <para> </para> @tree: @traverse_func: @traverse_type: @user_data: <!-- ##### USER_FUNCTION GTraverseFunc ##### --> <para> Specifies the type of function passed to g_tree_traverse(). It is passed the key and value of each node, together with the @user_data parameter passed to g_tree_traverse(). If the function returns %TRUE, the traversal is stopped. </para> @key: a key of a #GTree node. @value: the value corresponding to the key. @data: user data passed to g_tree_traverse(). @Returns: %TRUE to stop the traversal. <!-- ##### ENUM GTraverseType ##### --> <para> Specifies the type of traveral performed by g_tree_traverse(), g_node_traverse() and g_node_find(). </para> @G_IN_ORDER: vists a node's left child first, then the node itself, then its right child. This is the one to use if you want the output sorted according to the compare function. @G_PRE_ORDER: visits a node, then its children. @G_POST_ORDER: visits the node's children, then the node itself. @G_LEVEL_ORDER: is not implemented for <link linkend="glib-Balanced-Binary-Trees">Balanced Binary Trees</link>. For <link linkend="glib-N-ary-Trees">N-ary Trees</link>, it vists the root node first, then its children, then its grandchildren, and so on. Note that this is less efficient than the other orders. <!-- ##### FUNCTION g_tree_search ##### --> <para> </para> @tree: @search_func: @user_data: @Returns: <!-- ##### FUNCTION g_tree_remove ##### --> <para> </para> @tree: @key: <!-- ##### FUNCTION g_tree_steal ##### --> <para> </para> @tree: @key: <!-- ##### FUNCTION g_priq_destroy ##### --> <para> Destroy a #GPriq, freeing all memory allocated for it. If key and/or value destructors were specified using g_priq_new_full() when the queue was created, those destructors will be called on each key and/or value respectively. The items will not be destroyed in an arbitrary order. If not, the programmer is responsible for deallocating that memory, if required. </para> @priq: The the #Gpriq to be destroyed.
Comments: * What's missing here for me is an explanation of: - Why would an application want a priority queue? - What would the advantage be over something simpler, say g_queue_insert_sorted()). Yes, performance, but if we are talking 10-20 items, it's not really relevant. Generally, we don't want to add stuff to GLib just because it is neat data structure. There needs to be a sense that it would offer benefits to a significant fraction of people using GLib. * Generally, it's best to attach patches and source files as attachments instead of putting them into the body of the bug report. It's hard to retrieve them from the body, and they may be corrupted. * Documentation should be done inline with comments by the function definitions. For docs not inline (short and long descriptions), you want to add them in the appropriate file, not in glib-unused.txt, which is basically a junk heap for descriptions not apearing in the text. * While it may be a symptom of a gutter mind, I don't think that GPriq really will work as a name.
A priority queue however is a really good solution to a particular case I have of a soft-real time distributed shared memory/database application where the queues can be on the order of several thousand items (or tens of thousands of items), where g_queue_insert_sorted() is just too expensive. I do agree however that GPriq is a bit, ahem, suggestive when spoken. Might I suggest GPrioQueue with g_prio_queue_* as functions?
Created attachment 55598 [details] GPQueue code and test case I have seen a few other posts requesting a priority queue in Glib too and have found myself needing one for a project just recently. I can see the importance of having a data structure that efficiently maintains a (user-defined) sorted state during pushes() and pop()s. If one were to be added to glib, it would need to have a simple, consistent interface similar to the other data structures, and it shouldn't add a bunch of unnecessary bulk to the library. I experimented with implementing a priority queue in a few ways to compare the performance and code overhead, the goal here was to reuse as much Glib functionality as possible to keep it lightweight. 1. Wrapping GQueue The only additional code required for this method was a call to g_queue_insert_sorted() during push() (of course there are other ways to do it), and a GCompareDataFunc supplied during initialization for sort order. This is probably the way many people think of designing a PQ in a pinch, and it was useful because you could pop() min *and* max, both with constant time. However, the number of comparisons grew way to quickly with N in all cases, and it turned out that this method had the worst performance of the three by a significant margin. 2. Using GPtrArray and Lazy Evaluation The idea here was to have push() stuff pointers on the back of the GArray (for a constant insert time) and lazily sort the array before pops() (sort only if the array was out of sorted order). This method performed the best of the three on average, and only added a few extra lines of code for keeping track of the sorted state but the worst case (e.g. alternating inserts and pops with a heavily populated queue) unfortunately grew very quickly with N. Also, due to the lazy evaluation, the perceived state of the structure may not correspond to the actual state, which may cause trouble for the programmer. So the conclusion here was that, while the much superior average and best case performance was very nice, the deviation in performance for the worst case was too high for a general purpose utility library like Glib. 3. GPtrArray as a Heap The standard Data Structures 101 way to implement a priority queue. I implemented the standard heap algorithm for priority queues using a GPtrArray to store the heap. The major decision here was whether it would be useful to separate the Heap and PQ functionality into GHeap and GPQueue, but I don't see a heap as a generally useful data structure so all heap-specific functions are static and inline(able). The result for this method came up at 200 lines of code for a fairly complete initial interface: GPQueue* g_pqueue_new (GCompareFunc f); void g_pqueue_free (GPQueue *pqueue); void g_pqueue_push (GPQueue *pqueue, gpointer data); gpointer g_pqueue_pop (GPQueue *pqueue); guint g_pqueue_get_length (GPQueue *pqueue); void g_pqueue_foreach (GPQueue *pqueue, GFunc func, gpointer user_data); and push() and pop() perform at a very solid O(lg(n)) in all cases working on element sizes of 100,000 and larger as quickly as expected. I attached a the code and a test case, trying to keep coding consistent with Glib coding practices. I can create a patch against a release or CVS if it would be preferred. Feedback would be appreciated.
Created attachment 55599 [details] GPQueue code and test case Same attachment, not screwing up the content type.
I am having difficulty downloading the attachments using certain browsers. It's probably my fault, but if anyone else is experienceing the same problem the attachment can also be downloaded here: http://ikebo.hypermart.net/glib-pqueue.tar.gz
One should explore using skip-lists as the implementation.
A skip-list (or other binary tree-ish data structure) would be a fairly inefficient way to implement a priority queue compared to an array based one, because: - They have at least two words of overhead (plus malloc/gslice overhead) per stored item on average (maybe more depending on the skip-list implementation). - They have poor cache locality (based on pointer chasing) To the extent a skip-list based data structure makes sense in glib, what needs to be figured out is what API is exposed to applications. In my opinion, that API should be EggSequence, which has already been cutted and pasted into GTK+, nautilus, rhythmbox, and muine. The implementation of it could probably be a skiplist, but in the end it doesn't matter much, because all the pointer-linked O(log n) tree-ish data structures are pretty much equally efficient.
See also bug 575074
*** Bug 575074 has been marked as a duplicate of this bug. ***
Bug #575074 has another in-progress patch which might be useful if this bug is ever picked up and worked on.
-- GitLab Migration Automatic Message -- This bug has been migrated to GNOME's GitLab instance and has been closed from further activity. You can subscribe and participate further through the new bug through this link to our GitLab instance: https://gitlab.gnome.org/GNOME/glib/issues/6.