aboutsummaryrefslogtreecommitdiffstats
path: root/src/strset.c
diff options
context:
space:
mode:
authorMax Kellermann <max@duempel.org>2008-09-08 11:46:04 +0200
committerMax Kellermann <max@duempel.org>2008-09-08 11:46:04 +0200
commit2b8040b42524dad68ea85c45a4be25909a03eb5c (patch)
treef14c109213bc54e0623362fd02951c7cb5b18a46 /src/strset.c
parent3f6fe915ebff003b907bc0c70502d21691b50095 (diff)
downloadmpd-2b8040b42524dad68ea85c45a4be25909a03eb5c.tar.gz
mpd-2b8040b42524dad68ea85c45a4be25909a03eb5c.tar.xz
mpd-2b8040b42524dad68ea85c45a4be25909a03eb5c.zip
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.
Diffstat (limited to 'src/strset.c')
-rw-r--r--src/strset.c144
1 files changed, 144 insertions, 0 deletions
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;
+}
+