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.

1 files changed, 67 insertions, 93 deletions

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);
 }