directory: replace songvec with doubly linked list

11 files changed, 99 insertions, 228 deletions

diff --git a/Makefile.am b/Makefile.am
index 1cec459f..00edcfdd 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -185,7 +185,7 @@ mpd_headers = \
 	src/song_print.h \
 	src/song_save.h \
 	src/song_sticker.h \
-	src/songvec.h \
+	src/song_sort.c src/song_sort.h \
 	src/socket_util.h \
 	src/state_file.h \
 	src/stats.h \
@@ -327,7 +327,6 @@ src_mpd_SOURCES = \
 	src/song_update.c \
 	src/song_print.c \
 	src/song_save.c \
-	src/songvec.c \
 	src/resolver.c src/resolver.h \
 	src/socket_util.c \
 	src/state_file.c \
diff --git a/src/directory.c b/src/directory.c
index 3700579a..232c6bd3 100644
--- a/src/directory.c
+++ b/src/directory.c
@@ -20,6 +20,7 @@
 #include "config.h"
 #include "directory.h"
 #include "song.h"
+#include "song_sort.h"
 #include "path.h"
 #include "util/list_sort.h"
 #include "db_visitor.h"
@@ -43,6 +44,7 @@ directory_new(const char *path, struct directory *parent)
 	directory = g_malloc0(sizeof(*directory) -
 			      sizeof(directory->path) + pathlen + 1);
 	INIT_LIST_HEAD(&directory->children);
+	INIT_LIST_HEAD(&directory->songs);
 	directory->parent = parent;
 	memcpy(directory->path, path, pathlen + 1);
 
@@ -56,14 +58,14 @@ directory_free(struct directory *directory)
 {
 	playlist_vector_deinit(&directory->playlists);
 
-	for (unsigned i = 0; i < directory->songs.nr; ++i)
-		song_free(directory->songs.base[i]);
+	struct song *song, *ns;
+	directory_for_each_song_safe(song, ns, directory)
+		song_free(song);
 
 	struct directory *child, *n;
 	directory_for_each_child_safe(child, n, directory)
 		directory_free(child);
 
-	songvec_destroy(&directory->songs);
 	g_free(directory);
 	/* this resets last dir returned */
 	/*directory_get_path(NULL); */
@@ -184,7 +186,7 @@ directory_add_song(struct directory *directory, struct song *song)
 	assert(song != NULL);
 	assert(song->parent == directory);
 
-	songvec_add(&directory->songs, song);
+	list_add(&song->siblings, &directory->songs);
 }
 
 void
@@ -194,7 +196,7 @@ directory_remove_song(struct directory *directory, struct song *song)
 	assert(song != NULL);
 	assert(song->parent == directory);
 
-	songvec_delete(&directory->songs, song);
+	list_del(&song->siblings);
 }
 
 struct song *
@@ -203,9 +205,19 @@ directory_get_song(const struct directory *directory, const char *name_utf8)
 	assert(directory != NULL);
 	assert(name_utf8 != NULL);
 
-	struct song *song = songvec_find(&directory->songs, name_utf8);
-	assert(song == NULL || song->parent == directory);
-	return song;
+	db_lock();
+	struct song *song;
+	directory_for_each_song(song, directory) {
+		assert(song->parent == directory);
+
+		if (strcmp(song->uri, name_utf8) == 0) {
+			db_unlock();
+			return song;
+		}
+	}
+
+	db_unlock();
+	return NULL;
 }
 
 struct song *
@@ -251,10 +263,9 @@ directory_sort(struct directory *directory)
 {
 	db_lock();
 	list_sort(NULL, &directory->children, directory_cmp);
+	song_list_sort(&directory->songs);
 	db_unlock();
 
-	songvec_sort(&directory->songs);
-
 	struct directory *child;
 	directory_for_each_child(child, directory)
 		directory_sort(child);
@@ -270,9 +281,9 @@ directory_walk(const struct directory *directory, bool recursive,
 	assert(error_r == NULL || *error_r == NULL);
 
 	if (visitor->song != NULL) {
-		const struct songvec *sv = &directory->songs;
-		for (size_t i = 0; i < sv->nr; ++i)
-			if (!visitor->song(sv->base[i], ctx, error_r))
+		struct song *song;
+		directory_for_each_song(song, directory)
+			if (!visitor->song(song, ctx, error_r))
 				return false;
 	}
 
diff --git a/src/directory.h b/src/directory.h
index b866295a..5460cb46 100644
--- a/src/directory.h
+++ b/src/directory.h
@@ -22,7 +22,6 @@
 
 #include "check.h"
 #include "util/list.h"
-#include "songvec.h"
 #include "playlist_vector.h"
 
 #include <glib.h>
@@ -40,6 +39,13 @@
 #define directory_for_each_child_safe(pos, n, directory) \
 	list_for_each_entry_safe(pos, n, &directory->children, siblings)
 
+#define directory_for_each_song(pos, directory) \
+	list_for_each_entry(pos, &directory->songs, siblings)
+
+#define directory_for_each_song_safe(pos, n, directory) \
+	list_for_each_entry_safe(pos, n, &directory->songs, siblings)
+
+struct song;
 struct db_visitor;
 
 struct directory {
@@ -61,7 +67,13 @@ struct directory {
 	 */
 	struct list_head children;
 
-	struct songvec songs;
+	/**
+	 * A doubly linked list of songs within this directory.
+	 *
+	 * This attribute is protected with the global #db_mutex.
+	 * Read access in the update thread does not need protection.
+	 */
+	struct list_head songs;
 
 	struct playlist_vector playlists;
 
@@ -114,7 +126,7 @@ static inline bool
 directory_is_empty(const struct directory *directory)
 {
 	return list_empty(&directory->children) &&
-		directory->songs.nr == 0 &&
+		list_empty(&directory->songs) &&
 		playlist_vector_is_empty(&directory->playlists);
 }
 
diff --git a/src/directory_save.c b/src/directory_save.c
index 087fab4c..8d20a99f 100644
--- a/src/directory_save.c
+++ b/src/directory_save.c
@@ -65,7 +65,9 @@ directory_save(FILE *fp, const struct directory *directory)
 			return;
 	}
 
-	songvec_save(fp, &directory->songs);
+	struct song *song;
+	directory_for_each_song(song, directory)
+		song_save(fp, song);
 
 	playlist_vector_save(fp, &directory->playlists);
 
diff --git a/src/song.h b/src/song.h
index 9553c76c..95cc2eb8 100644
--- a/src/song.h
+++ b/src/song.h
@@ -20,6 +20,8 @@
 #ifndef MPD_SONG_H
 #define MPD_SONG_H
 
+#include "util/list.h"
+
 #include <stddef.h>
 #include <stdbool.h>
 #include <sys/time.h>
@@ -28,6 +30,16 @@
 #define SONG_TIME	"Time: "
 
 struct song {
+	/**
+	 * Pointers to the siblings of this directory within the
+	 * parent directory.  It is unused (undefined) if this song is
+	 * not in the database.
+	 *
+	 * This attribute is protected with the global #db_mutex.
+	 * Read access in the update thread does not need protection.
+	 */
+	struct list_head siblings;
+
 	struct tag *tag;
 	struct directory *parent;
 	time_t mtime;
diff --git a/src/song_print.c b/src/song_print.c
index 2065b336..fb608a8b 100644
--- a/src/song_print.c
+++ b/src/song_print.c
@@ -20,7 +20,6 @@
 #include "config.h"
 #include "song_print.h"
 #include "song.h"
-#include "songvec.h"
 #include "directory.h"
 #include "tag_print.h"
 #include "client.h"
diff --git a/src/song_save.c b/src/song_save.c
index 5c935362..0d4c36f9 100644
--- a/src/song_save.c
+++ b/src/song_save.c
@@ -59,19 +59,6 @@ song_save(FILE *fp, const struct song *song)
 	fprintf(fp, SONG_END "\n");
 }
 
-static int
-song_save_callback(struct song *song, void *data)
-{
-	FILE *fp = data;
-	song_save(fp, song);
-	return 0;
-}
-
-void songvec_save(FILE *fp, const struct songvec *sv)
-{
-	songvec_for_each(sv, song_save_callback, fp);
-}
-
 struct song *
 song_load(FILE *fp, struct directory *parent, const char *uri,
 	  GString *buffer, GError **error_r)
diff --git a/src/song_save.h b/src/song_save.h
index 1aaa7642..f6ecbbfe 100644
--- a/src/song_save.h
+++ b/src/song_save.h
@@ -27,15 +27,11 @@
 #define SONG_BEGIN "song_begin: "
 
 struct song;
-struct songvec;
 struct directory;
 
 void
 song_save(FILE *fp, const struct song *song);
 
-void
-songvec_save(FILE *fp, const struct songvec *sv);
-
 /**
  * Loads a song from the input file.  Reading stops after the
  * "song_end" line.
diff --git a/src/songvec.c b/src/song_sort.c
index 9e032158..397d2c7a 100644
--- a/src/songvec.c
+++ b/src/song_sort.c
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2003-2011 The Music Player Daemon Project
+ * Copyright (C) 2003-2012 The Music Player Daemon Project
  * http://www.musicpd.org
  *
  * This program is free software; you can redistribute it and/or modify
@@ -18,15 +18,15 @@
  */
 
 #include "config.h"
-#include "songvec.h"
+#include "song_sort.h"
 #include "song.h"
+#include "util/list.h"
+#include "util/list_sort.h"
 #include "tag.h"
-#include "db_lock.h"
 
 #include <glib.h>
 
 #include <assert.h>
-#include <string.h>
 #include <stdlib.h>
 
 static const char *
@@ -88,10 +88,11 @@ compare_tag_item(const struct tag *a, const struct tag *b, enum tag_type type)
 }
 
 /* Only used for sorting/searchin a songvec, not general purpose compares */
-static int songvec_cmp(const void *s1, const void *s2)
+static int
+song_cmp(G_GNUC_UNUSED void *priv, struct list_head *_a, struct list_head *_b)
 {
-	const struct song *a = ((const struct song * const *)s1)[0];
-	const struct song *b = ((const struct song * const *)s2)[0];
+	const struct song *a = (const struct song *)_a;
+	const struct song *b = (const struct song *)_b;
 	int ret;
 
 	/* first sort by album */
@@ -113,114 +114,8 @@ static int songvec_cmp(const void *s1, const void *s2)
 	return g_utf8_collate(a->uri, b->uri);
 }
 
-static size_t sv_size(const struct songvec *sv)
-{
-	return sv->nr * sizeof(struct song *);
-}
-
-void songvec_sort(struct songvec *sv)
-{
-	db_lock();
-	qsort(sv->base, sv->nr, sizeof(struct song *), songvec_cmp);
-	db_unlock();
-}
-
-struct song *
-songvec_find(const struct songvec *sv, const char *uri)
-{
-	int i;
-	struct song *ret = NULL;
-
-	db_lock();
-	for (i = sv->nr; --i >= 0; ) {
-		if (strcmp(sv->base[i]->uri, uri))
-			continue;
-		ret = sv->base[i];
-		break;
-	}
-	db_unlock();
-	return ret;
-}
-
-/**
- * Determine the index of the specified #song inside the #songvec, and
- * returns the index.  The caller must hold the db_mutex.
- */
-G_GNUC_PURE
-static size_t
-songvec_find_pointer(const struct songvec *sv, const struct song *song)
-{
-	for (size_t i = 0;; ++i) {
-		assert(i < sv->nr); /* the song must exist */
-
-		if (sv->base[i] == song)
-			return i;
-	}
-}
-
-void
-songvec_delete(struct songvec *sv, const struct song *del)
-{
-	db_lock();
-
-	const size_t i = songvec_find_pointer(sv, del);
-
-	/* we _don't_ call song_free() here */
-	if (!--sv->nr) {
-		g_free(sv->base);
-		sv->base = NULL;
-	} else {
-		memmove(&sv->base[i], &sv->base[i + 1],
-			(sv->nr - i) * sizeof(struct song *));
-		sv->base = g_realloc(sv->base, sv_size(sv));
-	}
-
-	db_unlock();
-}
-
 void
-songvec_add(struct songvec *sv, struct song *add)
-{
-	db_lock();
-	++sv->nr;
-	sv->base = g_realloc(sv->base, sv_size(sv));
-	sv->base[sv->nr - 1] = add;
-	db_unlock();
-}
-
-void songvec_destroy(struct songvec *sv)
-{
-	db_lock();
-	sv->nr = 0;
-	db_unlock();
-
-	g_free(sv->base);
-	sv->base = NULL;
-}
-
-int
-songvec_for_each(const struct songvec *sv,
-		 int (*fn)(struct song *, void *), void *arg)
+song_list_sort(struct list_head *songs)
 {
-	size_t i;
-	size_t prev_nr;
-
-	db_lock();
-	for (i = 0; i < sv->nr; ) {
-		struct song *song = sv->base[i];
-
-		assert(song);
-		assert(*song->uri);
-
-		prev_nr = sv->nr;
-		db_unlock(); /* fn() may block */
-		if (fn(song, arg) < 0)
-			return -1;
-		db_lock(); /* sv->nr may change in fn() */
-		if (prev_nr == sv->nr)
-			++i;
-	}
-	db_unlock();
-
-	return 0;
+	list_sort(NULL, songs, song_cmp);
 }
diff --git a/src/songvec.h b/src/song_sort.h
index e839b537..ec124cf4 100644
--- a/src/songvec.h
+++ b/src/song_sort.h
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2003-2011 The Music Player Daemon Project
+ * Copyright (C) 2003-2012 The Music Player Daemon Project
  * http://www.musicpd.org
  *
  * This program is free software; you can redistribute it and/or modify
@@ -17,35 +17,12 @@
  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  */
 
-#ifndef MPD_SONGVEC_H
-#define MPD_SONGVEC_H
+#ifndef MPD_SONG_SORT_H
+#define MPD_SONG_SORT_H
 
-#include <stddef.h>
-
-struct songvec {
-	struct song **base;
-	size_t nr;
-};
-
-void songvec_init(void);
-
-void songvec_deinit(void);
-
-void songvec_sort(struct songvec *sv);
-
-struct song *
-songvec_find(const struct songvec *sv, const char *uri);
+struct list_head;
 
 void
-songvec_delete(struct songvec *sv, const struct song *del);
-
-void
-songvec_add(struct songvec *sv, struct song *add);
-
-void songvec_destroy(struct songvec *sv);
-
-int
-songvec_for_each(const struct songvec *sv,
-		 int (*fn)(struct song *, void *), void *arg);
+song_list_sort(struct list_head *songs);
 
-#endif /* SONGVEC_H */
+#endif
diff --git a/src/update_walk.c b/src/update_walk.c
index 728e5bb0..e5eedc02 100644
--- a/src/update_walk.c
+++ b/src/update_walk.c
@@ -92,6 +92,8 @@ directory_set_stat(struct directory *dir, const struct stat *st)
 static void
 delete_song(struct directory *dir, struct song *del)
 {
+	assert(del->parent == dir);
+
 	/* first, prevent traversers in main task from getting this */
 	directory_remove_song(dir, del);
 
@@ -102,15 +104,6 @@ delete_song(struct directory *dir, struct song *del)
 	song_free(del);
 }
 
-static int
-delete_each_song(struct song *song, G_GNUC_UNUSED void *data)
-{
-	struct directory *directory = data;
-	assert(song->parent == directory);
-	delete_song(directory, song);
-	return 0;
-}
-
 static void
 delete_directory(struct directory *directory);
 
@@ -125,7 +118,11 @@ clear_directory(struct directory *directory)
 	directory_for_each_child_safe(child, n, directory)
 		delete_directory(child);
 
-	songvec_for_each(&directory->songs, delete_each_song, directory);
+	struct song *song, *ns;
+	directory_for_each_song_safe(song, ns, directory) {
+		assert(song->parent == directory);
+		delete_song(directory, song);
+	}
 }
 
 /**
@@ -159,25 +156,6 @@ delete_name_in(struct directory *parent, const char *name)
 	playlist_vector_remove(&parent->playlists, name);
 }
 
-/* passed to songvec_for_each */
-static int
-delete_song_if_excluded(struct song *song, void *_data)
-{
-	GSList *exclude_list = _data;
-	char *name_fs;
-
-	assert(song->parent != NULL);
-
-	name_fs = utf8_to_fs_charset(song->uri);
-	if (exclude_list_check(exclude_list, name_fs)) {
-		delete_song(song->parent, song);
-		modified = true;
-	}
-
-	g_free(name_fs);
-	return 0;
-}
-
 static void
 remove_excluded_from_directory(struct directory *directory,
 			       GSList *exclude_list)
@@ -194,26 +172,18 @@ remove_excluded_from_directory(struct directory *directory,
 		g_free(name_fs);
 	}
 
-	songvec_for_each(&directory->songs,
-			 delete_song_if_excluded, exclude_list);
-}
+	struct song *song, *ns;
+	directory_for_each_song_safe(song, ns, directory) {
+		assert(song->parent == directory);
 
-/* passed to songvec_for_each */
-static int
-delete_song_if_removed(struct song *song, void *_data)
-{
-	struct directory *dir = _data;
-	char *path;
-	struct stat st;
+		char *name_fs = utf8_to_fs_charset(song->uri);
+		if (exclude_list_check(exclude_list, name_fs)) {
+			delete_song(directory, song);
+			modified = true;
+		}
 
-	if ((path = map_song_fs(song)) == NULL ||
-	    stat(path, &st) < 0 || !S_ISREG(st.st_mode)) {
-		delete_song(dir, song);
-		modified = true;
+		g_free(name_fs);
 	}
-
-	g_free(path);
-	return 0;
 }
 
 static bool
@@ -266,7 +236,18 @@ removeDeletedFromDirectory(struct directory *directory)
 		modified = true;
 	}
 
-	songvec_for_each(&directory->songs, delete_song_if_removed, directory);
+	struct song *song, *ns;
+	directory_for_each_song_safe(song, ns, directory) {
+		char *path;
+		struct stat st;
+		if ((path = map_song_fs(song)) == NULL ||
+		    stat(path, &st) < 0 || !S_ISREG(st.st_mode)) {
+			delete_song(directory, song);
+			modified = true;
+		}
+
+		g_free(path);
+	}
 
 	for (const struct playlist_metadata *pm = directory->playlists.head;
 	     pm != NULL;) {