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

["Yves Mettier" <ymettier libertysurf fr>]

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".

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}

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.

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.

-- 
- Homepage    - http://ymettier.free.fr - http://www.logicacmg.com -
- GPG key     - http://ymettier.free.fr/gpg.txt                    -
- Maitretarot - http://www.nongnu.org/maitretarot/                 -
- C en action - http://www.oreilly.fr/catalogue/2841772896.html    -