2009/10/5 Dana Jansens <d...@cg.scs.carleton.ca>: > 2009/10/5 Mikkel Kamstrup Erlandsen <mikkel.kamst...@gmail.com>: >> Don't let that hold you back. As far as I can imagine I don't have any >> use case ready, but that is probably because I've never had a >> persistent BST at hand :-) >> >> If I where you I'd probably just develop on out-of-tree library for >> the datastructure, keeping the API aligned with glib, and making an >> effort to make it easy to merge to glib should the desire arise. >> >> Then do some lobbying for the lib in some areas where you can see use >> cases. If you can get tracktion from some real world apps, the chances >> of getting into glib are higher. As an alternative you could develop >> the datastructure for the collections library used by Vala; libgee. >> They have a much more rich collections API and are also still less >> frozen API-wise. > > Thanks for your suggestions. > >> I also have a few questions: >> What is the relation to the copy-on-write B-trees like used in Btrfs? >> Can I version sub-trees or is it always the entire tree? > > I'm not very familiar with the copy-on-write trees in Btrfs, but from > reading about it briefly, and from general intuition, it doesn't sound > quite like the same idea, though with the same effect. A simpler > implementation of a persistent BST can simply copy the path from the > root down along any changes for each insert/delete. However this > requires a lot more space than the implementation I am suggesting. > Instead, each node in the tree can keep a history of pointers to its > children, which are changed (and remembered) over time. Only one copy > of any node in the tree ever exists, and only O(1) pointers are > changed to perform an insert/delete. > > The difference to the Btrfs trees is that, in that case, the data is > changing within a node, so you need to copy the old data. In a > persistent BST as proposed, the data within a node is not what is > preserved, but the structure of the tree itself, as the tree evolves > with time. The persistence mechanism is described in this paper [1].
Aha - now I get it :-) Thanks for clearing it up. This sounds mighty interesting; now I just need to figure out what cool things I can use it for :-) -- Cheers, Mikkel _______________________________________________ gtk-devel-list mailing list gtk-devel-list@gnome.org http://mail.gnome.org/mailman/listinfo/gtk-devel-list