tree updates:

*) add copyright notice
*) implemented node deletion, but not yet tested

git-svn-id: https://svn.musicpd.org/mpd/trunk@4496 09075e82-0dd4-0310-85a5-a0d7c8717e4f

2 files changed, 246 insertions, 6 deletions

diff --git a/src/tree.c b/src/tree.c
index 58e8a221f..d1f07f74b 100644
--- a/src/tree.c
+++ b/src/tree.c
@@ -1,9 +1,26 @@
+/* the Music Player Daemon (MPD)
+ * (c)2006 by Warren Dukes (warren.dukes@gmail.com)
+ * This project's homepage is: http://www.musicpd.org
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+
 #include "tree.h"
 
 #include <assert.h>
 #include <stdlib.h>
 #include <string.h>
-#include <stdio.h>
 
 #ifndef CHILDREN_PER_NODE
 #define CHILDREN_PER_NODE 3
@@ -111,6 +128,13 @@ _Find(TreeIterator * iter, void * data)
 	}
 }
 
+static void _SetTreeIteratorToRoot(TreeIterator * iter, Tree * tree)
+{
+	iter->tree = tree;
+	iter->node = tree->rootNode;
+	iter->which = 0;
+}
+
 static
 TreeNode *
 _SplitNode(TreeNode * node)
@@ -313,15 +337,201 @@ _InsertAt(TreeIterator * iter, void * data)
 			node = NULL;
 		}
 	}
+}
+
+static
+void
+_MergeNodes(TreeNode * lessNode, TreeNode * moreNode)
+{
+	int i = 0;
+	int j = lessNode->dataCount;
+
+	assert((lessNode->dataCount + moreNode->dataCount) <= DATA_PER_NODE);
+
+	for(; i < moreNode->dataCount; i++,j++)
+	{
+		lessNode->data[j] = moreNode->data[i];
+		lessNode->children[j] = moreNode->children[i];
+		lessNode->children[j]->parent = lessNode;
+	}
+	lessNode->children[j] = moreNode->children[i];
+	lessNode->children[j]->parent = lessNode;
+	lessNode->dataCount = j;
 
-	return;
+	free(moreNode);
 }
 
-static void _SetTreeIteratorToRoot(TreeIterator * iter, Tree * tree)
+static
+void
+_DeleteAt(TreeIterator * iter)
 {
-	iter->tree = tree;
-	iter->node = tree->rootNode;
-	iter->which = 0;
+	TreeNode * node = iter->node;
+	void ** data = &(node->data[iter->which]);
+	void * dataToFree = *data;
+
+	// perculate up data to fill the whole!
+	while (1)
+	{
+		TreeNode ** child = &(node->children[iter->which+1]);
+		void ** childData = NULL;
+
+		if (*child)
+		{
+			assert((*child)->dataCount);
+			childData = &((*child)->data[0]);
+		}
+		else if (*(--child))
+		{
+			assert((*child)->dataCount);
+			childData = &((*child)->data[(*child)->dataCount-1]);
+		}
+		else
+		{
+			// no children!
+			break;
+		}
+
+		// move childData up to parent node
+		*data = *childData;
+
+		// set data and node for next iteration
+		data = childData;
+		node  = *child;
+	}
+
+	void * tempData = *data;
+
+	// move data nodes over, we're at a leaf node, so we can ignore
+	// children
+	void ** leftData = node->data[node->dataCount-1];
+	while (data != leftData)
+	{
+		*(leftData-1) = *leftData;
+		leftData--;
+	}
+	node->data[--(node->dataCount)] = NULL;
+
+	// merge the nodes from the bottom up which have too few data
+	while (node->dataCount < (CHILDREN_PER_NODE/2))
+	{
+		// if we're not the root
+		if (node->parent)
+		{
+			TreeNode ** child;
+			int pos;
+			_FindPositionInNode(iter->tree, 
+					    node->parent, 
+					    tempData, 
+					    &pos);
+			assert(node->parent->children[pos] == node);
+			child = &(node->parent->children[pos]);
+
+			// check siblings for superfulous data
+			if (pos < node->parent->dataCount &&
+			    (*(child+1))->dataCount > (CHILDREN_PER_NODE/2))
+			{
+				child++;
+				node->data[node->dataCount++] = 
+					node->parent->data[pos];
+				node->children[node->dataCount] =
+					(*child)->children[0];
+				node->children[node->dataCount]->parent = node;
+				node->parent->data[pos] =
+					(*child)->data[0];
+				int i = 0;
+				for(; i < (*child)->dataCount-1; i++)
+				{
+					(*child)->data[i] = (*child)->data[i+1];
+					(*child)->children[i+1] =
+						(*child)->children[i+2];
+				}
+				(*child)->children[(*child)->dataCount--] =NULL;
+				(*child)->data[(*child)->dataCount] = NULL;
+			}
+			else if (pos > 0 &&
+				 (*(child-1))->dataCount>(CHILDREN_PER_NODE/2))
+			{
+				child--;
+				int i = node->dataCount++;
+				for(; i > 0; i--)
+				{
+					node->data[i] = node->data[i-1];
+					node->children[i+1] = node->children[i];
+				}
+				node->data[0] = node->parent->data[pos-1];
+				node->children[0] = 
+					(*child)->children[(*child)->dataCount];
+				node->children[0]->parent = node;
+				node->parent->data[pos-1] = 
+					(*child)->data[(*child)->dataCount-1];
+				(*child)->children[(*child)->dataCount--] =NULL;
+				(*child)->data[(*child)->dataCount] = NULL;
+			}
+			else
+			{
+				// merge with one of our siblings
+				if(pos < node->parent->dataCount-1)
+				{
+					child++;
+					assert(*child);
+					pos--;
+
+					tempData = node->parent->data[pos];
+					node->data[node->dataCount++] = 
+						tempData;
+
+					_MergeNodes(node, *child);
+				}
+				else
+				{
+					assert(pos > 0);
+					child--;
+					assert(*child);
+
+					tempData = node->parent->data[pos];
+					(*child)->data[(*child)->dataCount++] = 
+						tempData;
+
+					_MergeNodes(*child, node);
+				}
+
+				int i = pos;
+				for(; i < node->parent->dataCount-1; i++)
+				{
+					node->parent->data[i] =
+						node->parent->data[i+1];
+					node->parent->children[i+1] =
+						node->parent->children[i+2];
+				}
+				node->parent->data[i] = NULL;
+				node->parent->children[i+1] = NULL;
+
+				node = node->parent;
+			}
+		}
+		// this is a root node
+		else 
+		{
+			if (node->dataCount == 0)
+			{
+				if (node->children[0])
+				{
+					node->children[0]->parent = NULL;
+				}
+
+				iter->tree->rootNode = node->children[0];
+
+				free(node);
+			}
+
+			break;
+		}
+	}
+
+	if (iter->tree->freeData)
+	{
+		iter->tree->freeData(dataToFree);
+	}
 }
 
 /************************* PUBLIC METHODS ***********************************/
@@ -411,3 +621,15 @@ InsertIntoTree(Tree * tree, void * data)
 
 	return 1;
 }
+
+void
+DeleteFromTree(Tree * tree, void * data)
+{
+	TreeIterator iter;
+	_SetTreeIteratorToRoot(&iter, tree);
+
+	if (_Find(&iter, data))
+	{
+		_DeleteAt(&iter);
+	}
+}
diff --git a/src/tree.h b/src/tree.h
index c47b15144..574e9e658 100644
--- a/src/tree.h
+++ b/src/tree.h
@@ -1,3 +1,21 @@
+/* the Music Player Daemon (MPD)
+ * (c)2006 by Warren Dukes (warren.dukes@gmail.com)
+ * This project's homepage is: http://www.musicpd.org
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+
 #ifndef TREE_H
 #define TREE_H