use the tree for the tagTracker.

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

4 files changed, 272 insertions, 216 deletions

diff --git a/src/Makefile.am b/src/Makefile.am
index 1dfcd476e..e7f301703 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -68,6 +68,7 @@ mpd_headers = \
 	stats.h \
 	tag.h \
 	tagTracker.h \
+	tree.h \
 	utf8.h \
 	utils.h \
 	volume.h
@@ -116,6 +117,7 @@ mpd_SOURCES = \
 	stats.c \
 	tag.c \
 	tagTracker.c \
+	tree.c \
 	utils.c \
 	volume.c \
 	utf8.c
diff --git a/src/tagTracker.c b/src/tagTracker.c
index b4de6129d..a0ab57d6f 100644
--- a/src/tagTracker.c
+++ b/src/tagTracker.c
@@ -18,12 +18,13 @@
 
 #include "tagTracker.h"
 
-#include "list.h"
+#include "tree.h"
 #include "log.h"
 
 #include <assert.h>
+#include <stdlib.h>
 
-static List *tagLists[TAG_NUM_OF_ITEM_TYPES] = {
+static Tree *tagTrees[TAG_NUM_OF_ITEM_TYPES] = {
 	NULL,
 	NULL,
 	NULL,
@@ -40,129 +41,113 @@ typedef struct tagTrackerItem {
 
 char *getTagItemString(int type, char *string)
 {
-	ListNode *node;
-	int pos;
-
-	if (tagLists[type] == NULL) {
-		tagLists[type] = makeList(free, 1);
-		sortList(tagLists[type]);
+	TreeIterator iter;
+	
+	if (tagTrees[type] == NULL) 
+	{
+		tagTrees[type] = MakeTree((TreeCompareKeyFunction)strcmp, 
+					  (TreeFreeFunction)free, 
+					  (TreeFreeFunction)free);
 	}
 
-	if (findNodeInList(tagLists[type], string, &node, &pos)) {
-		((TagTrackerItem *) node->data)->count++;
-	} else {
+	if (FindInTree(tagTrees[type], string, &iter)) 
+	{
+		((TagTrackerItem *)GetTreeKeyData(&iter).data)->count++;
+		return (char *)GetTreeKeyData(&iter).key;
+	} 
+	else 
+	{
 		TagTrackerItem *item = malloc(sizeof(TagTrackerItem));
 		item->count = 1;
 		item->visited = 0;
-		node = insertInListBeforeNode(tagLists[type], node, pos,
-					      string, item);
+		char * key= strdup(string);
+		InsertInTree(tagTrees[type], key, item);
+		return key;
 	}
-
-	return node->key;
 }
 
 void removeTagItemString(int type, char *string)
 {
-	ListNode *node;
-	int pos;
-
+	TreeIterator iter;
+	
 	assert(string);
 
-	assert(tagLists[type]);
-	if (tagLists[type] == NULL)
+	assert(tagTrees[type]);
+	if (tagTrees[type] == NULL)
 		return;
 
-	if (findNodeInList(tagLists[type], string, &node, &pos)) {
-		TagTrackerItem *item = node->data;
+	if (FindInTree(tagTrees[type], string, &iter)) 
+	{
+		TagTrackerItem * item = 
+			(TagTrackerItem *)GetTreeKeyData(&iter).data;
 		item->count--;
 		if (item->count <= 0)
-			deleteNodeFromList(tagLists[type], node);
+			RemoveFromTreeByIterator(tagTrees[type], &iter);
 	}
 
-	if (tagLists[type]->numberOfNodes == 0) {
-		freeList(tagLists[type]);
-		tagLists[type] = NULL;
+	if (GetTreeSize(tagTrees[type]) == 0) 
+	{
+		FreeTree(tagTrees[type]);
+		tagTrees[type] = NULL;
 	}
 }
 
 int getNumberOfTagItems(int type)
 {
-	if (tagLists[type] == NULL)
+	if (tagTrees[type] == NULL)
 		return 0;
 
-	return tagLists[type]->numberOfNodes;
-}
-
-void printMemorySavedByTagTracker(void)
-{
-	int i;
-	ListNode *node;
-	size_t sum = 0;
-
-	for (i = 0; i < TAG_NUM_OF_ITEM_TYPES; i++) {
-		if (!tagLists[i])
-			continue;
-
-		sum -= sizeof(List);
-
-		node = tagLists[i]->firstNode;
-
-		while (node != NULL) {
-			sum -= sizeof(ListNode);
-			sum -= sizeof(TagTrackerItem);
-			sum -= sizeof(node->key);
-			sum += (strlen(node->key) + 1) * (*((int *)node->data));
-			node = node->nextNode;
-		}
-	}
-
-	DEBUG("saved memory from tags: %li\n", (long)sum);
+	return GetTreeSize(tagTrees[type]);
 }
 
 void resetVisitedFlagsInTagTracker(int type)
 {
-	ListNode *node;
+	TreeIterator iter;
 
-	if (!tagLists[type])
+	if (!tagTrees[type])
 		return;
 
-	node = tagLists[type]->firstNode;
-
-	while (node) {
-		((TagTrackerItem *) node->data)->visited = 0;
-		node = node->nextNode;
+	for (SetTreeIteratorToBegin(tagTrees[type], &iter);
+	     !IsTreeIteratorAtEnd(&iter);
+	     IncrementTreeIterator(&iter))
+	{
+		((TagTrackerItem *)GetTreeKeyData(&iter).data)->visited = 0;
 	}
 }
 
 void visitInTagTracker(int type, char *str)
 {
-	void *item;
+	TreeIterator iter;
 
-	if (!tagLists[type])
+	if (!tagTrees[type])
 		return;
 
-	if (!findInList(tagLists[type], str, &item))
+	if (!FindInTree(tagTrees[type], str, &iter))
 		return;
 
-	((TagTrackerItem *) item)->visited = 1;
+	((TagTrackerItem *)GetTreeKeyData(&iter).data)->visited = 1;
 }
 
 void printVisitedInTagTracker(int fd, int type)
 {
-	ListNode *node;
-	TagTrackerItem *item;
+	TreeIterator iter;
+	TagTrackerItem * item;
 
-	if (!tagLists[type])
+	if (!tagTrees[type])
 		return;
 
-	node = tagLists[type]->firstNode;
-
-	while (node) {
-		item = node->data;
-		if (item->visited) {
-			fdprintf(fd, "%s: %s\n", mpdTagItemKeys[type],
-				 node->key);
+	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);
 		}
-		node = node->nextNode;
 	}
 }
diff --git a/src/tree.c b/src/tree.c
index f5a804a92..74159ab29 100644
--- a/src/tree.c
+++ b/src/tree.c
@@ -37,18 +37,20 @@
 
 struct _TreeNode
 {
-	void * data[DATA_PER_NODE];
+	TreeKeyData keyData[DATA_PER_NODE];
 	struct _TreeNode * parent;
 	short parentPos;
 	struct _TreeNode * children[CHILDREN_PER_NODE];
-	short dataCount;
+	short count;
 };
 
 struct _Tree
 {
-	TreeCompareDataFunction compareData;
-	TreeFreeDataFunction freeData;
+	TreeCompareKeyFunction compareData;
+	TreeFreeFunction freeKey;
+	TreeFreeFunction freeData;
 	TreeNode * rootNode;
+	int size;
 };
 
 /************************* STATIC METHODS ***********************************/
@@ -63,18 +65,25 @@ _MakeNode()
 }
 
 static
+void
+_ClearKeyData(TreeKeyData * keyData)
+{
+	memset(keyData, 0, sizeof(TreeKeyData));
+}
+
+static
 int
-_FindPosition(Tree * tree, TreeNode * node, void * data, int * pos)
+_FindPosition(Tree * tree, TreeNode * node, void * key, int * pos)
 {
 #ifdef USE_BINARY_SEARCH
 	int low = 0;
-	int high = node->dataCount;
+	int high = node->count;
 	int cmp = -1;
 
 	while (high > low)
 	{
 		int cur = (high + low) >> 1;
-		cmp = tree->compareData(data, node->data[cur]);
+		cmp = tree->compareKey(data, node->keyData[cur].key);
 		if (cmp > 0)
 		{
 			low = cur+1;
@@ -96,8 +105,8 @@ _FindPosition(Tree * tree, TreeNode * node, void * data, int * pos)
 	int i = 0;
 	int cmp = -1;
 	for (; 
-	     i < node->dataCount &&
-	     (cmp = tree->compareData(data, node->data[i])) > 0;
+	     i < node->count &&
+	     (cmp = tree->compareData(key, node->keyData[i].key)) > 0;
 	     i++);
 	*pos = i;
 	return (cmp == 0);
@@ -106,11 +115,11 @@ _FindPosition(Tree * tree, TreeNode * node, void * data, int * pos)
 
 static
 int
-_Find(TreeIterator * iter, void * data)
+_Find(TreeIterator * iter, void * key)
 {
 	while (1)
 	{
-		if (_FindPosition(iter->tree, iter->node, data, &iter->which))
+		if (_FindPosition(iter->tree, iter->node, key, &iter->which))
 		{
 			return 1;
 		}
@@ -126,7 +135,7 @@ _Find(TreeIterator * iter, void * data)
 	}
 }
 
-static void _SetTreeIteratorToRoot(TreeIterator * iter, Tree * tree)
+static void _SetIteratorToRoot(Tree * tree, TreeIterator * iter)
 {
 	iter->tree = tree;
 	iter->node = tree->rootNode;
@@ -137,7 +146,7 @@ static
 TreeNode *
 _SplitNode(TreeNode * node)
 {
-	assert(node->dataCount == DATA_PER_NODE);
+	assert(node->count == DATA_PER_NODE);
 
 	TreeNode * newNode = _MakeNode();
 
@@ -145,18 +154,18 @@ _SplitNode(TreeNode * node)
 	int j = 0;
 	for (; i < DATA_PER_NODE; i++, j++)
 	{
-		newNode->data[j] = node->data[i];
+		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;
 		}
-		node->data[i] = NULL;
+		_ClearKeyData(&(node->keyData[i]));
 		node->children[i+1] = NULL;
 	}
-	newNode->dataCount = (DATA_PER_NODE-DATA_PER_NODE/2);
-	node->dataCount -= (DATA_PER_NODE-DATA_PER_NODE/2);
+	newNode->count = (DATA_PER_NODE-DATA_PER_NODE/2);
+	node->count -= (DATA_PER_NODE-DATA_PER_NODE/2);
 
 	return newNode;
 }
@@ -167,17 +176,17 @@ _InsertNodeAndData(Tree * tree,
 		   TreeNode * node,
 		   int pos,
 		   TreeNode * newNode,
-		   void * data)
+		   TreeKeyData keyData)
 {
-	assert(node->dataCount < DATA_PER_NODE);
+	assert(node->count < DATA_PER_NODE);
 #ifdef TREE_DEBUG
-	assert(!newNode || tree->compareData(data, newNode->data[0]) < 0);
+	assert(!newNode || tree->compareData(data, newNode->keyData[0]) < 0);
 #endif
 
-	int j = node->dataCount;
+	int j = node->count;
 	for (; j > pos; j--)
 	{
-		node->data[j] = node->data[j-1];
+		node->keyData[j] = node->keyData[j-1];
 		node->children[j+1] = node->children[j];
 		if (node->children[j+1])
 		{
@@ -187,11 +196,11 @@ _InsertNodeAndData(Tree * tree,
 
 #ifdef TREE_DEBUG
 	assert(!node->children[pos] ||
-	       tree->compareData(data, node->children[pos]->data[0]) > 0);
+	       tree->compareData(data, node->children[pos]->keyData[0]) > 0);
 #endif
 
-	node->data[pos] = data;
-	node->dataCount++;
+	node->keyData[pos] = keyData;
+	node->count++;
 
 	node->children[pos+1] = newNode;
 	if (newNode)
@@ -202,48 +211,47 @@ _InsertNodeAndData(Tree * tree,
 }
 
 static
-void *
+TreeKeyData
 _AddDataToSplitNodes(Tree * tree,
 		     TreeNode * lessNode, 
 		     TreeNode * moreNode,
 		     int pos,
 		     TreeNode * newNode,
-		     void * data)
+		     TreeKeyData keyData)
 {
 #ifdef TREE_DEBUG
 	assert(newNode == NULL ||
-	       tree->compareData(data, newNode->data[0]) < 0);
+	       tree->compareData(data, newNode->keyData[0]) < 0);
 #endif
 	assert(moreNode->children[0] == NULL);
 
-	void * retData;
+	TreeKeyData retKeyData;
 
-	if (pos <= lessNode->dataCount)
+	if (pos <= lessNode->count)
 	{
-		_InsertNodeAndData(tree, lessNode, pos, newNode, data);
-		lessNode->dataCount--;
-		retData = lessNode->data[lessNode->dataCount];
-		lessNode->data[lessNode->dataCount] = NULL;
+		_InsertNodeAndData(tree, lessNode, pos, newNode, keyData);
+		lessNode->count--;
+		retKeyData = lessNode->keyData[lessNode->count];
+		_ClearKeyData(&(lessNode->keyData[lessNode->count]));
 		moreNode->children[0] = 
-			lessNode->children[lessNode->dataCount+1];
+			lessNode->children[lessNode->count+1];
 		if (moreNode->children[0])
 		{
 			moreNode->children[0]->parent = moreNode;
 			moreNode->children[0]->parentPos = 0;
 		}
-		lessNode->children[lessNode->dataCount+1] = NULL;
+		lessNode->children[lessNode->count+1] = NULL;
 	}
 	else
 	{
-		pos -= lessNode->dataCount;
-		retData = moreNode->data[0];
+		pos -= lessNode->count;
+		retKeyData = moreNode->keyData[0];
 		assert(!moreNode->children[0]);
-		assert(!moreNode->data[moreNode->dataCount]);
 
 		int j = 0;
 		for (; j < pos; j++)
 		{
-			moreNode->data[j] = moreNode->data[j+1];
+			moreNode->keyData[j] = moreNode->keyData[j+1];
 			moreNode->children[j] = moreNode->children[j+1];
 			if (moreNode->children[j])
 			{
@@ -251,11 +259,7 @@ _AddDataToSplitNodes(Tree * tree,
 			}
 		}
 
-		assert(!moreNode->children[pos-1] ||
-		       tree->compareData(data,
-			       		 moreNode->children[pos-1]->data[0]) > 0);
-
-		moreNode->data[pos-1] = data;
+		moreNode->keyData[pos-1] = keyData;
 		moreNode->children[pos] = newNode;
 		if (newNode)
 		{
@@ -264,12 +268,12 @@ _AddDataToSplitNodes(Tree * tree,
 		}
 	}
 
-	return retData;
+	return retKeyData;
 }
 
 static
 void
-_InsertAt(TreeIterator * iter, void * data)
+_InsertAt(TreeIterator * iter, TreeKeyData keyData)
 {
 	TreeNode * node = iter->node;
 	TreeNode * insertNode = NULL;
@@ -278,23 +282,23 @@ _InsertAt(TreeIterator * iter, void * data)
 	while (node != NULL)
 	{
 #ifdef TREE_DEBUG
-		assert((pos == node->dataCount ||
-		       iter->tree->compareData(data, node->data[pos]) < 0));
+		assert((pos == node->count ||
+		       iter->tree->compareData(data, node->keyData[pos]) < 0));
 #endif
 
 		// see if there's any NULL data in the current node
-		if (node->dataCount == DATA_PER_NODE)
+		if (node->count == DATA_PER_NODE)
 		{
 			// no open data slots, split this node!
 			TreeNode * newNode = _SplitNode(node);
 
 			// insert data in split nodes
-			data = _AddDataToSplitNodes(iter->tree,
-						    node, 
-						    newNode,
-						    pos,
-						    insertNode,
-						    data);
+			keyData = _AddDataToSplitNodes(iter->tree,
+						       node, 
+						       newNode,
+						       pos,
+						       insertNode,
+						       keyData);
 
 			if (node->parent == NULL)
 			{
@@ -306,8 +310,8 @@ _InsertAt(TreeIterator * iter, void * data)
 				iter->tree->rootNode->children[1] = newNode;
 				newNode->parent = iter->tree->rootNode;
 				newNode->parentPos = 1;
-				iter->tree->rootNode->data[0] = data;
-				iter->tree->rootNode->dataCount = 1;
+				iter->tree->rootNode->keyData[0] = keyData;
+				iter->tree->rootNode->count = 1;
 				return;
 			}
 
@@ -322,7 +326,7 @@ _InsertAt(TreeIterator * iter, void * data)
 					   node,
 					   pos,
 					   insertNode,
-					   data);
+					   keyData);
 			return;
 		}
 	}
@@ -333,16 +337,15 @@ void
 _MergeNodes(TreeNode * lessNode, TreeNode * moreNode)
 {
 	int i = 0;
-	int j = lessNode->dataCount;
+	int j = lessNode->count;
 
-	assert((lessNode->dataCount + moreNode->dataCount) <= DATA_PER_NODE);
+	assert((lessNode->count + moreNode->count) <= DATA_PER_NODE);
 	assert(lessNode->children[j] == NULL);
 
-	for(; i < moreNode->dataCount; i++,j++)
+	for(; i < moreNode->count; i++,j++)
 	{
 		assert(!lessNode->children[j]);
-		assert(!lessNode->data[j]);
-		lessNode->data[j] = moreNode->data[i];
+		lessNode->keyData[j] = moreNode->keyData[i];
 		lessNode->children[j] = moreNode->children[i];
 		if (lessNode->children[j])
 		{
@@ -356,7 +359,7 @@ _MergeNodes(TreeNode * lessNode, TreeNode * moreNode)
 		lessNode->children[j]->parent = lessNode;
 		lessNode->children[j]->parentPos = j;
 	}
-	lessNode->dataCount += i;
+	lessNode->count += i;
 
 	free(moreNode);
 }
@@ -366,8 +369,8 @@ _DeleteAt(TreeIterator * iter)
 {
 	TreeNode * node = iter->node;
 	int pos = iter->which;
-	void ** data = &(node->data[pos]);
-	void * dataToFree = *data;
+	TreeKeyData * keyData = &(node->keyData[pos]);
+	TreeKeyData keyDataToFree = *keyData;
 
 	{
 		// find the least greater than data to fill the whole!
@@ -380,22 +383,22 @@ _DeleteAt(TreeIterator * iter)
 				child = child->children[0];
 			}
 
-			*data = child->data[0];
-			data = &(child->data[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->dataCount])
+			while (child->children[child->count])
 			{
-				pos = child->dataCount;
-				child = child->children[child->dataCount];
+				pos = child->count;
+				child = child->children[child->count];
 			}
 
-			*data = child->data[child->dataCount-1];
-			data = &(child->data[child->dataCount-1]);
+			*keyData = child->keyData[child->count-1];
+			keyData = &(child->keyData[child->count-1]);
 			node = child;
 		}
 		else
@@ -406,15 +409,15 @@ _DeleteAt(TreeIterator * iter)
 
 	// move data nodes over, we're at a leaf node, so we can ignore
 	// children
-	int i = data - node->data;;
-	for (; i < node->dataCount-1; i++)
+	int i = keyData - node->keyData;;
+	for (; i < node->count-1; i++)
 	{
-		node->data[i] = node->data[i+1];
+		node->keyData[i] = node->keyData[i+1];
 	}
-	node->data[--node->dataCount] = NULL;
+	_ClearKeyData(&(node->keyData[--node->count]));
 
 	// merge the nodes from the bottom up which have too few data
-	while (node->dataCount < (DATA_PER_NODE/2))
+	while (node->count < (DATA_PER_NODE/2))
 	{
 		// if we're not the root
 		if (node->parent)
@@ -423,27 +426,28 @@ _DeleteAt(TreeIterator * iter)
 			assert(node->parent->children[pos] == node);
 
 			// check siblings for extra data
-			if (pos < node->parent->dataCount &&
-			    (*(child+1))->dataCount > (DATA_PER_NODE/2))
+			if (pos < node->parent->count &&
+			    (*(child+1))->count > (DATA_PER_NODE/2))
 			{
 				child++;
-				node->data[node->dataCount++] = 
-					node->parent->data[pos];
-				node->children[node->dataCount] =
+				node->keyData[node->count++] = 
+					node->parent->keyData[pos];
+				node->children[node->count] =
 					(*child)->children[0];
-				if (node->children[node->dataCount])
+				if (node->children[node->count])
 				{
-					node->children[node->dataCount]->
+					node->children[node->count]->
 						parent = node;
-					node->children[node->dataCount]->
-						parentPos = node->dataCount;
+					node->children[node->count]->
+						parentPos = node->count;
 				}
-				node->parent->data[pos] =
-					(*child)->data[0];
+				node->parent->keyData[pos] =
+					(*child)->keyData[0];
 				int i = 0;
-				for(; i < (*child)->dataCount-1; i++)
+				for(; i < (*child)->count-1; i++)
 				{
-					(*child)->data[i] = (*child)->data[i+1];
+					(*child)->keyData[i] = 
+						(*child)->keyData[i+1];
 					(*child)->children[i] =
 						(*child)->children[i+1];
 					if ((*child)->children[i])
@@ -458,17 +462,17 @@ _DeleteAt(TreeIterator * iter)
 					(*child)->children[i]->parentPos = i;
 				}
 				(*child)->children[i+1] =NULL;
-				(*child)->data[i] = NULL;
-				(*child)->dataCount--;
+				_ClearKeyData(&((*child)->keyData[i]));
+				(*child)->count--;
 			}
 			else if (pos > 0 &&
-				 (*(child-1))->dataCount>(DATA_PER_NODE/2))
+				 (*(child-1))->count>(DATA_PER_NODE/2))
 			{
 				child--;
-				int i = node->dataCount++;
+				int i = node->count++;
 				for(; i > 0; i--)
 				{
-					node->data[i] = node->data[i-1];
+					node->keyData[i] = node->keyData[i-1];
 					node->children[i+1] = node->children[i];
 					if (node->children[i+1])
 					{
@@ -481,30 +485,31 @@ _DeleteAt(TreeIterator * iter)
 				{
 					node->children[1]->parentPos = 1;
 				}
-				node->data[0] = node->parent->data[pos-1];
+				node->keyData[0] = node->parent->keyData[pos-1];
 				node->children[0] = 
-					(*child)->children[(*child)->dataCount];
+					(*child)->children[(*child)->count];
 				if (node->children[0])
 				{
 					node->children[0]->parent = node;
 					node->children[0]->parentPos = 0;
 				}
-				node->parent->data[pos-1] = 
-					(*child)->data[(*child)->dataCount-1];
-				(*child)->children[(*child)->dataCount--] =
+				node->parent->keyData[pos-1] = 
+					(*child)->keyData[(*child)->count-1];
+				(*child)->children[(*child)->count--] =
 					NULL;
-				(*child)->data[(*child)->dataCount] = NULL;
+				_ClearKeyData(
+					&((*child)->keyData[(*child)->count]));
 			}
 			// merge with one of our siblings
 			else
 			{
-				if (pos < node->parent->dataCount)
+				if (pos < node->parent->count)
 				{
 					child++;
 					assert(*child);
 
-					node->data[node->dataCount++] =
-						node->parent->data[pos];
+					node->keyData[node->count++] =
+						node->parent->keyData[pos];
 
 					_MergeNodes(node, *child);
 				}
@@ -515,18 +520,18 @@ _DeleteAt(TreeIterator * iter)
 					assert(*child);
 					pos--;
 
-					(*child)->data[(*child)->dataCount++] = 
-						node->parent->data[pos];
+					(*child)->keyData[(*child)->count++] = 
+						node->parent->keyData[pos];
 
 					_MergeNodes(*child, node);
 					node = *child;
 				}
 
 				int i = pos;
-				for(; i < node->parent->dataCount-1; i++)
+				for(; i < node->parent->count-1; i++)
 				{
-					node->parent->data[i] =
-						node->parent->data[i+1];
+					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])
@@ -535,9 +540,9 @@ _DeleteAt(TreeIterator * iter)
 							parentPos = i+1;
 					}
 				}
-				node->parent->data[i] = NULL;
+				_ClearKeyData(&(node->parent->keyData[i]));
 				node->parent->children[i+1] = NULL;
-				node->parent->dataCount--;
+				node->parent->count--;
 
 				node = node->parent;
 				pos = node->parentPos;
@@ -546,7 +551,7 @@ _DeleteAt(TreeIterator * iter)
 		// this is a root node
 		else 
 		{
-			if (node->dataCount == 0)
+			if (node->count == 0)
 			{
 				if (node->children[0])
 				{
@@ -563,27 +568,48 @@ _DeleteAt(TreeIterator * iter)
 		}
 	}
 
+	if (iter->tree->freeKey)
+	{
+		iter->tree->freeData(keyDataToFree.key);
+	}
 	if (iter->tree->freeData)
 	{
-		iter->tree->freeData(dataToFree);
+		iter->tree->freeData(keyDataToFree.data);
 	}
 }
 
 /************************* PUBLIC METHODS ***********************************/
 
 Tree *
-MakeTree(TreeCompareDataFunction compareData, TreeFreeDataFunction freeData)
+MakeTree(TreeCompareKeyFunction compareData,
+	 TreeFreeFunction freeKey,
+	 TreeFreeFunction freeData)
 {
 	Tree * ret = malloc(sizeof(Tree));
 	ret->compareData = compareData;
+	ret->freeKey = freeKey;
 	ret->freeData = freeData;
 	ret->rootNode = _MakeNode();
+	ret->size = 0;
 	return ret;
 }
 
-void SetTreeIteratorToBegin(TreeIterator * iter, Tree * tree)
+void
+FreeTree(Tree * tree)
 {
-	_SetTreeIteratorToRoot(iter, 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);
 }
 
@@ -606,7 +632,7 @@ void IncrementTreeIterator(TreeIterator * iter)
 			iter->which++;
 		}
 
-		while (iter->node && iter->which > iter->node->dataCount)
+		while (iter->node && iter->which > iter->node->count)
 		{
 			TreeNode * childNode = iter->node;
 			iter->node = childNode->parent;
@@ -618,54 +644,84 @@ void IncrementTreeIterator(TreeIterator * iter)
 				     iter->which++)
 				{
 					assert(iter->which <= 
-					       iter->node->dataCount);
+					       iter->node->count);
 				}
 				iter->which++;
 			}
 		}
 
 		if (iter->node &&
-		    iter->which > 0 && iter->which <= iter->node->dataCount)
+		    iter->which > 0 && iter->which <= iter->node->count)
 		{
 			return;
 		}
 	}
 }
 
-void *
-GetDataFromTreeIterator(TreeIterator * iter)
+TreeKeyData
+GetTreeKeyData(TreeIterator * iter)
 {
 	assert(iter->node && 
 	       iter->which > 0 && 
-	       iter->which <= iter->node->dataCount);
-	return iter->node->data[iter->which-1];
+	       iter->which <= iter->node->count);
+	return iter->node->keyData[iter->which-1];
 }
 
 int
-InsertIntoTree(Tree * tree, void * data)
+InsertInTree(Tree * tree, void * key, void * data)
 {
+	TreeKeyData keyData = {key, data};
 	TreeIterator iter;
-	_SetTreeIteratorToRoot(&iter, tree);
+	_SetIteratorToRoot(tree, &iter);
 
-	if (_Find(&iter, data))
+	if (_Find(&iter, key))
 	{
 		return 0;
 	}
 
-	_InsertAt(&iter, data);
+	_InsertAt(&iter, keyData);
+	tree->size++;
 
 	return 1;
 }
 
 int
-DeleteFromTree(Tree * tree, void * data)
+RemoveFromTreeByKey(Tree * tree, void * key)
 {
 	TreeIterator iter;
-	_SetTreeIteratorToRoot(&iter, tree);
+	_SetIteratorToRoot(tree, &iter);
 
-	if (_Find(&iter, data))
+	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, void * key, TreeIterator * iter)
+{
+	TreeIterator i;
+	
+	if (iter == NULL)
+	{
+		iter = &i;
+	}
+
+	_SetIteratorToRoot(tree, iter);
+	if (_Find(iter, key))
+	{
+		iter->which++;
 		return 1;
 	}
 
diff --git a/src/tree.h b/src/tree.h
index 6f53a9145..54416a065 100644
--- a/src/tree.h
+++ b/src/tree.h
@@ -22,6 +22,7 @@
 typedef struct _Tree Tree;
 typedef struct _TreeNode TreeNode;
 typedef struct _TreeIterator TreeIterator;
+typedef struct _TreeKeyData TreeKeyData;
 
 struct _TreeIterator
 {
@@ -30,20 +31,32 @@ struct _TreeIterator
 	int which;
 };
 
-typedef int (*TreeCompareDataFunction)(const void * data1, const void * data2);
-typedef void (*TreeFreeDataFunction)(void * data);
+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);
 
-Tree * MakeTree(TreeCompareDataFunction compareFunc, 
-		TreeFreeDataFunction freeData);
+int GetTreeSize(Tree * tree);
 
-void SetTreeIteratorToBegin(TreeIterator * iter, Tree * tree);
+void SetTreeIteratorToBegin(Tree * tree, TreeIterator * iter);
 int IsTreeIteratorAtEnd(const TreeIterator * iter);
 void IncrementTreeIterator(TreeIterator * iter);
 
-void * GetDataFromTreeIterator(TreeIterator * iter);
+TreeKeyData GetTreeKeyData(TreeIterator * iter);
 
-int InsertIntoTree(Tree * tree, void * data);
+int InsertInTree(Tree * tree, void * key, void * data);
+int RemoveFromTreeByKey(Tree * tree, void * key);
+void RemoveFromTreeByIterator(Tree * tree, TreeIterator * iter);
 
-int DeleteFromTree(Tree * tree, void * data);
+int FindInTree(Tree * tree, void * key, TreeIterator * iter /* can be NULL */);
 
 #endif