Priority queue for glib
Submitted by rgm..@..ra.net
Link to original bug (#107082)
Description
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 @@
+
+<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>
+
+
+
+<para>
+#GTree
+</para>
+
+
+
+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.
+
+
+
+Priority Queues
+
+
<para>
@@ -100,6 +146,13 @@ @G_MATCH_EXACT: a pattern matching exactly one string. @G_MATCH_LAST:
+
+<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>
+
+
<para>
Specifies the type of function passed to g_set_warning_handler().
@@ -277,6 +330,79 @@
</para>
@mem: the memory to check.
+
+
+<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.
+
+
+<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.
+
+
+<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.
+
+
+<para>
+Create a new #GPriq.
+</para>
+
+@key_compare_func: Key comparison function.
+@Returns: A pointer to the newly allocated #GPriq.
+
+
+<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.
+
+
+<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.
+
+
+<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.
<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 */
Priority Queues
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.
<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>
<para>
#GTree
</para>
<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>
<para>
Create a new #GPriq.
</para>
@key_compare_func: Key comparison function.
@Returns: A pointer to the newly allocated #GPriq.
<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.
<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.
<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.
<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.
@tree: @lookup_key: @orig_key: @value: @Returns:
<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.
<para>
</para>
@tree: @traverse_func: @traverse_type: @user_data:
<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.
<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.
<para>
</para>
@tree: @search_func: @user_data: @Returns:
<para>
</para>
@tree: @key:
<para>
</para>
@tree: @key:
<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.