directory: replace DirectoryList with dirvec

Small memory reduction compared to songvec since most users have
much fewer dirs than songs, but still nice to have.

4 files changed, 175 insertions, 197 deletions

diff --git a/src/Makefile.am b/src/Makefile.am
index 5fc4be55f..d0ef815d2 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -53,6 +53,7 @@ mpd_headers = \
 	decoder_api.h \
 	decoder_internal.h \
 	directory.h \
+	dirvec.h \
 	gcc.h \
 	decoder_list.h \
 	inputPlugins/_flac_common.h \
diff --git a/src/directory.c b/src/directory.c
index d051a9308..aa84d50b3 100644
--- a/src/directory.c
+++ b/src/directory.c
@@ -30,6 +30,7 @@
 #include "song_print.h"
 #include "song_save.h"
 #include "main_notify.h"
+#include "dirvec.h"
 
 #define DIRECTORY_DIR		"directory: "
 #define DIRECTORY_MTIME		"mtime: "
@@ -60,14 +61,10 @@ static pthread_t update_thr;
 
 static int directory_updateJobId;
 
-static DirectoryList *newDirectoryList(void);
-
 static enum update_return
 addToDirectory(Directory * directory,
 	       const char *shortname, const char *name);
 
-static void freeDirectoryList(DirectoryList * list);
-
 static void freeDirectory(Directory * directory);
 
 static enum update_return exploreDirectory(Directory * directory);
@@ -188,11 +185,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;
@@ -201,13 +193,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;
@@ -215,7 +200,7 @@ static Directory *newDirectory(const char *dirname, Directory * parent)
 
 static void freeDirectory(Directory * directory)
 {
-	freeDirectoryList(directory->subDirectories);
+	dirvec_destroy(&directory->children);
 	songvec_destroy(&directory->songs);
 	if (directory->path)
 		free(directory->path);
@@ -224,11 +209,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);
@@ -243,27 +223,22 @@ 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)
 {
 	Song *song;
-	void *subDir;
 	struct stat st;
 
 	if (myStat(name, &st))
@@ -280,10 +255,10 @@ 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) {
+			directory_set_stat(subdir, &st);
+			return updateDirectory(subdir);
 		} else {
 			return addSubDirectoryToDirectory(directory, shortname,
 							  name, &st);
@@ -304,29 +279,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 */
@@ -354,7 +317,7 @@ 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);
 
@@ -370,16 +333,14 @@ static Directory *addDirectoryPathToDB(const char *utf8path,
 	while (*(*shortname) && *(*shortname) == '/')
 		(*shortname)++;
 
-	if (!findInList
-	    (parentDirectory->subDirectories, *shortname, &directory)) {
+	if (!(directory = dirvec_find(&parentDirectory->children, utf8path))) {
 		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);
 		}
 	}
 
@@ -387,7 +348,7 @@ static Directory *addDirectoryPathToDB(const char *utf8path,
 	   with potentially the same name */
 	removeSongFromDirectory(parentDirectory, *shortname);
 
-	return (Directory *) directory;
+	return directory;
 }
 
 static Directory *addParentPathToDB(const char *utf8path, const char **shortname)
@@ -446,8 +407,7 @@ static enum update_return updatePath(const char *utf8path)
 		/* if updateDirectory fails, means we should delete it */
 		else {
 			LOG("removing directory: %s\n", path);
-			deleteFromList(parentDirectory->subDirectories,
-				       shortname);
+			dirvec_delete(&parentDirectory->children, directory);
 			ret = UPDATE_RETURN_UPDATED;
 			/* don't return, path maybe a song now */
 		}
@@ -623,7 +583,7 @@ static int inodeFoundInParent(Directory * parent, ino_t inode, dev_t device)
 }
 
 static enum update_return addSubDirectoryToDirectory(Directory * directory,
-				      const char *shortname,
+				      mpd_unused const char *shortname,
 				      const char *name, struct stat *st)
 {
 	Directory *subDirectory;
@@ -639,7 +599,7 @@ 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;
 }
@@ -678,27 +638,6 @@ void closeMp3Directory(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;
-}
-
 int isRootDirectory(const char *name)
 {
 	if (name == NULL || name[0] == '\0' || strcmp(name, "/") == 0) {
@@ -710,25 +649,34 @@ int isRootDirectory(const char *name)
 static Directory *getSubDirectory(Directory * directory, const char *name,
 				  const char **shortname)
 {
-	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;
+	duplicated = xstrdup(name);
+	locate = strchr(duplicated, '/');
+	while (1) {
+		if (locate)
+			*locate = '\0';
+		if (!(found = dirvec_find(&cur->children, duplicated)))
+			break;
+		cur = found;
+		if (!locate)
+			break;
+		*locate = '/';
+		locate = strchr(locate + 1, '/');
+	}
 
-	*shortname = name;
+	free(duplicated);
 
-	len = 0;
-	while (name[len] != '/' && name[len] != '\0')
-		len++;
-	while (name[len] == '/')
-		len++;
+	if (found && (!(*shortname = strrchr(found->path, '/'))))
+		*shortname = found->path;
 
-	return getSubDirectory(subDirectory, &(name[len]), shortname);
+	return found;
 }
 
 static Directory *getDirectoryDetails(const char *name, const char **shortname)
@@ -745,16 +693,13 @@ static Directory *getDirectory(const char *name)
 	return getSubDirectory(mp3rootDirectory, name, &shortname);
 }
 
-static int printDirectoryList(struct client *client, DirectoryList * directoryList)
+static int printDirectoryList(struct client *client, struct dirvec *dv)
 {
-	ListNode *node = directoryList->firstNode;
-	Directory *directory;
+	size_t i;
 
-	while (node != NULL) {
-		directory = (Directory *) node->data;
-		client_printf(client, "%s%s\n", DIRECTORY_DIR,
-			      getDirectoryPath(directory));
-		node = node->nextNode;
+	for (i = 0; i < dv->nr; ++i) {
+		client_printf(client, DIRECTORY_DIR "%s\n",
+			      getDirectoryPath(dv->base[i]));
 	}
 
 	return 0;
@@ -767,16 +712,17 @@ int printDirectoryInfo(struct client *client, const char *name)
 	if ((directory = getDirectory(name)) == NULL)
 		return -1;
 
-	printDirectoryList(client, directory->subDirectories);
+	printDirectoryList(client, &directory->children);
 	songvec_print(client, &directory->songs);
 
 	return 0;
 }
 
+/* TODO error checking */
 static void writeDirectoryInfo(FILE * fp, Directory * directory)
 {
-	ListNode *node = (directory->subDirectories)->firstNode;
-	Directory *subDirectory;
+	struct dirvec *children = &directory->children;
+	size_t i;
 	int retv;
 
 	if (directory->path) {
@@ -788,15 +734,20 @@ static void writeDirectoryInfo(FILE * fp, Directory * directory)
 		}
 	}
 
-	while (node != NULL) {
-		subDirectory = (Directory *) node->data;
-		retv = fprintf(fp, "%s%s\n", DIRECTORY_DIR, node->key);
+	for (i = 0; i < children->nr; ++i) {
+		Directory *cur = children->base[i];
+		const char *base = strrchr(cur->path, '/');
+
+		base = base ? base + 1 : cur->path;
+		assert(*base);
+
+		retv = fprintf(fp, DIRECTORY_DIR "%s\n", base);
 		if (retv < 0) {
-			ERROR("Failed to write data to database file: %s\n",strerror(errno));
+			ERROR("Failed to write data to database file: %s\n",
+			      strerror(errno));
 			return;
 		}
-		writeDirectoryInfo(fp, subDirectory);
-		node = node->nextNode;
+		writeDirectoryInfo(fp, cur);
 	}
 
 	songvec_save(fp, &directory->songs);
@@ -817,10 +768,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)) {
@@ -836,31 +784,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->songs, directory);
@@ -868,27 +793,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)
@@ -1074,9 +990,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);
@@ -1096,14 +1012,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;
 }
@@ -1137,43 +1048,33 @@ void initMp3Directory(void)
 static Song *getSongDetails(const char *file, const char **shortnameRet,
 			    Directory ** directoryRet)
 {
-	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;
 
-	free(duplicated);
 	if (shortnameRet)
-		*shortnameRet = shortname;
+		*shortnameRet = song->url;
 	if (directoryRet)
 		*directoryRet = directory;
+out:
+	free(duplicated);
 	return song;
 }
 
diff --git a/src/directory.h b/src/directory.h
index 320a93a7f..e7917c8cd 100644
--- a/src/directory.h
+++ b/src/directory.h
@@ -23,11 +23,14 @@
 #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;
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 */