From 0bec1d38078c88d07939a4c210b7cdeb9c8eb59c Mon Sep 17 00:00:00 2001 From: Eric Wong Date: Tue, 23 Sep 2008 20:48:39 +0200 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 | 1 + src/song_print.c | 13 ++++---- src/song_print.h | 4 ++- src/song_save.c | 85 +++++++++++++++++++------------------------------- src/song_save.h | 6 ++-- src/songvec.c | 89 +++++++++++++++++++++++++++++++++++++++++++++++++++++ src/songvec.h | 24 +++++++++++++++ 11 files changed, 212 insertions(+), 113 deletions(-) create mode 100644 src/songvec.c create mode 100644 src/songvec.h diff --git a/src/Makefile.am b/src/Makefile.am index 272a63199..368e051fc 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -86,6 +86,7 @@ mpd_headers = \ song.h \ song_print.h \ song_save.h \ + songvec.h \ state_file.h \ stats.h \ tag.h \ @@ -156,6 +157,7 @@ mpd_SOURCES = \ song.c \ song_print.c \ song_save.c \ + songvec.c \ state_file.c \ stats.c \ tag.c \ diff --git a/src/dbUtils.c b/src/dbUtils.c index d204d7e1e..a19294b04 100644 --- a/src/dbUtils.c +++ b/src/dbUtils.c @@ -51,7 +51,7 @@ static int countSongsInDirectory(Directory * directory, { int *count = (int *)data; - *count += directory->songs->numberOfNodes; + *count += directory->songs.nr; return 0; } @@ -362,7 +362,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 14d1a5b55..66f652867 100644 --- a/src/directory.c +++ b/src/directory.c @@ -241,14 +241,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; @@ -260,7 +260,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); @@ -275,13 +275,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); } } @@ -296,7 +296,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; @@ -311,7 +311,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; @@ -319,14 +319,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)) { @@ -361,6 +360,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) { @@ -381,22 +382,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; @@ -721,12 +720,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)) { @@ -834,7 +833,7 @@ int printDirectoryInfo(struct client *client, const char *name) return -1; printDirectoryList(client, directory->subDirectories); - printSongInfoFromList(client, directory->songs); + songvec_print(client, &directory->songs); return 0; } @@ -865,7 +864,7 @@ static void writeDirectoryInfo(FILE * fp, Directory * directory) node = node->nextNode; } - writeSongInfoFromList(fp, directory->songs); + songvec_save(fp, &directory->songs); if (directory->path) { retv = fprintf(fp, "%s%s\n", DIRECTORY_END, @@ -929,7 +928,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->songs, directory); } else { FATAL("Unknown line in db: %s\n", buffer); } @@ -948,7 +947,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; @@ -1140,8 +1139,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; @@ -1152,13 +1150,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; @@ -1202,7 +1202,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); @@ -1229,7 +1229,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; } @@ -1239,7 +1239,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 252224a6b..ccd20501e 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 a26603735..230388805 100644 --- a/src/song.c +++ b/src/song.c @@ -25,6 +25,7 @@ #include "playlist.h" #include "decoder_list.h" #include "decoder_api.h" + #include "os_compat.h" Song *newNullSong(void) diff --git a/src/song_print.c b/src/song_print.c index 77741e768..f754f2348 100644 --- a/src/song_print.c +++ b/src/song_print.c @@ -17,6 +17,7 @@ */ #include "song_print.h" +#include "songvec.h" #include "directory.h" #include "tag_print.h" #include "client.h" @@ -41,14 +42,14 @@ int printSongInfo(struct client *client, Song * song) return 0; } -int printSongInfoFromList(struct client *client, SongList * list) +int songvec_print(struct client *client, const struct songvec *sv) { - ListNode *tempNode = list->firstNode; + int i; + Song **sp = sv->base; - while (tempNode != NULL) { - printSongInfo(client, (Song *) tempNode->data); - tempNode = tempNode->nextNode; - } + for (i = sv->nr; --i >= 0;) + if (printSongInfo(client, *sp++) < 0) + return -1; return 0; } diff --git a/src/song_print.h b/src/song_print.h index bbc034248..bc7560e88 100644 --- a/src/song_print.h +++ b/src/song_print.h @@ -21,9 +21,11 @@ #include "song.h" +struct songvec; + int printSongInfo(struct client *client, Song * song); -int printSongInfoFromList(struct client *client, SongList * list); +int songvec_print(struct client *client, const struct songvec *sv); void printSongUrl(struct client *client, Song * song); diff --git a/src/song_save.c b/src/song_save.c index a875a65fb..0cff6ef4f 100644 --- a/src/song_save.c +++ b/src/song_save.c @@ -45,52 +45,41 @@ static void song_save(FILE *fp, Song * song) tag_save(fp, song->tag); } -void writeSongInfoFromList(FILE * fp, SongList * list) +void songvec_save(FILE *fp, struct songvec *sv) { - ListNode *tempNode = list->firstNode; + int i; + Song **sp = sv->base; fprintf(fp, "%s\n", SONG_BEGIN); - while (tempNode != NULL) { - fprintf(fp, "%s%s\n", SONG_KEY, tempNode->key); - song_save(fp, (Song *) tempNode->data); - fprintf(fp, "%s%li\n", SONG_MTIME, - (long)((Song *) tempNode->data)->mtime); - tempNode = tempNode->nextNode; + for (i = sv->nr; --i >= 0; ) { + Song *song = *sp++; + fprintf(fp, "%s%s\n", SONG_KEY, song->url); + song_save(fp, song); + fprintf(fp, "%s%li\n", SONG_MTIME, (long)song->mtime); } fprintf(fp, "%s\n", SONG_END); } -static void insertSongIntoList(SongList * list, ListNode ** nextSongNode, - char *key, Song * song) +static void insertSongIntoList(struct songvec *sv, Song *newsong) { - 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); } } @@ -109,23 +98,18 @@ static int matchesAnMpdTagItemKey(char *buffer, int *itemType) return 0; } -void readSongInfoIntoList(FILE * fp, SongList * list, Directory * parentDir) +void readSongInfoIntoList(FILE *fp, struct songvec *sv, + Directory *parentDir) { char buffer[MPD_PATH_MAX + 1024]; int bufferSize = MPD_PATH_MAX + 1024; Song *song = NULL; - ListNode *nextSongNode = list->firstNode; - ListNode *nodeTemp; int itemType; while (myFgets(buffer, bufferSize, fp) && 0 != strcmp(SONG_END, buffer)) { if (0 == strncmp(SONG_KEY, buffer, strlen(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)); @@ -163,15 +147,8 @@ 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); - } + if (song) + insertSongIntoList(sv, song); - while (nextSongNode) { - nodeTemp = nextSongNode->nextNode; - deleteNodeFromList(list, nextSongNode); - nextSongNode = nodeTemp; - } + songvec_prune(sv); } diff --git a/src/song_save.h b/src/song_save.h index 84acae39e..748a2696c 100644 --- a/src/song_save.h +++ b/src/song_save.h @@ -21,9 +21,11 @@ #include "song.h" -void writeSongInfoFromList(FILE * fp, SongList * list); +struct songvec; -void readSongInfoIntoList(FILE * fp, SongList * list, +void songvec_save(FILE *fp, struct songvec *sv); + +void readSongInfoIntoList(FILE * fp, struct songvec *sv, struct _Directory *parent); #endif diff --git a/src/songvec.c b/src/songvec.c new file mode 100644 index 000000000..620338781 --- /dev/null +++ b/src/songvec.c @@ -0,0 +1,89 @@ +#include "songvec.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; +} + +/* + * 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..ada7c262d --- /dev/null +++ b/src/songvec.h @@ -0,0 +1,24 @@ +#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); + +void songvec_prune(struct songvec *sv); + +#endif /* SONGVEC_H */ -- cgit v1.2.3