From 1952b762b0b7024c6a993e62ad957718ac669ac4 Mon Sep 17 00:00:00 2001 From: Eric Wong Date: Sat, 20 Sep 2008 16:20:48 -0700 Subject: Replace SongList with struct songvec Our linked-list implementation is wasteful and the SongList isn't modified enough to benefit from being a linked list. So use a more compact array of song pointers which saves ~200K on a library with ~9K songs (on x86-32). --- src/Makefile.am | 2 + src/dbUtils.c | 4 +- src/directory.c | 94 +++++++++++++++++++++---------------------- src/directory.h | 3 +- src/song.c | 103 +++++++++++------------------------------------ src/song.h | 9 ++--- src/songvec.c | 121 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/songvec.h | 26 ++++++++++++ 8 files changed, 226 insertions(+), 136 deletions(-) create mode 100644 src/songvec.c create mode 100644 src/songvec.h (limited to 'src') diff --git a/src/Makefile.am b/src/Makefile.am index 15efaf78e..88774fff1 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -79,6 +79,7 @@ mpd_headers = \ sig_handlers.h \ sllist.h \ song.h \ + songvec.h \ state_file.h \ stats.h \ tag.h \ @@ -137,6 +138,7 @@ mpd_SOURCES = \ signal_check.c \ sllist.c \ song.c \ + songvec.c \ state_file.c \ stats.c \ tag.c \ diff --git a/src/dbUtils.c b/src/dbUtils.c index 0eb485f1e..1ecb9f608 100644 --- a/src/dbUtils.c +++ b/src/dbUtils.c @@ -50,7 +50,7 @@ static int countSongsInDirectory(Directory * directory, { int *count = (int *)data; - *count += directory->songs->numberOfNodes; + *count += directory->songs.nr; return 0; } @@ -357,7 +357,7 @@ static int sumSavedFilenameMemoryInDirectory(Directory * dir, void *data) return 0; *sum += (strlen(getDirectoryPath(dir)) + 1 - sizeof(Directory *)) * - dir->songs->numberOfNodes; + dir->songs.nr; return 0; } diff --git a/src/directory.c b/src/directory.c index 404afd1a9..c9361fb18 100644 --- a/src/directory.c +++ b/src/directory.c @@ -247,14 +247,14 @@ static Directory *newDirectory(const char *dirname, Directory * parent) { Directory *directory; - directory = xmalloc(sizeof(Directory)); + directory = xcalloc(1, sizeof(Directory)); if (dirname && strlen(dirname)) directory->path = xstrdup(dirname); else directory->path = NULL; directory->subDirectories = newDirectoryList(); - directory->songs = newSongList(); + assert(!directory->songs.base); directory->stat = 0; directory->inode = 0; directory->device = 0; @@ -266,7 +266,7 @@ static Directory *newDirectory(const char *dirname, Directory * parent) static void freeDirectory(Directory * directory) { freeDirectoryList(directory->subDirectories); - freeSongList(directory->songs); + songvec_free(&directory->songs); if (directory->path) free(directory->path); free(directory); @@ -281,13 +281,13 @@ static void freeDirectoryList(DirectoryList * directoryList) static void removeSongFromDirectory(Directory * directory, const char *shortname) { - void *song; + Song *song = songvec_find(&directory->songs, shortname); - if (findInList(directory->songs, shortname, &song)) { + if (song) { char path_max_tmp[MPD_PATH_MAX]; /* wasteful */ - LOG("removing: %s\n", - get_song_url(path_max_tmp, (Song *) song)); - deleteFromList(directory->songs, shortname); + LOG("removing: %s\n", get_song_url(path_max_tmp, song)); + songvec_delete(&directory->songs, song); + freeSong(song); } } @@ -302,7 +302,7 @@ static void deleteEmptyDirectoriesInDirectory(Directory * directory) deleteEmptyDirectoriesInDirectory(subDir); nextNode = node->nextNode; if (subDir->subDirectories->numberOfNodes == 0 && - subDir->songs->numberOfNodes == 0) { + subDir->songs.nr == 0) { deleteNodeFromList(directory->subDirectories, node); } node = nextNode; @@ -317,7 +317,7 @@ static void deleteEmptyDirectoriesInDirectory(Directory * directory) static int updateInDirectory(Directory * directory, const char *shortname, const char *name) { - void *song; + Song *song; void *subDir; struct stat st; @@ -325,14 +325,13 @@ static int updateInDirectory(Directory * directory, return -1; if (S_ISREG(st.st_mode) && hasMusicSuffix(name, 0)) { - if (0 == findInList(directory->songs, shortname, &song)) { + if (!(song = songvec_find(&directory->songs, shortname))) { addToDirectory(directory, shortname, name); return DIRECTORY_RETURN_UPDATE; - } else if (st.st_mtime != ((Song *) song)->mtime) { + } else if (st.st_mtime != song->mtime) { LOG("updating %s\n", name); - if (updateSongInfo((Song *) song) < 0) { + if (updateSongInfo(song) < 0) removeSongFromDirectory(directory, shortname); - } return 1; } } else if (S_ISDIR(st.st_mode)) { @@ -367,6 +366,8 @@ static int removeDeletedFromDirectory(char *path_max_tmp, Directory * directory) ListNode *node, *tmpNode; DirectoryList *subdirs = directory->subDirectories; int ret = 0; + int i; + struct songvec *sv = &directory->songs; node = subdirs->firstNode; while (node) { @@ -387,22 +388,20 @@ static int removeDeletedFromDirectory(char *path_max_tmp, Directory * directory) node = tmpNode; } - node = directory->songs->firstNode; - while (node) { - tmpNode = node->nextNode; - if (node->key) { - if (dirname) - sprintf(path_max_tmp, "%s/%s", dirname, - node->key); - else - strcpy(path_max_tmp, node->key); + for (i = sv->nr; --i >= 0; ) { /* cleaner deletes if we go backwards */ + Song *song = sv->base[i]; + if (!song || !song->url) + continue; /* does this happen?, perhaps assert() */ - if (!isFile(path_max_tmp, NULL)) { - removeSongFromDirectory(directory, node->key); - ret = 1; - } + if (dirname) + sprintf(path_max_tmp, "%s/%s", dirname, song->url); + else + strcpy(path_max_tmp, song->url); + + if (!isFile(path_max_tmp, NULL)) { + removeSongFromDirectory(directory, song->url); + ret = 1; } - node = tmpNode; } return ret; @@ -727,12 +726,12 @@ static int addToDirectory(Directory * directory, return -1; } - if (S_ISREG(st.st_mode) && hasMusicSuffix(name, 0)) { - Song *song; - song = addSongToList(directory->songs, shortname, name, - SONG_TYPE_FILE, directory); + if (S_ISREG(st.st_mode) && + hasMusicSuffix(name, 0) && isMusic(name, NULL, 0)) { + Song *song = newSong(shortname, SONG_TYPE_FILE, directory); if (!song) return -1; + songvec_add(&directory->songs, song); LOG("added %s\n", name); return 1; } else if (S_ISDIR(st.st_mode)) { @@ -840,7 +839,7 @@ int printDirectoryInfo(int fd, const char *name) return -1; printDirectoryList(fd, directory->subDirectories); - printSongInfoFromList(fd, directory->songs); + songvec_write(&directory->songs, fd, 0); return 0; } @@ -871,7 +870,7 @@ static void writeDirectoryInfo(int fd, Directory * directory) node = node->nextNode; } - writeSongInfoFromList(fd, directory->songs); + songvec_write(&directory->songs, fd, 1); if (directory->path) { retv = fdprintf(fd, DIRECTORY_END "%s\n", @@ -935,7 +934,7 @@ static void readDirectoryInfo(FILE * fp, Directory * directory) readDirectoryInfo(fp, subDirectory); } else if (!prefixcmp(buffer, SONG_BEGIN)) { - readSongInfoIntoList(fp, directory->songs, directory); + readSongInfoIntoList(fp, directory); } else { FATAL("Unknown line in db: %s\n", buffer); } @@ -954,7 +953,7 @@ static void sortDirectory(Directory * directory) Directory *subDir; sortList(directory->subDirectories); - sortList(directory->songs); + songvec_sort(&directory->songs); while (node != NULL) { subDir = (Directory *) node->data; @@ -1151,8 +1150,7 @@ static int traverseAllInSubDirectory(Directory * directory, int (*forEachDir) (Directory *, void *), void *data) { - ListNode *node = directory->songs->firstNode; - Song *song; + ListNode *node; Directory *dir; int errFlag = 0; @@ -1163,13 +1161,15 @@ static int traverseAllInSubDirectory(Directory * directory, } if (forEachSong) { - while (node != NULL && !errFlag) { - song = (Song *) node->data; - errFlag = forEachSong(song, data); - node = node->nextNode; + int i; + struct songvec *sv = &directory->songs; + Song **sp = sv->base; + + for (i = sv->nr; --i >= 0; ) { + Song *song = *sp++; + if ((errFlag = forEachSong(song, data))) + return errFlag; } - if (errFlag) - return errFlag; } node = directory->subDirectories->firstNode; @@ -1213,7 +1213,7 @@ void initMp3Directory(void) static Song *getSongDetails(const char *file, const char **shortnameRet, Directory ** directoryRet) { - void *song = NULL; + Song *song; Directory *directory; char *dir = NULL; char *duplicated = xstrdup(file); @@ -1240,7 +1240,7 @@ static Song *getSongDetails(const char *file, const char **shortnameRet, return NULL; } - if (!findInList(directory->songs, shortname, &song)) { + if (!(song = songvec_find(&directory->songs, shortname))) { free(duplicated); return NULL; } @@ -1250,7 +1250,7 @@ static Song *getSongDetails(const char *file, const char **shortnameRet, *shortnameRet = shortname; if (directoryRet) *directoryRet = directory; - return (Song *) song; + return song; } Song *getSongFromDB(const char *file) diff --git a/src/directory.h b/src/directory.h index e881f7a04..40c9d6499 100644 --- a/src/directory.h +++ b/src/directory.h @@ -20,13 +20,14 @@ #define DIRECTORY_H #include "song.h" +#include "songvec.h" typedef List DirectoryList; typedef struct _Directory { char *path; DirectoryList *subDirectories; - SongList *songs; + struct songvec songs; struct _Directory *parent; ino_t inode; dev_t device; diff --git a/src/song.c b/src/song.c index ff0ada620..0abf5c9b7 100644 --- a/src/song.c +++ b/src/song.c @@ -27,9 +27,6 @@ #include "inputPlugin.h" #include "myfprintf.h" -#define SONG_KEY "key: " -#define SONG_MTIME "mtime: " - #include "os_compat.h" static Song *newNullSong(void) @@ -152,64 +149,24 @@ int printSongInfo(int fd, Song * song) return 0; } -int printSongInfoFromList(int fd, SongList * list) -{ - ListNode *tempNode = list->firstNode; - - while (tempNode != NULL) { - printSongInfo(fd, (Song *) tempNode->data); - tempNode = tempNode->nextNode; - } - - return 0; -} - -void writeSongInfoFromList(int fd, SongList * list) +static void insertSongIntoList(struct songvec *sv, Song *newsong) { - ListNode *tempNode = list->firstNode; - - fdprintf(fd, SONG_BEGIN "\n"); - - while (tempNode != NULL) { - fdprintf(fd, SONG_KEY "%s\n", tempNode->key); - printSongInfo(fd, (Song *) tempNode->data); - fdprintf(fd, SONG_MTIME "%li\n", - (long)((Song *) tempNode->data)->mtime); - tempNode = tempNode->nextNode; - } - - fdprintf(fd, SONG_END "\n"); -} - -static void insertSongIntoList(SongList * list, ListNode ** nextSongNode, - char *key, Song * song) -{ - ListNode *nodeTemp; - int cmpRet = 0; - - while (*nextSongNode - && (cmpRet = strcmp(key, (*nextSongNode)->key)) > 0) { - nodeTemp = (*nextSongNode)->nextNode; - deleteNodeFromList(list, *nextSongNode); - *nextSongNode = nodeTemp; - } - - if (!(*nextSongNode)) { - insertInList(list, song->url, (void *)song); - } else if (cmpRet == 0) { - Song *tempSong = (Song *) ((*nextSongNode)->data); - if (tempSong->mtime != song->mtime) { - tag_free(tempSong->tag); - tag_end_add(song->tag); - tempSong->tag = song->tag; - tempSong->mtime = song->mtime; - song->tag = NULL; + Song *existing = songvec_find(sv, newsong->url); + + if (!existing) { + songvec_add(sv, newsong); + if (newsong->tag) + tag_end_add(newsong->tag); + } else { /* prevent dupes, just update the existing song info */ + if (existing->mtime != newsong->mtime) { + tag_free(existing->tag); + if (newsong->tag) + tag_end_add(newsong->tag); + existing->tag = newsong->tag; + existing->mtime = newsong->mtime; + newsong->tag = NULL; } - freeJustSong(song); - *nextSongNode = (*nextSongNode)->nextNode; - } else { - insertInListBeforeNode(list, *nextSongNode, -1, song->url, - (void *)song); + freeJustSong(newsong); } } @@ -227,24 +184,18 @@ static int matchesAnMpdTagItemKey(char *buffer, int *itemType) return 0; } -void readSongInfoIntoList(FILE * fp, SongList * list, Directory * parentDir) +void readSongInfoIntoList(FILE * fp, Directory * parentDir) { char buffer[MPD_PATH_MAX + 1024]; int bufferSize = MPD_PATH_MAX + 1024; Song *song = NULL; - ListNode *nextSongNode = list->firstNode; - ListNode *nodeTemp; + struct songvec *sv = &parentDir->songs; int itemType; while (myFgets(buffer, bufferSize, fp) && 0 != strcmp(SONG_END, buffer)) { if (!prefixcmp(buffer, SONG_KEY)) { - if (song) { - insertSongIntoList(list, &nextSongNode, - song->url, song); - if (song->tag != NULL) - tag_end_add(song->tag); - } - + if (song) + insertSongIntoList(sv, song); song = newNullSong(); song->url = xstrdup(buffer + strlen(SONG_KEY)); song->type = SONG_TYPE_FILE; @@ -281,17 +232,9 @@ void readSongInfoIntoList(FILE * fp, SongList * list, Directory * parentDir) FATAL("songinfo: unknown line in db: %s\n", buffer); } - if (song) { - insertSongIntoList(list, &nextSongNode, song->url, song); - if (song->tag != NULL) - tag_end_add(song->tag); - } - - while (nextSongNode) { - nodeTemp = nextSongNode->nextNode; - deleteNodeFromList(list, nextSongNode); - nextSongNode = nodeTemp; - } + if (song) + insertSongIntoList(sv, song); + songvec_prune(sv); } int updateSongInfo(Song * song) diff --git a/src/song.h b/src/song.h index d27596abd..c31c39829 100644 --- a/src/song.h +++ b/src/song.h @@ -24,6 +24,8 @@ #include "tag.h" #include "list.h" +#define SONG_KEY "key: " +#define SONG_MTIME "mtime: " #define SONG_BEGIN "songList begin" #define SONG_END "songList end" @@ -58,12 +60,7 @@ Song *addSongToList(SongList * list, const char *url, const char *utf8path, int printSongInfo(int fd, Song * song); -int printSongInfoFromList(int fd, SongList * list); - -void writeSongInfoFromList(int fd, SongList * list); - -void readSongInfoIntoList(FILE * fp, SongList * list, - struct _Directory *parent); +void readSongInfoIntoList(FILE * fp, struct _Directory *parent); int updateSongInfo(Song * song); diff --git a/src/songvec.c b/src/songvec.c new file mode 100644 index 000000000..ac84e7f8e --- /dev/null +++ b/src/songvec.c @@ -0,0 +1,121 @@ +#include "songvec.h" +#include "myfprintf.h" +#include "utils.h" + +/* Only used for sorting/searchin a songvec, not general purpose compares */ +static int songvec_cmp(const void *s1, const void *s2) +{ + const Song *a = ((const Song * const *)s1)[0]; + const Song *b = ((const Song * const *)s2)[0]; + return strcmp(a->url, b->url); +} + +static size_t sv_size(struct songvec *sv) +{ + return sv->nr * sizeof(Song *); +} + +void songvec_sort(struct songvec *sv) +{ + qsort(sv->base, sv->nr, sizeof(Song *), songvec_cmp); +} + +Song *songvec_find(struct songvec *sv, const char *url) +{ + int i; + + for (i = sv->nr; --i >= 0; ) + if (!strcmp(sv->base[i]->url, url)) + return sv->base[i]; + return NULL; +} + +int songvec_delete(struct songvec *sv, Song *del) +{ + int i; + + for (i = sv->nr; --i >= 0; ) { + if (sv->base[i] != del) + continue; + /* we _don't_ call freeSong() here */ + if (!--sv->nr) { + free(sv->base); + sv->base = NULL; + } else { + memmove(&sv->base[i], &sv->base[i + 1], + (sv->nr - i + 1) * sizeof(Song *)); + sv->base = xrealloc(sv->base, sv_size(sv)); + } + return i; + } + + return -1; /* not found */ +} + +void songvec_add(struct songvec *sv, Song *add) +{ + ++sv->nr; + sv->base = xrealloc(sv->base, sv_size(sv)); + sv->base[sv->nr - 1] = add; +} + +void songvec_free(struct songvec *sv) +{ + free(sv->base); + sv->base = NULL; + sv->nr = 0; +} + +int songvec_write(struct songvec *sv, int fd, int extra) +{ + int i; + Song **sp = sv->base; + + if (extra) { + if (fdprintf(fd, SONG_BEGIN "\n") < 0) + return -1; + + for (i = sv->nr; --i >= 0; ) { + Song *song = *sp++; + if (fdprintf(fd, SONG_KEY "%s\n", song->url) < 0) + return -1; + if (printSongInfo(fd, song) < 0) + return -1; + if (fdprintf(fd, + SONG_MTIME "%li\n", (long)song->mtime) < 0) + return -1; + } + + if (fdprintf(fd, SONG_END "\n") < 0) + return -1; + } else { + for (i = sv->nr; --i >= 0;) + if (printSongInfo(fd, *sp++) < 0) + return -1; + } + + return 0; +} + +/* + * Removes missing songs from a songvec. This function is only temporary + * as updating will be moved into a thread and updating shared memory... + */ +#include "path.h" +#include "ls.h" +void songvec_prune(struct songvec *sv) +{ + int i; + char tmp[MPD_PATH_MAX]; + struct stat sb; + + for (i = sv->nr; --i >= 0; ) { + Song *song = sv->base[i]; + assert(song); + if (!myStat(get_song_url(tmp, song), &sb)) + continue; + songvec_delete(sv, song); + freeSong(song); + i = sv->nr; + } +} diff --git a/src/songvec.h b/src/songvec.h new file mode 100644 index 000000000..5952f871f --- /dev/null +++ b/src/songvec.h @@ -0,0 +1,26 @@ +#ifndef SONGVEC_H +#define SONGVEC_H + +#include "song.h" +#include "os_compat.h" + +struct songvec { + Song **base; + size_t nr; +}; + +void songvec_sort(struct songvec *sv); + +Song *songvec_find(struct songvec *sv, const char *url); + +int songvec_delete(struct songvec *sv, Song *del); + +void songvec_add(struct songvec *sv, Song *add); + +void songvec_free(struct songvec *sv); + +int songvec_write(struct songvec *sv, int fd, int extra); + +void songvec_prune(struct songvec *sv); + +#endif /* SONGVEC_H */ -- cgit v1.2.3