Persistent GTree
Submitted by Dana Jansens
Link to original bug (#602255)
Description
Created attachment 148001 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/
Patch 148001, "1st patch":
0001-Implement-GTree-with-a-treap-instead-of-an-AVL-tree.patch