Merge branch 'mk/tag'

* mk/tag: (22 commits)
  tag: fix segfault on update
  utf8.h: Fix build (broken os_compat.h #include)
  tag: optimize tag_dup(), copy item references
  tag: fix the shout and oggflac plugins
  const pointers
  tag: static directory name
  tag: try not to reallocate tag.items in every add() call
  song: don't export newNullSong()
  tag: try not to duplicate the input string
  tag: pass length to fix_utf8()
  added "length" parameter to validUtf8String()
  assert value!=NULL in fix_utf8()
  tag: converted macro fixUtf8() to an inline function
  tag: added a pool for tag items
  tag: converted tag_item.value to a char array
  removed tree.c
  tag: converted MpdTag.items to a pointer list
  tag: moved code to tag_id3.c
  wavpack: tag_new() cannot fail
  tag: converted tag_add_item() to an inline function
  ...

44 files changed, 998 insertions, 1468 deletions

diff --git a/src/Makefile.am b/src/Makefile.am
index 70306c125..d8640d304 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -81,8 +81,9 @@ mpd_headers = \
 	state_file.h \
 	stats.h \
 	tag.h \
+	tag_pool.h \
+	tag_id3.h \
 	tagTracker.h \
-	tree.h \
 	utf8.h \
 	utils.h \
 	volume.h \
@@ -138,8 +139,9 @@ mpd_SOURCES = \
 	state_file.c \
 	stats.c \
 	tag.c \
+	tag_pool.c \
+	tag_id3.c \
 	tagTracker.c \
-	tree.c \
 	utils.c \
 	volume.c \
 	utf8.c \
diff --git a/src/audio.c b/src/audio.c
index 409761177..9a65df858 100644
--- a/src/audio.c
+++ b/src/audio.c
@@ -419,7 +419,7 @@ void closeAudioDevice(void)
 	audioOpened = 0;
 }
 
-void sendMetadataToAudioDevice(const MpdTag * tag)
+void sendMetadataToAudioDevice(const struct mpd_tag *tag)
 {
 	unsigned int i;
 
diff --git a/src/audio.h b/src/audio.h
index 0032cff22..92cb9cf11 100644
--- a/src/audio.h
+++ b/src/audio.h
@@ -55,7 +55,7 @@ int isAudioDeviceOpen(void);
 
 int isCurrentAudioFormat(const AudioFormat * audioFormat);
 
-void sendMetadataToAudioDevice(const MpdTag * tag);
+void sendMetadataToAudioDevice(const struct mpd_tag *tag);
 
 /* these functions are called in the main parent process while the child
 	process is busy playing to the audio */
diff --git a/src/audioOutput.c b/src/audioOutput.c
index f165979d0..d5b37f0fe 100644
--- a/src/audioOutput.c
+++ b/src/audioOutput.c
@@ -244,7 +244,8 @@ void finishAudioOutput(AudioOutput * audioOutput)
 		free(audioOutput->convBuffer);
 }
 
-void sendMetadataToAudioOutput(AudioOutput * audioOutput, const MpdTag * tag)
+void sendMetadataToAudioOutput(AudioOutput * audioOutput,
+			       const struct mpd_tag *tag)
 {
 	if (!audioOutput->sendMetdataFunc)
 		return;
diff --git a/src/audioOutput.h b/src/audioOutput.h
index f82eedfba..4ce67a5de 100644
--- a/src/audioOutput.h
+++ b/src/audioOutput.h
@@ -50,7 +50,7 @@ typedef void (*AudioOutputDropBufferedAudioFunc) (AudioOutput * audioOutput);
 typedef void (*AudioOutputCloseDeviceFunc) (AudioOutput * audioOutput);
 
 typedef void (*AudioOutputSendMetadataFunc) (AudioOutput * audioOutput,
-					     const MpdTag * tag);
+					     const struct mpd_tag *tag);
 
 struct _AudioOutput {
 	int open;
@@ -104,7 +104,8 @@ void dropBufferedAudioOutput(AudioOutput * audioOutput);
 void closeAudioOutput(AudioOutput * audioOutput);
 void finishAudioOutput(AudioOutput * audioOutput);
 int keepAudioOutputAlive(AudioOutput * audioOutput, int ms);
-void sendMetadataToAudioOutput(AudioOutput * audioOutput, const MpdTag * tag);
+void sendMetadataToAudioOutput(AudioOutput * audioOutput,
+			       const struct mpd_tag *tag);
 
 void printAllOutputPluginTypes(FILE * fp);
 
diff --git a/src/audioOutputs/audioOutput_shout.c b/src/audioOutputs/audioOutput_shout.c
index c1f784986..b65a8253f 100644
--- a/src/audioOutputs/audioOutput_shout.c
+++ b/src/audioOutputs/audioOutput_shout.c
@@ -56,7 +56,7 @@ typedef struct _ShoutData {
 
 	int opened;
 
-	MpdTag *tag;
+	struct mpd_tag *tag;
 	int tagToSend;
 
 	int timeout;
@@ -93,7 +93,7 @@ static void freeShoutData(ShoutData * sd)
 	if (sd->shoutConn)
 		shout_free(sd->shoutConn);
 	if (sd->tag)
-		freeMpdTag(sd->tag);
+		tag_free(sd->tag);
 	if (sd->timer)
 		timer_free(sd->timer);
 
@@ -402,15 +402,15 @@ static void copyTagToVorbisComment(ShoutData * sd)
 		int i;
 
 		for (i = 0; i < sd->tag->numOfItems; i++) {
-			switch (sd->tag->items[i].type) {
+			switch (sd->tag->items[i]->type) {
 			case TAG_ITEM_ARTIST:
-				addTag(sd, "ARTIST", sd->tag->items[i].value);
+				addTag(sd, "ARTIST", sd->tag->items[i]->value);
 				break;
 			case TAG_ITEM_ALBUM:
-				addTag(sd, "ALBUM", sd->tag->items[i].value);
+				addTag(sd, "ALBUM", sd->tag->items[i]->value);
 				break;
 			case TAG_ITEM_TITLE:
-				addTag(sd, "TITLE", sd->tag->items[i].value);
+				addTag(sd, "TITLE", sd->tag->items[i]->value);
 				break;
 			default:
 				break;
@@ -593,7 +593,7 @@ static void myShout_sendMetadata(ShoutData * sd)
 		}
 	}
 
-	/*if(sd->tag) freeMpdTag(sd->tag);
+	/*if(sd->tag) tag_free(sd->tag);
 	   sd->tag = NULL; */
 	sd->tagToSend = 0;
 }
@@ -663,19 +663,19 @@ static int myShout_play(AudioOutput * audioOutput,
 	return 0;
 }
 
-static void myShout_setTag(AudioOutput * audioOutput, MpdTag * tag)
+static void myShout_setTag(AudioOutput * audioOutput, const struct mpd_tag *tag)
 {
 	ShoutData *sd = (ShoutData *) audioOutput->data;
 
 	if (sd->tag)
-		freeMpdTag(sd->tag);
+		tag_free(sd->tag);
 	sd->tag = NULL;
 	sd->tagToSend = 0;
 
 	if (!tag)
 		return;
 
-	sd->tag = mpdTagDup(tag);
+	sd->tag = tag_dup(tag);
 	sd->tagToSend = 1;
 }
 
diff --git a/src/command.c b/src/command.c
index 805addde1..bc646804e 100644
--- a/src/command.c
+++ b/src/command.c
@@ -245,7 +245,7 @@ static int handleUrlHandlers(int fd, mpd_unused int *permission,
 static int handleTagTypes(int fd, mpd_unused int *permission,
 			  mpd_unused int argc, mpd_unused char *argv[])
 {
-	printTagTypes(fd);
+	tag_print_types(fd);
 	return 0;
 }
 
diff --git a/src/dbUtils.c b/src/dbUtils.c
index 519c1802d..d39c9908c 100644
--- a/src/dbUtils.c
+++ b/src/dbUtils.c
@@ -257,7 +257,7 @@ static void freeListCommandItem(ListCommandItem * item)
 static void visitTag(int fd, Song * song, enum tag_type tagType)
 {
 	int i;
-	MpdTag *tag = song->tag;
+	struct mpd_tag *tag = song->tag;
 
 	if (tagType == LOCATE_TAG_FILE_TYPE) {
 		printSongUrl(fd, song);
@@ -268,8 +268,8 @@ static void visitTag(int fd, Song * song, enum tag_type tagType)
 		return;
 
 	for (i = 0; i < tag->numOfItems; i++) {
-		if (tag->items[i].type == tagType) {
-			visitInTagTracker(tagType, tag->items[i].value);
+		if (tag->items[i]->type == tagType) {
+			visitInTagTracker(tagType, tag->items[i]->value);
 		}
 	}
 }
diff --git a/src/directory.c b/src/directory.c
index 94a55d664..33a862ddd 100644
--- a/src/directory.c
+++ b/src/directory.c
@@ -901,7 +901,7 @@ static void readDirectoryInfo(FILE * fp, Directory * directory)
 {
 	char buffer[MPD_PATH_MAX * 2];
 	int bufferSize = MPD_PATH_MAX * 2;
-	char *key;
+	char key[MPD_PATH_MAX * 2];
 	Directory *subDirectory;
 	int strcmpRet;
 	char *name;
@@ -911,7 +911,7 @@ static void readDirectoryInfo(FILE * fp, Directory * directory)
 	while (myFgets(buffer, bufferSize, fp)
 	       && 0 != strncmp(DIRECTORY_END, buffer, strlen(DIRECTORY_END))) {
 		if (0 == strncmp(DIRECTORY_DIR, buffer, strlen(DIRECTORY_DIR))) {
-			key = xstrdup(&(buffer[strlen(DIRECTORY_DIR)]));
+			strcpy(key, &(buffer[strlen(DIRECTORY_DIR)]));
 			if (!myFgets(buffer, bufferSize, fp))
 				FATAL("Error reading db, fgets\n");
 			/* for compatibility with db's prior to 0.11 */
@@ -925,7 +925,7 @@ static void readDirectoryInfo(FILE * fp, Directory * directory)
 			     strlen(DIRECTORY_BEGIN))) {
 				FATAL("Error reading db at line: %s\n", buffer);
 			}
-			name = xstrdup(&(buffer[strlen(DIRECTORY_BEGIN)]));
+			name = &(buffer[strlen(DIRECTORY_BEGIN)]);
 
 			while (nextDirNode && (strcmpRet =
 					       strcmp(key,
@@ -951,8 +951,6 @@ static void readDirectoryInfo(FILE * fp, Directory * directory)
 						       (void *)subDirectory);
 			}
 
-			free(name);
-			free(key);
 			readDirectoryInfo(fp, subDirectory);
 		} else if (0 == strncmp(SONG_BEGIN, buffer, strlen(SONG_BEGIN))) {
 			readSongInfoIntoList(fp, directory->songs, directory);
diff --git a/src/inputPlugin.h b/src/inputPlugin.h
index 161a0db59..0fd39ea9f 100644
--- a/src/inputPlugin.h
+++ b/src/inputPlugin.h
@@ -54,7 +54,7 @@ typedef int (*InputPlugin_fileDecodeFunc) (char *path);
 
 /* file should be the full path!  Returns NULL if a tag cannot be found
  * or read */
-typedef MpdTag *(*InputPlugin_tagDupFunc) (char *file);
+typedef struct mpd_tag *(*InputPlugin_tagDupFunc) (char *file);
 
 typedef struct _InputPlugin {
 	const char *name;
diff --git a/src/inputPlugins/_flac_common.c b/src/inputPlugins/_flac_common.c
index 6890c7c50..9950f75db 100644
--- a/src/inputPlugins/_flac_common.c
+++ b/src/inputPlugins/_flac_common.c
@@ -101,7 +101,7 @@ static const char *VORBIS_COMMENT_DISC_KEY = "discnumber";
 static unsigned int commentMatchesAddToTag(const
 					   FLAC__StreamMetadata_VorbisComment_Entry
 					   * entry, unsigned int itemType,
-					   MpdTag ** tag)
+					   struct mpd_tag ** tag)
 {
 	const char *str;
 	size_t slen;
@@ -123,10 +123,10 @@ static unsigned int commentMatchesAddToTag(const
 	if ((vlen > 0) && (0 == strncasecmp(str, (char *)entry->entry, slen))
 	    && (*(entry->entry + slen) == '=')) {
 		if (!*tag)
-			*tag = newMpdTag();
+			*tag = tag_new();
 
-		addItemToMpdTagWithLen(*tag, itemType,
-				       (char *)(entry->entry + slen + 1), vlen);
+		tag_add_item_n(*tag, itemType,
+			       (char *)(entry->entry + slen + 1), vlen);
 
 		return 1;
 	}
@@ -134,8 +134,8 @@ static unsigned int commentMatchesAddToTag(const
 	return 0;
 }
 
-MpdTag *copyVorbisCommentBlockToMpdTag(const FLAC__StreamMetadata * block,
-				       MpdTag * tag)
+struct mpd_tag *copyVorbisCommentBlockToMpdTag(const FLAC__StreamMetadata * block,
+					   struct mpd_tag * tag)
 {
 	unsigned int i, j;
 	FLAC__StreamMetadata_VorbisComment_Entry *comments;
diff --git a/src/inputPlugins/_flac_common.h b/src/inputPlugins/_flac_common.h
index 6fe5bd744..a1b0cac8f 100644
--- a/src/inputPlugins/_flac_common.h
+++ b/src/inputPlugins/_flac_common.h
@@ -146,7 +146,7 @@ typedef struct {
 	FLAC__uint64 position;
 	InputStream *inStream;
 	ReplayGainInfo *replayGainInfo;
-	MpdTag *tag;
+	struct mpd_tag *tag;
 } FlacData;
 
 /* initializes a given FlacData struct */
@@ -157,8 +157,8 @@ void flac_error_common_cb(const char *plugin,
 			  FLAC__StreamDecoderErrorStatus status,
 			  FlacData * data);
 
-MpdTag *copyVorbisCommentBlockToMpdTag(const FLAC__StreamMetadata * block,
-				       MpdTag * tag);
+struct mpd_tag *copyVorbisCommentBlockToMpdTag(const FLAC__StreamMetadata * block,
+					   struct mpd_tag *tag);
 
 /* keep this inlined, this is just macro but prettier :) */
 static inline enum dc_action flacSendChunk(FlacData * data)
diff --git a/src/inputPlugins/aac_plugin.c b/src/inputPlugins/aac_plugin.c
index 512e73e53..dc97c1e08 100644
--- a/src/inputPlugins/aac_plugin.c
+++ b/src/inputPlugins/aac_plugin.c
@@ -553,14 +553,14 @@ out:
 	return 0;
 }
 
-static MpdTag *aacTagDup(char *file)
+static struct mpd_tag *aacTagDup(char *file)
 {
-	MpdTag *ret = NULL;
+	struct mpd_tag *ret = NULL;
 	int file_time = getAacTotalTime(file);
 
 	if (file_time >= 0) {
-		if ((ret = id3Dup(file)) == NULL)
-			ret = newMpdTag();
+		if ((ret = tag_id3_load(file)) == NULL)
+			ret = tag_new();
 		ret->time = file_time;
 	} else {
 		DEBUG("aacTagDup: Failed to get total song time from: %s\n",
diff --git a/src/inputPlugins/audiofile_plugin.c b/src/inputPlugins/audiofile_plugin.c
index fcebf562b..6fcc98239 100644
--- a/src/inputPlugins/audiofile_plugin.c
+++ b/src/inputPlugins/audiofile_plugin.c
@@ -116,14 +116,14 @@ static int audiofile_decode(char *path)
 	return 0;
 }
 
-static MpdTag *audiofileTagDup(char *file)
+static struct mpd_tag *audiofileTagDup(char *file)
 {
-	MpdTag *ret = NULL;
+	struct mpd_tag *ret = NULL;
 	int total_time = getAudiofileTotalTime(file);
 
 	if (total_time >= 0) {
 		if (!ret)
-			ret = newMpdTag();
+			ret = tag_new();
 		ret->time = total_time;
 	} else {
 		DEBUG
diff --git a/src/inputPlugins/flac_plugin.c b/src/inputPlugins/flac_plugin.c
index de0648c90..89e988a03 100644
--- a/src/inputPlugins/flac_plugin.c
+++ b/src/inputPlugins/flac_plugin.c
@@ -292,9 +292,9 @@ static FLAC__StreamDecoderWriteStatus flacWrite(const flac_decoder *dec,
 	return FLAC__STREAM_DECODER_WRITE_STATUS_CONTINUE;
 }
 
-static MpdTag *flacMetadataDup(char *file, int *vorbisCommentFound)
+static struct mpd_tag *flacMetadataDup(char *file, int *vorbisCommentFound)
 {
-	MpdTag *ret = NULL;
+	struct mpd_tag *ret = NULL;
 	FLAC__Metadata_SimpleIterator *it;
 	FLAC__StreamMetadata *block = NULL;
 
@@ -338,7 +338,7 @@ static MpdTag *flacMetadataDup(char *file, int *vorbisCommentFound)
 				*vorbisCommentFound = 1;
 		} else if (block->type == FLAC__METADATA_TYPE_STREAMINFO) {
 			if (!ret)
-				ret = newMpdTag();
+				ret = tag_new();
 			ret->time = ((float)block->data.stream_info.
 				     total_samples) /
 			    block->data.stream_info.sample_rate + 0.5;
@@ -350,9 +350,9 @@ static MpdTag *flacMetadataDup(char *file, int *vorbisCommentFound)
 	return ret;
 }
 
-static MpdTag *flacTagDup(char *file)
+static struct mpd_tag *flacTagDup(char *file)
 {
-	MpdTag *ret = NULL;
+	struct mpd_tag *ret = NULL;
 	int foundVorbisComment = 0;
 
 	ret = flacMetadataDup(file, &foundVorbisComment);
@@ -362,10 +362,10 @@ static MpdTag *flacTagDup(char *file)
 		return NULL;
 	}
 	if (!foundVorbisComment) {
-		MpdTag *temp = id3Dup(file);
+		struct mpd_tag *temp = tag_id3_load(file);
 		if (temp) {
 			temp->time = ret->time;
-			freeMpdTag(ret);
+			tag_free(ret);
 			ret = temp;
 		}
 	}
@@ -466,9 +466,9 @@ static int flac_decode(InputStream * inStream)
 /* some of this stuff is duplicated from oggflac_plugin.c */
 extern InputPlugin oggflacPlugin;
 
-static MpdTag *oggflac_tag_dup(char *file)
+static struct mpd_tag *oggflac_tag_dup(char *file)
 {
-	MpdTag *ret = NULL;
+	struct mpd_tag *ret = NULL;
 	FLAC__Metadata_Iterator *it;
 	FLAC__StreamMetadata *block;
 	FLAC__Metadata_Chain *chain = FLAC__metadata_chain_new();
@@ -484,7 +484,7 @@ static MpdTag *oggflac_tag_dup(char *file)
 			ret = copyVorbisCommentBlockToMpdTag(block, ret);
 		} else if (block->type == FLAC__METADATA_TYPE_STREAMINFO) {
 			if (!ret)
-				ret = newMpdTag();
+				ret = tag_new();
 			ret->time = ((float)block->data.stream_info.
 				     total_samples) /
 			    block->data.stream_info.sample_rate + 0.5;
diff --git a/src/inputPlugins/mod_plugin.c b/src/inputPlugins/mod_plugin.c
index df938f0ed..586d87ae9 100644
--- a/src/inputPlugins/mod_plugin.c
+++ b/src/inputPlugins/mod_plugin.c
@@ -205,9 +205,9 @@ static int mod_decode(char *path)
 	return 0;
 }
 
-static MpdTag *modTagDup(char *file)
+static struct mpd_tag *modTagDup(char *file)
 {
-	MpdTag *ret = NULL;
+	struct mpd_tag *ret = NULL;
 	MODULE *moduleHandle;
 	char *title;
 
@@ -224,12 +224,12 @@ static MpdTag *modTagDup(char *file)
 	}
 	Player_Free(moduleHandle);
 
-	ret = newMpdTag();
+	ret = tag_new();
 
 	ret->time = 0;
 	title = xstrdup(Player_LoadTitle(file));
 	if (title)
-		addItemToMpdTag(ret, TAG_ITEM_TITLE, title);
+		tag_add_item(ret, TAG_ITEM_TITLE, title);
 
 	MikMod_Exit();
 
diff --git a/src/inputPlugins/mp3_plugin.c b/src/inputPlugins/mp3_plugin.c
index f1304f401..ff3de80a3 100644
--- a/src/inputPlugins/mp3_plugin.c
+++ b/src/inputPlugins/mp3_plugin.c
@@ -301,13 +301,13 @@ static ReplayGainInfo *parseId3ReplayGainInfo(struct id3_tag *tag)
 
 #ifdef HAVE_ID3TAG
 static void mp3_parseId3Tag(mp3DecodeData * data, size_t tagsize,
-			    MpdTag ** mpdTag, ReplayGainInfo ** replayGainInfo)
+			    struct mpd_tag ** mpdTag, ReplayGainInfo ** replayGainInfo)
 {
 	struct id3_tag *id3Tag = NULL;
 	id3_length_t count;
 	id3_byte_t const *id3_data;
 	id3_byte_t *allocated = NULL;
-	MpdTag *tmpMpdTag;
+	struct mpd_tag *tmpMpdTag;
 	ReplayGainInfo *tmpReplayGainInfo;
 
 	count = data->stream.bufend - data->stream.this_frame;
@@ -348,10 +348,10 @@ static void mp3_parseId3Tag(mp3DecodeData * data, size_t tagsize,
 		goto fail;
 
 	if (mpdTag) {
-		tmpMpdTag = parseId3Tag(id3Tag);
+		tmpMpdTag = tag_id3_import(id3Tag);
 		if (tmpMpdTag) {
 			if (*mpdTag)
-				freeMpdTag(*mpdTag);
+				tag_free(*mpdTag);
 			*mpdTag = tmpMpdTag;
 		}
 	}
@@ -373,7 +373,7 @@ fail:
 #endif
 
 static enum mp3_action
-decodeNextFrameHeader(mp3DecodeData * data, MpdTag ** tag,
+decodeNextFrameHeader(mp3DecodeData * data, struct mpd_tag ** tag,
 		      ReplayGainInfo ** replayGainInfo)
 {
 	enum mad_layer layer;
@@ -688,7 +688,7 @@ static int parse_lame(struct lame *lame, struct mad_bitptr *ptr, int *bitlen)
 }
 
 static int decodeFirstFrame(mp3DecodeData * data,
-                            MpdTag ** tag, ReplayGainInfo ** replayGainInfo)
+                            struct mpd_tag ** tag, ReplayGainInfo ** replayGainInfo)
 {
 	struct xing xing;
 	struct lame lame;
@@ -811,7 +811,7 @@ static int getMp3TotalTime(char *file)
 }
 
 static int openMp3FromInputStream(InputStream * inStream, mp3DecodeData * data,
-				  MpdTag ** tag,
+				  struct mpd_tag ** tag,
 				  ReplayGainInfo ** replayGainInfo)
 {
 	initMp3DecodeData(data, inStream);
@@ -819,7 +819,7 @@ static int openMp3FromInputStream(InputStream * inStream, mp3DecodeData * data,
 	if (decodeFirstFrame(data, tag, replayGainInfo) < 0) {
 		mp3DecodeDataFinalize(data);
 		if (tag && *tag)
-			freeMpdTag(*tag);
+			tag_free(*tag);
 		return -1;
 	}
 
@@ -923,13 +923,12 @@ mp3Read(mp3DecodeData * data, ReplayGainInfo ** replayGainInfo)
 		}
 
 		if (data->inStream->metaTitle) {
-			MpdTag *tag = newMpdTag();
+			struct mpd_tag *tag = tag_new();
 			if (data->inStream->metaName) {
-				addItemToMpdTag(tag,
-						TAG_ITEM_NAME,
-						data->inStream->metaName);
+				tag_add_item(tag, TAG_ITEM_NAME,
+					     data->inStream->metaName);
 			}
-			addItemToMpdTag(tag, TAG_ITEM_TITLE,
+			tag_add_item(tag, TAG_ITEM_TITLE,
 					data->inStream->metaTitle);
 			free(data->inStream->metaTitle);
 			data->inStream->metaTitle = NULL;
@@ -1033,7 +1032,7 @@ static void initAudioFormatFromMp3DecodeData(mp3DecodeData * data,
 static int mp3_decode(InputStream * inStream)
 {
 	mp3DecodeData data;
-	MpdTag *tag = NULL;
+	struct mpd_tag *tag = NULL;
 	ReplayGainInfo *replayGainInfo = NULL;
 
 	if (openMp3FromInputStream(inStream, &data, &tag, &replayGainInfo) < 0) {
@@ -1051,23 +1050,23 @@ static int mp3_decode(InputStream * inStream)
 
 	if (inStream->metaTitle) {
 		if (tag)
-			freeMpdTag(tag);
-		tag = newMpdTag();
-		addItemToMpdTag(tag, TAG_ITEM_TITLE, inStream->metaTitle);
+			tag_free(tag);
+		tag = tag_new();
+		tag_add_item(tag, TAG_ITEM_TITLE, inStream->metaTitle);
 		free(inStream->metaTitle);
 		inStream->metaTitle = NULL;
 		if (inStream->metaName) {
-			addItemToMpdTag(tag, TAG_ITEM_NAME, inStream->metaName);
+			tag_add_item(tag, TAG_ITEM_NAME, inStream->metaName);
 		}
 	} else if (tag) {
 		if (inStream->metaName) {
-			clearItemsFromMpdTag(tag, TAG_ITEM_NAME);
-			addItemToMpdTag(tag, TAG_ITEM_NAME, inStream->metaName);
+			tag_clear_items_by_type(tag, TAG_ITEM_NAME);
+			tag_add_item(tag, TAG_ITEM_NAME, inStream->metaName);
 		}
 	} else if (inStream->metaName) {
-		tag = newMpdTag();
+		tag = tag_new();
 		if (inStream->metaName) {
-			addItemToMpdTag(tag, TAG_ITEM_NAME, inStream->metaName);
+			tag_add_item(tag, TAG_ITEM_NAME, inStream->metaName);
 		}
 	}
 	if (tag)
@@ -1081,18 +1080,18 @@ static int mp3_decode(InputStream * inStream)
 	return 0;
 }
 
-static MpdTag *mp3_tagDup(char *file)
+static struct mpd_tag *mp3_tagDup(char *file)
 {
-	MpdTag *ret = NULL;
+	struct mpd_tag *ret = NULL;
 	int total_time;
 
-	ret = id3Dup(file);
+	ret = tag_id3_load(file);
 
 	total_time = getMp3TotalTime(file);
 
 	if (total_time >= 0) {
 		if (!ret)
-			ret = newMpdTag();
+			ret = tag_new();
 		ret->time = total_time;
 	} else {
 		DEBUG("mp3_tagDup: Failed to get total song time from: %s\n",
diff --git a/src/inputPlugins/mp4_plugin.c b/src/inputPlugins/mp4_plugin.c
index 8e3d02354..cc2b89efc 100644
--- a/src/inputPlugins/mp4_plugin.c
+++ b/src/inputPlugins/mp4_plugin.c
@@ -284,9 +284,9 @@ static int mp4_decode(InputStream * inStream)
 	return 0;
 }
 
-static MpdTag *mp4DataDup(char *file, int *mp4MetadataFound)
+static struct mpd_tag *mp4DataDup(char *file, int *mp4MetadataFound)
 {
-	MpdTag *ret = NULL;
+	struct mpd_tag *ret = NULL;
 	InputStream inStream;
 	mp4ff_t *mp4fh;
 	mp4ff_callback_t *callback;
@@ -322,14 +322,14 @@ static MpdTag *mp4DataDup(char *file, int *mp4MetadataFound)
 		return NULL;
 	}
 
-	ret = newMpdTag();
+	ret = tag_new();
 	file_time = mp4ff_get_track_duration_use_offsets(mp4fh, track);
 	scale = mp4ff_time_scale(mp4fh, track);
 	if (scale < 0) {
 		mp4ff_close(mp4fh);
 		closeInputStream(&inStream);
 		free(callback);
-		freeMpdTag(ret);
+		tag_free(ret);
 		return NULL;
 	}
 	ret->time = ((float)file_time) / scale + 0.5;
@@ -341,25 +341,25 @@ static MpdTag *mp4DataDup(char *file, int *mp4MetadataFound)
 		mp4ff_meta_get_by_index(mp4fh, i, &item, &value);
 
 		if (0 == strcasecmp("artist", item)) {
-			addItemToMpdTag(ret, TAG_ITEM_ARTIST, value);
+			tag_add_item(ret, TAG_ITEM_ARTIST, value);
 			*mp4MetadataFound = 1;
 		} else if (0 == strcasecmp("title", item)) {
-			addItemToMpdTag(ret, TAG_ITEM_TITLE, value);
+			tag_add_item(ret, TAG_ITEM_TITLE, value);
 			*mp4MetadataFound = 1;
 		} else if (0 == strcasecmp("album", item)) {
-			addItemToMpdTag(ret, TAG_ITEM_ALBUM, value);
+			tag_add_item(ret, TAG_ITEM_ALBUM, value);
 			*mp4MetadataFound = 1;
 		} else if (0 == strcasecmp("track", item)) {
-			addItemToMpdTag(ret, TAG_ITEM_TRACK, value);
+			tag_add_item(ret, TAG_ITEM_TRACK, value);
 			*mp4MetadataFound = 1;
 		} else if (0 == strcasecmp("disc", item)) {	/* Is that the correct id? */
-			addItemToMpdTag(ret, TAG_ITEM_DISC, value);
+			tag_add_item(ret, TAG_ITEM_DISC, value);
 			*mp4MetadataFound = 1;
 		} else if (0 == strcasecmp("genre", item)) {
-			addItemToMpdTag(ret, TAG_ITEM_GENRE, value);
+			tag_add_item(ret, TAG_ITEM_GENRE, value);
 			*mp4MetadataFound = 1;
 		} else if (0 == strcasecmp("date", item)) {
-			addItemToMpdTag(ret, TAG_ITEM_DATE, value);
+			tag_add_item(ret, TAG_ITEM_DATE, value);
 			*mp4MetadataFound = 1;
 		}
 
@@ -373,19 +373,19 @@ static MpdTag *mp4DataDup(char *file, int *mp4MetadataFound)
 	return ret;
 }
 
-static MpdTag *mp4TagDup(char *file)
+static struct mpd_tag *mp4TagDup(char *file)
 {
-	MpdTag *ret = NULL;
+	struct mpd_tag *ret = NULL;
 	int mp4MetadataFound = 0;
 
 	ret = mp4DataDup(file, &mp4MetadataFound);
 	if (!ret)
 		return NULL;
 	if (!mp4MetadataFound) {
-		MpdTag *temp = id3Dup(file);
+		struct mpd_tag *temp = tag_id3_load(file);
 		if (temp) {
 			temp->time = ret->time;
-			freeMpdTag(ret);
+			tag_free(ret);
 			ret = temp;
 		}
 	}
diff --git a/src/inputPlugins/mpc_plugin.c b/src/inputPlugins/mpc_plugin.c
index ea27d1dbf..e5502a2f0 100644
--- a/src/inputPlugins/mpc_plugin.c
+++ b/src/inputPlugins/mpc_plugin.c
@@ -273,9 +273,9 @@ static float mpcGetTime(char *file)
 	return total_time;
 }
 
-static MpdTag *mpcTagDup(char *file)
+static struct mpd_tag *mpcTagDup(char *file)
 {
-	MpdTag *ret = NULL;
+	struct mpd_tag *ret = NULL;
 	float total_time = mpcGetTime(file);
 
 	if (total_time < 0) {
@@ -284,11 +284,11 @@ static MpdTag *mpcTagDup(char *file)
 		return NULL;
 	}
 
-	ret = apeDup(file);
+	ret = tag_ape_load(file);
 	if (!ret)
-		ret = id3Dup(file);
+		ret = tag_id3_load(file);
 	if (!ret)
-		ret = newMpdTag();
+		ret = tag_new();
 	ret->time = total_time;
 
 	return ret;
diff --git a/src/inputPlugins/oggflac_plugin.c b/src/inputPlugins/oggflac_plugin.c
index 4b3bb0a6b..841030481 100644
--- a/src/inputPlugins/oggflac_plugin.c
+++ b/src/inputPlugins/oggflac_plugin.c
@@ -28,6 +28,8 @@
 #include "../utils.h"
 #include "../log.h"
 
+#include <OggFLAC/seekable_stream_decoder.h>
+
 static void oggflac_cleanup(FlacData * data,
 			    OggFLAC__SeekableStreamDecoder * decoder)
 {
@@ -216,7 +218,7 @@ static void of_metadata_dup_cb(mpd_unused const OggFLAC__SeekableStreamDecoder *
 	switch (block->type) {
 	case FLAC__METADATA_TYPE_STREAMINFO:
 		if (!data->tag)
-			data->tag = newMpdTag();
+			data->tag = tag_new();
 		data->tag->time = ((float)block->data.stream_info.
 				   total_samples) /
 		    block->data.stream_info.sample_rate + 0.5;
@@ -300,7 +302,7 @@ fail:
 }
 
 /* public functions: */
-static MpdTag *oggflac_TagDup(char *file)
+static struct mpd_tag *oggflac_TagDup(char *file)
 {
 	InputStream inStream;
 	OggFLAC__SeekableStreamDecoder *decoder;
diff --git a/src/inputPlugins/oggvorbis_plugin.c b/src/inputPlugins/oggvorbis_plugin.c
index d14ae2bac..bb8af4465 100644
--- a/src/inputPlugins/oggvorbis_plugin.c
+++ b/src/inputPlugins/oggvorbis_plugin.c
@@ -145,7 +145,7 @@ static const char *VORBIS_COMMENT_DISC_KEY = "discnumber";
 
 static unsigned int ogg_parseCommentAddToTag(char *comment,
 					     unsigned int itemType,
-					     MpdTag ** tag)
+					     struct mpd_tag ** tag)
 {
 	const char *needle;
 	unsigned int len;
@@ -163,9 +163,9 @@ static unsigned int ogg_parseCommentAddToTag(char *comment,
 
 	if (strncasecmp(comment, needle, len) == 0 && *(comment + len) == '=') {
 		if (!*tag)
-			*tag = newMpdTag();
+			*tag = tag_new();
 
-		addItemToMpdTag(*tag, itemType, comment + len + 1);
+		tag_add_item(*tag, itemType, comment + len + 1);
 
 		return 1;
 	}
@@ -173,9 +173,9 @@ static unsigned int ogg_parseCommentAddToTag(char *comment,
 	return 0;
 }
 
-static MpdTag *oggCommentsParse(char **comments)
+static struct mpd_tag *oggCommentsParse(char **comments)
 {
-	MpdTag *tag = NULL;
+	struct mpd_tag *tag = NULL;
 
 	while (*comments) {
 		int j;
@@ -193,18 +193,18 @@ static void putOggCommentsIntoOutputBuffer(char *streamName,
 					   char **comments,
 					   float cur_time)
 {
-	MpdTag *tag;
+	struct mpd_tag *tag;
 
 	tag = oggCommentsParse(comments);
 	if (!tag && streamName) {
-		tag = newMpdTag();
+		tag = tag_new();
 	}
 	if (!tag)
 		return;
 
 	if (streamName) {
-		clearItemsFromMpdTag(tag, TAG_ITEM_NAME);
-		addItemToMpdTag(tag, TAG_ITEM_NAME, streamName);
+		tag_clear_items_by_type(tag, TAG_ITEM_NAME);
+		tag_add_item(tag, TAG_ITEM_NAME, streamName);
 	}
 
 	metadata_pipe_send(tag, cur_time);
@@ -332,9 +332,9 @@ static int oggvorbis_decode(InputStream * inStream)
 	return 0;
 }
 
-static MpdTag *oggvorbis_TagDup(char *file)
+static struct mpd_tag *oggvorbis_TagDup(char *file)
 {
-	MpdTag *ret;
+	struct mpd_tag *ret;
 	FILE *fp;
 	OggVorbis_File vf;
 
@@ -352,7 +352,7 @@ static MpdTag *oggvorbis_TagDup(char *file)
 	ret = oggCommentsParse(ov_comment(&vf, -1)->user_comments);
 
 	if (!ret)
-		ret = newMpdTag();
+		ret = tag_new();
 	ret->time = (int)(ov_time_total(&vf, -1) + 0.5);
 
 	ov_clear(&vf);
diff --git a/src/inputPlugins/wavpack_plugin.c b/src/inputPlugins/wavpack_plugin.c
index c7e024a41..77339dabd 100644
--- a/src/inputPlugins/wavpack_plugin.c
+++ b/src/inputPlugins/wavpack_plugin.c
@@ -270,10 +270,10 @@ static ReplayGainInfo *wavpack_replaygain(WavpackContext *wpc)
 /*
  * Reads metainfo from the specified file.
  */
-static MpdTag *wavpack_tagdup(char *fname)
+static struct mpd_tag *wavpack_tagdup(char *fname)
 {
 	WavpackContext *wpc;
-	MpdTag *tag;
+	struct mpd_tag *tag;
 	char error[ERRORLEN];
 	char *s;
 	int ssize;
@@ -285,12 +285,7 @@ static MpdTag *wavpack_tagdup(char *fname)
 		return NULL;
 	}
 
-	tag = newMpdTag();
-	if (tag == NULL) {
-		ERROR("failed to newMpdTag()\n");
-		return NULL;
-	}
-
+	tag = tag_new();
 	tag->time =
 		(float)WavpackGetNumSamples(wpc) / WavpackGetSampleRate(wpc);
 
@@ -314,7 +309,7 @@ static MpdTag *wavpack_tagdup(char *fname)
 			}
 
 			WavpackGetTagItem(wpc, tagtypes[i].name, s, j);
-			addItemToMpdTag(tag, tagtypes[i].type, s);
+			tag_add_item(tag, tagtypes[i].type, s);
 		}
 	}
 
diff --git a/src/locate.c b/src/locate.c
index f68afdedb..76e229f4c 100644
--- a/src/locate.c
+++ b/src/locate.c
@@ -142,11 +142,11 @@ static int strstrSearchTag(Song * song, enum tag_type type, char *str)
 
 	for (i = 0; i < song->tag->numOfItems && !ret; i++) {
 		if (type != LOCATE_TAG_ANY_TYPE &&
-		    song->tag->items[i].type != type) {
+		    song->tag->items[i]->type != type) {
 			continue;
 		}
 
-		duplicate = strDupToUpper(song->tag->items[i].value);
+		duplicate = strDupToUpper(song->tag->items[i]->value);
 		if (strstr(duplicate, str))
 			ret = 1;
 		free(duplicate);
@@ -186,11 +186,11 @@ static int tagItemFoundAndMatches(Song * song, enum tag_type type, char *str)
 
 	for (i = 0; i < song->tag->numOfItems; i++) {
 		if (type != LOCATE_TAG_ANY_TYPE &&
-		    song->tag->items[i].type != type) {
+		    song->tag->items[i]->type != type) {
 			continue;
 		}
 
-		if (0 == strcmp(str, song->tag->items[i].value))
+		if (0 == strcmp(str, song->tag->items[i]->value))
 			return 1;
 	}
 
diff --git a/src/main.c b/src/main.c
index 9d75fadc7..236b3bbe1 100644
--- a/src/main.c
+++ b/src/main.c
@@ -393,7 +393,7 @@ int main(int argc, char *argv[])
 		killFromPidFile();
 
 	initStats();
-	initTagConfig();
+	tag_lib_init();
 	initLog(options.verbose);
 
 	if (options.createDB <= 0)
diff --git a/src/metadata_pipe.c b/src/metadata_pipe.c
index d5bef630e..d968dee27 100644
--- a/src/metadata_pipe.c
+++ b/src/metadata_pipe.c
@@ -30,7 +30,7 @@ static struct ringbuf *mp;
 struct tag_container {
 	float metadata_time;
 	mpd_uint8 seq; /* ob.seq_decoder at time of metadata_pipe_send() */
-	MpdTag *tag; /* our payload */
+	struct mpd_tag *tag; /* our payload */
 };
 
 /*
@@ -39,13 +39,13 @@ struct tag_container {
  * done from one thread, so it will never block or clobber.
  */
 static pthread_mutex_t read_lock = PTHREAD_MUTEX_INITIALIZER;
-static MpdTag *current_tag; /* requires read_lock for both r/w access */
+static struct mpd_tag *current_tag; /* requires read_lock for both r/w access */
 
 static void metadata_pipe_finish(void)
 {
 	ringbuf_free(mp);
 	if (current_tag)
-		freeMpdTag(current_tag);
+		tag_free(current_tag);
 }
 
 void init_metadata_pipe(void)
@@ -54,7 +54,7 @@ void init_metadata_pipe(void)
 	atexit(metadata_pipe_finish);
 }
 
-void metadata_pipe_send(MpdTag *tag, float metadata_time)
+void metadata_pipe_send(struct mpd_tag *tag, float metadata_time)
 {
 	struct tag_container tc;
 	size_t written;
@@ -64,7 +64,7 @@ void metadata_pipe_send(MpdTag *tag, float metadata_time)
 	if (mpd_unlikely(ringbuf_write_space(mp)
 	                 < sizeof(struct tag_container))) {
 		DEBUG("metadata_pipe: insufficient buffer space, dropping\n");
-		freeMpdTag(tag);
+		tag_free(tag);
 		return;
 	}
 
@@ -75,14 +75,14 @@ void metadata_pipe_send(MpdTag *tag, float metadata_time)
 	assert(written == sizeof(struct tag_container));
 }
 
-MpdTag * metadata_pipe_recv(void)
+struct mpd_tag * metadata_pipe_recv(void)
 {
 	struct tag_container tc;
 	size_t r;
 	static const size_t mpd_uint8_max = 255; /* XXX CLEANUP */
 	mpd_uint8 expect_seq = ob_get_player_sequence();
 	unsigned long current_time = ob_get_elapsed_time();
-	MpdTag *tag = NULL;
+	struct mpd_tag *tag = NULL;
 
 	if (pthread_mutex_trylock(&read_lock) == EBUSY)
 		return NULL;
@@ -95,20 +95,20 @@ retry:
 	if (expect_seq == tc.seq) {
 		if (current_time < tc.metadata_time)
 			goto out; /* not ready for tag yet */
-		if (mpdTagsAreEqual(tc.tag, current_tag)) {
-			freeMpdTag(tc.tag);
+		if (tag_equal(tc.tag, current_tag)) {
+			tag_free(tc.tag);
 			ringbuf_read_advance(mp, sizeof(struct tag_container));
 			goto out; /* nothing changed, don't bother */
 		}
-		tag = mpdTagDup(tc.tag);
+		tag = tag_dup(tc.tag);
 		if (current_tag)
-			freeMpdTag(current_tag);
+			tag_free(current_tag);
 		current_tag = tc.tag;
 		ringbuf_read_advance(mp, sizeof(struct tag_container));
 	} else if (expect_seq > tc.seq ||
 	           (!expect_seq && tc.seq == mpd_uint8_max)) {
 		DEBUG("metadata_pipe: reader is ahead of writer\n");
-		freeMpdTag(tc.tag);
+		tag_free(tc.tag);
 		ringbuf_read_advance(mp, sizeof(struct tag_container));
 		goto retry; /* read and skip packets */
 	} else {
@@ -120,14 +120,14 @@ out:
 	return tag;
 }
 
-MpdTag *metadata_pipe_current(void)
+struct mpd_tag *metadata_pipe_current(void)
 {
-	MpdTag *tag;
+	struct mpd_tag *tag;
 
 	assert(! pthread_equal(pthread_self(), dc.thread));
 	if (pthread_mutex_trylock(&read_lock) == EBUSY)
 		return NULL;
-	tag = current_tag ? mpdTagDup(current_tag) : NULL;
+	tag = current_tag ? tag_dup(current_tag) : NULL;
 	pthread_mutex_unlock(&read_lock);
 
 	return tag;
@@ -142,11 +142,11 @@ void metadata_pipe_clear(void)
 
 	while ((r = ringbuf_read(mp, &tc, sizeof(struct tag_container)))) {
 		assert(r == sizeof(struct tag_container));
-		freeMpdTag(tc.tag);
+		tag_free(tc.tag);
 	}
 
 	if (current_tag) {
-		freeMpdTag(current_tag);
+		tag_free(current_tag);
 		current_tag = NULL;
 	}
 
diff --git a/src/metadata_pipe.h b/src/metadata_pipe.h
index e54c67584..cb891aa80 100644
--- a/src/metadata_pipe.h
+++ b/src/metadata_pipe.h
@@ -29,21 +29,21 @@ void init_metadata_pipe(void);
  * DO NOT FREE the tag placed into the pipe; that is that job of the
  * caller of metadata_pipe_recv() or metadata_pipe_clear().
  */
-void metadata_pipe_send(MpdTag * tag, float metadata_time);
+void metadata_pipe_send(struct mpd_tag * tag, float metadata_time);
 
 /*
- * Reads and consumes one MpdTag pointer off the pipe.  The caller
- * of this MUST free the MpdTag pointer after it is done using it.
+ * Reads and consumes one struct mpd_tag pointer off the pipe.  The caller
+ * of this MUST free the struct mpd_tag pointer after it is done using it.
  */
-MpdTag * metadata_pipe_recv(void);
+struct mpd_tag * metadata_pipe_recv(void);
 
 /*
- * Returns the last read MpdTag from metadata_pipe_recv(), caller
+ * Returns the last read struct mpd_tag from metadata_pipe_recv(), caller
  * must free this pointer when it is done using it.
  */
-MpdTag * metadata_pipe_current(void);
+struct mpd_tag * metadata_pipe_current(void);
 
-/* Clears all MpdTag pointers on the pipe, freeing all associated elements */
+/* Clears all struct mpd_tag pointers on the pipe, freeing all associated elements */
 void metadata_pipe_clear(void);
 
 #endif /* METADATA_PIPE_H */
diff --git a/src/outputBuffer.c b/src/outputBuffer.c
index a9a64712a..ac0f420d8 100644
--- a/src/outputBuffer.c
+++ b/src/outputBuffer.c
@@ -410,13 +410,13 @@ static void new_song_chunk(struct ob_chunk *a)
 
 static void send_next_tag(void)
 {
-	static MpdTag *last_tag;
-	MpdTag *tag;
+	static struct mpd_tag *last_tag;
+	struct mpd_tag *tag;
 
 	if ((tag = metadata_pipe_recv())) { /* streaming tag */
 		DEBUG("Caught new metadata! %p\n", tag);
 		sendMetadataToAudioDevice(tag);
-		freeMpdTag(tag);
+		tag_free(tag);
 		wakeup_main_task(); /* call sync_metadata() in playlist.c */
 	} else if ((tag = playlist_current_tag())) { /* static file tag */
 		/* shouldn't need mpdTagsAreEqual here for static tags */
diff --git a/src/path.c b/src/path.c
index 6aaff84cf..ceb00c5de 100644
--- a/src/path.c
+++ b/src/path.c
@@ -47,7 +47,7 @@ static char *path_conv_charset(char *dest, const char *to,
 char *fs_charset_to_utf8(char *dst, const char *str)
 {
 	char *ret = path_conv_charset(dst, "UTF-8", fsCharset, str);
-	return (ret && !validUtf8String(ret)) ? NULL : ret;
+	return (ret && !validUtf8String(ret, strlen(ret))) ? NULL : ret;
 }
 
 char *utf8_to_fs_charset(char *dst, const char *str)
diff --git a/src/playlist.c b/src/playlist.c
index ab5908ff1..9546dee70 100644
--- a/src/playlist.c
+++ b/src/playlist.c
@@ -969,7 +969,7 @@ int playPlaylistById(int fd, int id, int stopOnError)
 }
 
 /* This is used when we stream data out to shout while playing static files */
-MpdTag *playlist_current_tag(void)
+struct mpd_tag *playlist_current_tag(void)
 {
 	Song *song = song_at(playlist.current);
 
@@ -981,18 +981,18 @@ MpdTag *playlist_current_tag(void)
 static void sync_metadata(void)
 {
 	Song *song;
-	MpdTag *tag;
+	struct mpd_tag *tag;
 
 	if (!(tag = metadata_pipe_current()))
 		return;
 	song = song_at(playlist.current);
 	if (!song || song->type != SONG_TYPE_URL ||
-	    mpdTagsAreEqual(song->tag, tag)) {
-		freeMpdTag(tag);
+	    tag_equal(song->tag, tag)) {
+		tag_free(tag);
 		return;
 	}
 	if (song->tag)
-		freeMpdTag(song->tag);
+		tag_free(song->tag);
 	song->tag = tag;
 	playlist.songMod[playlist.order[playlist.current]] = playlist.version;
 	incrPlaylistVersion();
diff --git a/src/playlist.h b/src/playlist.h
index c51cb4d73..629bfa057 100644
--- a/src/playlist.h
+++ b/src/playlist.h
@@ -128,6 +128,6 @@ void findSongsInPlaylist(int fd, int numItems, LocateTagItem * items);
 
 int valid_playlist_name(int err_fd, const char *utf8path);
 
-MpdTag *playlist_current_tag(void);
+struct mpd_tag *playlist_current_tag(void);
 
 #endif
diff --git a/src/song.c b/src/song.c
index cc1547d10..9b8b7d4db 100644
--- a/src/song.c
+++ b/src/song.c
@@ -32,7 +32,7 @@
 
 #include "os_compat.h"
 
-Song *newNullSong(void)
+static Song *newNullSong(void)
 {
 	Song *song = xmalloc(sizeof(Song));
 
@@ -92,7 +92,7 @@ void freeJustSong(Song * song)
 {
 	free(song->url);
 	if (song->tag)
-		freeMpdTag(song->tag);
+		tag_free(song->tag);
 	free(song);
 }
 
@@ -147,7 +147,7 @@ int printSongInfo(int fd, Song * song)
 	printSongUrl(fd, song);
 
 	if (song->tag)
-		printMpdTag(fd, song->tag);
+		tag_print(fd, song->tag);
 
 	return 0;
 }
@@ -200,7 +200,8 @@ static void insertSongIntoList(SongList * list, ListNode ** nextSongNode,
 	} else if (cmpRet == 0) {
 		Song *tempSong = (Song *) ((*nextSongNode)->data);
 		if (tempSong->mtime != song->mtime) {
-			freeMpdTag(tempSong->tag);
+			tag_free(tempSong->tag);
+			tag_end_add(song->tag);
 			tempSong->tag = song->tag;
 			tempSong->mtime = song->mtime;
 			song->tag = NULL;
@@ -239,9 +240,12 @@ void readSongInfoIntoList(FILE * fp, SongList * list, Directory * parentDir)
 
 	while (myFgets(buffer, bufferSize, fp) && 0 != strcmp(SONG_END, buffer)) {
 		if (0 == strncmp(SONG_KEY, buffer, strlen(SONG_KEY))) {
-			if (song)
+			if (song) {
 				insertSongIntoList(list, &nextSongNode,
 						   song->url, song);
+				if (song->tag != NULL)
+					tag_end_add(song->tag);
+			}
 
 			song = newNullSong();
 			song->url = xstrdup(buffer + strlen(SONG_KEY));
@@ -256,15 +260,21 @@ void readSongInfoIntoList(FILE * fp, SongList * list, Directory * parentDir)
 			   song->url = xstrdup(&(buffer[strlen(SONG_FILE)]));
 			 */
 		} else if (matchesAnMpdTagItemKey(buffer, &itemType)) {
-			if (!song->tag)
-				song->tag = newMpdTag();
-			addItemToMpdTag(song->tag, itemType,
-					&(buffer
-					  [strlen(mpdTagItemKeys[itemType]) +
-					   2]));
+			if (!song->tag) {
+				song->tag = tag_new();
+				tag_begin_add(song->tag);
+			}
+
+			tag_add_item(song->tag, itemType,
+				     &(buffer
+				       [strlen(mpdTagItemKeys[itemType]) +
+					2]));
 		} else if (0 == strncmp(SONG_TIME, buffer, strlen(SONG_TIME))) {
-			if (!song->tag)
-				song->tag = newMpdTag();
+			if (!song->tag) {
+				song->tag = tag_new();
+				tag_begin_add(song->tag);
+			}
+
 			song->tag->time = atoi(&(buffer[strlen(SONG_TIME)]));
 		} else if (0 == strncmp(SONG_MTIME, buffer, strlen(SONG_MTIME))) {
 			song->mtime = atoi(&(buffer[strlen(SONG_MTIME)]));
@@ -273,8 +283,11 @@ void readSongInfoIntoList(FILE * fp, SongList * list, Directory * parentDir)
 			FATAL("songinfo: unknown line in db: %s\n", buffer);
 	}
 
-	if (song)
+	if (song) {
 		insertSongIntoList(list, &nextSongNode, song->url, song);
+		if (song->tag != NULL)
+			tag_end_add(song->tag);
+	}
 
 	while (nextSongNode) {
 		nodeTemp = nextSongNode->nextNode;
@@ -295,7 +308,7 @@ int updateSongInfo(Song * song)
 		rmp2amp_r(abs_path, abs_path);
 
 		if (song->tag)
-			freeMpdTag(song->tag);
+			tag_free(song->tag);
 
 		song->tag = NULL;
 
diff --git a/src/song.h b/src/song.h
index 8e2de410a..b7dc6c90b 100644
--- a/src/song.h
+++ b/src/song.h
@@ -36,15 +36,13 @@
 typedef struct _Song {
 	char *url;
 	mpd_sint8 type;
-	MpdTag *tag;
+	struct mpd_tag *tag;
 	struct _Directory *parentDir;
 	time_t mtime;
 } Song;
 
 typedef List SongList;
 
-Song *newNullSong(void);
-
 Song *newSong(const char *url, int songType, struct _Directory *parentDir);
 
 void freeSong(Song *);
diff --git a/src/tag.c b/src/tag.c
index c1ccd0a42..0e0ff1ab7 100644
--- a/src/tag.c
+++ b/src/tag.c
@@ -17,27 +17,27 @@
  */
 
 #include "tag.h"
+#include "tag_pool.h"
 #include "myfprintf.h"
 #include "utils.h"
 #include "utf8.h"
 #include "log.h"
 #include "conf.h"
-#include "charConv.h"
 #include "tagTracker.h"
 #include "song.h"
 
-#ifdef HAVE_ID3TAG
-#  define isId3v1(tag) (id3_tag_options(tag, 0, 0) & ID3_TAG_OPTION_ID3V1)
-#  ifndef ID3_FRAME_COMPOSER
-#    define ID3_FRAME_COMPOSER "TCOM"
-#  endif
-#  ifndef ID3_FRAME_PERFORMER
-#    define ID3_FRAME_PERFORMER "TOPE"
-#  endif
-#  ifndef ID3_FRAME_DISC
-#    define ID3_FRAME_DISC "TPOS"
-#  endif
+/**
+ * Maximum number of items managed in the bulk list; if it is
+ * exceeded, we switch back to "normal" reallocation.
+ */
+#define BULK_MAX 64
+
+static struct {
+#ifndef NDEBUG
+	int busy;
 #endif
+	struct tag_item *items[BULK_MAX];
+} bulk;
 
 const char *mpdTagItemKeys[TAG_NUM_OF_ITEM_TYPES] = {
 	"Artist",
@@ -55,7 +55,7 @@ const char *mpdTagItemKeys[TAG_NUM_OF_ITEM_TYPES] = {
 
 static mpd_sint8 ignoreTagItems[TAG_NUM_OF_ITEM_TYPES];
 
-void initTagConfig(void)
+void tag_lib_init(void)
 {
 	int quit = 0;
 	char *temp;
@@ -104,7 +104,7 @@ void initTagConfig(void)
 	free(temp);
 }
 
-void printTagTypes(int fd)
+void tag_print_types(int fd)
 {
 	int i;
 
@@ -114,7 +114,7 @@ void printTagTypes(int fd)
 	}
 }
 
-void printMpdTag(int fd, MpdTag * tag)
+void tag_print(int fd, const struct mpd_tag *tag)
 {
 	int i;
 
@@ -122,340 +122,14 @@ void printMpdTag(int fd, MpdTag * tag)
 		fdprintf(fd, SONG_TIME "%i\n", tag->time);
 
 	for (i = 0; i < tag->numOfItems; i++) {
-		fdprintf(fd, "%s: %s\n", mpdTagItemKeys[tag->items[i].type],
-			  tag->items[i].value);
-	}
-}
-
-#ifdef HAVE_ID3TAG
-/* This will try to convert a string to utf-8,
- */
-static id3_utf8_t * processID3FieldString (int is_id3v1, const id3_ucs4_t *ucs4, int type)
-{
-    id3_utf8_t *utf8;
-    id3_latin1_t *isostr;
-	char *encoding;
-
-    if (type == TAG_ITEM_GENRE)
-	    ucs4 = id3_genre_name(ucs4);
-    /* use encoding field here? */
-    if (is_id3v1 &&
-	(encoding = getConfigParamValue(CONF_ID3V1_ENCODING))) {
-	    isostr = id3_ucs4_latin1duplicate(ucs4);
-	    if (mpd_unlikely(!isostr)) {
-		    return NULL;
-	    }
-	    setCharSetConversion("UTF-8", encoding);
-	    utf8 = xmalloc(strlen((char *)isostr) + 1);
-	    utf8 = (id3_utf8_t *)char_conv_str((char *)utf8, (char *)isostr);
-	    if (!utf8) {
-		    DEBUG("Unable to convert %s string to UTF-8: "
-			  "'%s'\n", encoding, isostr);
-		    free(isostr);
-		    return NULL;
-	    }
-	    free(isostr);
-    } else {
-	    utf8 = id3_ucs4_utf8duplicate(ucs4);
-	    if (mpd_unlikely(!utf8)) {
-		    return NULL;
-	    }
-    }
-    return utf8;
-}
-
-static MpdTag *getID3Info(
-	struct id3_tag *tag, const char *id, int type, MpdTag * mpdTag)
-{
-	struct id3_frame const *frame;
-	id3_ucs4_t const *ucs4;
-	id3_utf8_t *utf8;
-	union id3_field const *field;
-	unsigned int nstrings, i;
-
-	frame = id3_tag_findframe(tag, id, 0);
-	/* Check frame */
-	if (!frame)
-	{
-		return mpdTag;
-	}
-	/* Check fields in frame */
-	if(frame->nfields == 0)
-	{
-		DEBUG(__FILE__": Frame has no fields\n");
-		return mpdTag;
-	}
-
-	/* Starting with T is a stringlist */
-	if (id[0] == 'T')
-	{
-		/* This one contains 2 fields:
-		 * 1st: Text encoding
-		 * 2: Stringlist
-		 * Shamefully this isn't the RL case.
-		 * But I am going to enforce it anyway. 
-		 */
-		if(frame->nfields != 2) 
-		{
-			DEBUG(__FILE__": Invalid number '%i' of fields for TXX frame\n",frame->nfields);
-			return mpdTag;
-		}
-		field = &frame->fields[0];
-		/**
-		 * First field is encoding field.
-		 * This is ignored by mpd.
-		 */
-		if(field->type != ID3_FIELD_TYPE_TEXTENCODING)
-		{
-			DEBUG(__FILE__": Expected encoding, found: %i\n",field->type);
-		}
-		/* Process remaining fields, should be only one */
-		field = &frame->fields[1];
-		/* Encoding field */
-		if(field->type == ID3_FIELD_TYPE_STRINGLIST) {
-			/* Get the number of strings available */
-			nstrings = id3_field_getnstrings(field);
-			for (i = 0; i < nstrings; i++) {
-				ucs4 = id3_field_getstrings(field,i);
-				if(!ucs4)
-					continue;
-				utf8 = processID3FieldString(isId3v1(tag),ucs4, type);
-				if(!utf8)
-					continue;
-
-				if (mpdTag == NULL)
-					mpdTag = newMpdTag();
-				addItemToMpdTag(mpdTag, type, (char *)utf8);
-				free(utf8);
-			}
-		}
-		else {
-			ERROR(__FILE__": Field type not processed: %i\n",(int)id3_field_gettextencoding(field));
-		}
-	}
-	/* A comment frame */
-	else if(!strcmp(ID3_FRAME_COMMENT, id))
-	{
-		/* A comment frame is different... */
-	/* 1st: encoding
-         * 2nd: Language
-         * 3rd: String
-         * 4th: FullString.
-         * The 'value' we want is in the 4th field
-         */
-		if(frame->nfields == 4)
-		{
-			/* for now I only read the 4th field, with the fullstring */
-			field = &frame->fields[3];
-			if(field->type == ID3_FIELD_TYPE_STRINGFULL)
-			{
-				ucs4 = id3_field_getfullstring(field);
-				if(ucs4)
-				{
-					utf8 = processID3FieldString(isId3v1(tag),ucs4, type);
-					if(utf8)
-					{
-						if (mpdTag == NULL)
-							mpdTag = newMpdTag();
-						addItemToMpdTag(mpdTag, type, (char *)utf8);
-						free(utf8);
-					}
-				}
-			}
-			else
-			{
-				DEBUG(__FILE__": 4th field in comment frame differs from expected, got '%i': ignoring\n",field->type);
-			}
-		}
-		else
-		{
-			DEBUG(__FILE__": Invalid 'comments' tag, got '%i' fields instead of 4\n", frame->nfields);
-		}
-	}
-	/* Unsupported */
-	else {
-		DEBUG(__FILE__": Unsupported tag type requrested\n");
-		return mpdTag;
-	}
-
-	return mpdTag;
-}
-#endif
-
-#ifdef HAVE_ID3TAG
-MpdTag *parseId3Tag(struct id3_tag * tag)
-{
-	MpdTag *ret = NULL;
-
-	ret = getID3Info(tag, ID3_FRAME_ARTIST, TAG_ITEM_ARTIST, ret);
-	ret = getID3Info(tag, ID3_FRAME_TITLE, TAG_ITEM_TITLE, ret);
-	ret = getID3Info(tag, ID3_FRAME_ALBUM, TAG_ITEM_ALBUM, ret);
-	ret = getID3Info(tag, ID3_FRAME_TRACK, TAG_ITEM_TRACK, ret);
-	ret = getID3Info(tag, ID3_FRAME_YEAR, TAG_ITEM_DATE, ret);
-	ret = getID3Info(tag, ID3_FRAME_GENRE, TAG_ITEM_GENRE, ret);
-	ret = getID3Info(tag, ID3_FRAME_COMPOSER, TAG_ITEM_COMPOSER, ret);
-	ret = getID3Info(tag, ID3_FRAME_PERFORMER, TAG_ITEM_PERFORMER, ret);
-	ret = getID3Info(tag, ID3_FRAME_COMMENT, TAG_ITEM_COMMENT, ret);
-	ret = getID3Info(tag, ID3_FRAME_DISC, TAG_ITEM_DISC, ret);
-
-	return ret;
-}
-#endif
-
-#ifdef HAVE_ID3TAG
-static int fillBuffer(void *buf, size_t size, FILE * stream,
-		      long offset, int whence)
-{
-	if (fseek(stream, offset, whence) != 0) return 0;
-	return fread(buf, 1, size, stream);
-}
-#endif
-
-#ifdef HAVE_ID3TAG
-static int getId3v2FooterSize(FILE * stream, long offset, int whence)
-{
-	id3_byte_t buf[ID3_TAG_QUERYSIZE];
-	int bufsize;
-
-	bufsize = fillBuffer(buf, ID3_TAG_QUERYSIZE, stream, offset, whence);
-	if (bufsize <= 0) return 0;
-	return id3_tag_query(buf, bufsize);
-}
-#endif
-
-#ifdef HAVE_ID3TAG
-static struct id3_tag *getId3Tag(FILE * stream, long offset, int whence)
-{
-	struct id3_tag *tag;
-	id3_byte_t queryBuf[ID3_TAG_QUERYSIZE];
-	id3_byte_t *tagBuf;
-	int tagSize;
-	int queryBufSize;
-	int tagBufSize;
-
-	/* It's ok if we get less than we asked for */
-	queryBufSize = fillBuffer(queryBuf, ID3_TAG_QUERYSIZE,
-	                          stream, offset, whence);
-	if (queryBufSize <= 0) return NULL;
-
-	/* Look for a tag header */
-	tagSize = id3_tag_query(queryBuf, queryBufSize);
-	if (tagSize <= 0) return NULL;
-
-	/* Found a tag.  Allocate a buffer and read it in. */
-	tagBuf = xmalloc(tagSize);
-	if (!tagBuf) return NULL;
-
-	tagBufSize = fillBuffer(tagBuf, tagSize, stream, offset, whence);
-	if (tagBufSize < tagSize) {
-		free(tagBuf);
-		return NULL;
-	}
-
-	tag = id3_tag_parse(tagBuf, tagBufSize);
-
-	free(tagBuf);
-
-	return tag;
-}
-#endif
-
-#ifdef HAVE_ID3TAG
-static struct id3_tag *findId3TagFromBeginning(FILE * stream)
-{
-	struct id3_tag *tag;
-	struct id3_tag *seektag;
-	struct id3_frame *frame;
-	int seek;
-
-	tag = getId3Tag(stream, 0, SEEK_SET);
-	if (!tag) {
-		return NULL;
-	} else if (isId3v1(tag)) {
-		/* id3v1 tags don't belong here */
-		id3_tag_delete(tag);
-		return NULL;
-	}
-
-	/* We have an id3v2 tag, so let's look for SEEK frames */
-	while ((frame = id3_tag_findframe(tag, "SEEK", 0))) {
-		/* Found a SEEK frame, get it's value */
-		seek = id3_field_getint(id3_frame_field(frame, 0));
-		if (seek < 0)
-			break;
-
-		/* Get the tag specified by the SEEK frame */
-		seektag = getId3Tag(stream, seek, SEEK_CUR);
-		if (!seektag || isId3v1(seektag))
-			break;
-
-		/* Replace the old tag with the new one */
-		id3_tag_delete(tag);
-		tag = seektag;
-	}
-
-	return tag;
-}
-#endif
-
-#ifdef HAVE_ID3TAG
-static struct id3_tag *findId3TagFromEnd(FILE * stream)
-{
-	struct id3_tag *tag;
-	struct id3_tag *v1tag;
-	int tagsize;
-
-	/* Get an id3v1 tag from the end of file for later use */
-	v1tag = getId3Tag(stream, -128, SEEK_END);
-
-	/* Get the id3v2 tag size from the footer (located before v1tag) */
-	tagsize = getId3v2FooterSize(stream, (v1tag ? -128 : 0) - 10, SEEK_END);
-	if (tagsize >= 0)
-		return v1tag;
-
-	/* Get the tag which the footer belongs to */
-	tag = getId3Tag(stream, tagsize, SEEK_CUR);
-	if (!tag)
-		return v1tag;
-
-	/* We have an id3v2 tag, so ditch v1tag */
-	id3_tag_delete(v1tag);
-
-	return tag;
-}
-#endif
-
-MpdTag *id3Dup(char *file)
-{
-	MpdTag *ret = NULL;
-#ifdef HAVE_ID3TAG
-	struct id3_tag *tag;
-	FILE *stream;
-
-	stream = fopen(file, "r");
-	if (!stream) {
-		DEBUG("id3Dup: Failed to open file: '%s', %s\n", file,
-		      strerror(errno));
-		return NULL;
+		fdprintf(fd, "%s: %s\n", mpdTagItemKeys[tag->items[i]->type],
+			  tag->items[i]->value);
 	}
-
-	tag = findId3TagFromBeginning(stream);
-	if (!tag)
-		tag = findId3TagFromEnd(stream);
-
-	fclose(stream);
-
-	if (!tag)
-		return NULL;
-	ret = parseId3Tag(tag);
-	id3_tag_delete(tag);
-#endif
-	return ret;
 }
 
-MpdTag *apeDup(char *file)
+struct mpd_tag *tag_ape_load(const char *file)
 {
-	MpdTag *ret = NULL;
+	struct mpd_tag *ret = NULL;
 	FILE *fp;
 	int tagCount;
 	char *buffer = NULL;
@@ -556,9 +230,9 @@ MpdTag *apeDup(char *file)
 			for (i = 0; i < 7; i++) {
 				if (strcasecmp(key, apeItems[i]) == 0) {
 					if (!ret)
-						ret = newMpdTag();
-					addItemToMpdTagWithLen(ret, tagItems[i],
-							       p, size);
+						ret = tag_new();
+					tag_add_item_n(ret, tagItems[i],
+						       p, size);
 				}
 			}
 		}
@@ -574,21 +248,21 @@ fail:
 	return ret;
 }
 
-MpdTag *newMpdTag(void)
+struct mpd_tag *tag_new(void)
 {
-	MpdTag *ret = xmalloc(sizeof(MpdTag));
+	struct mpd_tag *ret = xmalloc(sizeof(*ret));
 	ret->items = NULL;
 	ret->time = -1;
 	ret->numOfItems = 0;
 	return ret;
 }
 
-static void deleteItem(MpdTag * tag, int idx)
+static void deleteItem(struct mpd_tag *tag, int idx)
 {
 	assert(idx < tag->numOfItems);
 	tag->numOfItems--;
 
-	removeTagItemString(tag->items[idx].type, tag->items[idx].value);
+	tag_pool_put_item(tag->items[idx]);
 	/* free(tag->items[idx].value); */
 
 	if (tag->numOfItems - idx > 0) {
@@ -598,19 +272,19 @@ static void deleteItem(MpdTag * tag, int idx)
 
 	if (tag->numOfItems > 0) {
 		tag->items = xrealloc(tag->items,
-				     tag->numOfItems * sizeof(MpdTagItem));
+				      tag->numOfItems * sizeof(*tag->items));
 	} else {
 		free(tag->items);
 		tag->items = NULL;
 	}
 }
 
-void clearItemsFromMpdTag(MpdTag * tag, enum tag_type type)
+void tag_clear_items_by_type(struct mpd_tag *tag, enum tag_type type)
 {
 	int i;
 
 	for (i = 0; i < tag->numOfItems; i++) {
-		if (tag->items[i].type == type) {
+		if (tag->items[i]->type == type) {
 			deleteItem(tag, i);
 			/* decrement since when just deleted this node */
 			i--;
@@ -618,17 +292,24 @@ void clearItemsFromMpdTag(MpdTag * tag, enum tag_type type)
 	}
 }
 
-static void clearMpdTag(MpdTag * tag)
+static void clearMpdTag(struct mpd_tag *tag)
 {
 	int i;
 
 	for (i = 0; i < tag->numOfItems; i++) {
-		removeTagItemString(tag->items[i].type, tag->items[i].value);
 		/* free(tag->items[i].value); */
+		tag_pool_put_item(tag->items[i]);
 	}
 
-	if (tag->items)
+	if (tag->items == bulk.items) {
+#ifndef NDEBUG
+		assert(bulk.busy);
+		bulk.busy = 0;
+#endif
+	} else if (tag->items) {
 		free(tag->items);
+	}
+
 	tag->items = NULL;
 
 	tag->numOfItems = 0;
@@ -636,31 +317,33 @@ static void clearMpdTag(MpdTag * tag)
 	tag->time = -1;
 }
 
-void freeMpdTag(MpdTag * tag)
+void tag_free(struct mpd_tag *tag)
 {
 	clearMpdTag(tag);
 	free(tag);
 }
 
-MpdTag *mpdTagDup(MpdTag * tag)
+struct mpd_tag *tag_dup(const struct mpd_tag *tag)
 {
-	MpdTag *ret;
+	struct mpd_tag *ret;
 	int i;
 
 	if (!tag)
 		return NULL;
 
-	ret = newMpdTag();
+	ret = tag_new();
 	ret->time = tag->time;
+	ret->numOfItems = tag->numOfItems;
+	ret->items = xmalloc(ret->numOfItems * sizeof(ret->items[0]));
 
 	for (i = 0; i < tag->numOfItems; i++) {
-		addItemToMpdTag(ret, tag->items[i].type, tag->items[i].value);
+		ret->items[i] = tag_pool_dup_item(tag->items[i]);
 	}
 
 	return ret;
 }
 
-int mpdTagsAreEqual(MpdTag * tag1, MpdTag * tag2)
+int tag_equal(const struct mpd_tag *tag1, const struct mpd_tag *tag2)
 {
 	int i;
 
@@ -676,9 +359,9 @@ int mpdTagsAreEqual(MpdTag * tag1, MpdTag * tag2)
 		return 0;
 
 	for (i = 0; i < tag1->numOfItems; i++) {
-		if (tag1->items[i].type != tag2->items[i].type)
+		if (tag1->items[i]->type != tag2->items[i]->type)
 			return 0;
-		if (strcmp(tag1->items[i].value, tag2->items[i].value)) {
+		if (strcmp(tag1->items[i]->value, tag2->items[i]->value)) {
 			return 0;
 		}
 	}
@@ -686,39 +369,95 @@ int mpdTagsAreEqual(MpdTag * tag1, MpdTag * tag2)
 	return 1;
 }
 
-#define fixUtf8(str) { \
-	if(str && !validUtf8String(str)) { \
-		char * temp; \
-		DEBUG("not valid utf8 in tag: %s\n",str); \
-		temp = latin1StrToUtf8Dup(str); \
-		free(str); \
-		str = temp; \
-	} \
+static inline const char *fix_utf8(const char *str, size_t *length_r) {
+	const char *temp;
+
+	assert(str != NULL);
+
+	if (validUtf8String(str, *length_r))
+		return str;
+
+	DEBUG("not valid utf8 in tag: %s\n",str);
+	temp = latin1StrToUtf8Dup(str);
+	*length_r = strlen(temp);
+	return temp;
 }
 
-static void appendToTagItems(MpdTag * tag, enum tag_type type,
-			     const char *value, size_t len)
+void tag_begin_add(struct mpd_tag *tag)
 {
-	unsigned int i = tag->numOfItems;
-	char *duplicated = xmalloc(len + 1);
+	assert(!bulk.busy);
+	assert(tag != NULL);
+	assert(tag->items == NULL);
+	assert(tag->numOfItems == 0);
+
+#ifndef NDEBUG
+	bulk.busy = 1;
+#endif
+	tag->items = bulk.items;
+}
 
-	memcpy(duplicated, value, len);
-	duplicated[len] = '\0';
+void tag_end_add(struct mpd_tag *tag)
+{
+	if (tag->items == bulk.items) {
+		assert(tag->numOfItems <= BULK_MAX);
+
+		if (tag->numOfItems > 0) {
+			/* copy the tag items from the bulk list over
+			   to a new list (which fits exactly) */
+			tag->items = xmalloc(tag->numOfItems *
+					     sizeof(tag->items[0]));
+			memcpy(tag->items, bulk.items,
+			       tag->numOfItems * sizeof(tag->items[0]));
+		} else
+			tag->items = NULL;
+	}
+
+#ifndef NDEBUG
+	bulk.busy = 0;
+#endif
+}
 
-	fixUtf8(duplicated);
-	stripReturnChar(duplicated);
+static void appendToTagItems(struct mpd_tag *tag, enum tag_type type,
+			     const char *value, size_t len)
+{
+	unsigned int i = tag->numOfItems;
+	const char *p;
+
+	p = fix_utf8(value, &len);
+	if (memchr(p, '\n', len) != NULL) {
+		char *duplicated = xmalloc(len + 1);
+		memcpy(duplicated, p, len);
+		duplicated[len] = '\0';
+		if (p != value)
+			free(deconst_ptr(p));
+
+		stripReturnChar(duplicated);
+		p = duplicated;
+	}
 
 	tag->numOfItems++;
-	tag->items = xrealloc(tag->items, tag->numOfItems * sizeof(MpdTagItem));
 
-	tag->items[i].type = type;
-	tag->items[i].value = getTagItemString(type, duplicated);
+	if (tag->items != bulk.items)
+		/* bulk mode disabled */
+		tag->items = xrealloc(tag->items,
+				      tag->numOfItems * sizeof(*tag->items));
+	else if (tag->numOfItems >= BULK_MAX) {
+		/* bulk list already full - switch back to non-bulk */
+		assert(bulk.busy);
+
+		tag->items = xmalloc(tag->numOfItems * sizeof(tag->items[0]));
+		memcpy(tag->items, bulk.items,
+		       (tag->numOfItems - 1) * sizeof(tag->items[0]));
+	}
+
+	tag->items[i] = tag_pool_get_item(type, p, len);
 
-	free(duplicated);
+	if (p != value)
+		free(deconst_ptr(p));
 }
 
-void addItemToMpdTagWithLen(MpdTag * tag, enum tag_type itemType,
-			    const char *value, size_t len)
+void tag_add_item_n(struct mpd_tag *tag, enum tag_type itemType,
+		    const char *value, size_t len)
 {
 	if (ignoreTagItems[itemType])
 	{
diff --git a/src/tag.h b/src/tag.h
index a9bf19934..a05f7654a 100644
--- a/src/tag.h
+++ b/src/tag.h
@@ -19,14 +19,9 @@
 #ifndef TAG_H
 #define TAG_H
 
-#include "../config.h"
-
 #include "mpd_types.h"
 #include "os_compat.h"
-
-#ifdef HAVE_ID3TAG
-#include <id3tag.h>
-#endif
+#include "gcc.h"
 
 enum tag_type {
 	TAG_ITEM_ARTIST,
@@ -45,45 +40,56 @@ enum tag_type {
 
 extern const char *mpdTagItemKeys[];
 
-typedef struct _MpdTagItem {
+struct tag_item {
 	enum tag_type type;
-	char *value;
-} MpdTagItem;
+	char value[1];
+} mpd_packed;
 
-typedef struct _MpdTag {
+struct mpd_tag {
 	int time;
-	MpdTagItem *items;
+	struct tag_item **items;
 	mpd_uint8 numOfItems;
-} MpdTag;
+};
 
-#ifdef HAVE_ID3TAG
-MpdTag *parseId3Tag(struct id3_tag *);
-#endif
+struct mpd_tag *tag_ape_load(const char *file);
 
-MpdTag *apeDup(char *file);
+struct mpd_tag *tag_new(void);
 
-MpdTag *id3Dup(char *file);
+void tag_lib_init(void);
 
-MpdTag *newMpdTag(void);
+void tag_clear_items_by_type(struct mpd_tag *tag, enum tag_type itemType);
 
-void initTagConfig(void);
+void tag_free(struct mpd_tag *tag);
 
-void clearItemsFromMpdTag(MpdTag * tag, enum tag_type itemType);
+/**
+ * Gives an optional hint to the tag library that we will now add
+ * several tag items; this is used by the library to optimize memory
+ * allocation.  Only one tag may be in this state, and this tag must
+ * not have any items yet.  You must call tag_end_add() when you are
+ * done.
+ */
+void tag_begin_add(struct mpd_tag *tag);
 
-void freeMpdTag(MpdTag * tag);
+/**
+ * Finishes the operation started with tag_begin_add().
+ */
+void tag_end_add(struct mpd_tag *tag);
 
-void addItemToMpdTagWithLen(MpdTag * tag, enum tag_type itemType,
-			    const char *value, size_t len);
+void tag_add_item_n(struct mpd_tag *tag, enum tag_type itemType,
+		    const char *value, size_t len);
 
-#define addItemToMpdTag(tag, itemType, value) \
-		addItemToMpdTagWithLen(tag, itemType, value, strlen(value))
+static inline void tag_add_item(struct mpd_tag *tag, enum tag_type itemType,
+				const char *value)
+{
+	tag_add_item_n(tag, itemType, value, strlen(value));
+}
 
-void printTagTypes(int fd);
+void tag_print_types(int fd);
 
-void printMpdTag(int fd, MpdTag * tag);
+void tag_print(int fd, const struct mpd_tag *tag);
 
-MpdTag *mpdTagDup(MpdTag * tag);
+struct mpd_tag *tag_dup(const struct mpd_tag *tag);
 
-int mpdTagsAreEqual(MpdTag * tag1, MpdTag * tag2);
+int tag_equal(const struct mpd_tag *tag1, const struct mpd_tag *tag2);
 
 #endif
diff --git a/src/tagTracker.c b/src/tagTracker.c
index 892cc2955..bea58ae4c 100644
--- a/src/tagTracker.c
+++ b/src/tagTracker.c
@@ -19,137 +19,101 @@
 #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)
+static int visit_tag_items(int fd mpd_unused, Song *song, void *data)
 {
-	TreeIterator iter;
-	char *ret;
+	enum tag_type type = (enum tag_type)(size_t)data;
+	unsigned i;
 
-	pthread_mutex_lock(&tag_item_lock);
-
-	if (tagTrees[type] == NULL)
-	{
-		tagTrees[type] = MakeTree((TreeCompareKeyFunction)strcmp,
-					  (TreeFreeFunction)free,
-					  (TreeFreeFunction)free);
-	}
+	if (song->tag == NULL)
+		return 0;
 
-	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;
+	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;
-
-	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);
-	}
+	traverseAllIn(-1, NULL, visit_tag_items, NULL, (void*)(size_t)type);
 
-	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;
+	struct visited *v = find_visit(type, str);
+	size_t length;
 
-	if (!tagTrees[type])
+	if (v != NULL)
 		return;
 
-	if (!FindInTree(tagTrees[type], str, &iter))
-		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/tagTracker.h b/src/tagTracker.h
index 84506426e..2edb5aad0 100644
--- a/src/tagTracker.h
+++ b/src/tagTracker.h
@@ -19,10 +19,6 @@
 #ifndef TAG_TRACKER_H
 #define TAG_TRACKER_H
 
-char *getTagItemString(int type, char *string);
-
-void removeTagItemString(int type, char *string);
-
 int getNumberOfTagItems(int type);
 
 void printMemorySavedByTagTracker(void);
diff --git a/src/tag_id3.c b/src/tag_id3.c
new file mode 100644
index 000000000..83b78150a
--- /dev/null
+++ b/src/tag_id3.c
@@ -0,0 +1,367 @@
+/* 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 "tag_id3.h"
+#include "tag.h"
+#include "utils.h"
+#include "log.h"
+#include "conf.h"
+#include "charConv.h"
+
+#ifdef HAVE_ID3TAG
+#include <id3tag.h>
+#endif
+
+#ifdef HAVE_ID3TAG
+#  define isId3v1(tag) (id3_tag_options(tag, 0, 0) & ID3_TAG_OPTION_ID3V1)
+#  ifndef ID3_FRAME_COMPOSER
+#    define ID3_FRAME_COMPOSER "TCOM"
+#  endif
+#  ifndef ID3_FRAME_PERFORMER
+#    define ID3_FRAME_PERFORMER "TOPE"
+#  endif
+#  ifndef ID3_FRAME_DISC
+#    define ID3_FRAME_DISC "TPOS"
+#  endif
+#endif
+
+#ifdef HAVE_ID3TAG
+/* This will try to convert a string to utf-8,
+ */
+static id3_utf8_t * processID3FieldString (int is_id3v1, const id3_ucs4_t *ucs4, int type)
+{
+    id3_utf8_t *utf8;
+    id3_latin1_t *isostr;
+	char *encoding;
+
+    if (type == TAG_ITEM_GENRE)
+	    ucs4 = id3_genre_name(ucs4);
+    /* use encoding field here? */
+    if (is_id3v1 &&
+	(encoding = getConfigParamValue(CONF_ID3V1_ENCODING))) {
+	    isostr = id3_ucs4_latin1duplicate(ucs4);
+	    if (mpd_unlikely(!isostr)) {
+		    return NULL;
+	    }
+	    setCharSetConversion("UTF-8", encoding);
+	    utf8 = xmalloc(strlen((char *)isostr) + 1);
+	    utf8 = (id3_utf8_t *)char_conv_str((char *)utf8, (char *)isostr);
+	    if (!utf8) {
+		    DEBUG("Unable to convert %s string to UTF-8: "
+			  "'%s'\n", encoding, isostr);
+		    free(isostr);
+		    return NULL;
+	    }
+	    free(isostr);
+    } else {
+	    utf8 = id3_ucs4_utf8duplicate(ucs4);
+	    if (mpd_unlikely(!utf8)) {
+		    return NULL;
+	    }
+    }
+    return utf8;
+}
+
+static struct mpd_tag *getID3Info(
+	struct id3_tag *tag, const char *id, int type, struct mpd_tag *mpdTag)
+{
+	struct id3_frame const *frame;
+	id3_ucs4_t const *ucs4;
+	id3_utf8_t *utf8;
+	union id3_field const *field;
+	unsigned int nstrings, i;
+
+	frame = id3_tag_findframe(tag, id, 0);
+	/* Check frame */
+	if (!frame)
+	{
+		return mpdTag;
+	}
+	/* Check fields in frame */
+	if(frame->nfields == 0)
+	{
+		DEBUG(__FILE__": Frame has no fields\n");
+		return mpdTag;
+	}
+
+	/* Starting with T is a stringlist */
+	if (id[0] == 'T')
+	{
+		/* This one contains 2 fields:
+		 * 1st: Text encoding
+		 * 2: Stringlist
+		 * Shamefully this isn't the RL case.
+		 * But I am going to enforce it anyway.
+		 */
+		if(frame->nfields != 2)
+		{
+			DEBUG(__FILE__": Invalid number '%i' of fields for TXX frame\n",frame->nfields);
+			return mpdTag;
+		}
+		field = &frame->fields[0];
+		/**
+		 * First field is encoding field.
+		 * This is ignored by mpd.
+		 */
+		if(field->type != ID3_FIELD_TYPE_TEXTENCODING)
+		{
+			DEBUG(__FILE__": Expected encoding, found: %i\n",field->type);
+		}
+		/* Process remaining fields, should be only one */
+		field = &frame->fields[1];
+		/* Encoding field */
+		if(field->type == ID3_FIELD_TYPE_STRINGLIST) {
+			/* Get the number of strings available */
+			nstrings = id3_field_getnstrings(field);
+			for (i = 0; i < nstrings; i++) {
+				ucs4 = id3_field_getstrings(field,i);
+				if(!ucs4)
+					continue;
+				utf8 = processID3FieldString(isId3v1(tag),ucs4, type);
+				if(!utf8)
+					continue;
+
+				if (mpdTag == NULL)
+					mpdTag = tag_new();
+				tag_add_item(mpdTag, type, (char *)utf8);
+				free(utf8);
+			}
+		}
+		else {
+			ERROR(__FILE__": Field type not processed: %i\n",(int)id3_field_gettextencoding(field));
+		}
+	}
+	/* A comment frame */
+	else if(!strcmp(ID3_FRAME_COMMENT, id))
+	{
+		/* A comment frame is different... */
+	/* 1st: encoding
+         * 2nd: Language
+         * 3rd: String
+         * 4th: FullString.
+         * The 'value' we want is in the 4th field
+         */
+		if(frame->nfields == 4)
+		{
+			/* for now I only read the 4th field, with the fullstring */
+			field = &frame->fields[3];
+			if(field->type == ID3_FIELD_TYPE_STRINGFULL)
+			{
+				ucs4 = id3_field_getfullstring(field);
+				if(ucs4)
+				{
+					utf8 = processID3FieldString(isId3v1(tag),ucs4, type);
+					if(utf8)
+					{
+						if (mpdTag == NULL)
+							mpdTag = tag_new();
+						tag_add_item(mpdTag, type, (char *)utf8);
+						free(utf8);
+					}
+				}
+			}
+			else
+			{
+				DEBUG(__FILE__": 4th field in comment frame differs from expected, got '%i': ignoring\n",field->type);
+			}
+		}
+		else
+		{
+			DEBUG(__FILE__": Invalid 'comments' tag, got '%i' fields instead of 4\n", frame->nfields);
+		}
+	}
+	/* Unsupported */
+	else {
+		DEBUG(__FILE__": Unsupported tag type requrested\n");
+		return mpdTag;
+	}
+
+	return mpdTag;
+}
+#endif
+
+#ifdef HAVE_ID3TAG
+struct mpd_tag *tag_id3_import(struct id3_tag * tag)
+{
+	struct mpd_tag *ret = NULL;
+
+	ret = getID3Info(tag, ID3_FRAME_ARTIST, TAG_ITEM_ARTIST, ret);
+	ret = getID3Info(tag, ID3_FRAME_TITLE, TAG_ITEM_TITLE, ret);
+	ret = getID3Info(tag, ID3_FRAME_ALBUM, TAG_ITEM_ALBUM, ret);
+	ret = getID3Info(tag, ID3_FRAME_TRACK, TAG_ITEM_TRACK, ret);
+	ret = getID3Info(tag, ID3_FRAME_YEAR, TAG_ITEM_DATE, ret);
+	ret = getID3Info(tag, ID3_FRAME_GENRE, TAG_ITEM_GENRE, ret);
+	ret = getID3Info(tag, ID3_FRAME_COMPOSER, TAG_ITEM_COMPOSER, ret);
+	ret = getID3Info(tag, ID3_FRAME_PERFORMER, TAG_ITEM_PERFORMER, ret);
+	ret = getID3Info(tag, ID3_FRAME_COMMENT, TAG_ITEM_COMMENT, ret);
+	ret = getID3Info(tag, ID3_FRAME_DISC, TAG_ITEM_DISC, ret);
+
+	return ret;
+}
+#endif
+
+#ifdef HAVE_ID3TAG
+static int fillBuffer(void *buf, size_t size, FILE * stream,
+		      long offset, int whence)
+{
+	if (fseek(stream, offset, whence) != 0) return 0;
+	return fread(buf, 1, size, stream);
+}
+#endif
+
+#ifdef HAVE_ID3TAG
+static int getId3v2FooterSize(FILE * stream, long offset, int whence)
+{
+	id3_byte_t buf[ID3_TAG_QUERYSIZE];
+	int bufsize;
+
+	bufsize = fillBuffer(buf, ID3_TAG_QUERYSIZE, stream, offset, whence);
+	if (bufsize <= 0) return 0;
+	return id3_tag_query(buf, bufsize);
+}
+#endif
+
+#ifdef HAVE_ID3TAG
+static struct id3_tag *getId3Tag(FILE * stream, long offset, int whence)
+{
+	struct id3_tag *tag;
+	id3_byte_t queryBuf[ID3_TAG_QUERYSIZE];
+	id3_byte_t *tagBuf;
+	int tagSize;
+	int queryBufSize;
+	int tagBufSize;
+
+	/* It's ok if we get less than we asked for */
+	queryBufSize = fillBuffer(queryBuf, ID3_TAG_QUERYSIZE,
+	                          stream, offset, whence);
+	if (queryBufSize <= 0) return NULL;
+
+	/* Look for a tag header */
+	tagSize = id3_tag_query(queryBuf, queryBufSize);
+	if (tagSize <= 0) return NULL;
+
+	/* Found a tag.  Allocate a buffer and read it in. */
+	tagBuf = xmalloc(tagSize);
+	if (!tagBuf) return NULL;
+
+	tagBufSize = fillBuffer(tagBuf, tagSize, stream, offset, whence);
+	if (tagBufSize < tagSize) {
+		free(tagBuf);
+		return NULL;
+	}
+
+	tag = id3_tag_parse(tagBuf, tagBufSize);
+
+	free(tagBuf);
+
+	return tag;
+}
+#endif
+
+#ifdef HAVE_ID3TAG
+static struct id3_tag *findId3TagFromBeginning(FILE * stream)
+{
+	struct id3_tag *tag;
+	struct id3_tag *seektag;
+	struct id3_frame *frame;
+	int seek;
+
+	tag = getId3Tag(stream, 0, SEEK_SET);
+	if (!tag) {
+		return NULL;
+	} else if (isId3v1(tag)) {
+		/* id3v1 tags don't belong here */
+		id3_tag_delete(tag);
+		return NULL;
+	}
+
+	/* We have an id3v2 tag, so let's look for SEEK frames */
+	while ((frame = id3_tag_findframe(tag, "SEEK", 0))) {
+		/* Found a SEEK frame, get it's value */
+		seek = id3_field_getint(id3_frame_field(frame, 0));
+		if (seek < 0)
+			break;
+
+		/* Get the tag specified by the SEEK frame */
+		seektag = getId3Tag(stream, seek, SEEK_CUR);
+		if (!seektag || isId3v1(seektag))
+			break;
+
+		/* Replace the old tag with the new one */
+		id3_tag_delete(tag);
+		tag = seektag;
+	}
+
+	return tag;
+}
+#endif
+
+#ifdef HAVE_ID3TAG
+static struct id3_tag *findId3TagFromEnd(FILE * stream)
+{
+	struct id3_tag *tag;
+	struct id3_tag *v1tag;
+	int tagsize;
+
+	/* Get an id3v1 tag from the end of file for later use */
+	v1tag = getId3Tag(stream, -128, SEEK_END);
+
+	/* Get the id3v2 tag size from the footer (located before v1tag) */
+	tagsize = getId3v2FooterSize(stream, (v1tag ? -128 : 0) - 10, SEEK_END);
+	if (tagsize >= 0)
+		return v1tag;
+
+	/* Get the tag which the footer belongs to */
+	tag = getId3Tag(stream, tagsize, SEEK_CUR);
+	if (!tag)
+		return v1tag;
+
+	/* We have an id3v2 tag, so ditch v1tag */
+	id3_tag_delete(v1tag);
+
+	return tag;
+}
+#endif
+
+struct mpd_tag *tag_id3_load(const char *file)
+{
+	struct mpd_tag *ret = NULL;
+#ifdef HAVE_ID3TAG
+	struct id3_tag *tag;
+	FILE *stream;
+
+	stream = fopen(file, "r");
+	if (!stream) {
+		DEBUG("tag_id3_load: Failed to open file: '%s', %s\n", file,
+		      strerror(errno));
+		return NULL;
+	}
+
+	tag = findId3TagFromBeginning(stream);
+	if (!tag)
+		tag = findId3TagFromEnd(stream);
+
+	fclose(stream);
+
+	if (!tag)
+		return NULL;
+	ret = tag_id3_import(tag);
+	id3_tag_delete(tag);
+#endif
+	return ret;
+}
diff --git a/src/tag_id3.h b/src/tag_id3.h
new file mode 100644
index 000000000..89eac73aa
--- /dev/null
+++ b/src/tag_id3.h
@@ -0,0 +1,33 @@
+/* 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 MPD_TAG_ID3_H
+#define MPD_TAG_ID3_H
+
+#include "../config.h"
+
+struct mpd_tag;
+
+#ifdef HAVE_ID3TAG
+struct id3_tag;
+struct mpd_tag *tag_id3_import(struct id3_tag *);
+#endif
+
+struct mpd_tag *tag_id3_load(const char *file);
+
+#endif
diff --git a/src/tag_pool.c b/src/tag_pool.c
new file mode 100644
index 000000000..89efef1fc
--- /dev/null
+++ b/src/tag_pool.c
@@ -0,0 +1,139 @@
+/* the Music Player Daemon (MPD)
+ * 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
+ * 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 "tag_pool.h"
+#include "utils.h"
+
+#define NUM_SLOTS 4096
+
+struct slot {
+	struct slot *next;
+	unsigned char ref;
+	struct tag_item item;
+} mpd_packed;
+
+struct slot *slots[NUM_SLOTS];
+
+static inline unsigned
+calc_hash_n(enum tag_type type, const char *p, size_t length)
+{
+	unsigned hash = 5381;
+
+	assert(p != NULL);
+
+	while (length-- > 0)
+		hash = (hash << 5) + hash + *p++;
+
+	return hash ^ type;
+}
+
+static inline unsigned
+calc_hash(enum tag_type type, const char *p)
+{
+	unsigned hash = 5381;
+
+	assert(p != NULL);
+
+	while (*p != 0)
+		hash = (hash << 5) + hash + *p++;
+
+	return hash ^ type;
+}
+
+static inline struct slot *
+tag_item_to_slot(struct tag_item *item)
+{
+	return (struct slot*)(((char*)item) - offsetof(struct slot, item));
+}
+
+static struct slot *slot_alloc(struct slot *next,
+			       enum tag_type type,
+			       const char *value, int length)
+{
+	struct slot *slot = xmalloc(sizeof(*slot) + length);
+	slot->next = next;
+	slot->ref = 1;
+	slot->item.type = type;
+	memcpy(slot->item.value, value, length);
+	slot->item.value[length] = 0;
+	return slot;
+}
+
+struct tag_item *tag_pool_get_item(enum tag_type type,
+				   const char *value, int length)
+{
+	struct slot **slot_p, *slot;
+
+	slot_p = &slots[calc_hash_n(type, value, length) % NUM_SLOTS];
+	for (slot = *slot_p; slot != NULL; slot = slot->next) {
+		if (slot->item.type == type &&
+		    strcmp(value, slot->item.value) == 0 && slot->ref < 0xff) {
+			assert(slot->ref > 0);
+			++slot->ref;
+			return &slot->item;
+		}
+	}
+
+	slot = slot_alloc(*slot_p, type, value, length);
+	*slot_p = slot;
+	return &slot->item;
+}
+
+struct tag_item *tag_pool_dup_item(struct tag_item *item)
+{
+	struct slot *slot = tag_item_to_slot(item);
+
+	assert(slot->ref > 0);
+
+	if (slot->ref < 0xff) {
+		++slot->ref;
+		return item;
+	} else {
+		/* the reference counter overflows above 0xff;
+		   duplicate the item, and start with 1 */
+		size_t length = strlen(item->value);
+		struct slot **slot_p =
+			&slots[calc_hash_n(item->type, item->value,
+					   length) % NUM_SLOTS];
+		slot = slot_alloc(*slot_p, item->type,
+				  item->value, strlen(item->value));
+		*slot_p = slot;
+		return &slot->item;
+	}
+}
+
+void tag_pool_put_item(struct tag_item *item)
+{
+	struct slot **slot_p, *slot;
+
+	slot = tag_item_to_slot(item);
+	assert(slot->ref > 0);
+	--slot->ref;
+
+	if (slot->ref > 0)
+		return;
+
+	for (slot_p = &slots[calc_hash(item->type, item->value) % NUM_SLOTS];
+	     *slot_p != slot;
+	     slot_p = &(*slot_p)->next) {
+		assert(*slot_p != NULL);
+	}
+
+	*slot_p = slot->next;
+	free(slot);
+}
diff --git a/src/tag_pool.h b/src/tag_pool.h
new file mode 100644
index 000000000..e19b2f4b4
--- /dev/null
+++ b/src/tag_pool.h
@@ -0,0 +1,33 @@
+/* the Music Player Daemon (MPD)
+ * 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
+ * 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_POOL_H
+#define TAG_POOL_H
+
+#include "tag.h"
+
+struct tag_item;
+
+struct tag_item *tag_pool_get_item(enum tag_type type,
+				   const char *value, int length);
+
+struct tag_item *tag_pool_dup_item(struct tag_item *item);
+
+void tag_pool_put_item(struct tag_item *item);
+
+#endif
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
diff --git a/src/utf8.c b/src/utf8.c
index e8f3dbdde..1b03f5d20 100644
--- a/src/utf8.c
+++ b/src/utf8.c
@@ -69,10 +69,12 @@ static char utf8_to_latin1_char(const char *inUtf8)
 	return (char)(c + utf8[1]);
 }
 
-static unsigned int validateUtf8Char(const char *inUtf8Char)
+static unsigned int validateUtf8Char(const char *inUtf8Char, size_t length)
 {
 	const unsigned char *utf8Char = (const unsigned char *)inUtf8Char;
 
+	assert(length > 0);
+
 	if (utf8Char[0] < 0x80)
 		return 1;
 
@@ -84,7 +86,7 @@ static unsigned int validateUtf8Char(const char *inUtf8Char)
 			t = (t >> 1);
 			count++;
 		}
-		if (count > 5)
+		if (count > 5 || (size_t)count > length)
 			return 0;
 		for (i = 1; i <= count; i++) {
 			if (utf8Char[i] < 0x80 || utf8Char[i] > 0xBF)
@@ -95,15 +97,17 @@ static unsigned int validateUtf8Char(const char *inUtf8Char)
 		return 0;
 }
 
-int validUtf8String(const char *string)
+int validUtf8String(const char *string, size_t length)
 {
 	unsigned int ret;
 
-	while (*string) {
-		ret = validateUtf8Char(string);
+	while (length > 0) {
+		ret = validateUtf8Char(string, length);
+		assert((size_t)ret <= length);
 		if (0 == ret)
 			return 0;
 		string += ret;
+		length -= ret;
 	}
 
 	return 1;
@@ -118,7 +122,7 @@ char *utf8StrToLatin1Dup(const char *utf8)
 	size_t len = 0;
 
 	while (*utf8) {
-		count = validateUtf8Char(utf8);
+		count = validateUtf8Char(utf8, INT_MAX);
 		if (!count) {
 			free(ret);
 			return NULL;
@@ -140,7 +144,7 @@ char *utf8_to_latin1(char *dest, const char *utf8)
 	size_t len = 0;
 
 	while (*utf8) {
-		count = validateUtf8Char(utf8);
+		count = validateUtf8Char(utf8, INT_MAX);
 		if (count) {
 			*(cp++) = utf8_to_latin1_char(utf8);
 			utf8 += count;
diff --git a/src/utf8.h b/src/utf8.h
index 4a4983064..64e68f914 100644
--- a/src/utf8.h
+++ b/src/utf8.h
@@ -19,11 +19,13 @@
 #ifndef UTF_8_H
 #define UTF_8_H
 
+#include "os_compat.h"
+
 char *latin1StrToUtf8Dup(const char *latin1);
 
 char *utf8StrToLatin1Dup(const char *utf8);
 
-int validUtf8String(const char *string);
+int validUtf8String(const char *string, size_t length);
 
 char *utf8_to_latin1(char *dest, const char *utf8);