tag: added a pool for tag items

The new source tag_pool.c manages a pool of reference counted tag_item
objects.  This is used to merge tag items of the same type and value,
saving lots of memory.  Formerly, only the value itself was pooled,
wasting memory for all the pointers and tag_item structs.

The following results were measured with massif.  Started MPD on
amd64, typed "mpc", no song being played.  My music database contains
35k tagged songs.  The results are what massif reports as "peak".

 0.13.2:     total 14,131,392; useful 11,408,972; extra 2,722,420
 eric:       total 18,370,696; useful 15,648,182; extra 2,722,514
 mk f34f694: total 15,833,952; useful 13,111,470; extra 2,722,482
 mk now:     total 12,837,632; useful 10,626,383; extra 2,211,249

This patch set saves 20% memory, and does a good job in reducing heap
fragmentation.

5 files changed, 147 insertions, 6 deletions

diff --git a/src/Makefile.am b/src/Makefile.am
index d7049cd99..d8640d304 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -81,6 +81,7 @@ mpd_headers = \
 	state_file.h \
 	stats.h \
 	tag.h \
+	tag_pool.h \
 	tag_id3.h \
 	tagTracker.h \
 	utf8.h \
@@ -138,6 +139,7 @@ mpd_SOURCES = \
 	state_file.c \
 	stats.c \
 	tag.c \
+	tag_pool.c \
 	tag_id3.c \
 	tagTracker.c \
 	utils.c \
diff --git a/src/tag.c b/src/tag.c
index 2a4b27488..8cc27b551 100644
--- a/src/tag.c
+++ b/src/tag.c
@@ -17,6 +17,7 @@
  */
 
 #include "tag.h"
+#include "tag_pool.h"
 #include "myfprintf.h"
 #include "utils.h"
 #include "utf8.h"
@@ -248,7 +249,7 @@ static void deleteItem(struct mpd_tag *tag, int idx)
 	assert(idx < tag->numOfItems);
 	tag->numOfItems--;
 
-	free(tag->items[idx]);
+	tag_pool_put_item(tag->items[idx]);
 	/* free(tag->items[idx].value); */
 
 	if (tag->numOfItems - idx > 0) {
@@ -284,7 +285,7 @@ static void clearMpdTag(struct mpd_tag *tag)
 
 	for (i = 0; i < tag->numOfItems; i++) {
 		/* free(tag->items[i].value); */
-		free(tag->items[i]);
+		tag_pool_put_item(tag->items[i]);
 	}
 
 	if (tag->items)
@@ -373,9 +374,7 @@ static void appendToTagItems(struct mpd_tag *tag, enum tag_type type,
 			      tag->numOfItems * sizeof(*tag->items));
 
 	len = strlen(duplicated);
-	tag->items[i] = xmalloc(sizeof(*tag->items[i]) + len);
-	tag->items[i]->type = type;
-	memcpy(tag->items[i]->value, duplicated, len + 1);
+	tag->items[i] = tag_pool_get_item(type, duplicated, len);
 
 	free(duplicated);
 }
diff --git a/src/tag.h b/src/tag.h
index 6452691be..6ca48affa 100644
--- a/src/tag.h
+++ b/src/tag.h
@@ -21,6 +21,7 @@
 
 #include "mpd_types.h"
 #include "os_compat.h"
+#include "gcc.h"
 
 enum tag_type {
 	TAG_ITEM_ARTIST,
@@ -42,7 +43,7 @@ extern const char *mpdTagItemKeys[];
 struct tag_item {
 	enum tag_type type;
 	char value[1];
-} mpd_unused;
+} mpd_packed;
 
 struct mpd_tag {
 	int time;
diff --git a/src/tag_pool.c b/src/tag_pool.c
new file mode 100644
index 000000000..744a82fdb
--- /dev/null
+++ b/src/tag_pool.c
@@ -0,0 +1,108 @@
+/* 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));
+}
+
+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 = xmalloc(sizeof(*slot) + length);
+	slot->next = *slot_p;
+	slot->ref = 1;
+	slot->item.type = type;
+	memcpy(slot->item.value, value, length);
+	slot->item.value[length] = 0;
+	*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..4f063d1ed
--- /dev/null
+++ b/src/tag_pool.h
@@ -0,0 +1,31 @@
+/* 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);
+
+void tag_pool_put_item(struct tag_item *item);
+
+#endif