aboutsummaryrefslogtreecommitdiffstats
path: root/src
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
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 '')
-rw-r--r--src/Makefile.am2
-rw-r--r--src/strset.c144
-rw-r--r--src/strset.h49
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