[redland-dev] [Redland RDF API 0000297]: AVL "tree" storage delete bug

[Mantis Bug Tracker]

The following issue has been SUBMITTED. 
====================================================================== 
http://bugs.librdf.org/mantis/view.php?id=297 
====================================================================== 
Reported By:                Dave Beckett
Assigned To:                
====================================================================== 
Project:                    Redland RDF API
Issue ID:                   297
Category:                   api
Reproducibility:            have not tried
Severity:                   minor
Priority:                   normal
Status:                     new
====================================================================== 
Date Submitted:             2009-03-30 04:29
Last Modified:              2009-03-30 04:29
====================================================================== 
Summary:                    AVL "tree" storage delete bug
Description: 
Aymeric Barthe wrote 2008-09-28 to redland-dev: 

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-----
...
To: redland-dev
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? 

...

====================================================================== 

Issue History 
Date Modified    Username       Field                    Change               
====================================================================== 
2009-03-30 04:29 Dave Beckett   New Issue                                    
======================================================================