Merge branch 'ew/directory'

* ew/directory:
  directory: remove redundant sanitizePathDup
  update: move path sanitation up the stack to avoid extra copies
  clean up updateInit calling and error handling
  directory: isRootDirectory() is a one-liner
  directory: writeDirectoryInfo propagates errors
  directory: make it clear that DIRECTORY_MTIME is deprecated
  directory: remove "Mp3" references
  playlist: deleteASongFromPlaylist takes a const Song *
  songvec: songvec_delete takes a const Song pointer
  directory: remove shortname arguments everywhere
  path: add mpd_basename() function
  directory.h: remove directory_sigChldHandler decl
  directory: replace DirectoryList with dirvec
  directory: remove unused CPP defines
  songvec_free => songvec_destroy
  directory.c: kill unnecessary includes

12 files changed, 341 insertions, 375 deletions

diff --git a/src/Makefile.am b/src/Makefile.am
index 88774fff1..5962ed583 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -41,6 +41,7 @@ mpd_headers = \
 	dbUtils.h \
 	decode.h \
 	directory.h \
+	dirvec.h \
 	gcc.h \
 	inputPlugin.h \
 	inputPlugins/_flac_common.h \
diff --git a/src/command.c b/src/command.c
index 3d4e2ccd5..3f80dc916 100644
--- a/src/command.c
+++ b/src/command.c
@@ -36,6 +36,7 @@
 #include "os_compat.h"
 #include "player_error.h"
 #include "outputBuffer.h"
+#include "path.h"
 
 #define COMMAND_PLAY           	"play"
 #define COMMAND_PLAYID         	"playid"
@@ -799,26 +800,47 @@ static int handlePlaylistMove(int fd, mpd_unused int *permission,
 	return print_playlist_result(fd, result);
 }
 
+static int print_update_result(int fd, int ret)
+{
+	if (ret >= 0) {
+		fdprintf(fd, "updating_db: %i\n", ret);
+		return 0;
+	}
+	if (ret == -2)
+		commandError(fd, ACK_ERROR_ARG, "invalid path");
+	else
+		commandError(fd, ACK_ERROR_UPDATE_ALREADY, "already updating");
+	return -1;
+}
+
 static int listHandleUpdate(int fd,
 			    mpd_unused int *permission,
 			    mpd_unused int argc,
 			    char *argv[],
 			    struct strnode *cmdnode, CommandEntry * cmd)
 {
-	List *pathList = makeList(NULL, 1);
+	static char **pathv;
+	static int pathc;
 	CommandEntry *nextCmd = NULL;
 	struct strnode *next = cmdnode->next;
+	int last = pathc++;
 
-	if (argc == 2)
-		insertInList(pathList, argv[1], NULL);
-	else
-		insertInList(pathList, "", NULL);
+	pathv = xrealloc(pathv, pathc * sizeof(char *));
+	pathv[last] = sanitizePathDup(argc == 2 ? argv[1] : "");
 
 	if (next)
 		nextCmd = getCommandEntryFromString(next->data, permission);
 
-	if (cmd != nextCmd)
-		return updateInit(fd, pathList);
+	if (cmd != nextCmd) {
+		int ret = print_update_result(fd, updateInit(pathc, pathv));
+		if (pathc) {
+			assert(pathv);
+			free(pathv);
+			pathv = NULL;
+			pathc = 0;
+		}
+		return ret;
+	}
 
 	return 0;
 }
@@ -826,12 +848,12 @@ static int listHandleUpdate(int fd,
 static int handleUpdate(int fd, mpd_unused int *permission,
 			mpd_unused int argc, char *argv[])
 {
-	if (argc == 2) {
-		List *pathList = makeList(NULL, 1);
-		insertInList(pathList, argv[1], NULL);
-		return updateInit(fd, pathList);
-	}
-	return updateInit(fd, NULL);
+	char *pathv[1];
+
+	assert(argc <= 2);
+	if (argc == 2)
+		pathv[0] = sanitizePathDup(argv[1]);
+	return print_update_result(fd, updateInit(argc - 1, pathv));
 }
 
 static int handleNext(mpd_unused int fd, mpd_unused int *permission,
diff --git a/src/directory.c b/src/directory.c
index f7c426267..fc9c6b41d 100644
--- a/src/directory.c
+++ b/src/directory.c
@@ -18,25 +18,21 @@
 
 #include "directory.h"
 
-#include "command.h"
 #include "conf.h"
-#include "client.h"
-#include "listen.h"
 #include "log.h"
 #include "ls.h"
 #include "path.h"
 #include "playlist.h"
-#include "sig_handlers.h"
 #include "stats.h"
 #include "utils.h"
-#include "volume.h"
 #include "ack.h"
 #include "myfprintf.h"
 #include "dbUtils.h"
 #include "main_notify.h"
+#include "dirvec.h"
 
 #define DIRECTORY_DIR		"directory: "
-#define DIRECTORY_MTIME		"mtime: "
+#define DIRECTORY_MTIME		"mtime: " /* DEPRECATED, noop-read-only */
 #define DIRECTORY_BEGIN		"begin: "
 #define DIRECTORY_END		"end: "
 #define DIRECTORY_INFO_BEGIN	"info_begin"
@@ -44,10 +40,6 @@
 #define DIRECTORY_MPD_VERSION	"mpd_version: "
 #define DIRECTORY_FS_CHARSET	"fs_charset: "
 
-#define DIRECTORY_UPDATE_EXIT_NOUPDATE  0
-#define DIRECTORY_UPDATE_EXIT_UPDATE    1
-#define DIRECTORY_UPDATE_EXIT_ERROR     2
-
 enum update_return {
 	UPDATE_RETURN_ERROR = -1,
 	UPDATE_RETURN_NOUPDATE = 0,
@@ -60,7 +52,7 @@ enum update_progress {
 	UPDATE_PROGRESS_DONE = 2
 } progress;
 
-static Directory *mp3rootDirectory;
+static Directory *music_root;
 
 static time_t directory_dbModTime;
 
@@ -68,12 +60,7 @@ static pthread_t update_thr;
 
 static int directory_updateJobId;
 
-static DirectoryList *newDirectoryList(void);
-
-static int addToDirectory(Directory * directory,
-			  const char *shortname, const char *name);
-
-static void freeDirectoryList(DirectoryList * list);
+static int addToDirectory(Directory * directory, const char *name);
 
 static void freeDirectory(Directory * directory);
 
@@ -87,17 +74,10 @@ static void removeSongFromDirectory(Directory * directory,
 				    const char *shortname);
 
 static enum update_return addSubDirectoryToDirectory(Directory * directory,
-				      const char *shortname,
 				      const char *name, struct stat *st);
 
-static Directory *getDirectoryDetails(const char *name,
-				      const char **shortname);
-
 static Directory *getDirectory(const char *name);
 
-static Song *getSongDetails(const char *file, const char **shortnameRet,
-			    Directory ** directoryRet);
-
 static enum update_return updatePath(const char *utf8path);
 
 static void sortDirectory(Directory * directory);
@@ -134,16 +114,15 @@ void reap_update_task(void)
 	progress = UPDATE_PROGRESS_IDLE;
 }
 
-static void * update_task(void *arg)
+/* @argv represents a null-terminated array of (null-terminated) strings */
+static void * update_task(void *argv)
 {
-	List *path_list = (List *)arg;
 	enum update_return ret = UPDATE_RETURN_NOUPDATE;
 
-	if (path_list) {
-		ListNode *node = path_list->firstNode;
-
-		while (node) {
-			switch (updatePath(node->key)) {
+	if (argv) {
+		char **pathv;
+		for (pathv = (char **)argv; *pathv; pathv++) {
+			switch (updatePath(*pathv)) {
 			case UPDATE_RETURN_ERROR:
 				ret = UPDATE_RETURN_ERROR;
 				goto out;
@@ -152,11 +131,11 @@ static void * update_task(void *arg)
 			case UPDATE_RETURN_UPDATED:
 				ret = UPDATE_RETURN_UPDATED;
 			}
-			node = node->nextNode;
+			free(*pathv);
 		}
-		freeList(path_list);
+		free(argv);
 	} else {
-		ret = updateDirectory(mp3rootDirectory);
+		ret = updateDirectory(music_root);
 	}
 
 	if (ret == UPDATE_RETURN_UPDATED && writeDirectoryDB() < 0)
@@ -167,27 +146,39 @@ out:
 	return (void *)ret;
 }
 
-int updateInit(int fd, List * path_list)
+int updateInit(int argc, char *argv[])
 {
 	pthread_attr_t attr;
+	char **pathv = NULL;
+	int i;
 
 	if (progress != UPDATE_PROGRESS_IDLE) {
-		commandError(fd, ACK_ERROR_UPDATE_ALREADY, "already updating");
+		for (i = argc; --i >= 0; )
+			free(argv[i]);
 		return -1;
 	}
+
+	for (i = argc; --i >= 0; ) {
+		if (!argv[i])
+			return -2;
+	}
+
 	progress = UPDATE_PROGRESS_RUNNING;
+	if (argc > 0) {
+		pathv = xmalloc((argc + 1) * sizeof(char *));
+		memcpy(pathv, argv, argc * sizeof(char *));
+		pathv[argc] = NULL;
+	}
 
 	pthread_attr_init(&attr);
-	if (pthread_create(&update_thr, &attr, update_task, path_list))
+	if (pthread_create(&update_thr, &attr, update_task, pathv))
 		FATAL("Failed to spawn update task: %s\n", strerror(errno));
 	directory_updateJobId++;
 	if (directory_updateJobId > 1 << 15)
 		directory_updateJobId = 1;
 	DEBUG("updateInit: spawned update thread for update job id %i\n",
 	      (int)directory_updateJobId);
-	fdprintf(fd, "updating_db: %i\n", (int)directory_updateJobId);
-
-	return 0;
+	return directory_updateJobId;
 }
 
 static void directory_set_stat(Directory * dir, const struct stat *st)
@@ -197,11 +188,6 @@ static void directory_set_stat(Directory * dir, const struct stat *st)
 	dir->stat = 1;
 }
 
-static DirectoryList *newDirectoryList(void)
-{
-	return makeList((ListFreeDataFunc *) freeDirectory, 1);
-}
-
 static Directory *newDirectory(const char *dirname, Directory * parent)
 {
 	Directory *directory;
@@ -210,13 +196,6 @@ static Directory *newDirectory(const char *dirname, Directory * parent)
 
 	if (dirname && strlen(dirname))
 		directory->path = xstrdup(dirname);
-	else
-		directory->path = NULL;
-	directory->subDirectories = newDirectoryList();
-	assert(!directory->songs.base);
-	directory->stat = 0;
-	directory->inode = 0;
-	directory->device = 0;
 	directory->parent = parent;
 
 	return directory;
@@ -224,8 +203,8 @@ static Directory *newDirectory(const char *dirname, Directory * parent)
 
 static void freeDirectory(Directory * directory)
 {
-	freeDirectoryList(directory->subDirectories);
-	songvec_free(&directory->songs);
+	dirvec_destroy(&directory->children);
+	songvec_destroy(&directory->songs);
 	if (directory->path)
 		free(directory->path);
 	free(directory);
@@ -233,11 +212,6 @@ static void freeDirectory(Directory * directory)
 	/*getDirectoryPath(NULL); */
 }
 
-static void freeDirectoryList(DirectoryList * directoryList)
-{
-	freeList(directoryList);
-}
-
 static void removeSongFromDirectory(Directory * directory, const char *shortname)
 {
 	Song *song = songvec_find(&directory->songs, shortname);
@@ -252,35 +226,32 @@ static void removeSongFromDirectory(Directory * directory, const char *shortname
 
 static void deleteEmptyDirectoriesInDirectory(Directory * directory)
 {
-	ListNode *node = directory->subDirectories->firstNode;
-	ListNode *nextNode;
-	Directory *subDir;
-
-	while (node) {
-		subDir = (Directory *) node->data;
-		deleteEmptyDirectoriesInDirectory(subDir);
-		nextNode = node->nextNode;
-		if (subDir->subDirectories->numberOfNodes == 0 &&
-		    subDir->songs.nr == 0) {
-			deleteNodeFromList(directory->subDirectories, node);
-		}
-		node = nextNode;
+	int i;
+	struct dirvec *dv = &directory->children;
+
+	for (i = dv->nr; --i >= 0; ) {
+		deleteEmptyDirectoriesInDirectory(dv->base[i]);
+		if (!dv->base[i]->children.nr && !dv->base[i]->songs.nr)
+			dirvec_delete(dv, dv->base[i]);
 	}
+	if (!dv->nr)
+		dirvec_destroy(dv);
 }
 
-static enum update_return updateInDirectory(Directory * directory,
-			     const char *shortname, const char *name)
+static enum update_return
+updateInDirectory(Directory * directory, const char *name)
 {
 	Song *song;
-	void *subDir;
 	struct stat st;
 
 	if (myStat(name, &st))
 		return UPDATE_RETURN_ERROR;
 
 	if (S_ISREG(st.st_mode) && hasMusicSuffix(name, 0)) {
+		const char *shortname = mpd_basename(name);
+
 		if (!(song = songvec_find(&directory->songs, shortname))) {
-			addToDirectory(directory, shortname, name);
+			addToDirectory(directory, name);
 			return UPDATE_RETURN_UPDATED;
 		} else if (st.st_mtime != song->mtime) {
 			LOG("updating %s\n", name);
@@ -289,13 +260,13 @@ static enum update_return updateInDirectory(Directory * directory,
 			return UPDATE_RETURN_UPDATED;
 		}
 	} else if (S_ISDIR(st.st_mode)) {
-		if (findInList
-		    (directory->subDirectories, shortname, (void **)&subDir)) {
-			directory_set_stat((Directory *)subDir, &st);
-			return updateDirectory((Directory *) subDir);
+		Directory *subdir = dirvec_find(&directory->children, name);
+		if (subdir) {
+			assert(directory == subdir->parent);
+			directory_set_stat(subdir, &st);
+			return updateDirectory(subdir);
 		} else {
-			return addSubDirectoryToDirectory(directory, shortname,
-							  name, &st);
+			return addSubDirectoryToDirectory(directory, name, &st);
 		}
 	}
 
@@ -313,29 +284,17 @@ removeDeletedFromDirectory(char *path_max_tmp, Directory * directory)
 {
 	const char *dirname = (directory && directory->path) ?
 	    directory->path : NULL;
-	ListNode *node, *tmpNode;
-	DirectoryList *subdirs = directory->subDirectories;
 	enum update_return ret = UPDATE_RETURN_NOUPDATE;
 	int i;
 	struct songvec *sv = &directory->songs;
+	struct dirvec *dv = &directory->children;
 
-	node = subdirs->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);
-
-			if (!isDir(path_max_tmp)) {
-				LOG("removing directory: %s\n", path_max_tmp);
-				deleteFromList(subdirs, node->key);
-				ret = UPDATE_RETURN_UPDATED;
-			}
-		}
-		node = tmpNode;
+	for (i = dv->nr; --i >= 0; ) {
+		if (isDir(dv->base[i]->path))
+			continue;
+		LOG("removing directory: %s\n", dv->base[i]->path);
+		dirvec_delete(dv, dv->base[i]);
+		ret = UPDATE_RETURN_UPDATED;
 	}
 
 	for (i = sv->nr; --i >= 0; ) { /* cleaner deletes if we go backwards */
@@ -357,49 +316,44 @@ removeDeletedFromDirectory(char *path_max_tmp, Directory * directory)
 	return ret;
 }
 
-static Directory *addDirectoryPathToDB(const char *utf8path,
-				       const char **shortname)
+static Directory *addDirectoryPathToDB(const char *utf8path)
 {
 	char path_max_tmp[MPD_PATH_MAX];
 	char *parent;
 	Directory *parentDirectory;
-	void *directory;
+	Directory *directory;
 
 	parent = parent_path(path_max_tmp, utf8path);
 
 	if (strlen(parent) == 0)
-		parentDirectory = (void *)mp3rootDirectory;
+		parentDirectory = music_root;
 	else
-		parentDirectory = addDirectoryPathToDB(parent, shortname);
+		parentDirectory = addDirectoryPathToDB(parent);
 
 	if (!parentDirectory)
 		return NULL;
 
-	*shortname = utf8path + strlen(parent);
-	while (*(*shortname) && *(*shortname) == '/')
-		(*shortname)++;
-
-	if (!findInList
-	    (parentDirectory->subDirectories, *shortname, &directory)) {
+	if ((directory = dirvec_find(&parentDirectory->children, utf8path))) {
+		assert(parentDirectory == directory->parent);
+	} else {
 		struct stat st;
 		if (myStat(utf8path, &st) < 0 ||
 		    inodeFoundInParent(parentDirectory, st.st_ino, st.st_dev))
 			return NULL;
 		else {
 			directory = newDirectory(utf8path, parentDirectory);
-			insertInList(parentDirectory->subDirectories,
-				     *shortname, directory);
+			dirvec_add(&parentDirectory->children, directory);
 		}
 	}
 
 	/* if we're adding directory paths, make sure to delete filenames
 	   with potentially the same name */
-	removeSongFromDirectory(parentDirectory, *shortname);
+	removeSongFromDirectory(parentDirectory, mpd_basename(directory->path));
 
-	return (Directory *) directory;
+	return directory;
 }
 
-static Directory *addParentPathToDB(const char *utf8path, const char **shortname)
+static Directory *addParentPathToDB(const char *utf8path)
 {
 	char *parent;
 	char path_max_tmp[MPD_PATH_MAX];
@@ -408,17 +362,13 @@ static Directory *addParentPathToDB(const char *utf8path, const char **shortname
 	parent = parent_path(path_max_tmp, utf8path);
 
 	if (strlen(parent) == 0)
-		parentDirectory = (void *)mp3rootDirectory;
+		parentDirectory = music_root;
 	else
-		parentDirectory = addDirectoryPathToDB(parent, shortname);
+		parentDirectory = addDirectoryPathToDB(parent);
 
 	if (!parentDirectory)
 		return NULL;
 
-	*shortname = utf8path + strlen(parent);
-	while (*(*shortname) && *(*shortname) == '/')
-		(*shortname)++;
-
 	return (Directory *) parentDirectory;
 }
 
@@ -427,64 +377,56 @@ static enum update_return updatePath(const char *utf8path)
 	Directory *directory;
 	Directory *parentDirectory;
 	Song *song;
-	const char *shortname;
-	char *path = sanitizePathDup(utf8path);
 	time_t mtime;
 	enum update_return ret = UPDATE_RETURN_NOUPDATE;
 	char path_max_tmp[MPD_PATH_MAX];
 
-	if (NULL == path)
-		return UPDATE_RETURN_ERROR;
+	assert(utf8path);
 
 	/* if path is in the DB try to update it, or else delete it */
-	if ((directory = getDirectoryDetails(path, &shortname))) {
+	if ((directory = getDirectory(utf8path))) {
 		parentDirectory = directory->parent;
 
 		/* if this update directory is successfull, we are done */
 		if ((ret = updateDirectory(directory)) >= 0) {
-			free(path);
 			sortDirectory(directory);
 			return ret;
 		}
 		/* we don't want to delete the root directory */
-		else if (directory == mp3rootDirectory) {
-			free(path);
+		else if (directory == music_root) {
 			return UPDATE_RETURN_NOUPDATE;
 		}
 		/* if updateDirectory fails, means we should delete it */
 		else {
-			LOG("removing directory: %s\n", path);
-			deleteFromList(parentDirectory->subDirectories,
-				       shortname);
+			LOG("removing directory: %s\n", utf8path);
+			dirvec_delete(&parentDirectory->children, directory);
 			ret = UPDATE_RETURN_UPDATED;
 			/* don't return, path maybe a song now */
 		}
-	} else if ((song = getSongDetails(path, &shortname, &parentDirectory))) {
+	} else if ((song = getSongFromDB(utf8path))) {
+		parentDirectory = song->parentDir;
 		if (!parentDirectory->stat
 		    && statDirectory(parentDirectory) < 0) {
-			free(path);
 			return UPDATE_RETURN_NOUPDATE;
 		}
-		/* if this song update is successfull, we are done */
-		else if (0 == inodeFoundInParent(parentDirectory->parent,
+		/* if this song update is successful, we are done */
+		else if (!inodeFoundInParent(parentDirectory->parent,
 						 parentDirectory->inode,
-						 parentDirectory->device)
-			 && song &&
+						 parentDirectory->device) &&
 			 isMusic(get_song_url(path_max_tmp, song), &mtime, 0)) {
-			free(path);
 			if (song->mtime == mtime)
 				return UPDATE_RETURN_NOUPDATE;
 			else if (updateSongInfo(song) == 0)
 				return UPDATE_RETURN_UPDATED;
 			else {
 				removeSongFromDirectory(parentDirectory,
-							shortname);
+							song->url);
 				return UPDATE_RETURN_UPDATED;
 			}
 		}
 		/* if updateDirectory fails, means we should delete it */
 		else {
-			removeSongFromDirectory(parentDirectory, shortname);
+			removeSongFromDirectory(parentDirectory, song->url);
 			ret = UPDATE_RETURN_UPDATED;
 			/* don't return, path maybe a directory now */
 		}
@@ -494,21 +436,19 @@ static enum update_return updatePath(const char *utf8path)
 	 * Also, if by chance a directory was replaced by a file of the same
 	 * name or vice versa, we need to add it to the db
 	 */
-	if (isDir(path) || isMusic(path, NULL, 0)) {
-		parentDirectory = addParentPathToDB(path, &shortname);
+	if (isDir(utf8path) || isMusic(utf8path, NULL, 0)) {
+		parentDirectory = addParentPathToDB(utf8path);
 		if (!parentDirectory || (!parentDirectory->stat &&
 					 statDirectory(parentDirectory) < 0)) {
 		} else if (0 == inodeFoundInParent(parentDirectory->parent,
 						   parentDirectory->inode,
 						   parentDirectory->device)
-			   && addToDirectory(parentDirectory, shortname, path)
+			   && addToDirectory(parentDirectory, utf8path)
 			   > 0) {
 			ret = UPDATE_RETURN_UPDATED;
 		}
 	}
 
-	free(path);
-
 	return ret;
 }
 
@@ -554,7 +494,7 @@ static enum update_return updateDirectory(Directory * directory)
 		if (directory->path)
 			utf8 = pfx_dir(path_max_tmp, utf8, strlen(utf8),
 			               dirname, strlen(dirname));
-		if (updateInDirectory(directory, utf8, path_max_tmp) > 0)
+		if (updateInDirectory(directory, path_max_tmp) > 0)
 			ret = UPDATE_RETURN_UPDATED;
 	}
 
@@ -593,7 +533,7 @@ static enum update_return exploreDirectory(Directory * directory)
 		if (directory->path)
 			utf8 = pfx_dir(path_max_tmp, utf8, strlen(utf8),
 			               dirname, strlen(dirname));
-		if (addToDirectory(directory, utf8, path_max_tmp) > 0)
+		if (addToDirectory(directory, path_max_tmp) > 0)
 			ret = UPDATE_RETURN_UPDATED;
 	}
 
@@ -630,7 +570,6 @@ static int inodeFoundInParent(Directory * parent, ino_t inode, dev_t device)
 }
 
 static enum update_return addSubDirectoryToDirectory(Directory * directory,
-				      const char *shortname,
 				      const char *name, struct stat *st)
 {
 	Directory *subDirectory;
@@ -646,13 +585,12 @@ static enum update_return addSubDirectoryToDirectory(Directory * directory,
 		return UPDATE_RETURN_NOUPDATE;
 	}
 
-	insertInList(directory->subDirectories, shortname, subDirectory);
+	dirvec_add(&directory->children, subDirectory);
 
 	return UPDATE_RETURN_UPDATED;
 }
 
-static int addToDirectory(Directory * directory,
-			  const char *shortname, const char *name)
+static int addToDirectory(Directory * directory, const char *name)
 {
 	struct stat st;
 
@@ -663,15 +601,16 @@ static int addToDirectory(Directory * directory,
 
 	if (S_ISREG(st.st_mode) &&
 	    hasMusicSuffix(name, 0) && isMusic(name, NULL, 0)) {
-		Song *song = newSong(shortname, SONG_TYPE_FILE, directory);
-		if (!song)
+		Song *song;
+		const char *shortname = mpd_basename(name);
+
+		if (!(song = newSong(shortname, SONG_TYPE_FILE, directory)))
 			return -1;
 		songvec_add(&directory->songs, song);
 		LOG("added %s\n", name);
 		return 1;
 	} else if (S_ISDIR(st.st_mode)) {
-		return addSubDirectoryToDirectory(directory, shortname, name,
-						  &st);
+		return addSubDirectoryToDirectory(directory, name, &st);
 	}
 
 	DEBUG("addToDirectory: %s is not a directory or music\n", name);
@@ -679,88 +618,59 @@ static int addToDirectory(Directory * directory,
 	return -1;
 }
 
-void closeMp3Directory(void)
+void directory_finish(void)
 {
-	freeDirectory(mp3rootDirectory);
-}
-
-static Directory *findSubDirectory(Directory * directory, const char *name)
-{
-	void *subDirectory;
-	char *duplicated = xstrdup(name);
-	char *key;
-
-	key = strtok(duplicated, "/");
-	if (!key) {
-		free(duplicated);
-		return NULL;
-	}
-
-	if (findInList(directory->subDirectories, key, &subDirectory)) {
-		free(duplicated);
-		return (Directory *) subDirectory;
-	}
-
-	free(duplicated);
-	return NULL;
+	freeDirectory(music_root);
 }
 
 int isRootDirectory(const char *name)
 {
-	if (name == NULL || name[0] == '\0' || strcmp(name, "/") == 0) {
-		return 1;
-	}
-	return 0;
+	return (!name || name[0] == '\0' || !strcmp(name, "/"));
 }
 
-static Directory *getSubDirectory(Directory * directory, const char *name,
-				  const char **shortname)
+static Directory *getSubDirectory(Directory * directory, const char *name)
 {
-	Directory *subDirectory;
-	int len;
+	Directory *cur = directory;
+	Directory *found = NULL;
+	char *duplicated;
+	char *locate;
 
-	if (isRootDirectory(name)) {
+	if (isRootDirectory(name))
 		return directory;
-	}
 
-	if ((subDirectory = findSubDirectory(directory, name)) == NULL)
-		return NULL;
-
-	*shortname = name;
-
-	len = 0;
-	while (name[len] != '/' && name[len] != '\0')
-		len++;
-	while (name[len] == '/')
-		len++;
-
-	return getSubDirectory(subDirectory, &(name[len]), shortname);
-}
+	duplicated = xstrdup(name);
+	locate = strchr(duplicated, '/');
+	while (1) {
+		if (locate)
+			*locate = '\0';
+		if (!(found = dirvec_find(&cur->children, duplicated)))
+			break;
+		assert(cur == found->parent);
+		cur = found;
+		if (!locate)
+			break;
+		*locate = '/';
+		locate = strchr(locate + 1, '/');
+	}
 
-static Directory *getDirectoryDetails(const char *name, const char **shortname)
-{
-	*shortname = NULL;
+	free(duplicated);
 
-	return getSubDirectory(mp3rootDirectory, name, shortname);
+	return found;
 }
 
 static Directory *getDirectory(const char *name)
 {
-	const char *shortname;
-
-	return getSubDirectory(mp3rootDirectory, name, &shortname);
+	return getSubDirectory(music_root, name);
 }
 
-static int printDirectoryList(int fd, DirectoryList * directoryList)
+static int printDirectoryList(int fd, struct dirvec *dv)
 {
-	ListNode *node = directoryList->firstNode;
-	Directory *directory;
+	size_t i;
 
-	while (node != NULL) {
-		directory = (Directory *) node->data;
-		fdprintf(fd, "%s%s\n", DIRECTORY_DIR,
-			 getDirectoryPath(directory));
-		node = node->nextNode;
+	for (i = 0; i < dv->nr; ++i) {
+		if (fdprintf(fd, DIRECTORY_DIR "%s\n",
+		             getDirectoryPath(dv->base[i])) < 0)
+			return -1;
 	}
 
 	return 0;
@@ -773,48 +683,39 @@ int printDirectoryInfo(int fd, const char *name)
 	if ((directory = getDirectory(name)) == NULL)
 		return -1;
 
-	printDirectoryList(fd, directory->subDirectories);
+	printDirectoryList(fd, &directory->children);
 	songvec_write(&directory->songs, fd, 0);
 
 	return 0;
 }
 
-static void writeDirectoryInfo(int fd, Directory * directory)
+/* TODO error checking */
+static int writeDirectoryInfo(int fd, Directory * directory)
 {
-	ListNode *node = (directory->subDirectories)->firstNode;
-	Directory *subDirectory;
-	int retv;
-
-	if (directory->path) {
-		retv = fdprintf(fd, DIRECTORY_BEGIN "%s\n",
-			  getDirectoryPath(directory));
-		if (retv < 0) {
-			ERROR("Failed to write data to database file: %s\n",strerror(errno));
-			return;
-		}
-	}
+	struct dirvec *children = &directory->children;
+	size_t i;
 
-	while (node != NULL) {
-		subDirectory = (Directory *) node->data;
-		retv = fdprintf(fd, DIRECTORY_DIR "%s\n", node->key);
-		if (retv < 0) {
-			ERROR("Failed to write data to database file: %s\n",strerror(errno));
-			return;
-		}
-		writeDirectoryInfo(fd, subDirectory);
-		node = node->nextNode;
-	}
+	if (directory->path &&
+	    fdprintf(fd, DIRECTORY_BEGIN "%s\n",
+	             getDirectoryPath(directory)) < 0)
+		return -1;
 
-	songvec_write(&directory->songs, fd, 1);
+	for (i = 0; i < children->nr; ++i) {
+		Directory *cur = children->base[i];
+		const char *base = mpd_basename(cur->path);
 
-	if (directory->path) {
-		retv = fdprintf(fd, DIRECTORY_END "%s\n",
-			  getDirectoryPath(directory));
-		if (retv < 0) {
-			ERROR("Failed to write data to database file: %s\n",strerror(errno));
-			return;
-		}
+		if (fdprintf(fd, DIRECTORY_DIR "%s\n", base) < 0)
+			return -1;
+		if (writeDirectoryInfo(fd, cur) < 0)
+			return -1;
 	}
+	songvec_write(&directory->songs, fd, 1);
+
+	if (directory->path &&
+	    fdprintf(fd, DIRECTORY_END "%s\n",
+	             getDirectoryPath(directory)) < 0)
+		return -1;
+	return 0;
 }
 
 static void readDirectoryInfo(FILE * fp, Directory * directory)
@@ -823,10 +724,7 @@ static void readDirectoryInfo(FILE * fp, Directory * directory)
 	int bufferSize = MPD_PATH_MAX * 2;
 	char key[MPD_PATH_MAX * 2];
 	Directory *subDirectory;
-	int strcmpRet;
 	char *name;
-	ListNode *nextDirNode = directory->subDirectories->firstNode;
-	ListNode *nodeTemp;
 
 	while (myFgets(buffer, bufferSize, fp)
 	       && prefixcmp(buffer, DIRECTORY_END)) {
@@ -842,31 +740,8 @@ static void readDirectoryInfo(FILE * fp, Directory * directory)
 			if (prefixcmp(buffer, DIRECTORY_BEGIN))
 				FATAL("Error reading db at line: %s\n", buffer);
 			name = &(buffer[strlen(DIRECTORY_BEGIN)]);
-
-			while (nextDirNode && (strcmpRet =
-					       strcmp(key,
-						      nextDirNode->key)) > 0) {
-				nodeTemp = nextDirNode->nextNode;
-				deleteNodeFromList(directory->subDirectories,
-						   nextDirNode);
-				nextDirNode = nodeTemp;
-			}
-
-			if (NULL == nextDirNode) {
-				subDirectory = newDirectory(name, directory);
-				insertInList(directory->subDirectories,
-					     key, (void *)subDirectory);
-			} else if (strcmpRet == 0) {
-				subDirectory = (Directory *) nextDirNode->data;
-				nextDirNode = nextDirNode->nextNode;
-			} else {
-				subDirectory = newDirectory(name, directory);
-				insertInListBeforeNode(directory->
-						       subDirectories,
-						       nextDirNode, -1, key,
-						       (void *)subDirectory);
-			}
-
+			subDirectory = newDirectory(name, directory);
+			dirvec_add(&directory->children, subDirectory);
 			readDirectoryInfo(fp, subDirectory);
 		} else if (!prefixcmp(buffer, SONG_BEGIN)) {
 			readSongInfoIntoList(fp, directory);
@@ -874,27 +749,18 @@ static void readDirectoryInfo(FILE * fp, Directory * directory)
 			FATAL("Unknown line in db: %s\n", buffer);
 		}
 	}
-
-	while (nextDirNode) {
-		nodeTemp = nextDirNode->nextNode;
-		deleteNodeFromList(directory->subDirectories, nextDirNode);
-		nextDirNode = nodeTemp;
-	}
 }
 
 static void sortDirectory(Directory * directory)
 {
-	ListNode *node = directory->subDirectories->firstNode;
-	Directory *subDir;
+	int i;
+	struct dirvec *dv = &directory->children;
 
-	sortList(directory->subDirectories);
+	dirvec_sort(dv);
 	songvec_sort(&directory->songs);
 
-	while (node != NULL) {
-		subDir = (Directory *) node->data;
-		sortDirectory(subDir);
-		node = node->nextNode;
-	}
+	for (i = dv->nr; --i >= 0; )
+		sortDirectory(dv->base[i]);
 }
 
 int checkDirectoryDB(void)
@@ -964,11 +830,11 @@ int writeDirectoryDB(void)
 	struct stat st;
 
 	DEBUG("removing empty directories from DB\n");
-	deleteEmptyDirectoriesInDirectory(mp3rootDirectory);
+	deleteEmptyDirectoriesInDirectory(music_root);
 
 	DEBUG("sorting DB\n");
 
-	sortDirectory(mp3rootDirectory);
+	sortDirectory(music_root);
 
 	DEBUG("writing DB\n");
 
@@ -989,8 +855,10 @@ int writeDirectoryDB(void)
 	         DIRECTORY_FS_CHARSET "%s\n"
 	         DIRECTORY_INFO_END "\n", getFsCharset());
 
-	writeDirectoryInfo(fd, mp3rootDirectory);
-
+	if (writeDirectoryInfo(fd, music_root) < 0)
+		ERROR("Failed to write to database file: %s\n",
+		      strerror(errno));
+	return -1;
 	xclose(fd);
 
 	if (stat(dbFile, &st) == 0)
@@ -1005,8 +873,8 @@ int readDirectoryDB(void)
 	char *dbFile = getDbFile();
 	struct stat st;
 
-	if (!mp3rootDirectory)
-		mp3rootDirectory = newDirectory(NULL, NULL);
+	if (!music_root)
+		music_root = newDirectory(NULL, NULL);
 	while (!(fp = fopen(dbFile, "r")) && errno == EINTR) ;
 	if (fp == NULL) {
 		ERROR("unable to open db file \"%s\": %s\n",
@@ -1067,7 +935,7 @@ int readDirectoryDB(void)
 
 	DEBUG("reading DB\n");
 
-	readDirectoryInfo(fp, mp3rootDirectory);
+	readDirectoryInfo(fp, music_root);
 	while (fclose(fp) && errno == EINTR) ;
 
 	stats.numberOfSongs = countSongsIn(NULL);
@@ -1084,9 +952,9 @@ static int traverseAllInSubDirectory(Directory * directory,
 				     int (*forEachDir) (Directory *, void *),
 				     void *data)
 {
-	ListNode *node;
-	Directory *dir;
+	struct dirvec *dv = &directory->children;
 	int errFlag = 0;
+	size_t j;
 
 	if (forEachDir) {
 		errFlag = forEachDir(directory, data);
@@ -1106,14 +974,9 @@ static int traverseAllInSubDirectory(Directory * directory,
 		}
 	}
 
-	node = directory->subDirectories->firstNode;
-
-	while (node != NULL && !errFlag) {
-		dir = (Directory *) node->data;
-		errFlag = traverseAllInSubDirectory(dir, forEachSong,
+	for (j = 0; !errFlag && j < dv->nr; ++j)
+		errFlag = traverseAllInSubDirectory(dv->base[j], forEachSong,
 						    forEachDir, data);
-		node = node->nextNode;
-	}
 
 	return errFlag;
 }
@@ -1136,62 +999,43 @@ int traverseAllIn(const char *name,
 					 data);
 }
 
-void initMp3Directory(void)
+void directory_init(void)
 {
-	mp3rootDirectory = newDirectory(NULL, NULL);
-	exploreDirectory(mp3rootDirectory);
+	music_root = newDirectory(NULL, NULL);
+	exploreDirectory(music_root);
 	stats.numberOfSongs = countSongsIn(NULL);
 	stats.dbPlayTime = sumSongTimesIn(NULL);
 }
 
-static Song *getSongDetails(const char *file, const char **shortnameRet,
-			    Directory ** directoryRet)
+Song *getSongFromDB(const char *file)
 {
-	Song *song;
+	Song *song = NULL;
 	Directory *directory;
 	char *dir = NULL;
 	char *duplicated = xstrdup(file);
-	char *shortname = duplicated;
-	char *c = strtok(duplicated, "/");
+	char *shortname = strrchr(duplicated, '/');
 
 	DEBUG("get song: %s\n", file);
 
-	while (c) {
-		shortname = c;
-		c = strtok(NULL, "/");
-	}
-
-	if (shortname != duplicated) {
-		for (c = duplicated; c < shortname - 1; c++) {
-			if (*c == '\0')
-				*c = '/';
-		}
+	if (!shortname) {
+		shortname = duplicated;
+	} else {
+		*shortname = '\0';
+		++shortname;
 		dir = duplicated;
 	}
 
-	if (!(directory = getDirectory(dir))) {
-		free(duplicated);
-		return NULL;
-	}
-
-	if (!(song = songvec_find(&directory->songs, shortname))) {
-		free(duplicated);
-		return NULL;
-	}
+	if (!(directory = getDirectory(dir)))
+		goto out;
+	if (!(song = songvec_find(&directory->songs, shortname)))
+		goto out;
+	assert(song->parentDir == directory);
 
+out:
 	free(duplicated);
-	if (shortnameRet)
-		*shortnameRet = shortname;
-	if (directoryRet)
-		*directoryRet = directory;
 	return song;
 }
 
-Song *getSongFromDB(const char *file)
-{
-	return getSongDetails(file, NULL, NULL);
-}
-
 time_t getDbModTime(void)
 {
 	return directory_dbModTime;
diff --git a/src/directory.h b/src/directory.h
index e2ff3832a..eb1b35aa7 100644
--- a/src/directory.h
+++ b/src/directory.h
@@ -21,13 +21,15 @@
 
 #include "song.h"
 #include "songvec.h"
-#include "list.h"
 
-typedef List DirectoryList;
+struct dirvec {
+	struct _Directory **base;
+	size_t nr;
+};
 
 typedef struct _Directory {
 	char *path;
-	DirectoryList *subDirectories;
+	struct dirvec children;
 	struct songvec songs;
 	struct _Directory *parent;
 	ino_t inode;
@@ -39,13 +41,17 @@ void reap_update_task(void);
 
 int isUpdatingDB(void);
 
-void directory_sigChldHandler(int pid, int status);
-
-int updateInit(int fd, List * pathList);
+/*
+ * returns the non-negative update job ID on success,
+ * -1 if busy, -2 if invalid argument
+ * @argv itself is safe to free once updateInit returns, but the
+ * string values contained by @argv MUST NOT be freed manually
+ */
+int updateInit(int argc, char *argv[]);
 
-void initMp3Directory(void);
+void directory_init(void);
 
-void closeMp3Directory(void);
+void directory_finish(void);
 
 int isRootDirectory(const char *name);
 
diff --git a/src/dirvec.h b/src/dirvec.h
new file mode 100644
index 000000000..8b2f634e2
--- /dev/null
+++ b/src/dirvec.h
@@ -0,0 +1,73 @@
+#ifndef DIRVEC_H
+#define DIRVEC_H
+
+#include "directory.h"
+#include "os_compat.h"
+#include "utils.h"
+
+static size_t dv_size(struct dirvec *dv)
+{
+	return dv->nr * sizeof(Directory *);
+}
+
+/* Only used for sorting/searching a dirvec, not general purpose compares */
+static int dirvec_cmp(const void *d1, const void *d2)
+{
+	const Directory *a = ((const Directory * const *)d1)[0];
+	const Directory *b = ((const Directory * const *)d2)[0];
+	return strcmp(a->path, b->path);
+}
+
+static void dirvec_sort(struct dirvec *dv)
+{
+	qsort(dv->base, dv->nr, sizeof(Directory *), dirvec_cmp);
+}
+
+static Directory *dirvec_find(struct dirvec *dv, const char *path)
+{
+	int i;
+
+	for (i = dv->nr; --i >= 0; )
+		if (!strcmp(dv->base[i]->path, path))
+			return dv->base[i];
+	return NULL;
+}
+
+static int dirvec_delete(struct dirvec *dv, Directory *del)
+{
+	int i;
+
+	for (i = dv->nr; --i >= 0; ) {
+		if (dv->base[i] != del)
+			continue;
+		/* we _don't_ call freeDirectory() here */
+		if (!--dv->nr) {
+			free(dv->base);
+			dv->base = NULL;
+		} else {
+			memmove(&dv->base[i], &dv->base[i + 1],
+				(dv->nr - i + 1) * sizeof(Directory *));
+			dv->base = xrealloc(dv->base, dv_size(dv));
+		}
+		return i;
+	}
+
+	return -1; /* not found */
+}
+
+static void dirvec_add(struct dirvec *dv, Directory *add)
+{
+	++dv->nr;
+	dv->base = xrealloc(dv->base, dv_size(dv));
+	dv->base[dv->nr - 1] = add;
+}
+
+static void dirvec_destroy(struct dirvec *dv)
+{
+	if (dv->base) {
+		free(dv->base);
+		dv->base = NULL;
+	}
+	dv->nr = 0;
+}
+#endif /* DIRVEC_H */
diff --git a/src/main.c b/src/main.c
index 8028505ab..c0acc260b 100644
--- a/src/main.c
+++ b/src/main.c
@@ -277,7 +277,7 @@ static void openDB(Options * options, char *argv0)
 		flushWarningLog();
 		if (checkDirectoryDB() < 0)
 			exit(EXIT_FAILURE);
-		initMp3Directory();
+		directory_init();
 		if (writeDirectoryDB() < 0)
 			exit(EXIT_FAILURE);
 		if (options->createDB)
@@ -450,8 +450,8 @@ int main(int argc, char *argv[])
 	finishPlaylist();
 
 	start = clock();
-	closeMp3Directory();
-	DEBUG("closeMp3Directory took %f seconds\n", 
+	directory_finish();
+	DEBUG("directory_finish took %f seconds\n",
 	      ((float)(clock()-start))/CLOCKS_PER_SEC);
 
 	finishNormalization();
diff --git a/src/path.c b/src/path.c
index ceb00c5de..8d1b0018d 100644
--- a/src/path.c
+++ b/src/path.c
@@ -290,3 +290,15 @@ void utf8_to_fs_playlist_path(char *path_max_tmp, const char *utf8path)
 	rpp2app_r(path_max_tmp, path_max_tmp);
 	strncat(path_max_tmp, "." PLAYLIST_FILE_SUFFIX, MPD_PATH_MAX - 1);
 }
+
+/* Only takes sanitized paths w/o trailing slashes */
+const char *mpd_basename(const char *path)
+{
+	const char *ret = strrchr(path, '/');
+
+	if (!ret)
+		return path;
+	++ret;
+	assert(*ret != '\0');
+	return ret;
+}
diff --git a/src/path.h b/src/path.h
index a91728126..2c5801528 100644
--- a/src/path.h
+++ b/src/path.h
@@ -88,4 +88,12 @@ void pathcpy_trunc(char *dest, const char *src);
  */
 void utf8_to_fs_playlist_path(char *path_max_tmp, const char *utf8path);
 
+/*
+ * Like basename(3) but with predictable semantics independent
+ * of C library or build options used.  This is also much more strict
+ * and does not account for trailing slashes (mpd should never deal with
+ * trailing slashes on internal functions).
+ */
+const char *mpd_basename(const char *path);
+
 #endif
diff --git a/src/playlist.c b/src/playlist.c
index 0e35bfbdb..af0aaccc0 100644
--- a/src/playlist.c
+++ b/src/playlist.c
@@ -825,7 +825,7 @@ enum playlist_result deleteFromPlaylistById(int id)
 	return deleteFromPlaylist(playlist.idToPosition[id]);
 }
 
-void deleteASongFromPlaylist(Song * song)
+void deleteASongFromPlaylist(const Song * song)
 {
 	int i;
 
diff --git a/src/playlist.h b/src/playlist.h
index 560a4d1e2..6b5fe0cd7 100644
--- a/src/playlist.h
+++ b/src/playlist.h
@@ -92,7 +92,7 @@ enum playlist_result savePlaylist(const char *utf8file);
 
 enum playlist_result deletePlaylist(const char *utf8file);
 
-void deleteASongFromPlaylist(Song * song);
+void deleteASongFromPlaylist(const Song * song);
 
 enum playlist_result moveSongInPlaylist(int from, int to);
 
diff --git a/src/songvec.c b/src/songvec.c
index 842e7afcd..579ac7033 100644
--- a/src/songvec.c
+++ b/src/songvec.c
@@ -30,7 +30,7 @@ Song *songvec_find(struct songvec *sv, const char *url)
 	return NULL;
 }
 
-int songvec_delete(struct songvec *sv, Song *del)
+int songvec_delete(struct songvec *sv, const Song *del)
 {
 	int i;
 
@@ -59,7 +59,7 @@ void songvec_add(struct songvec *sv, Song *add)
 	sv->base[sv->nr - 1] = add;
 }
 
-void songvec_free(struct songvec *sv)
+void songvec_destroy(struct songvec *sv)
 {
 	if (sv->base) {
 		free(sv->base);
diff --git a/src/songvec.h b/src/songvec.h
index abbc9365b..fb5c38c8b 100644
--- a/src/songvec.h
+++ b/src/songvec.h
@@ -13,11 +13,11 @@ void songvec_sort(struct songvec *sv);
 
 Song *songvec_find(struct songvec *sv, const char *url);
 
-int songvec_delete(struct songvec *sv, Song *del);
+int songvec_delete(struct songvec *sv, const Song *del);
 
 void songvec_add(struct songvec *sv, Song *add);
 
-void songvec_free(struct songvec *sv);
+void songvec_destroy(struct songvec *sv);
 
 int songvec_write(struct songvec *sv, int fd, int extra);