diff options
| -rw-r--r-- | src/Makefile.am | 2 | ||||
| -rw-r--r-- | src/strset.c | 144 | ||||
| -rw-r--r-- | src/strset.h | 49 |
3 files changed, 195 insertions, 0 deletions
diff --git a/src/Makefile.am b/src/Makefile.am index 30408288c..5a5439bfc 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -92,6 +92,7 @@ mpd_headers = \ tag_save.h \ tagTracker.h \ utf8.h \ + strset.h \ utils.h \ volume.h \ ioops.h \ @@ -158,6 +159,7 @@ mpd_SOURCES = \ tag_print.c \ tag_save.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 <max@duempel.org> + * 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 <max@duempel.org> + * 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 |