From d99f074eb73d5228528961a78c13419c2c4c26ae Mon Sep 17 00:00:00 2001 From: Max Kellermann Date: Tue, 24 Jan 2012 18:20:58 +0100 Subject: directory: replace dirvec with doubly linked list Random access is not needed, and a linked list is easier to manage: we don't need to (re-)allocate the pointer array. --- Makefile.am | 2 - src/db/simple_db_plugin.c | 8 +++- src/directory.c | 71 ++++++++++++++++++++--------- src/directory.h | 41 +++++++++++++---- src/directory_save.c | 7 +-- src/dirvec.c | 111 ---------------------------------------------- src/dirvec.h | 40 ----------------- src/update_walk.c | 26 ++++------- 8 files changed, 99 insertions(+), 207 deletions(-) delete mode 100644 src/dirvec.c delete mode 100644 src/dirvec.h diff --git a/Makefile.am b/Makefile.am index 546d0cdc8..1cec459f7 100644 --- a/Makefile.am +++ b/Makefile.am @@ -90,7 +90,6 @@ mpd_headers = \ src/inotify_source.h \ src/inotify_queue.h \ src/inotify_update.h \ - src/dirvec.h \ src/gcc.h \ src/decoder_list.h \ src/decoder_print.h \ @@ -257,7 +256,6 @@ src_mpd_SOURCES = \ src/db_visitor.h \ src/db_selection.h \ src/db/simple_db_plugin.c src/db/simple_db_plugin.h \ - src/dirvec.c \ src/exclude.c \ src/fd_util.c \ src/fifo_buffer.c src/fifo_buffer.h \ diff --git a/src/db/simple_db_plugin.c b/src/db/simple_db_plugin.c index 7b13d0a26..816f4503b 100644 --- a/src/db/simple_db_plugin.c +++ b/src/db/simple_db_plugin.c @@ -24,6 +24,7 @@ #include "db_selection.h" #include "db_visitor.h" #include "db_save.h" +#include "db_lock.h" #include "conf.h" #include "glib_compat.h" #include "directory.h" @@ -266,8 +267,11 @@ simple_db_visit(struct db *_db, const struct db_selection *selection, !visitor->directory(directory, ctx, error_r)) return false; - return directory_walk(directory, selection->recursive, - visitor, ctx, error_r); + db_lock(); + bool ret = directory_walk(directory, selection->recursive, + visitor, ctx, error_r); + db_unlock(); + return ret; } const struct db_plugin simple_db_plugin = { diff --git a/src/directory.c b/src/directory.c index e77eb69f2..0dbc23847 100644 --- a/src/directory.c +++ b/src/directory.c @@ -21,7 +21,9 @@ #include "directory.h" #include "song.h" #include "path.h" +#include "util/list_sort.h" #include "db_visitor.h" +#include "db_lock.h" #include @@ -40,6 +42,7 @@ directory_new(const char *path, struct directory *parent) directory = g_malloc0(sizeof(*directory) - sizeof(directory->path) + pathlen + 1); + INIT_LIST_HEAD(&directory->children); directory->parent = parent; memcpy(directory->path, path, pathlen + 1); @@ -56,10 +59,10 @@ directory_free(struct directory *directory) for (unsigned i = 0; i < directory->songs.nr; ++i) song_free(directory->songs.base[i]); - for (unsigned i = 0; i < directory->children.nr; ++i) - directory_free(directory->children.base[i]); + struct directory *child, *n; + directory_for_each_child_safe(child, n, directory) + directory_free(child); - dirvec_destroy(&directory->children); songvec_destroy(&directory->songs); g_free(directory); /* this resets last dir returned */ @@ -72,7 +75,10 @@ directory_delete(struct directory *directory) assert(directory != NULL); assert(directory->parent != NULL); - dirvec_delete(&directory->parent->children, directory); + db_lock(); + list_del(&directory->siblings); + db_unlock(); + directory_free(directory); } @@ -103,26 +109,39 @@ directory_new_child(struct directory *parent, const char *name_utf8) struct directory *directory = directory_new(path_utf8, parent); g_free(allocated); - dirvec_add(&parent->children, directory); + db_lock(); + list_add(&directory->siblings, &parent->children); + db_unlock(); return directory; } -void -directory_prune_empty(struct directory *directory) +struct directory * +directory_get_child(const struct directory *directory, const char *name) { - int i; - struct dirvec *dv = &directory->children; + db_lock(); - for (i = dv->nr; --i >= 0; ) { - struct directory *child = dv->base[i]; + struct directory *child; + directory_for_each_child(child, directory) { + if (strcmp(directory_get_name(child), name) == 0) { + db_unlock(); + return child; + } + } + + db_unlock(); + return NULL; +} +void +directory_prune_empty(struct directory *directory) +{ + struct directory *child, *n; + directory_for_each_child_safe(child, n, directory) { directory_prune_empty(child); if (directory_is_empty(child)) directory_delete(child); } - if (!dv->nr) - dirvec_destroy(dv); } struct directory * @@ -188,17 +207,27 @@ directory_lookup_song(struct directory *directory, const char *uri) } +static int +directory_cmp(G_GNUC_UNUSED void *priv, + struct list_head *_a, struct list_head *_b) +{ + const struct directory *a = (const struct directory *)_a; + const struct directory *b = (const struct directory *)_b; + return g_utf8_collate(a->path, b->path); +} + void directory_sort(struct directory *directory) { - int i; - struct dirvec *dv = &directory->children; + db_lock(); + list_sort(NULL, &directory->children, directory_cmp); + db_unlock(); - dirvec_sort(dv); songvec_sort(&directory->songs); - for (i = dv->nr; --i >= 0; ) - directory_sort(dv->base[i]); + struct directory *child; + directory_for_each_child(child, directory) + directory_sort(child); } bool @@ -225,10 +254,8 @@ directory_walk(const struct directory *directory, bool recursive, return false; } - const struct dirvec *dv = &directory->children; - for (size_t i = 0; i < dv->nr; ++i) { - struct directory *child = dv->base[i]; - + struct directory *child; + directory_for_each_child(child, directory) { if (visitor->directory != NULL && !visitor->directory(child, ctx, error_r)) return false; diff --git a/src/directory.h b/src/directory.h index 9f7698d09..b6e199555 100644 --- a/src/directory.h +++ b/src/directory.h @@ -21,7 +21,7 @@ #define MPD_DIRECTORY_H #include "check.h" -#include "dirvec.h" +#include "util/list.h" #include "songvec.h" #include "playlist_vector.h" @@ -34,10 +34,33 @@ #define DEVICE_INARCHIVE (dev_t)(-1) #define DEVICE_CONTAINER (dev_t)(-2) +#define directory_for_each_child(pos, directory) \ + list_for_each_entry(pos, &directory->children, siblings) + +#define directory_for_each_child_safe(pos, n, directory) \ + list_for_each_entry_safe(pos, n, &directory->children, siblings) + struct db_visitor; struct directory { - struct dirvec children; + /** + * Pointers to the siblings of this directory within the + * parent directory. It is unused (undefined) in the root + * directory. + * + * This attribute is protected with the global #db_mutex. + * Read access in the update thread does not need protection. + */ + struct list_head siblings; + + /** + * A doubly linked list of child directories. + * + * This attribute is protected with the global #db_mutex. + * Read access in the update thread does not need protection. + */ + struct list_head children; + struct songvec songs; struct playlist_vector playlists; @@ -90,7 +113,8 @@ directory_delete(struct directory *directory); static inline bool directory_is_empty(const struct directory *directory) { - return directory->children.nr == 0 && directory->songs.nr == 0 && + return list_empty(&directory->children) && + directory->songs.nr == 0 && playlist_vector_is_empty(&directory->playlists); } @@ -116,11 +140,9 @@ G_GNUC_PURE const char * directory_get_name(const struct directory *directory); -static inline struct directory * -directory_get_child(const struct directory *directory, const char *name) -{ - return dirvec_find(&directory->children, name); -} +G_GNUC_PURE +struct directory * +directory_get_child(const struct directory *directory, const char *name); /** * Create a new #directory object as a child of the given one. @@ -171,6 +193,9 @@ directory_lookup_song(struct directory *directory, const char *uri); void directory_sort(struct directory *directory); +/** + * Caller must lock #db_mutex. + */ bool directory_walk(const struct directory *directory, bool recursive, const struct db_visitor *visitor, void *ctx, diff --git a/src/directory_save.c b/src/directory_save.c index 975e2e745..087c99fe4 100644 --- a/src/directory_save.c +++ b/src/directory_save.c @@ -44,8 +44,6 @@ directory_quark(void) void directory_save(FILE *fp, const struct directory *directory) { - size_t i; - if (!directory_is_root(directory)) { fprintf(fp, DIRECTORY_MTIME "%lu\n", (unsigned long)directory->mtime); @@ -54,9 +52,8 @@ directory_save(FILE *fp, const struct directory *directory) directory_get_path(directory)); } - const struct dirvec *children = &directory->children; - for (i = 0; i < children->nr; ++i) { - const struct directory *cur = children->base[i]; + struct directory *cur; + directory_for_each_child(cur, directory) { char *base = g_path_get_basename(cur->path); fprintf(fp, DIRECTORY_DIR "%s\n", base); diff --git a/src/dirvec.c b/src/dirvec.c deleted file mode 100644 index acc573e13..000000000 --- a/src/dirvec.c +++ /dev/null @@ -1,111 +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 "dirvec.h" -#include "directory.h" -#include "db_lock.h" - -#include - -#include -#include -#include - -static size_t dv_size(const struct dirvec *dv) -{ - return dv->nr * sizeof(struct directory *); -} - -/* Only used for sorting/searching a dirvec, not general purpose compares */ -static int dirvec_cmp(const void *d1, const void *d2) -{ - const struct directory *a = ((const struct directory * const *)d1)[0]; - const struct directory *b = ((const struct directory * const *)d2)[0]; - return g_utf8_collate(a->path, b->path); -} - -void dirvec_sort(struct dirvec *dv) -{ - db_lock(); - qsort(dv->base, dv->nr, sizeof(struct directory *), dirvec_cmp); - db_unlock(); -} - -struct directory *dirvec_find(const struct dirvec *dv, const char *path) -{ - int i; - - db_lock(); - for (i = dv->nr; --i >= 0; ) - if (!strcmp(directory_get_name(dv->base[i]), path)) { - db_unlock(); - return dv->base[i]; - } - - db_unlock(); - - return NULL; -} - -int dirvec_delete(struct dirvec *dv, struct directory *del) -{ - size_t i; - - db_lock(); - for (i = 0; i < dv->nr; ++i) { - if (dv->base[i] != del) - continue; - /* we _don't_ call directory_free() here */ - if (!--dv->nr) { - db_unlock(); - g_free(dv->base); - dv->base = NULL; - return i; - } else { - memmove(&dv->base[i], &dv->base[i + 1], - (dv->nr - i) * sizeof(struct directory *)); - dv->base = g_realloc(dv->base, dv_size(dv)); - } - break; - } - db_unlock(); - - return i; -} - -void dirvec_add(struct dirvec *dv, struct directory *add) -{ - db_lock(); - ++dv->nr; - dv->base = g_realloc(dv->base, dv_size(dv)); - dv->base[dv->nr - 1] = add; - db_unlock(); -} - -void dirvec_destroy(struct dirvec *dv) -{ - db_lock(); - dv->nr = 0; - db_unlock(); - if (dv->base) { - g_free(dv->base); - dv->base = NULL; - } -} diff --git a/src/dirvec.h b/src/dirvec.h deleted file mode 100644 index 8d840f469..000000000 --- a/src/dirvec.h +++ /dev/null @@ -1,40 +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_DIRVEC_H -#define MPD_DIRVEC_H - -#include - -struct dirvec { - struct directory **base; - size_t nr; -}; - -void dirvec_sort(struct dirvec *dv); - -struct directory *dirvec_find(const struct dirvec *dv, const char *path); - -int dirvec_delete(struct dirvec *dv, struct directory *del); - -void dirvec_add(struct dirvec *dv, struct directory *add); - -void dirvec_destroy(struct dirvec *dv); - -#endif /* DIRVEC_H */ diff --git a/src/update_walk.c b/src/update_walk.c index 332f62bbb..1c0bb30b6 100644 --- a/src/update_walk.c +++ b/src/update_walk.c @@ -121,12 +121,9 @@ delete_directory(struct directory *directory); static void clear_directory(struct directory *directory) { - int i; - - for (i = directory->children.nr; --i >= 0;) - delete_directory(directory->children.base[i]); - - assert(directory->children.nr == 0); + struct directory *child, *n; + directory_for_each_child_safe(child, n, directory) + delete_directory(child); songvec_for_each(&directory->songs, delete_each_song, directory); } @@ -185,11 +182,8 @@ static void remove_excluded_from_directory(struct directory *directory, GSList *exclude_list) { - int i; - struct dirvec *dv = &directory->children; - - for (i = dv->nr; --i >= 0; ) { - struct directory *child = dv->base[i]; + struct directory *child, *n; + directory_for_each_child_safe(child, n, directory) { char *name_fs = utf8_to_fs_charset(directory_get_name(child)); if (exclude_list_check(exclude_list, name_fs)) { @@ -263,14 +257,12 @@ directory_child_is_regular(const struct directory *directory, static void removeDeletedFromDirectory(struct directory *directory) { - int i; - struct dirvec *dv = &directory->children; - - for (i = dv->nr; --i >= 0; ) { - if (directory_exists(dv->base[i])) + struct directory *child, *n; + directory_for_each_child_safe(child, n, directory) { + if (directory_exists(child)) continue; - delete_directory(dv->base[i]); + delete_directory(child); modified = true; } -- cgit v1.2.3