After an evaluation, GNOME has moved from Bugzilla to GitLab. Learn more about GitLab.
No new issues can be reported in GNOME Bugzilla anymore.
To report an issue in a GNOME project, go to GNOME GitLab.
Do not go to GNOME Gitlab for: Bluefish, Doxygen, GnuCash, GStreamer, java-gnome, LDTP, NetworkManager, Tomboy.
Bug 602255 - Persistent GTree
Persistent GTree
Status: RESOLVED OBSOLETE
Product: glib
Classification: Platform
Component: general
unspecified
Other Linux
: Normal enhancement
: ---
Assigned To: gtkdev
gtkdev
Depends on:
Blocks:
 
 
Reported: 2009-11-17 23:54 UTC by danakj
Modified: 2018-05-24 12:01 UTC
See Also:
GNOME target: ---
GNOME version: ---


Attachments
1st patch (20.53 KB, patch)
2009-11-17 23:54 UTC, danakj
none Details | Review
2nd patch (13.71 KB, patch)
2009-11-17 23:54 UTC, danakj
none Details | Review
3rd patch (56.57 KB, patch)
2009-11-17 23:54 UTC, danakj
none Details | Review
4th patch (11.97 KB, patch)
2009-11-17 23:55 UTC, danakj
none Details | Review
5th patch (22.34 KB, patch)
2009-11-17 23:55 UTC, danakj
none Details | Review
6th patch (9.41 KB, patch)
2009-11-17 23:56 UTC, danakj
none Details | Review

Description danakj 2009-11-17 23:54:02 UTC
Created attachment 148001 [details] [review]
1st patch

Hello,

I've implemented a persistent version of a GTree.  I sent an email to the gtk-devel list about this recently [1], which describes what a persistent binary search tree is, and why I wanted to this.

I have a git repository with the patches in it [2] and I will also attach the necessary patches, created with git-format-patch, to this request.

There is an additional feature in the middle of this, which is to allow searching for the nearest neighbour of a key in a GTree, when the searched key is not present in the tree.  This is in the second patch of the series.

Lastly, I have written a report [3] detailing my implementation decisions, and showing benchmarks comparing the persistent GTree to the current upstream implementation.  The report shows the performance of the persistent trees to be roughly equal to the upstream implementation (a bit faster sometimes, a bit slower sometimes, but by only an epsilon constant factor).

I would definitely like to see this added to upstream, so if you have any issues with the code, or with the interface, let me know and I will address them.  I will include any additional changes as further patches to the attached patch-set.

Thanks!

[1] http://www.mail-archive.com/gtk-devel-list@gnome.org/msg10799.html
[2] http://git.icculus.org/?p=dana/cg-glib.git
[3] http://cg.scs.carleton.ca/~dana/pbst/
Comment 1 danakj 2009-11-17 23:54:36 UTC
Created attachment 148002 [details] [review]
2nd patch
Comment 2 danakj 2009-11-17 23:54:57 UTC
Created attachment 148003 [details] [review]
3rd patch
Comment 3 danakj 2009-11-17 23:55:19 UTC
Created attachment 148004 [details] [review]
4th patch
Comment 4 danakj 2009-11-17 23:55:51 UTC
Created attachment 148005 [details] [review]
5th patch
Comment 5 danakj 2009-11-17 23:56:06 UTC
Created attachment 148006 [details] [review]
6th patch
Comment 6 danakj 2009-11-25 23:21:53 UTC
I would like to point out an additional observation.  The current upstream GTree implementation is a pointer-based structure, as is the persistent GTree implemented in these patches.  And both are near-optimal in their space and performance for a pointer-based structure.  It may be possible in the future to improve the performance of the current GTree some by making it a cache-oblivious data structure, and thus no longer pointer based.  Persistence requires that the structure remain pointer-based in order to work efficiently, and so if this is a serious possibility/requirement, it may be desirable to keep a separate persistent tree implementation.  I'd of course be happy to provide patches to adjust it to that model if that was the case, there's a lot of "if"s involved though, so someone would some idea of/authority on where GTree should be going in the future needs to say something here.
Comment 7 danakj 2010-03-15 14:22:15 UTC
I recently moved my git repositories to a new home.  The same git tree now resides at http://git.openbox.org/?p=dana/cg-glib.git

Thanks.
Comment 8 GNOME Infrastructure Team 2018-05-24 12:01:05 UTC
-- 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/248.