sset: New data type for a set of strings.

Many uses of "shash" or "svec" data structures really call for a "set of
strings" data type.  This commit introduces such a data structure.  Later
commits convert inappropriate uses of shash and svec to use sset instead.

diff --git a/lib/automake.mk b/lib/automake.mk
index 78a45ea..60d030e 100644 (file)
--- a/lib/automake.mk
+++ b/lib/automake.mk
@@ -126,6 +126,8 @@ lib_libopenvswitch_a_SOURCES = \
        lib/socket-util.h \
        lib/sort.c \
        lib/sort.h \
+       lib/sset.c \
+       lib/sset.h \
        lib/stream-fd.c \
        lib/stream-fd.h \
        lib/stream-provider.h \

diff --git a/lib/sset.c b/lib/sset.c
new file mode 100644 (file)
index 0000000..9a0936b
--- /dev/null
+++ b/lib/sset.c
@@ -0,0 +1,253 @@
+/*
+ * Copyright (c) 2011 Nicira Networks.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <config.h>
+
+#include "sset.h"
+
+#include <assert.h>
+
+#include "hash.h"
+
+static uint32_t
+hash_name__(const char *name, size_t length)
+{
+    return hash_bytes(name, length, 0);
+}
+
+static uint32_t
+hash_name(const char *name)
+{
+    return hash_name__(name, strlen(name));
+}
+
+static struct sset_node *
+sset_find__(const struct sset *set, const char *name, size_t hash)
+{
+    struct sset_node *node;
+
+    HMAP_FOR_EACH_WITH_HASH (node, hmap_node, hash, &set->map) {
+        if (!strcmp(node->name, name)) {
+            return node;
+        }
+    }
+    return NULL;
+}
+
+static struct sset_node *
+sset_add__(struct sset *set, const char *name, size_t length, size_t hash)
+{
+    struct sset_node *node = xmalloc(length + sizeof *node);
+    memcpy(node->name, name, length + 1);
+    hmap_insert(&set->map, &node->hmap_node, hash);
+    return node;
+}
+
+/* Initializes 'set' as an empty set of strings. */
+void
+sset_init(struct sset *set)
+{
+    hmap_init(&set->map);
+}
+
+/* Destroys 'sets'. */
+void
+sset_destroy(struct sset *set)
+{
+    if (set) {
+        sset_clear(set);
+        hmap_destroy(&set->map);
+    }
+}
+
+/* Initializes 'set' to contain the same strings as 'orig'. */
+void
+sset_clone(struct sset *set, const struct sset *orig)
+{
+    struct sset_node *node;
+
+    sset_init(set);
+    HMAP_FOR_EACH (node, hmap_node, &orig->map) {
+        sset_add__(set, node->name, strlen(node->name),
+                   node->hmap_node.hash);
+    }
+}
+
+/* Exchanges the contents of 'a' and 'b'. */
+void
+sset_swap(struct sset *a, struct sset *b)
+{
+    hmap_swap(&a->map, &b->map);
+}
+
+/* Adjusts 'set' so that it is still valid after it has been moved around in
+ * memory (e.g. due to realloc()). */
+void
+sset_moved(struct sset *set)
+{
+    hmap_moved(&set->map);
+}
+
+/* Returns true if 'set' contains no strings, false if it contains at least one
+ * string. */
+bool
+sset_is_empty(const struct sset *set)
+{
+    return hmap_is_empty(&set->map);
+}
+
+/* Returns the number of strings in 'set'. */
+size_t
+sset_count(const struct sset *set)
+{
+    return hmap_count(&set->map);
+}
+
+/* Adds 'name' to 'set'.  If 'name' is new, returns the new sset_node;
+ * otherwise (if a copy of 'name' already existed in 'set'), returns NULL. */
+struct sset_node *
+sset_add(struct sset *set, const char *name)
+{
+    size_t length = strlen(name);
+    uint32_t hash = hash_name__(name, length);
+
+    return (sset_find__(set, name, hash)
+            ? NULL
+            : sset_add__(set, name, length, hash));
+}
+
+/* Adds a copy of 'name' to 'set' and frees 'name'.
+ *
+ * If 'name' is new, returns the new sset_node; otherwise (if a copy of 'name'
+ * already existed in 'set'), returns NULL. */
+struct sset_node *
+sset_add_and_free(struct sset *set, char *name)
+{
+    struct sset_node *node = sset_add(set, name);
+    free(name);
+    return node;
+}
+
+/* Adds 'name' to 'set'.  Assert-fails if a copy of 'name' was already in
+ * 'set'. */
+void
+sset_add_assert(struct sset *set, const char *name)
+{
+    bool added OVS_UNUSED = sset_add(set, name);
+    assert(added);
+}
+
+/* Adds a copy of each of the 'n' names in 'names' to 'set'. */
+void
+sset_add_array(struct sset *set, char **names, size_t n)
+{
+    size_t i;
+
+    for (i = 0; i < n; i++) {
+        sset_add(set, names[i]);
+    }
+}
+
+/* Removes all of the strings from 'set'. */
+void
+sset_clear(struct sset *set)
+{
+    const char *name, *next;
+
+    SSET_FOR_EACH_SAFE (name, next, set) {
+        sset_delete(set, SSET_NODE_FROM_NAME(name));
+    }
+}
+
+/* Deletes 'node' from 'set' and frees 'node'. */
+void
+sset_delete(struct sset *set, struct sset_node *node)
+{
+    hmap_remove(&set->map, &node->hmap_node);
+    free(node);
+}
+
+/* Searches for 'name' in 'set'.  If found, deletes it and returns true.  If
+ * not found, returns false without modifying 'set'. */
+bool
+sset_find_and_delete(struct sset *set, const char *name)
+{
+    struct sset_node *node = sset_find(set, name);
+    if (node) {
+        sset_delete(set, node);
+    }
+    return node != NULL;
+}
+
+/* Searches for 'name' in 'set' and deletes it.  Assert-fails if 'name' is not
+ * in 'set'. */
+void
+sset_find_and_delete_assert(struct sset *set, const char *name)
+{
+    bool deleted OVS_UNUSED = sset_find_and_delete(set, name);
+    assert(deleted);
+}
+
+/* Removes a string from 'set' and returns a copy of it.  The caller must free
+ * the returned string (with free()).
+ *
+ * 'set' must not be empty.
+ *
+ * This is not a very good way to iterate through an sset: it copies each name
+ * and it takes O(n**2) time to remove all the names.  Use SSET_FOR_EACH_SAFE
+ * instead, if you can. */
+char *
+sset_pop(struct sset *set)
+{
+    const char *name = SSET_FIRST(set);
+    char *copy = xstrdup(name);
+    sset_delete(set, SSET_NODE_FROM_NAME(name));
+    return copy;
+}
+
+/* Searches for 'name' in 'set'.  Returns its node, if found, otherwise a null
+ * pointer. */
+struct sset_node *
+sset_find(const struct sset *set, const char *name)
+{
+    return sset_find__(set, name, hash_name(name));
+}
+
+/* Returns true if 'set' contains a copy of 'name', false otherwise. */
+bool
+sset_contains(const struct sset *set, const char *name)
+{
+    return sset_find(set, name) != NULL;
+}
+
+/* Returns true if 'a' and 'b' contain the same strings, false otherwise. */
+bool
+sset_equals(const struct sset *a, const struct sset *b)
+{
+    struct sset_node *node;
+
+    if (sset_count(a) != sset_count(b)) {
+        return false;
+    }
+
+    HMAP_FOR_EACH (node, hmap_node, &a->map) {
+        if (!sset_find__(b, node->name, node->hmap_node.hash)) {
+            return false;
+        }
+    }
+
+    return true;
+}

diff --git a/lib/sset.h b/lib/sset.h
new file mode 100644 (file)
index 0000000..8810067
--- /dev/null
+++ b/lib/sset.h
@@ -0,0 +1,88 @@
+/*
+ * Copyright (c) 2011 Nicira Networks.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef SSET_H
+#define SSET_H
+
+#include "hmap.h"
+
+struct sset_node {
+    struct hmap_node hmap_node;
+    char name[1];
+};
+
+/* A set of strings. */
+struct sset {
+    struct hmap map;
+};
+
+#define SSET_INITIALIZER(SSET) { HMAP_INITIALIZER(&(SSET)->map) }
+
+/* Basics. */
+void sset_init(struct sset *);
+void sset_destroy(struct sset *);
+void sset_clone(struct sset *, const struct sset *);
+void sset_swap(struct sset *, struct sset *);
+void sset_moved(struct sset *);
+
+/* Count. */
+bool sset_is_empty(const struct sset *);
+size_t sset_count(const struct sset *);
+
+/* Insertion. */
+struct sset_node *sset_add(struct sset *, const char *);
+struct sset_node *sset_add_and_free(struct sset *, char *);
+void sset_add_assert(struct sset *, const char *);
+void sset_add_array(struct sset *, char **, size_t n);
+
+/* Deletion. */
+void sset_clear(struct sset *);
+void sset_delete(struct sset *, struct sset_node *);
+bool sset_find_and_delete(struct sset *, const char *);
+void sset_find_and_delete_assert(struct sset *, const char *);
+char *sset_pop(struct sset *);
+
+/* Search. */
+struct sset_node *sset_find(const struct sset *, const char *);
+bool sset_contains(const struct sset *, const char *);
+bool sset_equals(const struct sset *, const struct sset *);
+
+/* Iteration macros. */
+#define SSET_FOR_EACH(NAME, SSET)               \
+    for ((NAME) = SSET_FIRST(SSET);             \
+         SSET_NODE_FROM_NAME(NAME) != NULL;     \
+         (NAME) = SSET_NEXT(SSET, NAME))
+
+#define SSET_FOR_EACH_SAFE(NAME, NEXT, SSET)        \
+    for ((NAME) = SSET_FIRST(SSET);                 \
+         (SSET_NODE_FROM_NAME(NAME) != NULL         \
+          ? (NEXT) = SSET_NEXT(SSET, NAME), true    \
+          : false);                                 \
+         (NAME) = (NEXT))
+\f
+/* Implementation helper macros. */
+
+#define SSET_NODE_FROM_HMAP_NODE(HMAP_NODE) \
+    CONTAINER_OF(HMAP_NODE, struct sset_node, hmap_node)
+#define SSET_NAME_FROM_HMAP_NODE(HMAP_NODE) \
+    ((const char *) (SSET_NODE_FROM_HMAP_NODE(HMAP_NODE)->name))
+#define SSET_NODE_FROM_NAME(NAME) CONTAINER_OF(NAME, struct sset_node, name)
+#define SSET_FIRST(SSET) SSET_NAME_FROM_HMAP_NODE(hmap_first(&(SSET)->map))
+#define SSET_NEXT(SSET, NAME)                                           \
+    SSET_NAME_FROM_HMAP_NODE(                                           \
+        hmap_next(&(SSET)->map, &SSET_NODE_FROM_NAME(NAME)->hmap_node))
+
+#endif /* sset.h */