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/strset.c | 144 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 144 insertions(+) create mode 100644 src/strset.c (limited to 'src/strset.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; +} + -- 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(-) (limited to 'src/strset.c') 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