removed tree.c

This patch makes MPD consume much more memory because string pooling
is disabled, but it prepares the next bunch of patches.  Replace the
code in tagTracker.c with naive algorithms without the tree code.  For
now, this should do; later we should find better algorithms,
especially for getNumberOfTagItems(), which has become wasteful with
temporary memory.

4 files changed, 67 insertions, 857 deletions

diff --git a/src/Makefile.am b/src/Makefile.am
index d7deb1190..d7049cd99 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -83,7 +83,6 @@ mpd_headers = \
 	tag.h \
 	tag_id3.h \
 	tagTracker.h \
-	tree.h \
 	utf8.h \
 	utils.h \
 	volume.h \
@@ -141,7 +140,6 @@ mpd_SOURCES = \
 	tag.c \
 	tag_id3.c \
 	tagTracker.c \
-	tree.c \
 	utils.c \
 	volume.c \
 	utf8.c \
diff --git a/src/tagTracker.c b/src/tagTracker.c
index 892cc2955..fdc535823 100644
--- a/src/tagTracker.c
+++ b/src/tagTracker.c
@@ -19,137 +19,111 @@
 #include "tagTracker.h"
 
 #include "tag.h"
-#include "tree.h"
 #include "utils.h"
 #include "myfprintf.h"
 #include "os_compat.h"
+#include "directory.h"
 
-static Tree *tagTrees[TAG_NUM_OF_ITEM_TYPES];
+struct visited {
+	struct visited *next;
 
-typedef struct tagTrackerItem {
-	int count;
-	mpd_sint8 visited;
-} TagTrackerItem;
+	/**
+	 * this is the original pointer passed to visitInTagTracker(),
+	 * i.e. the caller must not invalidate it until he calls
+	 * resetVisitedFlagsInTagTracker().
+	 */
+	const char *value;
+} mpd_packed;
 
-static pthread_mutex_t tag_item_lock = PTHREAD_MUTEX_INITIALIZER;
+static struct visited *visited_heads[TAG_NUM_OF_ITEM_TYPES];
+static unsigned num_visited[TAG_NUM_OF_ITEM_TYPES];
 
-char *getTagItemString(int type, char *string)
+char *getTagItemString(int type mpd_unused, char *string)
 {
-	TreeIterator iter;
-	char *ret;
+	return xstrdup(string);
+}
 
-	pthread_mutex_lock(&tag_item_lock);
+void removeTagItemString(int type mpd_unused, char *string)
+{
+	free(string);
+}
 
-	if (tagTrees[type] == NULL)
-	{
-		tagTrees[type] = MakeTree((TreeCompareKeyFunction)strcmp,
-					  (TreeFreeFunction)free,
-					  (TreeFreeFunction)free);
-	}
+static int visit_tag_items(int fd mpd_unused, Song *song, void *data)
+{
+	enum tag_type type = (enum tag_type)(size_t)data;
+	unsigned i;
 
-	if (FindInTree(tagTrees[type], string, &iter))
-	{
-		((TagTrackerItem *)GetTreeKeyData(&iter)->data)->count++;
-		ret = (char *)GetTreeKeyData(&iter)->key;
-	}
-	else
-	{
-		TagTrackerItem *item = xmalloc(sizeof(TagTrackerItem));
-		char *key = xstrdup(string);
-		item->count = 1;
-		item->visited = 0;
-		InsertInTree(tagTrees[type], key, item);
-		ret = key;
+	if (song->tag == NULL)
+		return 0;
+
+	for (i = 0; i < (unsigned)song->tag->numOfItems; ++i) {
+		const struct tag_item *item = song->tag->items[i];
+		if (item->type == type)
+			visitInTagTracker(type, item->value);
 	}
 
-	pthread_mutex_unlock(&tag_item_lock);
-	return ret;
+	return 0;
 }
 
-void removeTagItemString(int type, char *string)
+int getNumberOfTagItems(int type)
 {
-	TreeIterator iter;
+	int ret;
 
-	assert(string);
+	resetVisitedFlagsInTagTracker(type);
 
-	assert(tagTrees[type]);
-	if (tagTrees[type] == NULL)
-		return;
+	traverseAllIn(-1, NULL, visit_tag_items, NULL, (void*)(size_t)type);
 
-	pthread_mutex_lock(&tag_item_lock);
-	if (FindInTree(tagTrees[type], string, &iter))
-	{
-		TagTrackerItem * item =
-			(TagTrackerItem *)GetTreeKeyData(&iter)->data;
-		item->count--;
-		if (item->count <= 0)
-			RemoveFromTreeByIterator(tagTrees[type], &iter);
-	}
-
-	if (GetTreeSize(tagTrees[type]) == 0)
-	{
-		FreeTree(tagTrees[type]);
-		tagTrees[type] = NULL;
-	}
-	pthread_mutex_unlock(&tag_item_lock);
+	ret = (int)num_visited[type];
+	resetVisitedFlagsInTagTracker(type);
+	return ret;
 }
 
-int getNumberOfTagItems(int type)
+void resetVisitedFlagsInTagTracker(int type)
 {
-	if (tagTrees[type] == NULL)
-		return 0;
+	while (visited_heads[type] != NULL) {
+		struct visited *v = visited_heads[type];
+		visited_heads[type] = v->next;
+		free(v);
+	}
 
-	return GetTreeSize(tagTrees[type]);
+	num_visited[type] = 0;
 }
 
-void resetVisitedFlagsInTagTracker(int type)
+static struct visited *
+find_visit(int type, const char *p)
 {
-	TreeIterator iter;
+	struct visited *v;
 
-	if (!tagTrees[type])
-		return;
+	for (v = visited_heads[type]; v != NULL; v = v->next)
+		if (strcmp(v->value, p) == 0)
+			return v;
 
-	for (SetTreeIteratorToBegin(tagTrees[type], &iter);
-	     !IsTreeIteratorAtEnd(&iter);
-	     IncrementTreeIterator(&iter))
-	{
-		((TagTrackerItem *)GetTreeKeyData(&iter)->data)->visited = 0;
-	}
+	return NULL;
 }
 
 void visitInTagTracker(int type, const char *str)
 {
-	TreeIterator iter;
-
-	if (!tagTrees[type])
-		return;
+	struct visited *v = find_visit(type, str);
+	size_t length;
 
-	if (!FindInTree(tagTrees[type], str, &iter))
+	if (v != NULL)
 		return;
 
-	((TagTrackerItem *)GetTreeKeyData(&iter)->data)->visited = 1;
+	length = strlen(str);
+	v = xmalloc(sizeof(*v));
+	v->value = str;
+	v->next = visited_heads[type];
+	visited_heads[type] = v;
+	++num_visited[type];
 }
 
 void printVisitedInTagTracker(int fd, int type)
 {
-	TreeIterator iter;
-	TagTrackerItem * item;
+	struct visited *v;
 
-	if (!tagTrees[type])
-		return;
-
-	for (SetTreeIteratorToBegin(tagTrees[type], &iter);
-	     !IsTreeIteratorAtEnd(&iter);
-	     IncrementTreeIterator(&iter))
-	{
-		item = ((TagTrackerItem *)GetTreeKeyData(&iter)->data);
-
-		if (item->visited)
-		{
-			fdprintf(fd,
-				 "%s: %s\n",
-				 mpdTagItemKeys[type],
-				 (char *)GetTreeKeyData(&iter)->key);
-		}
-	}
+	for (v = visited_heads[type]; v != NULL; v = v->next)
+		fdprintf(fd,
+			 "%s: %s\n",
+			 mpdTagItemKeys[type],
+			 v->value);
 }
diff --git a/src/tree.c b/src/tree.c
deleted file mode 100644
index d583aee7c..000000000
--- a/src/tree.c
+++ /dev/null
@@ -1,699 +0,0 @@
-/* the Music Player Daemon (MPD)
- * Copyright (C) 2006-2007 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 "utils.h"
-#include "os_compat.h"
-
-#ifndef CHILDREN_PER_NODE
-#define CHILDREN_PER_NODE 25
-#endif
-
-#define DATA_PER_NODE (CHILDREN_PER_NODE-1)
-
-#if CHILDREN_PER_NODE > 7
-#define USE_BINARY_SEARCH 1
-#endif
-
-
-/************************* DATA STRUCTURES **********************************/
-
-struct _TreeNode
-{
-	TreeKeyData keyData[DATA_PER_NODE];
-	struct _TreeNode * parent;
-	short parentPos;
-	struct _TreeNode * children[CHILDREN_PER_NODE];
-	short count;
-};
-
-struct _Tree
-{
-	TreeCompareKeyFunction compareKey;
-	TreeFreeFunction freeKey;
-	TreeFreeFunction freeData;
-	TreeNode * rootNode;
-	int size;
-};
-
-/************************* STATIC METHODS ***********************************/
-
-static
-TreeNode *
-_MakeNode(void)
-{
-	TreeNode * ret = xmalloc(sizeof(TreeNode));
-	memset(ret, 0, sizeof(TreeNode));
-	return ret;
-}
-
-static
-void
-_ClearKeyData(TreeKeyData * keyData)
-{
-	memset(keyData, 0, sizeof(TreeKeyData));
-}
-
-static
-int
-_FindPosition(Tree * tree, TreeNode * node, const void * key, int * pos)
-{
-#ifdef USE_BINARY_SEARCH
-	int low = 0;
-	int high = node->count;
-	int cmp = -1;
-
-	while (high > low)
-	{
-		int cur = (high + low) >> 1;
-		cmp = tree->compareKey(key, node->keyData[cur].key);
-		if (cmp > 0)
-		{
-			low = cur+1;
-		}
-		else if (cmp < 0)
-		{
-			high = cur;
-		}
-		else
-		{
-			low = cur;
-			break;
-		}
-	}
-
-	*pos = low;
-	return (cmp == 0);
-#else
-	int i = 0;
-	int cmp = -1;
-	for (; 
-	     i < node->count &&
-	     (cmp = tree->compareKey(key, node->keyData[i].key)) > 0;
-	     i++);
-	*pos = i;
-	return (cmp == 0);
-#endif
-}
-
-static
-int
-_Find(TreeIterator * iter, const void * key)
-{
-	while (1)
-	{
-		if (_FindPosition(iter->tree, iter->node, key, &iter->which))
-		{
-			iter->which++;
-			return 1;
-		}
-
-		if (iter->node->children[iter->which])
-		{
-			iter->node = iter->node->children[iter->which];
-		}
-		else
-		{
-			return 0;
-		}
-	}
-}
-
-static void _SetIteratorToRoot(Tree * tree, TreeIterator * iter)
-{
-	iter->tree = tree;
-	iter->node = tree->rootNode;
-	iter->which = 0;
-}
-
-static
-TreeNode *
-_SplitNode(TreeNode * node)
-{
-	TreeNode *newNode = _MakeNode();
-	int i = DATA_PER_NODE/2;
-	int j = 0;
-
-	assert(node->count == DATA_PER_NODE);
-
-	for (; i < DATA_PER_NODE; i++, j++)
-	{
-		newNode->keyData[j] = node->keyData[i];
-		newNode->children[j+1] = node->children[i+1];
-		if (newNode->children[j+1])
-		{
-			newNode->children[j+1]->parent = newNode;
-			newNode->children[j+1]->parentPos = j+1;
-		}
-		_ClearKeyData(&(node->keyData[i]));
-		node->children[i+1] = NULL;
-	}
-	newNode->count = (DATA_PER_NODE-DATA_PER_NODE/2);
-	node->count -= (DATA_PER_NODE-DATA_PER_NODE/2);
-
-	return newNode;
-}
-
-static
-void
-_InsertNodeAndData(TreeNode * node,
-		   int pos,
-		   TreeNode * newNode,
-		   TreeKeyData keyData)
-{
-	int j = node->count;
-
-	assert(node->count < DATA_PER_NODE);
-
-	for (; j > pos; j--)
-	{
-		node->keyData[j] = node->keyData[j-1];
-		node->children[j+1] = node->children[j];
-		if (node->children[j+1])
-		{
-			node->children[j+1]->parentPos = j+1;
-		}
-	}
-
-	node->keyData[pos] = keyData;
-	node->count++;
-
-	node->children[pos+1] = newNode;
-	if (newNode)
-	{
-		newNode->parent = node;
-		newNode->parentPos = pos+1;
-	}
-}
-
-static
-TreeKeyData
-_AddDataToSplitNodes(TreeNode * lessNode,
-		     TreeNode * moreNode,
-		     int pos,
-		     TreeNode * newNode,
-		     TreeKeyData keyData)
-{
-	TreeKeyData retKeyData;
-
-	assert(moreNode->children[0] == NULL);
-
-	if (pos <= lessNode->count)
-	{
-		_InsertNodeAndData(lessNode, pos, newNode, keyData);
-		lessNode->count--;
-		retKeyData = lessNode->keyData[lessNode->count];
-		_ClearKeyData(&(lessNode->keyData[lessNode->count]));
-		moreNode->children[0] = 
-			lessNode->children[lessNode->count+1];
-		if (moreNode->children[0])
-		{
-			moreNode->children[0]->parent = moreNode;
-			moreNode->children[0]->parentPos = 0;
-		}
-		lessNode->children[lessNode->count+1] = NULL;
-	}
-	else
-	{
-		int j;
-
-		pos -= lessNode->count;
-		retKeyData = moreNode->keyData[0];
-		assert(!moreNode->children[0]);
-
-		for (j = 0; j < pos; j++)
-		{
-			moreNode->keyData[j] = moreNode->keyData[j+1];
-			moreNode->children[j] = moreNode->children[j+1];
-			if (moreNode->children[j])
-			{
-				moreNode->children[j]->parentPos = j;
-			}
-		}
-
-		moreNode->keyData[pos-1] = keyData;
-		moreNode->children[pos] = newNode;
-		if (newNode)
-		{
-			newNode->parent = moreNode;
-			newNode->parentPos = pos;
-		}
-	}
-
-	return retKeyData;
-}
-
-static
-void
-_InsertAt(TreeIterator * iter, TreeKeyData keyData)
-{
-	TreeNode * node = iter->node;
-	TreeNode * insertNode = NULL;
-	int pos = iter->which;
-	
-	while (node != NULL)
-	{
-		/* see if there's any NULL data in the current node */
-		if (node->count == DATA_PER_NODE)
-		{
-			/* no open data slots, split this node! */
-			TreeNode * newNode = _SplitNode(node);
-
-			/* insert data in split nodes */
-			keyData = _AddDataToSplitNodes(node,
-						       newNode,
-						       pos,
-						       insertNode,
-						       keyData);
-
-			if (node->parent == NULL)
-			{
-				assert(node == iter->tree->rootNode);
-				iter->tree->rootNode = _MakeNode();
-				iter->tree->rootNode->children[0] = node;
-				node->parent = iter->tree->rootNode;
-				node->parentPos = 0;
-				iter->tree->rootNode->children[1] = newNode;
-				newNode->parent = iter->tree->rootNode;
-				newNode->parentPos = 1;
-				iter->tree->rootNode->keyData[0] = keyData;
-				iter->tree->rootNode->count = 1;
-				return;
-			}
-
-			pos = node->parentPos;
-			node = node->parent;
-			insertNode = newNode;
-		}
-		else
-		{
-			/* insert the data and newNode */
-			_InsertNodeAndData(node,
-					   pos,
-					   insertNode,
-					   keyData);
-			return;
-		}
-	}
-}
-
-static
-void
-_MergeNodes(TreeNode * lessNode, TreeNode * moreNode)
-{
-	int i = 0;
-	int j = lessNode->count;
-
-	assert((lessNode->count + moreNode->count) <= DATA_PER_NODE);
-	assert(lessNode->children[j] == NULL);
-
-	for(; i < moreNode->count; i++,j++)
-	{
-		assert(!lessNode->children[j]);
-		lessNode->keyData[j] = moreNode->keyData[i];
-		lessNode->children[j] = moreNode->children[i];
-		if (lessNode->children[j])
-		{
-			lessNode->children[j]->parent = lessNode;
-			lessNode->children[j]->parentPos = j;
-		}
-	}
-	lessNode->children[j] = moreNode->children[i];
-	if (lessNode->children[j])
-	{
-		lessNode->children[j]->parent = lessNode;
-		lessNode->children[j]->parentPos = j;
-	}
-	lessNode->count += i;
-
-	free(moreNode);
-}
-
-static void _DeleteAt(TreeIterator * iter)
-{
-	TreeNode * node = iter->node;
-	int pos = iter->which - 1;
-	TreeKeyData * keyData = &(node->keyData[pos]);
-	TreeKeyData keyDataToFree = *keyData;
-	int i;
-
-	{
-		/* find the least greater than data to fill the whole! */
-		if (node->children[pos+1])
-		{
-			TreeNode * child = node->children[++pos];
-			while (child->children[0])
-			{
-				pos = 0;
-				child = child->children[0];
-			}
-
-			*keyData = child->keyData[0];
-			keyData = &(child->keyData[0]);
-			node = child;
-		}
-		/* or the greatest lesser than data to fill the whole! */
-		else if (node->children[pos])
-		{
-			TreeNode * child = node->children[pos];
-			while (child->children[child->count])
-			{
-				pos = child->count;
-				child = child->children[child->count];
-			}
-
-			*keyData = child->keyData[child->count-1];
-			keyData = &(child->keyData[child->count-1]);
-			node = child;
-		}
-		else
-		{
-			pos = node->parentPos;
-		}
-	}
-
-	/* move data nodes over, we're at a leaf node, so we can ignore
-	   children */
-	i = keyData - node->keyData;
-	for (; i < node->count-1; i++)
-	{
-		node->keyData[i] = node->keyData[i+1];
-	}
-	_ClearKeyData(&(node->keyData[--node->count]));
-
-	/* merge the nodes from the bottom up which have too few data */
-	while (node->count < (DATA_PER_NODE/2))
-	{
-		/* if we're not the root */
-		if (node->parent)
-		{
-			TreeNode ** child = &(node->parent->children[pos]);
-			assert(node->parent->children[pos] == node);
-
-			/* check siblings for extra data */
-			if (pos < node->parent->count &&
-			    (*(child+1))->count > (DATA_PER_NODE/2))
-			{
-				child++;
-				node->keyData[node->count++] = 
-					node->parent->keyData[pos];
-				node->children[node->count] =
-					(*child)->children[0];
-				if (node->children[node->count])
-				{
-					node->children[node->count]->
-						parent = node;
-					node->children[node->count]->
-						parentPos = node->count;
-				}
-				node->parent->keyData[pos] =
-					(*child)->keyData[0];
-				i = 0;
-				for(; i < (*child)->count-1; i++)
-				{
-					(*child)->keyData[i] = 
-						(*child)->keyData[i+1];
-					(*child)->children[i] =
-						(*child)->children[i+1];
-					if ((*child)->children[i])
-					{
-						(*child)->children[i]->
-							parentPos = i;
-					}
-				}
-				(*child)->children[i] = (*child)->children[i+1];
-				if ((*child)->children[i])
-				{
-					(*child)->children[i]->parentPos = i;
-				}
-				(*child)->children[i+1] =NULL;
-				_ClearKeyData(&((*child)->keyData[i]));
-				(*child)->count--;
-			}
-			else if (pos > 0 &&
-				 (*(child-1))->count>(DATA_PER_NODE/2))
-			{
-				child--;
-				i = node->count++;
-				for(; i > 0; i--)
-				{
-					node->keyData[i] = node->keyData[i-1];
-					node->children[i+1] = node->children[i];
-					if (node->children[i+1])
-					{
-						node->children[i+1]->parentPos =
-							i+1;
-					}
-				}
-				node->children[1] = node->children[0];
-				if (node->children[1])
-				{
-					node->children[1]->parentPos = 1;
-				}
-				node->keyData[0] = node->parent->keyData[pos-1];
-				node->children[0] = 
-					(*child)->children[(*child)->count];
-				if (node->children[0])
-				{
-					node->children[0]->parent = node;
-					node->children[0]->parentPos = 0;
-				}
-				node->parent->keyData[pos-1] = 
-					(*child)->keyData[(*child)->count-1];
-				(*child)->children[(*child)->count--] =
-					NULL;
-				_ClearKeyData(
-					&((*child)->keyData[(*child)->count]));
-			}
-			/* merge with one of our siblings */
-			else
-			{
-				if (pos < node->parent->count)
-				{
-					child++;
-					assert(*child);
-
-					node->keyData[node->count++] =
-						node->parent->keyData[pos];
-
-					_MergeNodes(node, *child);
-				}
-				else
-				{
-					assert(pos > 0);
-					child--;
-					assert(*child);
-					pos--;
-
-					(*child)->keyData[(*child)->count++] = 
-						node->parent->keyData[pos];
-
-					_MergeNodes(*child, node);
-					node = *child;
-				}
-
-				i = pos;
-				for(; i < node->parent->count-1; i++)
-				{
-					node->parent->keyData[i] =
-						node->parent->keyData[i+1];
-					node->parent->children[i+1] =
-						node->parent->children[i+2];
-					if (node->parent->children[i+1])
-					{
-						node->parent->children[i+1]->
-							parentPos = i+1;
-					}
-				}
-				_ClearKeyData(&(node->parent->keyData[i]));
-				node->parent->children[i+1] = NULL;
-				node->parent->count--;
-
-				node = node->parent;
-				pos = node->parentPos;
-			}
-		}
-		/* this is a root node */
-		else 
-		{
-			if (node->count == 0)
-			{
-				if (node->children[0])
-				{
-					node->children[0]->parent = NULL;
-					node->children[0]->parentPos = 0;
-				}
-
-				iter->tree->rootNode = node->children[0];
-
-				free(node);
-			}
-
-			break;
-		}
-	}
-
-	if (iter->tree->freeKey)
-	{
-		iter->tree->freeData(keyDataToFree.key);
-	}
-	if (iter->tree->freeData)
-	{
-		iter->tree->freeData(keyDataToFree.data);
-	}
-}
-
-/************************* PUBLIC METHODS ***********************************/
-
-Tree *
-MakeTree(TreeCompareKeyFunction compareKey,
-	 TreeFreeFunction freeKey,
-	 TreeFreeFunction freeData)
-{
-	Tree * ret = xmalloc(sizeof(Tree));
-	ret->compareKey = compareKey;
-	ret->freeKey = freeKey;
-	ret->freeData = freeData;
-	ret->rootNode = _MakeNode();
-	ret->size = 0;
-	return ret;
-}
-
-void
-FreeTree(Tree * tree)
-{
-	assert(tree->rootNode == NULL);
-	free(tree);
-}
-
-int
-GetTreeSize(Tree * tree)
-{
-	return tree->size;
-}
-
-void SetTreeIteratorToBegin(Tree * tree, TreeIterator * iter)
-{
-	_SetIteratorToRoot(tree, iter);
-	IncrementTreeIterator(iter);
-}
-
-int IsTreeIteratorAtEnd(const TreeIterator * iter)
-{
-	return (iter->node == NULL);
-}
-
-void IncrementTreeIterator(TreeIterator * iter)
-{
-	while(iter->node)
-	{
-		if (iter->node->children[iter->which])
-		{
-			iter->node = iter->node->children[iter->which];
-			iter->which = 0;
-		}
-		else
-		{
-			iter->which++;
-		}
-
-		while (iter->node && iter->which > iter->node->count)
-		{
-			iter->which = iter->node->parentPos + 1;
-			iter->node = iter->node->parent;
-		}
-
-		if (iter->node &&
-		    iter->which > 0 && iter->which <= iter->node->count)
-		{
-			return;
-		}
-	}
-}
-
-const TreeKeyData *
-GetTreeKeyData(TreeIterator * iter)
-{
-	assert(iter->node && 
-	       iter->which > 0 && 
-	       iter->which <= iter->node->count);
-	return &iter->node->keyData[iter->which-1];
-}
-
-int
-InsertInTree(Tree * tree, void * key, void * data)
-{
-	TreeKeyData keyData;
-	TreeIterator iter;
-
-	_SetIteratorToRoot(tree, &iter);
-
-	if (_Find(&iter, key))
-	{
-		return 0;
-	}
-
-	keyData.key = key;
-	keyData.data = data;
-	_InsertAt(&iter, keyData);
-	tree->size++;
-
-	return 1;
-}
-
-int
-RemoveFromTreeByKey(Tree * tree, void * key)
-{
-	TreeIterator iter;
-	_SetIteratorToRoot(tree, &iter);
-
-	if (_Find(&iter, key))
-	{
-		_DeleteAt(&iter);
-		tree->size--;
-		return 1;
-	}
-
-	return 0;
-}
-
-void
-RemoveFromTreeByIterator(Tree * tree, TreeIterator * iter)
-{
-	_DeleteAt(iter);
-	tree->size--;
-}
-
-int
-FindInTree(Tree * tree, const void * key, TreeIterator * iter)
-{
-	TreeIterator i;
-	
-	if (iter == NULL)
-	{
-		iter = &i;
-	}
-
-	_SetIteratorToRoot(tree, iter);
-	if (_Find(iter, key))
-	{
-		return 1;
-	}
-
-	return 0;
-}
diff --git a/src/tree.h b/src/tree.h
deleted file mode 100644
index ef397bbd4..000000000
--- a/src/tree.h
+++ /dev/null
@@ -1,63 +0,0 @@
-/* the Music Player Daemon (MPD)
- * Copyright (C) 2006-2007 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
-
-typedef struct _Tree Tree;
-typedef struct _TreeNode TreeNode;
-typedef struct _TreeIterator TreeIterator;
-typedef struct _TreeKeyData TreeKeyData;
-
-struct _TreeIterator
-{
-	Tree * tree;
-	TreeNode * node;
-	int which;
-};
-
-struct _TreeKeyData
-{
-	void * key;
-	void * data;
-};
-
-typedef int (*TreeCompareKeyFunction)(const void * key1, const void * key2);
-typedef void (*TreeFreeFunction)(void * data);
-
-Tree * MakeTree(TreeCompareKeyFunction compareFunc, 
-		TreeFreeFunction freeKey,
-		TreeFreeFunction freeData);
-void FreeTree(Tree * tree);
-
-int GetTreeSize(Tree * tree);
-
-void SetTreeIteratorToBegin(Tree * tree, TreeIterator * iter);
-int IsTreeIteratorAtEnd(const TreeIterator * iter);
-void IncrementTreeIterator(TreeIterator * iter);
-
-const TreeKeyData *GetTreeKeyData(TreeIterator * iter);
-
-int InsertInTree(Tree * tree, void * key, void * data);
-int RemoveFromTreeByKey(Tree * tree, void * key);
-void RemoveFromTreeByIterator(Tree * tree, TreeIterator * iter);
-
-int FindInTree(Tree * tree, const void * key,
-	       TreeIterator * iter /* can be NULL */);
-
-#endif