From 890be9ba54716ba765326228f7b34c0d1902e02b Mon Sep 17 00:00:00 2001 From: Max Kellermann Date: Mon, 8 Sep 2008 11:46:04 +0200 Subject: added string set library "struct strset" is a hashed string set: you can add strings to this library, and it stores them as a set of unique strings. You can get the size of the set, and you can enumerate through all values. This will be used to replace the linear tagTracker library. --- src/Makefile.am | 2 + src/strset.c | 144 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/strset.h | 49 +++++++++++++++++++ 3 files changed, 195 insertions(+) create mode 100644 src/strset.c create mode 100644 src/strset.h diff --git a/src/Makefile.am b/src/Makefile.am index d8640d304..fcb313418 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -85,6 +85,7 @@ mpd_headers = \ tag_id3.h \ tagTracker.h \ utf8.h \ + strset.h \ utils.h \ volume.h \ ioops.h \ @@ -142,6 +143,7 @@ mpd_SOURCES = \ tag_pool.c \ tag_id3.c \ tagTracker.c \ + strset.c \ utils.c \ volume.c \ utf8.c \ diff --git a/src/strset.c b/src/strset.c new file mode 100644 index 000000000..6bf61a4b2 --- /dev/null +++ b/src/strset.c @@ -0,0 +1,144 @@ +/* the Music Player Daemon (MPD) + * Copyright (C) 2008 Max Kellermann + * This project's homepage is: 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#include "strset.h" +#include "utils.h" +#include "os_compat.h" + +#define NUM_SLOTS 16384 + +struct strset_slot { + struct strset_slot *next; + const char *value; +}; + +struct strset { + unsigned size; + + struct strset_slot *current_slot; + unsigned next_slot; + + struct strset_slot slots[NUM_SLOTS]; +}; + +static unsigned calc_hash(const char *p) { + unsigned hash = 5381; + + assert(p != NULL); + + while (*p != 0) + hash = (hash << 5) + hash + *p++; + + return hash; +} + +mpd_malloc struct strset *strset_new(void) +{ + struct strset *set = xcalloc(1, sizeof(*set)); + return set; +} + +void strset_free(struct strset *set) +{ + unsigned i; + + for (i = 0; i < NUM_SLOTS; ++i) { + struct strset_slot *slot = set->slots[i].next, *next; + + while (slot != NULL) { + next = slot->next; + free(slot); + slot = next; + } + } + + free(set); +} + +void strset_add(struct strset *set, const char *value) +{ + struct strset_slot *base_slot + = &set->slots[calc_hash(value) % NUM_SLOTS]; + struct strset_slot *slot = base_slot; + + if (base_slot->value == NULL) { + /* empty slot - put into base_slot */ + assert(base_slot->next == NULL); + + base_slot->value = value; + ++set->size; + return; + } + + for (slot = base_slot->next; slot != NULL; slot = slot->next) + if (strcmp(slot->value, value) == 0) + /* found it - do nothing */ + return; + + /* insert it into the slot chain */ + slot = xmalloc(sizeof(*slot)); + slot->next = base_slot->next; + slot->value = value; + base_slot->next = slot; + ++set->size; +} + +int strset_get(const struct strset *set, const char *value) +{ + const struct strset_slot *slot = &set->slots[calc_hash(value)]; + + if (slot->value == NULL) + return 0; + + for (slot = slot->next; slot != NULL; slot = slot->next) + if (strcmp(slot->value, value) == 0) + /* found it - do nothing */ + return 1; + + return 0; +} + +unsigned strset_size(const struct strset *set) +{ + return set->size; +} + +void strset_rewind(struct strset *set) +{ + set->current_slot = NULL; + set->next_slot = 0; +} + +const char *strset_next(struct strset *set) +{ + if (set->current_slot != NULL && set->current_slot->next != NULL) { + set->current_slot = set->current_slot->next; + return set->current_slot->value; + } + + while (set->next_slot < NUM_SLOTS && + set->slots[set->next_slot].value == NULL) + ++set->next_slot; + + if (set->next_slot >= NUM_SLOTS) + return NULL; + + set->current_slot = &set->slots[set->next_slot++]; + return set->current_slot->value; +} + diff --git a/src/strset.h b/src/strset.h new file mode 100644 index 000000000..41ef0e1bd --- /dev/null +++ b/src/strset.h @@ -0,0 +1,49 @@ +/* the Music Player Daemon (MPD) + * Copyright (C) 2008 Max Kellermann + * This project's homepage is: 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +/** + * "struct strset" is a hashed string set: you can add strings to this + * library, and it stores them as a set of unique strings. You can + * get the size of the set, and you can enumerate through all values. + * + * It is important to note that the strset does not copy the string + * values - it stores the exact pointers it was given in strset_add(). + */ + +#ifndef STRSET_H +#define STRSET_H + +#include "gcc.h" + +struct strset; + +mpd_malloc struct strset *strset_new(void); + +void strset_free(struct strset *set); + +void strset_add(struct strset *set, const char *value); + +int strset_get(const struct strset *set, const char *value); + +unsigned strset_size(const struct strset *set); + +void strset_rewind(struct strset *set); + +const char *strset_next(struct strset *set); + +#endif -- cgit v1.2.3 From 65c88720fbc08bb9ca2cb37ffa75fd842ff3f1d1 Mon Sep 17 00:00:00 2001 From: Max Kellermann Date: Mon, 8 Sep 2008 12:07:08 +0200 Subject: strset: fix duplicate values Due to a minor typo, the string set had duplicate values, because strset_add() didn't check the base slot properly. --- src/strset.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/src/strset.c b/src/strset.c index 6bf61a4b2..475266370 100644 --- a/src/strset.c +++ b/src/strset.c @@ -85,7 +85,7 @@ void strset_add(struct strset *set, const char *value) return; } - for (slot = base_slot->next; slot != NULL; slot = slot->next) + for (slot = base_slot; slot != NULL; slot = slot->next) if (strcmp(slot->value, value) == 0) /* found it - do nothing */ return; -- cgit v1.2.3 From 09dccb79f611110a5a653030c7c21958eda95a03 Mon Sep 17 00:00:00 2001 From: Max Kellermann Date: Mon, 8 Sep 2008 11:47:57 +0200 Subject: use strset.h instead of tagTracker.h With a large music database, the linear string collection in tagTracker.c becomes very slow. We implemented that in a quick'n'dirty fashion when we removed tree.c, and now we rewrite it using the fast hashed string set. --- src/Makefile.am | 2 - src/dbUtils.c | 38 +++++++++++++----- src/stats.c | 65 +++++++++++++++++++++++++----- src/tag.c | 1 - src/tagTracker.c | 119 ------------------------------------------------------- src/tagTracker.h | 32 --------------- 6 files changed, 84 insertions(+), 173 deletions(-) delete mode 100644 src/tagTracker.c delete mode 100644 src/tagTracker.h diff --git a/src/Makefile.am b/src/Makefile.am index fcb313418..0592d8e72 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -83,7 +83,6 @@ mpd_headers = \ tag.h \ tag_pool.h \ tag_id3.h \ - tagTracker.h \ utf8.h \ strset.h \ utils.h \ @@ -142,7 +141,6 @@ mpd_SOURCES = \ tag.c \ tag_pool.c \ tag_id3.c \ - tagTracker.c \ strset.c \ utils.c \ volume.c \ diff --git a/src/dbUtils.c b/src/dbUtils.c index d39c9908c..00fa1d441 100644 --- a/src/dbUtils.c +++ b/src/dbUtils.c @@ -24,7 +24,7 @@ #include "playlist.h" #include "song.h" #include "tag.h" -#include "tagTracker.h" +#include "strset.h" #include "log.h" #include "storedPlaylist.h" @@ -254,7 +254,8 @@ static void freeListCommandItem(ListCommandItem * item) free(item); } -static void visitTag(int fd, Song * song, enum tag_type tagType) +static void visitTag(int fd, struct strset *set, + Song * song, enum tag_type tagType) { int i; struct mpd_tag *tag = song->tag; @@ -269,18 +270,25 @@ static void visitTag(int fd, Song * song, enum tag_type tagType) for (i = 0; i < tag->numOfItems; i++) { if (tag->items[i]->type == tagType) { - visitInTagTracker(tagType, tag->items[i]->value); + strset_add(set, tag->items[i]->value); } } } -static int listUniqueTagsInDirectory(int fd, Song * song, void *data) +struct list_tags_data { + int fd; + ListCommandItem *item; + struct strset *set; +}; + +static int listUniqueTagsInDirectory(int fd, Song * song, void *_data) { - ListCommandItem *item = data; + struct list_tags_data *data = _data; + ListCommandItem *item = data->item; if (tagItemsFoundAndMatches(song, item->numConditionals, item->conditionals)) { - visitTag(fd, song, item->tagType); + visitTag(fd, data->set, song, item->tagType); } return 0; @@ -290,18 +298,28 @@ int listAllUniqueTags(int fd, int type, int numConditionals, LocateTagItem * conditionals) { int ret; + struct list_tags_data data; ListCommandItem *item = newListCommandItem(type, numConditionals, conditionals); + data.fd = fd; + data.item = item; + if (type >= 0 && type <= TAG_NUM_OF_ITEM_TYPES) { - resetVisitedFlagsInTagTracker(type); + data.set = strset_new(); } - ret = traverseAllIn(fd, NULL, listUniqueTagsInDirectory, NULL, - (void *)item); + ret = traverseAllIn(fd, NULL, listUniqueTagsInDirectory, NULL, &data); if (type >= 0 && type <= TAG_NUM_OF_ITEM_TYPES) { - printVisitedInTagTracker(fd, type); + const char *value; + + strset_rewind(data.set); + + while ((value = strset_next(data.set)) != NULL) + fdprintf(fd, "%s: %s\n", mpdTagItemKeys[type], value); + + strset_free(data.set); } freeListCommandItem(item); diff --git a/src/stats.c b/src/stats.c index 39ba39e9a..c576d2870 100644 --- a/src/stats.c +++ b/src/stats.c @@ -1,5 +1,6 @@ /* the Music Player Daemon (MPD) * Copyright (C) 2003-2007 by Warren Dukes (warren.dukes@gmail.com) + * Copyright (C) 2008 Max Kellermann * This project's homepage is: http://www.musicpd.org * * This program is free software; you can redistribute it and/or modify @@ -21,8 +22,10 @@ #include "directory.h" #include "myfprintf.h" #include "outputBuffer.h" -#include "tagTracker.h" +#include "tag.h" +#include "strset.h" #include "os_compat.h" +#include "gcc.h" Stats stats; @@ -32,15 +35,59 @@ void initStats(void) stats.numberOfSongs = 0; } +struct visit_data { + enum tag_type type; + struct strset *set; +}; + +static int visit_tag_items(mpd_unused int fd, Song *song, void *_data) +{ + const struct visit_data *data = _data; + unsigned i; + + if (song->tag == NULL) + return 0; + + for (i = 0; i < (unsigned)song->tag->numOfItems; ++i) { + const struct tag_item *item = song->tag->items[i]; + if (item->type == data->type) + strset_add(data->set, item->value); + } + + return 0; +} + +static unsigned int getNumberOfTagItems(int type) +{ + struct visit_data data; + unsigned int ret; + + data.type = type; + data.set = strset_new(); + + traverseAllIn(STDERR_FILENO, NULL, visit_tag_items, NULL, &data); + + ret = strset_size(data.set); + strset_free(data.set); + return ret; +} + int printStats(int fd) { - fdprintf(fd, "artists: %i\n", getNumberOfTagItems(TAG_ITEM_ARTIST)); - fdprintf(fd, "albums: %i\n", getNumberOfTagItems(TAG_ITEM_ALBUM)); - fdprintf(fd, "songs: %i\n", stats.numberOfSongs); - fdprintf(fd, "uptime: %li\n", time(NULL) - stats.daemonStart); - fdprintf(fd, "playtime: %li\n", - (long)(ob_get_total_time() + 0.5)); - fdprintf(fd, "db_playtime: %li\n", stats.dbPlayTime); - fdprintf(fd, "db_update: %li\n", getDbModTime()); + fdprintf(fd, + "artists: %u\n" + "albums: %u\n" + "songs: %i\n" + "uptime: %li\n" + "playtime: %li\n" + "db_playtime: %li\n" + "db_update: %li\n", + getNumberOfTagItems(TAG_ITEM_ARTIST), + getNumberOfTagItems(TAG_ITEM_ALBUM), + stats.numberOfSongs, + time(NULL) - stats.daemonStart, + (long)(ob_get_total_time() + 0.5), + stats.dbPlayTime, + getDbModTime()); return 0; } diff --git a/src/tag.c b/src/tag.c index e5c306eb4..f1acb7c79 100644 --- a/src/tag.c +++ b/src/tag.c @@ -23,7 +23,6 @@ #include "utf8.h" #include "log.h" #include "conf.h" -#include "tagTracker.h" #include "song.h" /** diff --git a/src/tagTracker.c b/src/tagTracker.c deleted file mode 100644 index bea58ae4c..000000000 --- a/src/tagTracker.c +++ /dev/null @@ -1,119 +0,0 @@ -/* the Music Player Daemon (MPD) - * Copyright (C) 2003-2007 by Warren Dukes (warren.dukes@gmail.com) - * This project's homepage is: 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA - */ - -#include "tagTracker.h" - -#include "tag.h" -#include "utils.h" -#include "myfprintf.h" -#include "os_compat.h" -#include "directory.h" - -struct visited { - struct visited *next; - - /** - * this is the original pointer passed to visitInTagTracker(), - * i.e. the caller must not invalidate it until he calls - * resetVisitedFlagsInTagTracker(). - */ - const char *value; -} mpd_packed; - -static struct visited *visited_heads[TAG_NUM_OF_ITEM_TYPES]; -static unsigned num_visited[TAG_NUM_OF_ITEM_TYPES]; - -static int visit_tag_items(int fd mpd_unused, Song *song, void *data) -{ - enum tag_type type = (enum tag_type)(size_t)data; - unsigned i; - - if (song->tag == NULL) - return 0; - - for (i = 0; i < (unsigned)song->tag->numOfItems; ++i) { - const struct tag_item *item = song->tag->items[i]; - if (item->type == type) - visitInTagTracker(type, item->value); - } - - return 0; -} - -int getNumberOfTagItems(int type) -{ - int ret; - - resetVisitedFlagsInTagTracker(type); - - traverseAllIn(-1, NULL, visit_tag_items, NULL, (void*)(size_t)type); - - ret = (int)num_visited[type]; - resetVisitedFlagsInTagTracker(type); - return ret; -} - -void resetVisitedFlagsInTagTracker(int type) -{ - while (visited_heads[type] != NULL) { - struct visited *v = visited_heads[type]; - visited_heads[type] = v->next; - free(v); - } - - num_visited[type] = 0; -} - -static struct visited * -find_visit(int type, const char *p) -{ - struct visited *v; - - for (v = visited_heads[type]; v != NULL; v = v->next) - if (strcmp(v->value, p) == 0) - return v; - - return NULL; -} - -void visitInTagTracker(int type, const char *str) -{ - struct visited *v = find_visit(type, str); - size_t length; - - if (v != NULL) - return; - - length = strlen(str); - v = xmalloc(sizeof(*v)); - v->value = str; - v->next = visited_heads[type]; - visited_heads[type] = v; - ++num_visited[type]; -} - -void printVisitedInTagTracker(int fd, int type) -{ - struct visited *v; - - for (v = visited_heads[type]; v != NULL; v = v->next) - fdprintf(fd, - "%s: %s\n", - mpdTagItemKeys[type], - v->value); -} diff --git a/src/tagTracker.h b/src/tagTracker.h deleted file mode 100644 index 2edb5aad0..000000000 --- a/src/tagTracker.h +++ /dev/null @@ -1,32 +0,0 @@ -/* the Music Player Daemon (MPD) - * Copyright (C) 2003-2007 by Warren Dukes (warren.dukes@gmail.com) - * This project's homepage is: 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA - */ - -#ifndef TAG_TRACKER_H -#define TAG_TRACKER_H - -int getNumberOfTagItems(int type); - -void printMemorySavedByTagTracker(void); - -void resetVisitedFlagsInTagTracker(int type); - -void visitInTagTracker(int type, const char *str); - -void printVisitedInTagTracker(int fd, int type); - -#endif -- cgit v1.2.3