Replace SongList with struct songvec

Our linked-list implementation is wasteful and the
SongList isn't modified enough to benefit from being a linked
list.  So use a more compact array of song pointers which
saves ~200K on a library with ~9K songs (on x86-32).

11 files changed, 212 insertions, 113 deletions

diff --git a/src/Makefile.am b/src/Makefile.am
index 272a63199..368e051fc 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -86,6 +86,7 @@ mpd_headers = \
 	song.h \
 	song_print.h \
 	song_save.h \
+	songvec.h \
 	state_file.h \
 	stats.h \
 	tag.h \
@@ -156,6 +157,7 @@ mpd_SOURCES = \
 	song.c \
 	song_print.c \
 	song_save.c \
+	songvec.c \
 	state_file.c \
 	stats.c \
 	tag.c \
diff --git a/src/dbUtils.c b/src/dbUtils.c
index d204d7e1e..a19294b04 100644
--- a/src/dbUtils.c
+++ b/src/dbUtils.c
@@ -51,7 +51,7 @@ static int countSongsInDirectory(Directory * directory,
 {
 	int *count = (int *)data;
 
-	*count += directory->songs->numberOfNodes;
+	*count += directory->songs.nr;
 
 	return 0;
 }
@@ -362,7 +362,7 @@ static int sumSavedFilenameMemoryInDirectory(Directory * dir, void *data)
 		return 0;
 
 	*sum += (strlen(getDirectoryPath(dir)) + 1 - sizeof(Directory *)) *
-	    dir->songs->numberOfNodes;
+	    dir->songs.nr;
 
 	return 0;
 }
diff --git a/src/directory.c b/src/directory.c
index 14d1a5b55..66f652867 100644
--- a/src/directory.c
+++ b/src/directory.c
@@ -241,14 +241,14 @@ static Directory *newDirectory(const char *dirname, Directory * parent)
 {
 	Directory *directory;
 
-	directory = xmalloc(sizeof(Directory));
+	directory = xcalloc(1, sizeof(Directory));
 
 	if (dirname && strlen(dirname))
 		directory->path = xstrdup(dirname);
 	else
 		directory->path = NULL;
 	directory->subDirectories = newDirectoryList();
-	directory->songs = newSongList();
+	assert(!directory->songs.base);
 	directory->stat = 0;
 	directory->inode = 0;
 	directory->device = 0;
@@ -260,7 +260,7 @@ static Directory *newDirectory(const char *dirname, Directory * parent)
 static void freeDirectory(Directory * directory)
 {
 	freeDirectoryList(directory->subDirectories);
-	freeSongList(directory->songs);
+	songvec_free(&directory->songs);
 	if (directory->path)
 		free(directory->path);
 	free(directory);
@@ -275,13 +275,13 @@ static void freeDirectoryList(DirectoryList * directoryList)
 
 static void removeSongFromDirectory(Directory * directory, const char *shortname)
 {
-	void *song;
+	Song *song = songvec_find(&directory->songs, shortname);
 
-	if (findInList(directory->songs, shortname, &song)) {
+	if (song) {
 		char path_max_tmp[MPD_PATH_MAX]; /* wasteful */
-		LOG("removing: %s\n",
-		    get_song_url(path_max_tmp, (Song *) song));
-		deleteFromList(directory->songs, shortname);
+		LOG("removing: %s\n", get_song_url(path_max_tmp, song));
+		songvec_delete(&directory->songs, song);
+		freeSong(song);
 	}
 }
 
@@ -296,7 +296,7 @@ static void deleteEmptyDirectoriesInDirectory(Directory * directory)
 		deleteEmptyDirectoriesInDirectory(subDir);
 		nextNode = node->nextNode;
 		if (subDir->subDirectories->numberOfNodes == 0 &&
-		    subDir->songs->numberOfNodes == 0) {
+		    subDir->songs.nr == 0) {
 			deleteNodeFromList(directory->subDirectories, node);
 		}
 		node = nextNode;
@@ -311,7 +311,7 @@ static void deleteEmptyDirectoriesInDirectory(Directory * directory)
 static int updateInDirectory(Directory * directory,
 			     const char *shortname, const char *name)
 {
-	void *song;
+	Song *song;
 	void *subDir;
 	struct stat st;
 
@@ -319,14 +319,13 @@ static int updateInDirectory(Directory * directory,
 		return -1;
 
 	if (S_ISREG(st.st_mode) && hasMusicSuffix(name, 0)) {
-		if (0 == findInList(directory->songs, shortname, &song)) {
+		if (!(song = songvec_find(&directory->songs, shortname))) {
 			addToDirectory(directory, shortname, name);
 			return DIRECTORY_RETURN_UPDATE;
-		} else if (st.st_mtime != ((Song *) song)->mtime) {
+		} else if (st.st_mtime != song->mtime) {
 			LOG("updating %s\n", name);
-			if (updateSongInfo((Song *) song) < 0) {
+			if (updateSongInfo(song) < 0)
 				removeSongFromDirectory(directory, shortname);
-			}
 			return 1;
 		}
 	} else if (S_ISDIR(st.st_mode)) {
@@ -361,6 +360,8 @@ static int removeDeletedFromDirectory(char *path_max_tmp, Directory * directory)
 	ListNode *node, *tmpNode;
 	DirectoryList *subdirs = directory->subDirectories;
 	int ret = 0;
+	int i;
+	struct songvec *sv = &directory->songs;
 
 	node = subdirs->firstNode;
 	while (node) {
@@ -381,22 +382,20 @@ static int removeDeletedFromDirectory(char *path_max_tmp, Directory * directory)
 		node = tmpNode;
 	}
 
-	node = directory->songs->firstNode;
-	while (node) {
-		tmpNode = node->nextNode;
-		if (node->key) {
-			if (dirname)
-				sprintf(path_max_tmp, "%s/%s", dirname,
-					node->key);
-			else
-				strcpy(path_max_tmp, node->key);
+	for (i = sv->nr; --i >= 0; ) { /* cleaner deletes if we go backwards */
+		Song *song = sv->base[i];
+		if (!song || !song->url)
+			continue; /* does this happen?, perhaps assert() */
 
-			if (!isFile(path_max_tmp, NULL)) {
-				removeSongFromDirectory(directory, node->key);
-				ret = 1;
-			}
+		if (dirname)
+			sprintf(path_max_tmp, "%s/%s", dirname, song->url);
+		else
+			strcpy(path_max_tmp, song->url);
+
+		if (!isFile(path_max_tmp, NULL)) {
+			removeSongFromDirectory(directory, song->url);
+			ret = 1;
 		}
-		node = tmpNode;
 	}
 
 	return ret;
@@ -721,12 +720,12 @@ static int addToDirectory(Directory * directory,
 		return -1;
 	}
 
-	if (S_ISREG(st.st_mode) && hasMusicSuffix(name, 0)) {
-		Song *song;
-		song = addSongToList(directory->songs, shortname, name,
-				     SONG_TYPE_FILE, directory);
+	if (S_ISREG(st.st_mode) &&
+	    hasMusicSuffix(name, 0) && isMusic(name, NULL, 0)) {
+		Song *song = newSong(shortname, SONG_TYPE_FILE, directory);
 		if (!song)
 			return -1;
+		songvec_add(&directory->songs, song);
 		LOG("added %s\n", name);
 		return 1;
 	} else if (S_ISDIR(st.st_mode)) {
@@ -834,7 +833,7 @@ int printDirectoryInfo(struct client *client, const char *name)
 		return -1;
 
 	printDirectoryList(client, directory->subDirectories);
-	printSongInfoFromList(client, directory->songs);
+	songvec_print(client, &directory->songs);
 
 	return 0;
 }
@@ -865,7 +864,7 @@ static void writeDirectoryInfo(FILE * fp, Directory * directory)
 		node = node->nextNode;
 	}
 
-	writeSongInfoFromList(fp, directory->songs);
+	songvec_save(fp, &directory->songs);
 
 	if (directory->path) {
 		retv = fprintf(fp, "%s%s\n", DIRECTORY_END,
@@ -929,7 +928,7 @@ static void readDirectoryInfo(FILE * fp, Directory * directory)
 
 			readDirectoryInfo(fp, subDirectory);
 		} else if (!prefixcmp(buffer, SONG_BEGIN)) {
-			readSongInfoIntoList(fp, directory->songs, directory);
+			readSongInfoIntoList(fp, &directory->songs, directory);
 		} else {
 			FATAL("Unknown line in db: %s\n", buffer);
 		}
@@ -948,7 +947,7 @@ static void sortDirectory(Directory * directory)
 	Directory *subDir;
 
 	sortList(directory->subDirectories);
-	sortList(directory->songs);
+	songvec_sort(&directory->songs);
 
 	while (node != NULL) {
 		subDir = (Directory *) node->data;
@@ -1140,8 +1139,7 @@ static int traverseAllInSubDirectory(Directory * directory,
 				     int (*forEachDir) (Directory *, void *),
 				     void *data)
 {
-	ListNode *node = directory->songs->firstNode;
-	Song *song;
+	ListNode *node;
 	Directory *dir;
 	int errFlag = 0;
 
@@ -1152,13 +1150,15 @@ static int traverseAllInSubDirectory(Directory * directory,
 	}
 
 	if (forEachSong) {
-		while (node != NULL && !errFlag) {
-			song = (Song *) node->data;
-			errFlag = forEachSong(song, data);
-			node = node->nextNode;
+		int i;
+		struct songvec *sv = &directory->songs;
+		Song **sp = sv->base;
+
+		for (i = sv->nr; --i >= 0; ) {
+			Song *song = *sp++;
+			if ((errFlag = forEachSong(song, data)))
+				return errFlag;
 		}
-		if (errFlag)
-			return errFlag;
 	}
 
 	node = directory->subDirectories->firstNode;
@@ -1202,7 +1202,7 @@ void initMp3Directory(void)
 static Song *getSongDetails(const char *file, const char **shortnameRet,
 			    Directory ** directoryRet)
 {
-	void *song = NULL;
+	Song *song;
 	Directory *directory;
 	char *dir = NULL;
 	char *duplicated = xstrdup(file);
@@ -1229,7 +1229,7 @@ static Song *getSongDetails(const char *file, const char **shortnameRet,
 		return NULL;
 	}
 
-	if (!findInList(directory->songs, shortname, &song)) {
+	if (!(song = songvec_find(&directory->songs, shortname))) {
 		free(duplicated);
 		return NULL;
 	}
@@ -1239,7 +1239,7 @@ static Song *getSongDetails(const char *file, const char **shortnameRet,
 		*shortnameRet = shortname;
 	if (directoryRet)
 		*directoryRet = directory;
-	return (Song *) song;
+	return song;
 }
 
 Song *getSongFromDB(const char *file)
diff --git a/src/directory.h b/src/directory.h
index 252224a6b..ccd20501e 100644
--- a/src/directory.h
+++ b/src/directory.h
@@ -20,13 +20,14 @@
 #define DIRECTORY_H
 
 #include "song.h"
+#include "songvec.h"
 
 typedef List DirectoryList;
 
 typedef struct _Directory {
 	char *path;
 	DirectoryList *subDirectories;
-	SongList *songs;
+	struct songvec songs;
 	struct _Directory *parent;
 	ino_t inode;
 	dev_t device;
diff --git a/src/song.c b/src/song.c
index a26603735..230388805 100644
--- a/src/song.c
+++ b/src/song.c
@@ -25,6 +25,7 @@
 #include "playlist.h"
 #include "decoder_list.h"
 #include "decoder_api.h"
+
 #include "os_compat.h"
 
 Song *newNullSong(void)
diff --git a/src/song_print.c b/src/song_print.c
index 77741e768..f754f2348 100644
--- a/src/song_print.c
+++ b/src/song_print.c
@@ -17,6 +17,7 @@
  */
 
 #include "song_print.h"
+#include "songvec.h"
 #include "directory.h"
 #include "tag_print.h"
 #include "client.h"
@@ -41,14 +42,14 @@ int printSongInfo(struct client *client, Song * song)
 	return 0;
 }
 
-int printSongInfoFromList(struct client *client, SongList * list)
+int songvec_print(struct client *client, const struct songvec *sv)
 {
-	ListNode *tempNode = list->firstNode;
+	int i;
+	Song **sp = sv->base;
 
-	while (tempNode != NULL) {
-		printSongInfo(client, (Song *) tempNode->data);
-		tempNode = tempNode->nextNode;
-	}
+	for (i = sv->nr; --i >= 0;)
+		if (printSongInfo(client, *sp++) < 0)
+			return -1;
 
 	return 0;
 }
diff --git a/src/song_print.h b/src/song_print.h
index bbc034248..bc7560e88 100644
--- a/src/song_print.h
+++ b/src/song_print.h
@@ -21,9 +21,11 @@
 
 #include "song.h"
 
+struct songvec;
+
 int printSongInfo(struct client *client, Song * song);
 
-int printSongInfoFromList(struct client *client, SongList * list);
+int songvec_print(struct client *client, const struct songvec *sv);
 
 void printSongUrl(struct client *client, Song * song);
 
diff --git a/src/song_save.c b/src/song_save.c
index a875a65fb..0cff6ef4f 100644
--- a/src/song_save.c
+++ b/src/song_save.c
@@ -45,52 +45,41 @@ static void song_save(FILE *fp, Song * song)
 		tag_save(fp, song->tag);
 }
 
-void writeSongInfoFromList(FILE * fp, SongList * list)
+void songvec_save(FILE *fp, struct songvec *sv)
 {
-	ListNode *tempNode = list->firstNode;
+	int i;
+	Song **sp = sv->base;
 
 	fprintf(fp, "%s\n", SONG_BEGIN);
 
-	while (tempNode != NULL) {
-		fprintf(fp, "%s%s\n", SONG_KEY, tempNode->key);
-		song_save(fp, (Song *) tempNode->data);
-		fprintf(fp, "%s%li\n", SONG_MTIME,
-			  (long)((Song *) tempNode->data)->mtime);
-		tempNode = tempNode->nextNode;
+	for (i = sv->nr; --i >= 0; ) {
+		Song *song = *sp++;
+		fprintf(fp, "%s%s\n", SONG_KEY, song->url);
+		song_save(fp, song);
+		fprintf(fp, "%s%li\n", SONG_MTIME, (long)song->mtime);
 	}
 
 	fprintf(fp, "%s\n", SONG_END);
 }
 
-static void insertSongIntoList(SongList * list, ListNode ** nextSongNode,
-			       char *key, Song * song)
+static void insertSongIntoList(struct songvec *sv, Song *newsong)
 {
-	ListNode *nodeTemp;
-	int cmpRet = 0;
-
-	while (*nextSongNode
-	       && (cmpRet = strcmp(key, (*nextSongNode)->key)) > 0) {
-		nodeTemp = (*nextSongNode)->nextNode;
-		deleteNodeFromList(list, *nextSongNode);
-		*nextSongNode = nodeTemp;
-	}
-
-	if (!(*nextSongNode)) {
-		insertInList(list, song->url, (void *)song);
-	} else if (cmpRet == 0) {
-		Song *tempSong = (Song *) ((*nextSongNode)->data);
-		if (tempSong->mtime != song->mtime) {
-			tag_free(tempSong->tag);
-			tag_end_add(song->tag);
-			tempSong->tag = song->tag;
-			tempSong->mtime = song->mtime;
-			song->tag = NULL;
+	Song *existing = songvec_find(sv, newsong->url);
+
+	if (!existing) {
+		songvec_add(sv, newsong);
+		if (newsong->tag)
+			tag_end_add(newsong->tag);
+	} else { /* prevent dupes, just update the existing song info */
+		if (existing->mtime != newsong->mtime) {
+			tag_free(existing->tag);
+			if (newsong->tag)
+				tag_end_add(newsong->tag);
+			existing->tag = newsong->tag;
+			existing->mtime = newsong->mtime;
+			newsong->tag = NULL;
 		}
-		freeJustSong(song);
-		*nextSongNode = (*nextSongNode)->nextNode;
-	} else {
-		insertInListBeforeNode(list, *nextSongNode, -1, song->url,
-				       (void *)song);
+		freeJustSong(newsong);
 	}
 }
 
@@ -109,23 +98,18 @@ static int matchesAnMpdTagItemKey(char *buffer, int *itemType)
 	return 0;
 }
 
-void readSongInfoIntoList(FILE * fp, SongList * list, Directory * parentDir)
+void readSongInfoIntoList(FILE *fp, struct songvec *sv,
+			  Directory *parentDir)
 {
 	char buffer[MPD_PATH_MAX + 1024];
 	int bufferSize = MPD_PATH_MAX + 1024;
 	Song *song = NULL;
-	ListNode *nextSongNode = list->firstNode;
-	ListNode *nodeTemp;
 	int itemType;
 
 	while (myFgets(buffer, bufferSize, fp) && 0 != strcmp(SONG_END, buffer)) {
 		if (0 == strncmp(SONG_KEY, buffer, strlen(SONG_KEY))) {
-			if (song) {
-				insertSongIntoList(list, &nextSongNode,
-						   song->url, song);
-				if (song->tag != NULL)
-					tag_end_add(song->tag);
-			}
+			if (song)
+				insertSongIntoList(sv, song);
 
 			song = newNullSong();
 			song->url = xstrdup(buffer + strlen(SONG_KEY));
@@ -163,15 +147,8 @@ void readSongInfoIntoList(FILE * fp, SongList * list, Directory * parentDir)
 			FATAL("songinfo: unknown line in db: %s\n", buffer);
 	}
 
-	if (song) {
-		insertSongIntoList(list, &nextSongNode, song->url, song);
-		if (song->tag != NULL)
-			tag_end_add(song->tag);
-	}
+	if (song)
+		insertSongIntoList(sv, song);
 
-	while (nextSongNode) {
-		nodeTemp = nextSongNode->nextNode;
-		deleteNodeFromList(list, nextSongNode);
-		nextSongNode = nodeTemp;
-	}
+	songvec_prune(sv);
 }
diff --git a/src/song_save.h b/src/song_save.h
index 84acae39e..748a2696c 100644
--- a/src/song_save.h
+++ b/src/song_save.h
@@ -21,9 +21,11 @@
 
 #include "song.h"
 
-void writeSongInfoFromList(FILE * fp, SongList * list);
+struct songvec;
 
-void readSongInfoIntoList(FILE * fp, SongList * list,
+void songvec_save(FILE *fp, struct songvec *sv);
+
+void readSongInfoIntoList(FILE * fp, struct songvec *sv,
 			  struct _Directory *parent);
 
 #endif
diff --git a/src/songvec.c b/src/songvec.c
new file mode 100644
index 000000000..620338781
--- /dev/null
+++ b/src/songvec.c
@@ -0,0 +1,89 @@
+#include "songvec.h"
+#include "utils.h"
+
+/* Only used for sorting/searchin a songvec, not general purpose compares */
+static int songvec_cmp(const void *s1, const void *s2)
+{
+	const Song *a = ((const Song * const *)s1)[0];
+	const Song *b = ((const Song * const *)s2)[0];
+	return strcmp(a->url, b->url);
+}
+
+static size_t sv_size(struct songvec *sv)
+{
+	return sv->nr * sizeof(Song *);
+}
+
+void songvec_sort(struct songvec *sv)
+{
+	qsort(sv->base, sv->nr, sizeof(Song *), songvec_cmp);
+}
+
+Song *songvec_find(struct songvec *sv, const char *url)
+{
+	int i;
+
+	for (i = sv->nr; --i >= 0; )
+		if (!strcmp(sv->base[i]->url, url))
+			return sv->base[i];
+	return NULL;
+}
+
+int songvec_delete(struct songvec *sv, Song *del)
+{
+	int i;
+
+	for (i = sv->nr; --i >= 0; ) {
+		if (sv->base[i] != del)
+			continue;
+		/* we _don't_ call freeSong() here */
+		if (!--sv->nr) {
+			free(sv->base);
+			sv->base = NULL;
+		} else {
+			memmove(&sv->base[i], &sv->base[i + 1],
+				(sv->nr - i + 1) * sizeof(Song *));
+			sv->base = xrealloc(sv->base, sv_size(sv));
+		}
+		return i;
+	}
+
+	return -1; /* not found */
+}
+
+void songvec_add(struct songvec *sv, Song *add)
+{
+	++sv->nr;
+	sv->base = xrealloc(sv->base, sv_size(sv));
+	sv->base[sv->nr - 1] = add;
+}
+
+void songvec_free(struct songvec *sv)
+{
+	free(sv->base);
+	sv->base = NULL;
+	sv->nr = 0;
+}
+
+/*
+ * Removes missing songs from a songvec. This function is only temporary
+ * as updating will be moved into a thread and updating shared memory...
+ */
+#include "path.h"
+#include "ls.h"
+void songvec_prune(struct songvec *sv)
+{
+	int i;
+	char tmp[MPD_PATH_MAX];
+	struct stat sb;
+
+	for (i = sv->nr; --i >= 0; ) {
+		Song *song = sv->base[i];
+		assert(song);
+		if (!myStat(get_song_url(tmp, song), &sb))
+			continue;
+		songvec_delete(sv, song);
+		freeSong(song);
+		i = sv->nr;
+	}
+}
diff --git a/src/songvec.h b/src/songvec.h
new file mode 100644
index 000000000..ada7c262d
--- /dev/null
+++ b/src/songvec.h
@@ -0,0 +1,24 @@
+#ifndef SONGVEC_H
+#define SONGVEC_H
+
+#include "song.h"
+#include "os_compat.h"
+
+struct songvec {
+	Song **base;
+	size_t nr;
+};
+
+void songvec_sort(struct songvec *sv);
+
+Song *songvec_find(struct songvec *sv, const char *url);
+
+int songvec_delete(struct songvec *sv, Song *del);
+
+void songvec_add(struct songvec *sv, Song *add);
+
+void songvec_free(struct songvec *sv);
+
+void songvec_prune(struct songvec *sv);
+
+#endif /* SONGVEC_H */