use strset.h instead of tagTracker.h

With a large music database, the linear string collection in
tagTracker.c becomes very slow.  We implemented that in a
quick'n'dirty fashion when we removed tree.c, and now we rewrite it
using the fast hashed string set.

6 files changed, 84 insertions, 173 deletions

diff --git a/src/Makefile.am b/src/Makefile.am
index fcb313418..0592d8e72 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -83,7 +83,6 @@ mpd_headers = \
 	tag.h \
 	tag_pool.h \
 	tag_id3.h \
-	tagTracker.h \
 	utf8.h \
 	strset.h \
 	utils.h \
@@ -142,7 +141,6 @@ mpd_SOURCES = \
 	tag.c \
 	tag_pool.c \
 	tag_id3.c \
-	tagTracker.c \
 	strset.c \
 	utils.c \
 	volume.c \
diff --git a/src/dbUtils.c b/src/dbUtils.c
index d39c9908c..00fa1d441 100644
--- a/src/dbUtils.c
+++ b/src/dbUtils.c
@@ -24,7 +24,7 @@
 #include "playlist.h"
 #include "song.h"
 #include "tag.h"
-#include "tagTracker.h"
+#include "strset.h"
 #include "log.h"
 #include "storedPlaylist.h"
 
@@ -254,7 +254,8 @@ static void freeListCommandItem(ListCommandItem * item)
 	free(item);
 }
 
-static void visitTag(int fd, Song * song, enum tag_type tagType)
+static void visitTag(int fd, struct strset *set,
+		     Song * song, enum tag_type tagType)
 {
 	int i;
 	struct mpd_tag *tag = song->tag;
@@ -269,18 +270,25 @@ static void visitTag(int fd, Song * song, enum tag_type tagType)
 
 	for (i = 0; i < tag->numOfItems; i++) {
 		if (tag->items[i]->type == tagType) {
-			visitInTagTracker(tagType, tag->items[i]->value);
+			strset_add(set, tag->items[i]->value);
 		}
 	}
 }
 
-static int listUniqueTagsInDirectory(int fd, Song * song, void *data)
+struct list_tags_data {
+	int fd;
+	ListCommandItem *item;
+	struct strset *set;
+};
+
+static int listUniqueTagsInDirectory(int fd, Song * song, void *_data)
 {
-	ListCommandItem *item = data;
+	struct list_tags_data *data = _data;
+	ListCommandItem *item = data->item;
 
 	if (tagItemsFoundAndMatches(song, item->numConditionals,
 	                            item->conditionals)) {
-		visitTag(fd, song, item->tagType);
+		visitTag(fd, data->set, song, item->tagType);
 	}
 
 	return 0;
@@ -290,18 +298,28 @@ int listAllUniqueTags(int fd, int type, int numConditionals,
 		      LocateTagItem * conditionals)
 {
 	int ret;
+	struct list_tags_data data;
 	ListCommandItem *item = newListCommandItem(type, numConditionals,
 						   conditionals);
 
+	data.fd = fd;
+	data.item = item;
+
 	if (type >= 0 && type <= TAG_NUM_OF_ITEM_TYPES) {
-		resetVisitedFlagsInTagTracker(type);
+		data.set = strset_new();
 	}
 
-	ret = traverseAllIn(fd, NULL, listUniqueTagsInDirectory, NULL,
-			    (void *)item);
+	ret = traverseAllIn(fd, NULL, listUniqueTagsInDirectory, NULL, &data);
 
 	if (type >= 0 && type <= TAG_NUM_OF_ITEM_TYPES) {
-		printVisitedInTagTracker(fd, type);
+		const char *value;
+
+		strset_rewind(data.set);
+
+		while ((value = strset_next(data.set)) != NULL)
+			fdprintf(fd, "%s: %s\n", mpdTagItemKeys[type], value);
+
+		strset_free(data.set);
 	}
 
 	freeListCommandItem(item);
diff --git a/src/stats.c b/src/stats.c
index 39ba39e9a..c576d2870 100644
--- a/src/stats.c
+++ b/src/stats.c
@@ -1,5 +1,6 @@
 /* the Music Player Daemon (MPD)
  * Copyright (C) 2003-2007 by Warren Dukes (warren.dukes@gmail.com)
+ * Copyright (C) 2008 Max Kellermann <max@duempel.org>
  * This project's homepage is: http://www.musicpd.org
  *
  * This program is free software; you can redistribute it and/or modify
@@ -21,8 +22,10 @@
 #include "directory.h"
 #include "myfprintf.h"
 #include "outputBuffer.h"
-#include "tagTracker.h"
+#include "tag.h"
+#include "strset.h"
 #include "os_compat.h"
+#include "gcc.h"
 
 Stats stats;
 
@@ -32,15 +35,59 @@ void initStats(void)
 	stats.numberOfSongs = 0;
 }
 
+struct visit_data {
+	enum tag_type type;
+	struct strset *set;
+};
+
+static int visit_tag_items(mpd_unused int fd, Song *song, void *_data)
+{
+	const struct visit_data *data = _data;
+	unsigned i;
+
+	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 == data->type)
+			strset_add(data->set, item->value);
+	}
+
+	return 0;
+}
+
+static unsigned int getNumberOfTagItems(int type)
+{
+	struct visit_data data;
+	unsigned int ret;
+
+	data.type = type;
+	data.set = strset_new();
+
+	traverseAllIn(STDERR_FILENO, NULL, visit_tag_items, NULL, &data);
+
+	ret = strset_size(data.set);
+	strset_free(data.set);
+	return ret;
+}
+
 int printStats(int fd)
 {
-	fdprintf(fd, "artists: %i\n", getNumberOfTagItems(TAG_ITEM_ARTIST));
-	fdprintf(fd, "albums: %i\n", getNumberOfTagItems(TAG_ITEM_ALBUM));
-	fdprintf(fd, "songs: %i\n", stats.numberOfSongs);
-	fdprintf(fd, "uptime: %li\n", time(NULL) - stats.daemonStart);
-	fdprintf(fd, "playtime: %li\n",
-		  (long)(ob_get_total_time() + 0.5));
-	fdprintf(fd, "db_playtime: %li\n", stats.dbPlayTime);
-	fdprintf(fd, "db_update: %li\n", getDbModTime());
+	fdprintf(fd,
+		      "artists: %u\n"
+		      "albums: %u\n"
+		      "songs: %i\n"
+		      "uptime: %li\n"
+		      "playtime: %li\n"
+		      "db_playtime: %li\n"
+		      "db_update: %li\n",
+		      getNumberOfTagItems(TAG_ITEM_ARTIST),
+		      getNumberOfTagItems(TAG_ITEM_ALBUM),
+		      stats.numberOfSongs,
+		      time(NULL) - stats.daemonStart,
+		      (long)(ob_get_total_time() + 0.5),
+		      stats.dbPlayTime,
+		      getDbModTime());
 	return 0;
 }
diff --git a/src/tag.c b/src/tag.c
index e5c306eb4..f1acb7c79 100644
--- a/src/tag.c
+++ b/src/tag.c
@@ -23,7 +23,6 @@
 #include "utf8.h"
 #include "log.h"
 #include "conf.h"
-#include "tagTracker.h"
 #include "song.h"
 
 /**
diff --git a/src/tagTracker.c b/src/tagTracker.c
deleted file mode 100644
index bea58ae4c..000000000
--- a/src/tagTracker.c
+++ /dev/null
@@ -1,119 +0,0 @@
-/* the Music Player Daemon (MPD)
- * Copyright (C) 2003-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 "tagTracker.h"
-
-#include "tag.h"
-#include "utils.h"
-#include "myfprintf.h"
-#include "os_compat.h"
-#include "directory.h"
-
-struct visited {
-	struct visited *next;
-
-	/**
-	 * 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 struct visited *visited_heads[TAG_NUM_OF_ITEM_TYPES];
-static unsigned num_visited[TAG_NUM_OF_ITEM_TYPES];
-
-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 (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);
-	}
-
-	return 0;
-}
-
-int getNumberOfTagItems(int type)
-{
-	int ret;
-
-	resetVisitedFlagsInTagTracker(type);
-
-	traverseAllIn(-1, NULL, visit_tag_items, NULL, (void*)(size_t)type);
-
-	ret = (int)num_visited[type];
-	resetVisitedFlagsInTagTracker(type);
-	return ret;
-}
-
-void resetVisitedFlagsInTagTracker(int type)
-{
-	while (visited_heads[type] != NULL) {
-		struct visited *v = visited_heads[type];
-		visited_heads[type] = v->next;
-		free(v);
-	}
-
-	num_visited[type] = 0;
-}
-
-static struct visited *
-find_visit(int type, const char *p)
-{
-	struct visited *v;
-
-	for (v = visited_heads[type]; v != NULL; v = v->next)
-		if (strcmp(v->value, p) == 0)
-			return v;
-
-	return NULL;
-}
-
-void visitInTagTracker(int type, const char *str)
-{
-	struct visited *v = find_visit(type, str);
-	size_t length;
-
-	if (v != NULL)
-		return;
-
-	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)
-{
-	struct visited *v;
-
-	for (v = visited_heads[type]; v != NULL; v = v->next)
-		fdprintf(fd,
-			 "%s: %s\n",
-			 mpdTagItemKeys[type],
-			 v->value);
-}
diff --git a/src/tagTracker.h b/src/tagTracker.h
deleted file mode 100644
index 2edb5aad0..000000000
--- a/src/tagTracker.h
+++ /dev/null
@@ -1,32 +0,0 @@
-/* the Music Player Daemon (MPD)
- * Copyright (C) 2003-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 TAG_TRACKER_H
-#define TAG_TRACKER_H
-
-int getNumberOfTagItems(int type);
-
-void printMemorySavedByTagTracker(void);
-
-void resetVisitedFlagsInTagTracker(int type);
-
-void visitInTagTracker(int type, const char *str);
-
-void printVisitedInTagTracker(int fd, int type);
-
-#endif