Make a GTree persistent.
authorDana Jansens <danakj@orodu.net>
Fri, 13 Nov 2009 16:20:47 +0000 (11:20 -0500)
committerDana Jansens <danakj@orodu.net>
Wed, 25 Nov 2009 17:01:11 +0000 (12:01 -0500)
commite5140fdb4ec99728bedab4765bd644f1af674ac4
tree52e5e3200c1781a199315ae009581856b44870d7
parentacc3d292dd50d6b89dd7c93058478f65f782c08f
Make a GTree persistent.

* Change the GTreeNode structure so that it can keep multiple versions of its
navigation pointers.

* Remove left_child and right_child from GTreeNode in favor of parent. For
persistence to work, a node needs to know where its incoming pointers are.
If node->right/left can point to the next/previous node in the tree, then we
might have an incoming pointer from our previous node, but don't have a
pointer to it.  Finding the next/previous node takes up to log(n) time, which
isn't cool to do every time we change a node.  So, if we want next/previous
pointers, we need to always have the pointer, so that it can be recipricated,
and thus would require two extra pointer spots beyond left/right to store that.

Because a node points to its children, they also need to be able to find their
incoming pointer in their parent.  We add a pointer for this, which allows us
to still navigate the tree, and thus we don't need to add next/previous
pointers also.

* Reflect that g_tree_nnodes() now returns the number of nodes for the current
version of the tree.

* Add g_tree_current_version() and g_tree_next_version() functions which
report the current version, and allow you to move the tree into the next
version.  Inserts/deletes after that will occur in the new version only.

* Add g_tree_root_next_version() and g_tree_node_next_version() functions that
move a node or a root pointer into the tree up to the current version of the
tree so that it can be modified (for insert/delete).

Make sure nodes have pointers for the current version when changing them, and
that we always modify the current root pointer into the tree.

When moving a node to the current version of the tree, it's pointer table
may become full, and a new node needs to be created.  Then any nodes with
pointers to the old one need to be updated.

* Add functions g_tree_root_find_version() and g_tree_node_find_version()
that take a version number, and find the pointers which match for
that version (the largest ones <= the version).

* Fix g_tree_remove() and g_tree_steal() for a persistent tree. Free a node's
data and return TRUE for these functions only if it's the last
version of the node in the persistent tree.  Make the functions return FALSE
if the node is found but cannot be removed because it is in an older version
of the tree.

This should help people from freeing things accidentally based on the return
result.

* Make g_tree_node_search() and g_tree_node_find() search for a key within a
given version of the GTree, rather than always in the latest version.

* Make g_tree_destroy_all() delete all versions of everything in the tree.

* Make the new g_tree_lookup_related() function take an argument "version".
This function now searches in the requested version of the tree, rather than
only in the current/latest version.

* Update the debug testing code to check all versions of a persistent tree.

* Add units tests for consistency in all versions of a persistent/versioned
GTree using g_tree_lookup_related().
glib/gtree.c
glib/gtree.h
tests/tree-test.c