From 3b8bc33a0454caf0521b4eb836ac0bbba293ece5 Mon Sep 17 00:00:00 2001
From: Eric Wong <normalperson@yhbt.net>
Date: Mon, 29 Sep 2008 13:11:40 +0200
Subject: 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.
---
src/Makefile.am | 1 +
src/directory.c | 291 +++++++++++++++++++-------------------------------------
src/directory.h | 7 +-
src/dirvec.h | 73 ++++++++++++++
4 files changed, 175 insertions(+), 197 deletions(-)
create mode 100644 src/dirvec.h
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 */
--
cgit v1.2.3