bug in glib/gtree.c (severity=low; easy to fix)
- From: "Yves Mettier" <ymettier libertysurf fr>
- To: gtk-devel-list gnome org
- Cc: timj gtk org, mclasen redhat com
- Subject: bug in glib/gtree.c (severity=low; easy to fix)
- Date: Fri, 3 Nov 2006 11:54:49 +0100 (CET)
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 -
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]