Remove left_child and right_child from GTreeNode in favor of parent.
authorDana Jansens <danakj@orodu.net>
Mon, 2 Nov 2009 14:51:29 +0000 (09:51 -0500)
committerDana Jansens <danakj@orodu.net>
Thu, 12 Nov 2009 21:54:06 +0000 (16:54 -0500)
commitbf0e75da0778d41845eed6c9556dbb0da3131806
tree89af3d372639822cbf1cc8f9bd1365af153441e4
parent2940a0f63e1009c0ce85ca800bef3b3444f447d2
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.

Also remove test code that tests the right/left pointers as next/prev.
glib/gtree.c