From 3b8bc33a0454caf0521b4eb836ac0bbba293ece5 Mon Sep 17 00:00:00 2001 From: Eric Wong 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