Re: High-performance Priority Queue / Heap for glib

[Behdad Esfahbod <behdad behdad org>]

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