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

On Fri, 3 Nov 2006, Yves Mettier wrote:


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:
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;
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;

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:

PS2 : on the cvsweb
(, if you click
on gtree.c
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:


[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]