merge changes from mpd-tree:

-use tree for tagTracker
-eliminate the master process

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

12 files changed, 916 insertions, 295 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/directory.c b/src/directory.c
index da4b0a4eb..9b90418f2 100644
--- a/src/directory.c
+++ b/src/directory.c
@@ -173,6 +173,7 @@ int updateInit(int fd, List * pathList)
 	if (directory_updatePid == 0) {
 		/* child */
 		int dbUpdated = 0;
+		clearPlayerPid();
 
 		unblockSignals();
 
diff --git a/src/main.c b/src/main.c
index d06202857..30324cea2 100644
--- a/src/main.c
+++ b/src/main.c
@@ -54,14 +54,12 @@
 #include <fcntl.h>
 #include <pwd.h>
 #include <grp.h>
+#include <time.h>
 #include <unistd.h>
 
 #define SYSTEM_CONFIG_FILE_LOCATION	"/etc/mpd.conf"
 #define USER_CONFIG_FILE_LOCATION	"/.mpdconf"
 
-volatile int masterPid = 0;
-volatile int mainPid = 0;
-
 typedef struct _Options {
 	int kill;
 	int daemon;
@@ -311,47 +309,6 @@ static void openDB(Options * options, char *argv0)
 	}
 }
 
-static void startMainProcess(void)
-{
-	int pid;
-	fflush(0);
-	pid = fork();
-	if (pid > 0) {
-		initInputStream();
-		initReplayGainState();
-
-		/* free stuff we don't need */
-		freeAllListenSockets();
-
-		mainPid = pid;
-		masterInitSigHandlers();
-		kill(mainPid, SIGUSR1);
-		while (masterHandlePendingSignals() != COMMAND_RETURN_KILL)
-			waitOnSignals();
-		/* we're killed */
-		playerKill();
-
-		finishPlaylist();
-
-		finishAudioConfig();
-		finishAudioDriver();
-
-		finishPaths();
-
-		kill(mainPid, SIGTERM);
-		waitpid(mainPid, NULL, 0);
-		finishConf();
-		close_log_files();
-		exit(EXIT_SUCCESS);
-
-	} else if (pid < 0) {
-		ERROR("problems fork'ing main process!\n");
-		exit(EXIT_FAILURE);
-	}
-
-	DEBUG("main process started!\n");
-}
-
 static void daemonize(Options * options)
 {
 	FILE *fp = NULL;
@@ -409,7 +366,6 @@ static void daemonize(Options * options)
 		DEBUG("writing pid file\n");
 		fprintf(fp, "%lu\n", (unsigned long)getpid());
 		fclose(fp);
-		masterPid = getpid();
 	}
 }
 
@@ -480,38 +436,30 @@ int main(int argc, char *argv[])
 
 	open_log_files(options.stdOutput);
 
-	initPlayerData();
-
-	initInputPlugins();
 	initPaths();
+	initPermissions();
+	initPlaylist();
+	initInputPlugins();
+
+	openDB(&options, argv[0]);
+
+	initCommands();
+	initPlayerData();
 	initAudioConfig();
 	initAudioDriver();
+	initVolume();
+	initInterfaces();
+	initReplayGainState();
 	initNormalization();
-	initPlaylist();
-	openDB(&options, argv[0]);
+	initInputStream();
 
 	daemonize(&options);
 
-	initSigHandlers();
 	setup_log_output(options.stdOutput);
-	startMainProcess();
-	/* This is the main process which has
-	 * been forked from the master process.
-	 */
-
-	initPermissions();
 
-	initCommands();
-	initVolume();
-	initInterfaces();
 
-	printMemorySavedByTagTracker();
-	printSavedMemoryFromFilenames();
 
-	/* wait for the master process to get ready so we can start 
-	 * playing if readPlaylistState thinks we should*/
-	while (COMMAND_MASTER_READY != handlePendingSignals())
-		my_usleep(1);
+	initSigHandlers();
 
 	openVolumeDevice();
 	read_state_file();
@@ -525,13 +473,14 @@ int main(int argc, char *argv[])
 	}
 
 	write_state_file();
-
+	playerKill();
 	freeAllInterfaces();
 	closeAllListenSockets();
 
-	/* This slows shutdown immensely, and doesn't really accomplish
-	 * anything.  Uncomment when we rewrite tagTracker to use a tree. */
-	/*closeMp3Directory(); */
+	clock_t start = clock();
+	closeMp3Directory();
+	DEBUG("closeMp3Directory took %f seconds\n", 
+	      ((float)(clock()-start))/CLOCKS_PER_SEC);
 
 	finishPlaylist();
 	freePlayerData();
diff --git a/src/player.c b/src/player.c
index 7353debcf..17ec780ed 100644
--- a/src/player.c
+++ b/src/player.c
@@ -44,7 +44,12 @@
 #include <errno.h>
 #include <fcntl.h>
 
-extern int masterPid;
+volatile int player_pid = 0;
+
+void clearPlayerPid()
+{
+	player_pid = 0;
+}
 
 static void resetPlayerMetadata()
 {
@@ -59,7 +64,7 @@ void resetPlayer()
 {
 	int pid;
 
-	setPlayerPid(0);
+	clearPlayerPid();
 	getPlayerData()->playerControl.stop = 0;
 	getPlayerData()->playerControl.play = 0;
 	getPlayerData()->playerControl.pause = 0;
@@ -78,17 +83,23 @@ void resetPlayer()
 
 void player_sigChldHandler(int pid, int status)
 {
-	if (getPlayerPid() == pid) {
+	if (player_pid == pid) 
+	{
 		DEBUG("SIGCHLD caused by player process\n");
-		if (WIFSIGNALED(status) && WTERMSIG(status) != SIGTERM &&
-		    WTERMSIG(status) != SIGINT) {
+		if (WIFSIGNALED(status) && 
+		    WTERMSIG(status) != SIGTERM &&
+		    WTERMSIG(status) != SIGINT) 
+		{
 			ERROR("player process died from signal: %i\n",
 			      WTERMSIG(status));
 		}
 		resetPlayer();
-	} else if (pid == getPlayerData()->playerControl.decode_pid
-		   && getPlayerPid() <= 0) {
-		if (WIFSIGNALED(status) && WTERMSIG(status) != SIGTERM) {
+	} 
+	else if (pid == getPlayerData()->playerControl.decode_pid &&
+		 player_pid <= 0) 
+	{
+		if (WIFSIGNALED(status) && WTERMSIG(status) != SIGTERM) 
+		{
 			ERROR("(caught by master parent) "
 			      "decode process died from a "
 			      "non-TERM signal: %i\n", WTERMSIG(status));
@@ -99,25 +110,29 @@ void player_sigChldHandler(int pid, int status)
 
 int playerInit()
 {
-	kill(masterPid, SIGUSR2);
-	/* we need to wait for the signal to take effect: */
-	while (getPlayerPid() == 0)
-		my_usleep(10000);
-	return 0;
-}
-
-int playerInitReal()
-{
-	int player_pid;
 	blockSignals();
 	player_pid = fork();
-	if (player_pid == 0) {
+	if (player_pid==0)
+	{
+		clock_t start = clock();
+
 		PlayerControl *pc = &(getPlayerData()->playerControl);
 
 		unblockSignals();
 
 		setSigHandlersForDecoder();
 
+		closeAllListenSockets();
+		freeAllInterfaces();
+		closeMp3Directory();
+		finishPlaylist();
+		finishPermissions();
+		finishCommands();
+		finishVolume();
+
+		DEBUG("took %f to init player\n", 
+		      (float)(clock()-start)/CLOCKS_PER_SEC);
+
 		while (1) {
 			if (pc->play)
 				decode();
@@ -143,14 +158,14 @@ int playerInitReal()
 		}
 
 		exit(EXIT_SUCCESS);
-	} else if (player_pid < 0) {
+	} 
+	else if (player_pid < 0) 
+	{
 		unblockSignals();
 		ERROR("player Problems fork()'ing\n");
-		setPlayerPid(0);
 		player_pid = 0;
 		return -1;
-	} else
-		setPlayerPid(player_pid);
+	}
 
 	unblockSignals();
 
@@ -174,13 +189,13 @@ int playerPlay(int fd, Song * song)
 	pathcpy_trunc(pc->utf8url, getSongUrl(song));
 
 	pc->play = 1;
-	if (getPlayerPid() == 0 && playerInit() < 0) {
+	if (player_pid == 0 && playerInit() < 0) {
 		pc->play = 0;
 		return -1;
 	}
 
 	resetPlayerMetadata();
-	while (getPlayerPid() > 0 && pc->play)
+	while (player_pid > 0 && pc->play)
 		my_usleep(1000);
 
 	return 0;
@@ -190,9 +205,9 @@ int playerStop(int fd)
 {
 	PlayerControl *pc = &(getPlayerData()->playerControl);
 
-	if (getPlayerPid() > 0 && pc->state != PLAYER_STATE_STOP) {
+	if (player_pid > 0 && pc->state != PLAYER_STATE_STOP) {
 		pc->stop = 1;
-		while (getPlayerPid() > 0 && pc->stop)
+		while (player_pid > 0 && pc->stop)
 			my_usleep(1000);
 	}
 
@@ -211,7 +226,7 @@ void playerKill()
 	   playerCloseAudio(stderr);
 	   if(player_pid>0 && pc->closeAudio) sleep(1); */
 
-	pid = getPlayerPid();
+	pid = player_pid;
 	if (pid > 0)
 		kill(pid, SIGTERM);
 }
@@ -220,9 +235,9 @@ int playerPause(int fd)
 {
 	PlayerControl *pc = &(getPlayerData()->playerControl);
 
-	if (getPlayerPid() > 0 && pc->state != PLAYER_STATE_STOP) {
+	if (player_pid > 0 && pc->state != PLAYER_STATE_STOP) {
 		pc->pause = 1;
-		while (getPlayerPid() > 0 && pc->pause)
+		while (player_pid > 0 && pc->pause)
 			my_usleep(1000);
 	}
 
@@ -233,7 +248,7 @@ int playerSetPause(int fd, int pause)
 {
 	PlayerControl *pc = &(getPlayerData()->playerControl);
 
-	if (getPlayerPid() <= 0)
+	if (player_pid <= 0)
 		return 0;
 
 	switch (pc->state) {
@@ -325,7 +340,7 @@ void playerCloseAudio()
 {
 	PlayerControl *pc = &(getPlayerData()->playerControl);
 
-	if (getPlayerPid() > 0) {
+	if (player_pid > 0) {
 		if (playerStop(STDERR_FILENO) < 0)
 			return;
 		pc->closeAudio = 1;
@@ -371,9 +386,9 @@ void playerQueueLock()
 {
 	PlayerControl *pc = &(getPlayerData()->playerControl);
 
-	if (getPlayerPid() > 0 && pc->queueLockState == PLAYER_QUEUE_UNLOCKED) {
+	if (player_pid > 0 && pc->queueLockState == PLAYER_QUEUE_UNLOCKED) {
 		pc->lockQueue = 1;
-		while (getPlayerPid() > 0 && pc->lockQueue)
+		while (player_pid > 0 && pc->lockQueue)
 			my_usleep(1000);
 	}
 }
@@ -382,9 +397,9 @@ void playerQueueUnlock()
 {
 	PlayerControl *pc = &(getPlayerData()->playerControl);
 
-	if (getPlayerPid() > 0 && pc->queueLockState == PLAYER_QUEUE_LOCKED) {
+	if (player_pid > 0 && pc->queueLockState == PLAYER_QUEUE_LOCKED) {
 		pc->unlockQueue = 1;
-		while (getPlayerPid() > 0 && pc->unlockQueue)
+		while (player_pid > 0 && pc->unlockQueue)
 			my_usleep(1000);
 	}
 }
@@ -414,7 +429,7 @@ int playerSeek(int fd, Song * song, float time)
 		resetPlayerMetadata();
 		pc->seekWhere = time;
 		pc->seek = 1;
-		while (getPlayerPid() > 0 && pc->seek)
+		while (player_pid > 0 && pc->seek)
 			my_usleep(1000);
 	}
 
diff --git a/src/player.h b/src/player.h
index 77d16174b..ac83c9ea5 100644
--- a/src/player.h
+++ b/src/player.h
@@ -89,8 +89,6 @@ typedef struct _PlayerControl {
 	MetadataChunk fileMetadataChunk;
 } PlayerControl;
 
-int playerInitReal();
-
 void player_sigChldHandler(int pid, int status);
 
 int playerPlay(int fd, Song * song);
diff --git a/src/playerData.c b/src/playerData.c
index 79663f00f..df928acc4 100644
--- a/src/playerData.c
+++ b/src/playerData.c
@@ -95,15 +95,18 @@ void initPlayerData(void)
 	/* for audioDeviceStates[] */
 	allocationSize += device_array_size;
 
-	if ((shmid = shmget(IPC_PRIVATE, allocationSize, IPC_CREAT | 0600)) < 0) {
+	if ((shmid = shmget(IPC_PRIVATE, allocationSize, IPC_CREAT | 0600)) < 0)
+	{
 		ERROR("problems shmget'ing\n");
 		exit(EXIT_FAILURE);
 	}
-	if (!(playerData_pd = shmat(shmid, NULL, 0))) {
+	if (!(playerData_pd = shmat(shmid, NULL, 0))) 
+	{
 		ERROR("problems shmat'ing\n");
 		exit(EXIT_FAILURE);
 	}
-	if (shmctl(shmid, IPC_RMID, NULL) < 0) {
+	if (shmctl(shmid, IPC_RMID, NULL) < 0) 
+	{
 		ERROR("problems shmctl'ing\n");
 		exit(EXIT_FAILURE);
 	}
@@ -159,16 +162,6 @@ PlayerData *getPlayerData(void)
 	return playerData_pd;
 }
 
-int getPlayerPid(void)
-{
-	return playerData_pd->pid;
-}
-
-void setPlayerPid(int pid)
-{
-	playerData_pd->pid = pid;
-}
-
 void freePlayerData(void)
 {
 	shmdt(playerData_pd);
diff --git a/src/playerData.h b/src/playerData.h
index 777232bfa..00ba66d02 100644
--- a/src/playerData.h
+++ b/src/playerData.h
@@ -38,14 +38,11 @@ typedef struct _PlayerData {
 	PlayerControl playerControl;
 	DecoderControl decoderControl;
 	mpd_uint8 *audioDeviceStates;
-	int pid;
 } PlayerData;
 
 void initPlayerData();
 
 PlayerData *getPlayerData();
-int getPlayerPid();
-void setPlayerPid(int pid);
 
 void freePlayerData();
 
diff --git a/src/sig_handlers.c b/src/sig_handlers.c
index e5d300778..2c6a07a00 100644
--- a/src/sig_handlers.c
+++ b/src/sig_handlers.c
@@ -39,34 +39,8 @@
 extern volatile int masterPid;
 extern volatile int mainPid;
 
-int masterHandlePendingSignals()
-{
-	if (signal_is_pending(SIGINT) || signal_is_pending(SIGTERM)) {
-		DEBUG("master process got SIGINT or SIGTERM, exiting\n");
-		return COMMAND_RETURN_KILL;
-	}
-
-	if (signal_is_pending(SIGHUP)) {
-		signal_clear(SIGHUP);
-		/* Forward it to the main process, which will update the DB */
-		kill(mainPid, SIGHUP);
-	}
-
-	return 0;
-}
-
 int handlePendingSignals()
 {
-	/* this SIGUSR1 signal comes before the KILL signals, because there if the process is 
-	 * looping, waiting for this signal, it will not respond to the KILL signal. This might be
-	 * better implemented by using bit-wise defines and or'ing of the COMMAND_FOO as return.
-	 */
-	if (signal_is_pending(SIGUSR1)) {
-		signal_clear(SIGUSR1);
-		DEBUG("The master process is ready to receive signals\n");
-		return COMMAND_MASTER_READY;
-	}
-
 	if (signal_is_pending(SIGINT) || signal_is_pending(SIGTERM)) {
 		DEBUG("main process got SIGINT or SIGTERM, exiting\n");
 		return COMMAND_RETURN_KILL;
@@ -99,56 +73,11 @@ void chldSigHandler(int signal)
 			else
 				break;
 		}
-		directory_sigChldHandler(pid, status);
-	}
-}
-
-void masterChldSigHandler(int signal)
-{
-	int status;
-	int pid;
-	DEBUG("master process got SIGCHLD\n");
-	while (0 != (pid = wait3(&status, WNOHANG, NULL))) {
-		if (pid < 0) {
-			if (errno == EINTR)
-				continue;
-			else
-				break;
-		}
-		DEBUG("PID: %d\n", pid);
-		if (pid == mainPid)
-			kill(getpid(), SIGTERM);
 		player_sigChldHandler(pid, status);
+		directory_sigChldHandler(pid, status);
 	}
 }
 
-int playerInitReal();
-
-void masterSigUsr2Handler(int signal)
-{
-	DEBUG("Master process got SIGUSR2 starting a new player process\n");
-	if (getPlayerPid() <= 0)
-		playerInitReal();
-}
-
-void masterInitSigHandlers()
-{
-	struct sigaction sa;
-
-	sa.sa_flags = 0;
-	sigemptyset(&sa.sa_mask);
-	sa.sa_handler = SIG_IGN;
-	while (sigaction(SIGPIPE, &sa, NULL) < 0 && errno == EINTR) ;
-	sa.sa_handler = masterChldSigHandler;
-	while (sigaction(SIGCHLD, &sa, NULL) < 0 && errno == EINTR) ;
-	sa.sa_handler = masterSigUsr2Handler;
-	while (sigaction(SIGUSR2, &sa, NULL) < 0 && errno == EINTR) ;
-	signal_handle(SIGUSR1);
-	signal_handle(SIGINT);
-	signal_handle(SIGTERM);
-	signal_handle(SIGHUP);
-}
-
 void initSigHandlers()
 {
 	struct sigaction sa;
@@ -159,7 +88,6 @@ void initSigHandlers()
 	while (sigaction(SIGPIPE, &sa, NULL) < 0 && errno == EINTR) ;
 	sa.sa_handler = chldSigHandler;
 	while (sigaction(SIGCHLD, &sa, NULL) < 0 && errno == EINTR) ;
-	signal_handle(SIGUSR2);
 	signal_handle(SIGUSR1);
 	signal_handle(SIGINT);
 	signal_handle(SIGTERM);
@@ -202,26 +130,11 @@ void ignoreSignals()
 	while (sigaction(SIGPIPE, &sa, NULL) < 0 && errno == EINTR) ;
 	while (sigaction(SIGCHLD, &sa, NULL) < 0 && errno == EINTR) ;
 	while (sigaction(SIGUSR1, &sa, NULL) < 0 && errno == EINTR) ;
-	while (sigaction(SIGUSR2, &sa, NULL) < 0 && errno == EINTR) ;
 	while (sigaction(SIGINT, &sa, NULL) < 0 && errno == EINTR) ;
 	while (sigaction(SIGTERM, &sa, NULL) < 0 && errno == EINTR) ;
 	while (sigaction(SIGHUP, &sa, NULL) < 0 && errno == EINTR) ;
 }
 
-void waitOnSignals()
-{
-	sigset_t sset;
-
-	sigfillset(&sset);
-	sigdelset(&sset, SIGCHLD);
-	sigdelset(&sset, SIGUSR1);
-	sigdelset(&sset, SIGUSR2);
-	sigdelset(&sset, SIGHUP);
-	sigdelset(&sset, SIGINT);
-	sigdelset(&sset, SIGTERM);
-	sigsuspend(&sset);
-}
-
 void blockSignals()
 {
 	sigset_t sset;
@@ -229,7 +142,6 @@ void blockSignals()
 	sigemptyset(&sset);
 	sigaddset(&sset, SIGCHLD);
 	sigaddset(&sset, SIGUSR1);
-	sigaddset(&sset, SIGUSR2);
 	sigaddset(&sset, SIGHUP);
 	sigaddset(&sset, SIGINT);
 	sigaddset(&sset, SIGTERM);
@@ -243,7 +155,6 @@ void unblockSignals()
 	sigemptyset(&sset);
 	sigaddset(&sset, SIGCHLD);
 	sigaddset(&sset, SIGUSR1);
-	sigaddset(&sset, SIGUSR2);
 	sigaddset(&sset, SIGHUP);
 	sigaddset(&sset, SIGINT);
 	sigaddset(&sset, SIGTERM);
diff --git a/src/sig_handlers.h b/src/sig_handlers.h
index 186ebb85f..c58696d0d 100644
--- a/src/sig_handlers.h
+++ b/src/sig_handlers.h
@@ -22,10 +22,8 @@
 #include "../config.h"
 
 int handlePendingSignals();
-int masterHandlePendingSignals();
 
 void initSigHandlers();
-void masterInitSigHandlers();
 
 void finishSigHandlers();
 
@@ -33,8 +31,6 @@ void setSigHandlersForDecoder();
 
 void ignoreSignals();
 
-void waitOnSignals();
-
 void blockSignals();
 
 void unblockSignals();
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
new file mode 100644
index 000000000..9462d2a2c
--- /dev/null
+++ b/src/tree.c
@@ -0,0 +1,712 @@
+/* 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>
+
+#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()
+{
+	TreeNode * ret = malloc(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, 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, 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)
+{
+	assert(node->count == DATA_PER_NODE);
+
+	TreeNode * newNode = _MakeNode();
+
+	int i = DATA_PER_NODE/2;
+	int j = 0;
+	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(Tree * tree, 
+		   TreeNode * node,
+		   int pos,
+		   TreeNode * newNode,
+		   TreeKeyData keyData)
+{
+	assert(node->count < DATA_PER_NODE);
+
+	int j = node->count;
+	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(Tree * tree,
+		     TreeNode * lessNode, 
+		     TreeNode * moreNode,
+		     int pos,
+		     TreeNode * newNode,
+		     TreeKeyData keyData)
+{
+	assert(moreNode->children[0] == NULL);
+
+	TreeKeyData retKeyData;
+
+	if (pos <= lessNode->count)
+	{
+		_InsertNodeAndData(tree, 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
+	{
+		pos -= lessNode->count;
+		retKeyData = moreNode->keyData[0];
+		assert(!moreNode->children[0]);
+
+		int j = 0;
+		for (; 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(iter->tree,
+						       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(iter->tree, 
+					   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);
+}
+
+void
+_DeleteAt(TreeIterator * iter)
+{
+	TreeNode * node = iter->node;
+	int pos = iter->which - 1;
+	TreeKeyData * keyData = &(node->keyData[pos]);
+	TreeKeyData keyDataToFree = *keyData;
+
+	{
+		// 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
+	int 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];
+				int 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--;
+				int 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;
+				}
+
+				int 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 = malloc(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)
+		{
+			TreeNode * childNode = iter->node;
+			iter->node = childNode->parent;
+			if (iter->node)
+			{
+				for (iter->which = 0;
+				     childNode != 
+				     iter->node->children[iter->which];
+				     iter->which++)
+				{
+					assert(iter->which <= 
+					       iter->node->count);
+				}
+				iter->which++;
+			}
+		}
+
+		if (iter->node &&
+		    iter->which > 0 && iter->which <= iter->node->count)
+		{
+			return;
+		}
+	}
+}
+
+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 = {key, data};
+	TreeIterator iter;
+	_SetIteratorToRoot(tree, &iter);
+
+	if (_Find(&iter, key))
+	{
+		return 0;
+	}
+
+	_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, 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
new file mode 100644
index 000000000..54416a065
--- /dev/null
+++ b/src/tree.h
@@ -0,0 +1,62 @@
+/* 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
+
+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);
+
+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, void * key, TreeIterator * iter /* can be NULL */);
+
+#endif