Re: bug in glib/gtree.c (severity=low; easy to fix)

[Tim Janik <timj imendio com>]

On Fri, 3 Nov 2006, Yves Mettier wrote:

> Hi,
>
> I think I found a bug in glib/gtree.c in the structure _GTreeNode :
>
> struct _GTreeNode
> {
>   gpointer   key;         /* key for this node */
>   gpointer   value;       /* value stored at this node */
>   GTreeNode *left;        /* left subtree */
>   GTreeNode *right;       /* right subtree */
>   gint8      balance;     /* height (left) - height (right) */
>   guint8     left_child;
>   guint8     right_child;
> };
>
>
> Shouldn't the comment for "gint8 balance" be "/* height (right) - height (left) */" ?
>
> For example, when you add a node, in g_tree_insert_internal(), you can read this :
> node->left = child;
>               node->left = child;
>               node->left_child = TRUE;
>               node->balance -= 1;
>
> This means that when there is a new node on the left, so when height(left) increases,
> the balance decreases.
>
> If you also have a little time for me, I have 2 questions :
> 1/ Why is the need for "guint8 left_child" and "guint8 right_child" ? Why test
> left_child and right_child instead of left != NULL and right != NULL ?
> I noticed that even when left_child and right_child are false, left and right point to
> nodes that would be before and after in the sorted list of nodes. But I see no use of
> this "feature".

it seems you're simply not familiar with the concept of balanced trees.
to understand what rotation is good for, why its needed, why the flags
are needed etc, you should simply read about the theoretical treatment
and implementation concerns of balanced trees in standard CS literature.
as a start, see this page:
  http://en.wikipedia.org/wiki/Balanced_tree
it also has literature references, i.e. you should be able to find and
read a copy of "The Art of Computer Programming" at your local library.

> 2/ in g_tree_node_rotate_left() (and in g_tree_node_rotate right(), same thing), I can
> read this :
> 1 right = node->right;
> 2
> 3 if (right->left_child)
> 4   node->right = right->left;
> 5 else
> 6   {
> 7     node->right_child = FALSE;
> 8     node->right = right;
> 9     right->left_child = TRUE;
> 10}

you need to consider the rest of the function as well, and to understand
balanced tree rotation in general for this to make sense.
basically, another node is made the root in these functions, which requires
the subtrees to be relinked.

> What does the line 8 exactly ? If you read line 1, line 8 seems to do nothing. Can't you
> remove it ?
>
> I'm asking those questions after an audit of the code that I made before writing an
> article in the French Linux Magazine :)
>
> Yves (who spent a lot of time to understand the algorithm of gtree because of this
> comment :)
>
>
> PS1 : there is no entry for glib nor for gtk+ in the gnome bugzilla. This is why I'm
> writing here.

well, you can try these:
  http://bugzilla.gnome.org/browse.cgi?product=glib
  http://bugzilla.gnome.org/browse.cgi?product=gtk%2B

> PS2 : on the cvsweb
> (http://cvs.gnome.org/bonsai/rview.cgi?cvsroot=/cvs/gnome&dir=glib/glib), if you click
> on gtree.c
> (http://cvs.gnome.org/registry/file.cgi?cvsroot=/cvs/gnome&file=gtree.c&dir=glib/glib),
> the link is broken. I don't know where to report this bug.

not sure where you have this link from, but this one works:
  http://cvs.gnome.org/viewcvs/glib/glib/gtree.c

---
ciaoTJ