From c5cab16509e6b803f7b4346500e029c271361ca7 Mon Sep 17 00:00:00 2001
From: Warren Dukes <warren.dukes@gmail.com>
Date: Tue, 1 Aug 2006 00:31:09 +0000
Subject: deletion of tree nodes now works. next is to clean up the code and
 make obvious optimizations

git-svn-id: https://svn.musicpd.org/mpd/trunk@4502 09075e82-0dd4-0310-85a5-a0d7c8717e4f
---
 src/tree.c | 18 +++++++++++++-----
 src/tree.h |  2 +-
 2 files changed, 14 insertions(+), 6 deletions(-)

diff --git a/src/tree.c b/src/tree.c
index 5006e5362..c38d0a904 100644
--- a/src/tree.c
+++ b/src/tree.c
@@ -355,6 +355,7 @@ _MergeNodes(TreeNode * lessNode, TreeNode * moreNode)
 	int j = lessNode->dataCount;
 
 	assert((lessNode->dataCount + moreNode->dataCount) <= DATA_PER_NODE);
+	assert(lessNode->children[j] == NULL);
 
 	for(; i < moreNode->dataCount; i++,j++)
 	{
@@ -444,6 +445,7 @@ _DeleteAt(TreeIterator * iter)
 		{
 			TreeNode ** child;
 			int pos;
+			// XXX : this find is unneccesary!
 			if (_FindPositionInNode(iter->tree,
 					    	node->parent, 
 						tempData, 
@@ -477,11 +479,13 @@ _DeleteAt(TreeIterator * iter)
 				for(; i < (*child)->dataCount-1; i++)
 				{
 					(*child)->data[i] = (*child)->data[i+1];
-					(*child)->children[i+1] =
-						(*child)->children[i+2];
+					(*child)->children[i] =
+						(*child)->children[i+1];
 				}
-				(*child)->children[(*child)->dataCount--] =NULL;
-				(*child)->data[(*child)->dataCount] = NULL;
+				(*child)->children[i] = (*child)->children[i+1];
+				(*child)->children[i+1] =NULL;
+				(*child)->data[i] = NULL;
+				(*child)->dataCount--;
 			}
 			else if (pos > 0 &&
 				 (*(child-1))->dataCount>(CHILDREN_PER_NODE/2))
@@ -493,6 +497,7 @@ _DeleteAt(TreeIterator * iter)
 					node->data[i] = node->data[i-1];
 					node->children[i+1] = node->children[i];
 				}
+				node->children[1] = node->children[0];
 				node->data[0] = node->parent->data[pos-1];
 				node->children[0] = 
 					(*child)->children[(*child)->dataCount];
@@ -663,7 +668,7 @@ InsertIntoTree(Tree * tree, void * data)
 	return 1;
 }
 
-void
+int
 DeleteFromTree(Tree * tree, void * data)
 {
 	TreeIterator iter;
@@ -672,5 +677,8 @@ DeleteFromTree(Tree * tree, void * data)
 	if (_Find(&iter, data))
 	{
 		_DeleteAt(&iter);
+		return 1;
 	}
+
+	return 0;
 }
diff --git a/src/tree.h b/src/tree.h
index 574e9e658..6f53a9145 100644
--- a/src/tree.h
+++ b/src/tree.h
@@ -44,6 +44,6 @@ void * GetDataFromTreeIterator(TreeIterator * iter);
 
 int InsertIntoTree(Tree * tree, void * data);
 
-void DeleteFromTree(Tree * tree, void * data);
+int DeleteFromTree(Tree * tree, void * data);
 
 #endif
-- 
cgit v1.2.3