From 84ba14fa294f43b5dc75f899533d0596031aabd6 Mon Sep 17 00:00:00 2001 From: Max Kellermann Date: Tue, 24 Jan 2012 21:33:09 +0100 Subject: directory: replace songvec with doubly linked list --- src/directory.c | 37 ++++++--- src/directory.h | 18 +++- src/directory_save.c | 4 +- src/song.h | 12 +++ src/song_print.c | 1 - src/song_save.c | 13 --- src/song_save.h | 4 - src/song_sort.c | 121 +++++++++++++++++++++++++++ src/song_sort.h | 28 +++++++ src/songvec.c | 226 --------------------------------------------------- src/songvec.h | 51 ------------ src/update_walk.c | 75 +++++++---------- 12 files changed, 231 insertions(+), 359 deletions(-) create mode 100644 src/song_sort.c create mode 100644 src/song_sort.h delete mode 100644 src/songvec.c delete mode 100644 src/songvec.h (limited to 'src') diff --git a/src/directory.c b/src/directory.c index 3700579af..232c6bd34 100644 --- a/src/directory.c +++ b/src/directory.c @@ -20,6 +20,7 @@ #include "config.h" #include "directory.h" #include "song.h" +#include "song_sort.h" #include "path.h" #include "util/list_sort.h" #include "db_visitor.h" @@ -43,6 +44,7 @@ directory_new(const char *path, struct directory *parent) directory = g_malloc0(sizeof(*directory) - sizeof(directory->path) + pathlen + 1); INIT_LIST_HEAD(&directory->children); + INIT_LIST_HEAD(&directory->songs); directory->parent = parent; memcpy(directory->path, path, pathlen + 1); @@ -56,14 +58,14 @@ directory_free(struct directory *directory) { playlist_vector_deinit(&directory->playlists); - for (unsigned i = 0; i < directory->songs.nr; ++i) - song_free(directory->songs.base[i]); + struct song *song, *ns; + directory_for_each_song_safe(song, ns, directory) + song_free(song); struct directory *child, *n; directory_for_each_child_safe(child, n, directory) directory_free(child); - songvec_destroy(&directory->songs); g_free(directory); /* this resets last dir returned */ /*directory_get_path(NULL); */ @@ -184,7 +186,7 @@ directory_add_song(struct directory *directory, struct song *song) assert(song != NULL); assert(song->parent == directory); - songvec_add(&directory->songs, song); + list_add(&song->siblings, &directory->songs); } void @@ -194,7 +196,7 @@ directory_remove_song(struct directory *directory, struct song *song) assert(song != NULL); assert(song->parent == directory); - songvec_delete(&directory->songs, song); + list_del(&song->siblings); } struct song * @@ -203,9 +205,19 @@ directory_get_song(const struct directory *directory, const char *name_utf8) assert(directory != NULL); assert(name_utf8 != NULL); - struct song *song = songvec_find(&directory->songs, name_utf8); - assert(song == NULL || song->parent == directory); - return song; + db_lock(); + struct song *song; + directory_for_each_song(song, directory) { + assert(song->parent == directory); + + if (strcmp(song->uri, name_utf8) == 0) { + db_unlock(); + return song; + } + } + + db_unlock(); + return NULL; } struct song * @@ -251,10 +263,9 @@ directory_sort(struct directory *directory) { db_lock(); list_sort(NULL, &directory->children, directory_cmp); + song_list_sort(&directory->songs); db_unlock(); - songvec_sort(&directory->songs); - struct directory *child; directory_for_each_child(child, directory) directory_sort(child); @@ -270,9 +281,9 @@ directory_walk(const struct directory *directory, bool recursive, assert(error_r == NULL || *error_r == NULL); if (visitor->song != NULL) { - const struct songvec *sv = &directory->songs; - for (size_t i = 0; i < sv->nr; ++i) - if (!visitor->song(sv->base[i], ctx, error_r)) + struct song *song; + directory_for_each_song(song, directory) + if (!visitor->song(song, ctx, error_r)) return false; } diff --git a/src/directory.h b/src/directory.h index b866295ae..5460cb46a 100644 --- a/src/directory.h +++ b/src/directory.h @@ -22,7 +22,6 @@ #include "check.h" #include "util/list.h" -#include "songvec.h" #include "playlist_vector.h" #include @@ -40,6 +39,13 @@ #define directory_for_each_child_safe(pos, n, directory) \ list_for_each_entry_safe(pos, n, &directory->children, siblings) +#define directory_for_each_song(pos, directory) \ + list_for_each_entry(pos, &directory->songs, siblings) + +#define directory_for_each_song_safe(pos, n, directory) \ + list_for_each_entry_safe(pos, n, &directory->songs, siblings) + +struct song; struct db_visitor; struct directory { @@ -61,7 +67,13 @@ struct directory { */ struct list_head children; - struct songvec songs; + /** + * A doubly linked list of songs within this directory. + * + * This attribute is protected with the global #db_mutex. + * Read access in the update thread does not need protection. + */ + struct list_head songs; struct playlist_vector playlists; @@ -114,7 +126,7 @@ static inline bool directory_is_empty(const struct directory *directory) { return list_empty(&directory->children) && - directory->songs.nr == 0 && + list_empty(&directory->songs) && playlist_vector_is_empty(&directory->playlists); } diff --git a/src/directory_save.c b/src/directory_save.c index 087fab4c7..8d20a99f9 100644 --- a/src/directory_save.c +++ b/src/directory_save.c @@ -65,7 +65,9 @@ directory_save(FILE *fp, const struct directory *directory) return; } - songvec_save(fp, &directory->songs); + struct song *song; + directory_for_each_song(song, directory) + song_save(fp, song); playlist_vector_save(fp, &directory->playlists); diff --git a/src/song.h b/src/song.h index 9553c76c4..95cc2eb86 100644 --- a/src/song.h +++ b/src/song.h @@ -20,6 +20,8 @@ #ifndef MPD_SONG_H #define MPD_SONG_H +#include "util/list.h" + #include #include #include @@ -28,6 +30,16 @@ #define SONG_TIME "Time: " struct song { + /** + * Pointers to the siblings of this directory within the + * parent directory. It is unused (undefined) if this song is + * not in the database. + * + * This attribute is protected with the global #db_mutex. + * Read access in the update thread does not need protection. + */ + struct list_head siblings; + struct tag *tag; struct directory *parent; time_t mtime; diff --git a/src/song_print.c b/src/song_print.c index 2065b336d..fb608a8b2 100644 --- a/src/song_print.c +++ b/src/song_print.c @@ -20,7 +20,6 @@ #include "config.h" #include "song_print.h" #include "song.h" -#include "songvec.h" #include "directory.h" #include "tag_print.h" #include "client.h" diff --git a/src/song_save.c b/src/song_save.c index 5c9353628..0d4c36f99 100644 --- a/src/song_save.c +++ b/src/song_save.c @@ -59,19 +59,6 @@ song_save(FILE *fp, const struct song *song) fprintf(fp, SONG_END "\n"); } -static int -song_save_callback(struct song *song, void *data) -{ - FILE *fp = data; - song_save(fp, song); - return 0; -} - -void songvec_save(FILE *fp, const struct songvec *sv) -{ - songvec_for_each(sv, song_save_callback, fp); -} - struct song * song_load(FILE *fp, struct directory *parent, const char *uri, GString *buffer, GError **error_r) diff --git a/src/song_save.h b/src/song_save.h index 1aaa7642c..f6ecbbfeb 100644 --- a/src/song_save.h +++ b/src/song_save.h @@ -27,15 +27,11 @@ #define SONG_BEGIN "song_begin: " struct song; -struct songvec; struct directory; void song_save(FILE *fp, const struct song *song); -void -songvec_save(FILE *fp, const struct songvec *sv); - /** * Loads a song from the input file. Reading stops after the * "song_end" line. diff --git a/src/song_sort.c b/src/song_sort.c new file mode 100644 index 000000000..397d2c7a9 --- /dev/null +++ b/src/song_sort.c @@ -0,0 +1,121 @@ +/* + * Copyright (C) 2003-2012 The Music Player Daemon Project + * http://www.musicpd.org + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ + +#include "config.h" +#include "song_sort.h" +#include "song.h" +#include "util/list.h" +#include "util/list_sort.h" +#include "tag.h" + +#include + +#include +#include + +static const char * +tag_get_value_checked(const struct tag *tag, enum tag_type type) +{ + return tag != NULL + ? tag_get_value(tag, type) + : NULL; +} + +static int +compare_utf8_string(const char *a, const char *b) +{ + if (a == NULL) + return b == NULL ? 0 : -1; + + if (b == NULL) + return 1; + + return g_utf8_collate(a, b); +} + +/** + * Compare two string tag values, ignoring case. Either one may be + * NULL. + */ +static int +compare_string_tag_item(const struct tag *a, const struct tag *b, + enum tag_type type) +{ + return compare_utf8_string(tag_get_value_checked(a, type), + tag_get_value_checked(b, type)); +} + +/** + * Compare two tag values which should contain an integer value + * (e.g. disc or track number). Either one may be NULL. + */ +static int +compare_number_string(const char *a, const char *b) +{ + long ai = a == NULL ? 0 : strtol(a, NULL, 10); + long bi = b == NULL ? 0 : strtol(b, NULL, 10); + + if (ai <= 0) + return bi <= 0 ? 0 : -1; + + if (bi <= 0) + return 1; + + return ai - bi; +} + +static int +compare_tag_item(const struct tag *a, const struct tag *b, enum tag_type type) +{ + return compare_number_string(tag_get_value_checked(a, type), + tag_get_value_checked(b, type)); +} + +/* Only used for sorting/searchin a songvec, not general purpose compares */ +static int +song_cmp(G_GNUC_UNUSED void *priv, struct list_head *_a, struct list_head *_b) +{ + const struct song *a = (const struct song *)_a; + const struct song *b = (const struct song *)_b; + int ret; + + /* first sort by album */ + ret = compare_string_tag_item(a->tag, b->tag, TAG_ALBUM); + if (ret != 0) + return ret; + + /* then sort by disc */ + ret = compare_tag_item(a->tag, b->tag, TAG_DISC); + if (ret != 0) + return ret; + + /* then by track number */ + ret = compare_tag_item(a->tag, b->tag, TAG_TRACK); + if (ret != 0) + return ret; + + /* still no difference? compare file name */ + return g_utf8_collate(a->uri, b->uri); +} + +void +song_list_sort(struct list_head *songs) +{ + list_sort(NULL, songs, song_cmp); +} diff --git a/src/song_sort.h b/src/song_sort.h new file mode 100644 index 000000000..ec124cf4a --- /dev/null +++ b/src/song_sort.h @@ -0,0 +1,28 @@ +/* + * Copyright (C) 2003-2012 The Music Player Daemon Project + * http://www.musicpd.org + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ + +#ifndef MPD_SONG_SORT_H +#define MPD_SONG_SORT_H + +struct list_head; + +void +song_list_sort(struct list_head *songs); + +#endif diff --git a/src/songvec.c b/src/songvec.c deleted file mode 100644 index 9e0321583..000000000 --- a/src/songvec.c +++ /dev/null @@ -1,226 +0,0 @@ -/* - * Copyright (C) 2003-2011 The Music Player Daemon Project - * http://www.musicpd.org - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License along - * with this program; if not, write to the Free Software Foundation, Inc., - * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. - */ - -#include "config.h" -#include "songvec.h" -#include "song.h" -#include "tag.h" -#include "db_lock.h" - -#include - -#include -#include -#include - -static const char * -tag_get_value_checked(const struct tag *tag, enum tag_type type) -{ - return tag != NULL - ? tag_get_value(tag, type) - : NULL; -} - -static int -compare_utf8_string(const char *a, const char *b) -{ - if (a == NULL) - return b == NULL ? 0 : -1; - - if (b == NULL) - return 1; - - return g_utf8_collate(a, b); -} - -/** - * Compare two string tag values, ignoring case. Either one may be - * NULL. - */ -static int -compare_string_tag_item(const struct tag *a, const struct tag *b, - enum tag_type type) -{ - return compare_utf8_string(tag_get_value_checked(a, type), - tag_get_value_checked(b, type)); -} - -/** - * Compare two tag values which should contain an integer value - * (e.g. disc or track number). Either one may be NULL. - */ -static int -compare_number_string(const char *a, const char *b) -{ - long ai = a == NULL ? 0 : strtol(a, NULL, 10); - long bi = b == NULL ? 0 : strtol(b, NULL, 10); - - if (ai <= 0) - return bi <= 0 ? 0 : -1; - - if (bi <= 0) - return 1; - - return ai - bi; -} - -static int -compare_tag_item(const struct tag *a, const struct tag *b, enum tag_type type) -{ - return compare_number_string(tag_get_value_checked(a, type), - tag_get_value_checked(b, type)); -} - -/* Only used for sorting/searchin a songvec, not general purpose compares */ -static int songvec_cmp(const void *s1, const void *s2) -{ - const struct song *a = ((const struct song * const *)s1)[0]; - const struct song *b = ((const struct song * const *)s2)[0]; - int ret; - - /* first sort by album */ - ret = compare_string_tag_item(a->tag, b->tag, TAG_ALBUM); - if (ret != 0) - return ret; - - /* then sort by disc */ - ret = compare_tag_item(a->tag, b->tag, TAG_DISC); - if (ret != 0) - return ret; - - /* then by track number */ - ret = compare_tag_item(a->tag, b->tag, TAG_TRACK); - if (ret != 0) - return ret; - - /* still no difference? compare file name */ - return g_utf8_collate(a->uri, b->uri); -} - -static size_t sv_size(const struct songvec *sv) -{ - return sv->nr * sizeof(struct song *); -} - -void songvec_sort(struct songvec *sv) -{ - db_lock(); - qsort(sv->base, sv->nr, sizeof(struct song *), songvec_cmp); - db_unlock(); -} - -struct song * -songvec_find(const struct songvec *sv, const char *uri) -{ - int i; - struct song *ret = NULL; - - db_lock(); - for (i = sv->nr; --i >= 0; ) { - if (strcmp(sv->base[i]->uri, uri)) - continue; - ret = sv->base[i]; - break; - } - db_unlock(); - return ret; -} - -/** - * Determine the index of the specified #song inside the #songvec, and - * returns the index. The caller must hold the db_mutex. - */ -G_GNUC_PURE -static size_t -songvec_find_pointer(const struct songvec *sv, const struct song *song) -{ - for (size_t i = 0;; ++i) { - assert(i < sv->nr); /* the song must exist */ - - if (sv->base[i] == song) - return i; - } -} - -void -songvec_delete(struct songvec *sv, const struct song *del) -{ - db_lock(); - - const size_t i = songvec_find_pointer(sv, del); - - /* we _don't_ call song_free() here */ - if (!--sv->nr) { - g_free(sv->base); - sv->base = NULL; - } else { - memmove(&sv->base[i], &sv->base[i + 1], - (sv->nr - i) * sizeof(struct song *)); - sv->base = g_realloc(sv->base, sv_size(sv)); - } - - db_unlock(); -} - -void -songvec_add(struct songvec *sv, struct song *add) -{ - db_lock(); - ++sv->nr; - sv->base = g_realloc(sv->base, sv_size(sv)); - sv->base[sv->nr - 1] = add; - db_unlock(); -} - -void songvec_destroy(struct songvec *sv) -{ - db_lock(); - sv->nr = 0; - db_unlock(); - - g_free(sv->base); - sv->base = NULL; -} - -int -songvec_for_each(const struct songvec *sv, - int (*fn)(struct song *, void *), void *arg) -{ - size_t i; - size_t prev_nr; - - db_lock(); - for (i = 0; i < sv->nr; ) { - struct song *song = sv->base[i]; - - assert(song); - assert(*song->uri); - - prev_nr = sv->nr; - db_unlock(); /* fn() may block */ - if (fn(song, arg) < 0) - return -1; - db_lock(); /* sv->nr may change in fn() */ - if (prev_nr == sv->nr) - ++i; - } - db_unlock(); - - return 0; -} diff --git a/src/songvec.h b/src/songvec.h deleted file mode 100644 index e839b537b..000000000 --- a/src/songvec.h +++ /dev/null @@ -1,51 +0,0 @@ -/* - * Copyright (C) 2003-2011 The Music Player Daemon Project - * http://www.musicpd.org - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License along - * with this program; if not, write to the Free Software Foundation, Inc., - * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. - */ - -#ifndef MPD_SONGVEC_H -#define MPD_SONGVEC_H - -#include - -struct songvec { - struct song **base; - size_t nr; -}; - -void songvec_init(void); - -void songvec_deinit(void); - -void songvec_sort(struct songvec *sv); - -struct song * -songvec_find(const struct songvec *sv, const char *uri); - -void -songvec_delete(struct songvec *sv, const struct song *del); - -void -songvec_add(struct songvec *sv, struct song *add); - -void songvec_destroy(struct songvec *sv); - -int -songvec_for_each(const struct songvec *sv, - int (*fn)(struct song *, void *), void *arg); - -#endif /* SONGVEC_H */ diff --git a/src/update_walk.c b/src/update_walk.c index 728e5bb04..e5eedc025 100644 --- a/src/update_walk.c +++ b/src/update_walk.c @@ -92,6 +92,8 @@ directory_set_stat(struct directory *dir, const struct stat *st) static void delete_song(struct directory *dir, struct song *del) { + assert(del->parent == dir); + /* first, prevent traversers in main task from getting this */ directory_remove_song(dir, del); @@ -102,15 +104,6 @@ delete_song(struct directory *dir, struct song *del) song_free(del); } -static int -delete_each_song(struct song *song, G_GNUC_UNUSED void *data) -{ - struct directory *directory = data; - assert(song->parent == directory); - delete_song(directory, song); - return 0; -} - static void delete_directory(struct directory *directory); @@ -125,7 +118,11 @@ clear_directory(struct directory *directory) directory_for_each_child_safe(child, n, directory) delete_directory(child); - songvec_for_each(&directory->songs, delete_each_song, directory); + struct song *song, *ns; + directory_for_each_song_safe(song, ns, directory) { + assert(song->parent == directory); + delete_song(directory, song); + } } /** @@ -159,25 +156,6 @@ delete_name_in(struct directory *parent, const char *name) playlist_vector_remove(&parent->playlists, name); } -/* passed to songvec_for_each */ -static int -delete_song_if_excluded(struct song *song, void *_data) -{ - GSList *exclude_list = _data; - char *name_fs; - - assert(song->parent != NULL); - - name_fs = utf8_to_fs_charset(song->uri); - if (exclude_list_check(exclude_list, name_fs)) { - delete_song(song->parent, song); - modified = true; - } - - g_free(name_fs); - return 0; -} - static void remove_excluded_from_directory(struct directory *directory, GSList *exclude_list) @@ -194,26 +172,18 @@ remove_excluded_from_directory(struct directory *directory, g_free(name_fs); } - songvec_for_each(&directory->songs, - delete_song_if_excluded, exclude_list); -} + struct song *song, *ns; + directory_for_each_song_safe(song, ns, directory) { + assert(song->parent == directory); -/* passed to songvec_for_each */ -static int -delete_song_if_removed(struct song *song, void *_data) -{ - struct directory *dir = _data; - char *path; - struct stat st; + char *name_fs = utf8_to_fs_charset(song->uri); + if (exclude_list_check(exclude_list, name_fs)) { + delete_song(directory, song); + modified = true; + } - if ((path = map_song_fs(song)) == NULL || - stat(path, &st) < 0 || !S_ISREG(st.st_mode)) { - delete_song(dir, song); - modified = true; + g_free(name_fs); } - - g_free(path); - return 0; } static bool @@ -266,7 +236,18 @@ removeDeletedFromDirectory(struct directory *directory) modified = true; } - songvec_for_each(&directory->songs, delete_song_if_removed, directory); + struct song *song, *ns; + directory_for_each_song_safe(song, ns, directory) { + char *path; + struct stat st; + if ((path = map_song_fs(song)) == NULL || + stat(path, &st) < 0 || !S_ISREG(st.st_mode)) { + delete_song(directory, song); + modified = true; + } + + g_free(path); + } for (const struct playlist_metadata *pm = directory->playlists.head; pm != NULL;) { -- cgit v1.2.3