[redland-dev] Patch for AVL "tree" storage delete bug

[Aymeric Barthe]

Hello,

It looks like the problem I described previously (see below) is really a
bug of librdf_avltree_delete().

Issue: When nodes are deleted from the trees, their parent pointers are
not updated. The tree is corrupted after calling
librdf_avltree_delete().

I propose the following patch to fix the problem.

Kind Regards,

Aymeric Barthe 
Thomson Reuters


--- rdf_avltree.c	
+++ rdf_avltree.c	
@@ -604,10 +604,14 @@
     if(pr_q->right == NULL) {
       LIBRDF_AVLTREE_DEBUG1("right subtree null\n");
       *node_pp= pr_q->left;
+	  if (*node_pp)
+		(*node_pp)->parent = pr_q->parent;
       *rebalancing_p= TRUE;
     } else if(pr_q->left == NULL) {
       LIBRDF_AVLTREE_DEBUG1("right subtree non-null, left subtree
null\n");
       *node_pp= pr_q->right;
+	  if (*node_pp)
+		(*node_pp)->parent = pr_q->parent;
       *rebalancing_p= TRUE;
     } else {
       LIBRDF_AVLTREE_DEBUG1("neither subtree null\n");
@@ -643,11 +647,15 @@
       librdf_avltree_balance_right(tree, ppr_r, rebalancing_p);
 
   } else {
-    rdata=(*ppr_q)->data;
+	librdf_avltree_node* parent = (*ppr_r)->parent;
+	rdata=(*ppr_q)->data;
 
     (*ppr_q)->data= (*ppr_r)->data;
     *ppr_q= *ppr_r;
     *ppr_r= (*ppr_r)->left;
+
+	if (*ppr_r)
+	  (*ppr_r)->parent = parent;
     *rebalancing_p= TRUE;
   }



-----Original Message-----
From: redland-dev-bounces at lists.librdf.org
[mailto:redland-dev-bounces at lists.librdf.org] On Behalf Of Aymeric
Barthe
Sent: Wednesday, September 24, 2008 11:47 AM
To: redland-dev at lists.librdf.org
Subject: [redland-dev] Possible problem in "tree" storage
implementation. librdf_avltree_delete()

We have a tool using librdf and we recently switched to the experimental
"tree" storage. We have a small rdf database of roughly 200kb that fits
in memory. We make a lot of SPARQL requests and some changes
(add/delete) in the db. We found out that "tree" provides a real
performance boost for our application.

However we have encountered some crashes. I can't provide you with a
sample of code that can reproduce the crash yet, but after investigation
I suspect the librdf_avltree_delete().

The problem is the following. After calling librdf_avltree_delete() (via
librdf_model_remove_statement()) we end up with a corrupted (SPO) tree
in memory. What happens is that the parent of some child node (right or
left) points to an incorrect memory location. 

Basically we end up with (node->left->parent != node) or
(node->right->parent != node).

Have any of you experienced similar troubles with the avl tree storage?
Is this a known problem? If not, I hope to pursue my investigation and
possibly provide a patch on next week. Any idea/advice of how I could
approach the issue? 

Kind Regards,

Aymeric Barthe 
Thomson Reuters



This email was sent to you by Thomson Reuters, the global news and
information company.
Any views expressed in this message are those of the individual sender,
except where the sender specifically states them to be the views of
Thomson Reuters.


_______________________________________________
redland-dev mailing list
redland-dev at lists.librdf.org
http://lists.librdf.org/mailman/listinfo/redland-dev


This email was sent to you by Thomson Reuters, the global news and information company.
Any views expressed in this message are those of the individual sender, except where the sender specifically states them to be the views of Thomson Reuters.