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 47482bea3..d73030aa7 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -82,6 +82,7 @@ mpd_headers = \
 	state_file.h \
 	stats.h \
 	tag.h \
+	tag_pool.h \
 	tag_id3.h \
 	tagTracker.h \
 	utf8.h \
@@ -144,6 +145,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 9192cb171..f99375110 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 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 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 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 afded5d7d..21dbfa487 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 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