simap: New data structure for string-to-integer maps.
authorBen Pfaff <blp@nicira.com>
Tue, 22 May 2012 17:32:02 +0000 (10:32 -0700)
committerBen Pfaff <blp@nicira.com>
Tue, 22 May 2012 17:32:02 +0000 (10:32 -0700)
This commit adapts a couple of existing pieces of code to use the
new data structure.  The following commit will add another user
(which is also the first use of the simap_increas() function).

Signed-off-by: Ben Pfaff <blp@nicira.com>
lib/automake.mk
lib/learning-switch.c
lib/learning-switch.h
lib/odp-util.c
lib/odp-util.h
lib/simap.c [new file with mode: 0644]
lib/simap.h [new file with mode: 0644]
utilities/ovs-controller.c
utilities/ovs-dpctl.c

index 52e112bc165000ce1631fe0e7d02023fa2ea898d..338d39cdf7cf304d986defa28ace999144c78358 100644 (file)
@@ -135,6 +135,8 @@ lib_libopenvswitch_a_SOURCES = \
        lib/sha1.h \
        lib/shash.c \
        lib/shash.h \
+       lib/simap.c \
+       lib/simap.h \
        lib/signals.c \
        lib/signals.h \
        lib/socket-util.c \
index 4e7cedaf7e581466b418561ae94101b94a25094e..595b7f0229b6836ad782fb05cfb0e28efbdd76f9 100644 (file)
@@ -37,6 +37,7 @@
 #include "poll-loop.h"
 #include "rconn.h"
 #include "shash.h"
+#include "simap.h"
 #include "timeval.h"
 #include "vconn.h"
 #include "vlog.h"
@@ -125,12 +126,12 @@ lswitch_create(struct rconn *rconn, const struct lswitch_config *cfg)
     hmap_init(&sw->queue_numbers);
     shash_init(&sw->queue_names);
     if (cfg->port_queues) {
-        struct shash_node *node;
+        struct simap_node *node;
 
-        SHASH_FOR_EACH (node, cfg->port_queues) {
+        SIMAP_FOR_EACH (node, cfg->port_queues) {
             struct lswitch_port *port = xmalloc(sizeof *port);
             hmap_node_nullify(&port->hmap_node);
-            port->queue_id = (uintptr_t) node->data;
+            port->queue_id = node->data;
             shash_add(&sw->queue_names, node->name, port);
         }
     }
index e42aec16a47af9314e060cbbfaa886a649df2ddb..c3c37f2966fff6ff428f9347d2610fc4f8d49509 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2008, 2010, 2011 Nicira, Inc.
+ * Copyright (c) 2008, 2010, 2011, 2012 Nicira, Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -55,8 +55,8 @@ struct lswitch_config {
      * specifying a particular queue. */
     uint32_t default_queue;
 
-    /* Maps from a port name to a queue_id (cast to void *). */
-    const struct shash *port_queues;
+    /* Maps from a port name to a queue_id. */
+    const struct simap *port_queues;
 };
 
 struct lswitch *lswitch_create(struct rconn *, const struct lswitch_config *);
index ce4563536e56c8c32d3d96f1cd6c6e7e512f5144..13cdf8e58d5c07c3067d38f5082e6ecef2f7ac26 100644 (file)
@@ -32,7 +32,7 @@
 #include "ofpbuf.h"
 #include "openvswitch/tunnel.h"
 #include "packets.h"
-#include "shash.h"
+#include "simap.h"
 #include "timeval.h"
 #include "util.h"
 #include "vlog.h"
@@ -49,7 +49,7 @@ VLOG_DEFINE_THIS_MODULE(odp_util);
  * from another. */
 static const char *delimiters = ", \t\r\n";
 
-static int parse_odp_key_attr(const char *, const struct shash *port_names,
+static int parse_odp_key_attr(const char *, const struct simap *port_names,
                               struct ofpbuf *);
 static void format_odp_key_attr(const struct nlattr *a, struct ds *ds);
 
@@ -355,7 +355,7 @@ format_odp_actions(struct ds *ds, const struct nlattr *actions,
 }
 
 static int
-parse_odp_action(const char *s, const struct shash *port_names,
+parse_odp_action(const char *s, const struct simap *port_names,
                  struct ofpbuf *actions)
 {
     /* Many of the sscanf calls in this function use oversized destination
@@ -380,12 +380,11 @@ parse_odp_action(const char *s, const struct shash *port_names,
 
     if (port_names) {
         int len = strcspn(s, delimiters);
-        struct shash_node *node;
+        struct simap_node *node;
 
-        node = shash_find_len(port_names, s, len);
+        node = simap_find_len(port_names, s, len);
         if (node) {
-            nl_msg_put_u32(actions, OVS_ACTION_ATTR_OUTPUT,
-                           (uintptr_t) node->data);
+            nl_msg_put_u32(actions, OVS_ACTION_ATTR_OUTPUT, node->data);
             return len;
         }
     }
@@ -561,7 +560,7 @@ parse_odp_action(const char *s, const struct shash *port_names,
  * Netlink attributes.  On failure, no data is appended to 'actions'.  Either
  * way, 'actions''s data might be reallocated. */
 int
-odp_actions_from_string(const char *s, const struct shash *port_names,
+odp_actions_from_string(const char *s, const struct simap *port_names,
                         struct ofpbuf *actions)
 {
     size_t old_size;
@@ -878,7 +877,7 @@ ovs_frag_type_from_string(const char *s, enum ovs_frag_type *type)
 }
 
 static int
-parse_odp_key_attr(const char *s, const struct shash *port_names,
+parse_odp_key_attr(const char *s, const struct simap *port_names,
                    struct ofpbuf *key)
 {
     /* Many of the sscanf calls in this function use oversized destination
@@ -925,14 +924,14 @@ parse_odp_key_attr(const char *s, const struct shash *port_names,
 
     if (port_names && !strncmp(s, "in_port(", 8)) {
         const char *name;
-        const struct shash_node *node;
+        const struct simap_node *node;
         int name_len;
 
         name = s + 8;
         name_len = strcspn(s, ")");
-        node = shash_find_len(port_names, name, name_len);
+        node = simap_find_len(port_names, name, name_len);
         if (node) {
-            nl_msg_put_u32(key, OVS_KEY_ATTR_IN_PORT, (uintptr_t) node->data);
+            nl_msg_put_u32(key, OVS_KEY_ATTR_IN_PORT, node->data);
             return 8 + name_len + 1;
         }
     }
@@ -1209,15 +1208,15 @@ parse_odp_key_attr(const char *s, const struct shash *port_names,
  * data is appended to 'key'.  Either way, 'key''s data might be
  * reallocated.
  *
- * If 'port_names' is nonnull, it points to an shash that maps from a port name
- * to a port number cast to void *.  (Port names may be used instead of port
- * numbers in in_port.)
+ * If 'port_names' is nonnull, it points to an simap that maps from a port name
+ * to a port number.  (Port names may be used instead of port numbers in
+ * in_port.)
  *
  * On success, the attributes appended to 'key' are individually syntactically
  * valid, but they may not be valid as a sequence.  'key' might, for example,
  * have duplicated keys.  odp_flow_key_to_flow() will detect those errors. */
 int
-odp_flow_key_from_string(const char *s, const struct shash *port_names,
+odp_flow_key_from_string(const char *s, const struct simap *port_names,
                          struct ofpbuf *key)
 {
     const size_t old_size = key->size;
index 08b0a2a413b371112e5a7fc547ea1c50491210de..d53f0836ba749bc8704edb839cc02d74b6e5ece3 100644 (file)
@@ -30,7 +30,7 @@ struct ds;
 struct flow;
 struct nlattr;
 struct ofpbuf;
-struct shash;
+struct simap;
 
 #define OVSP_NONE ((uint16_t) -1)
 
@@ -62,7 +62,7 @@ odp_port_to_ofp_port(uint16_t odp_port)
 
 void format_odp_actions(struct ds *, const struct nlattr *odp_actions,
                         size_t actions_len);
-int odp_actions_from_string(const char *, const struct shash *port_names,
+int odp_actions_from_string(const char *, const struct simap *port_names,
                             struct ofpbuf *odp_actions);
 
 /* Upper bound on the length of a nlattr-formatted flow key.  The longest
@@ -92,7 +92,7 @@ struct odputil_keybuf {
 };
 
 void odp_flow_key_format(const struct nlattr *, size_t, struct ds *);
-int odp_flow_key_from_string(const char *s, const struct shash *port_names,
+int odp_flow_key_from_string(const char *s, const struct simap *port_names,
                              struct ofpbuf *);
 
 void odp_flow_key_from_flow(struct ofpbuf *, const struct flow *);
diff --git a/lib/simap.c b/lib/simap.c
new file mode 100644 (file)
index 0000000..f6804aa
--- /dev/null
@@ -0,0 +1,244 @@
+/*
+ * Copyright (c) 2009, 2010, 2011, 2012 Nicira, Inc.
+ *
+ * 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 "simap.h"
+#include <assert.h>
+#include "hash.h"
+
+static size_t hash_name(const char *, size_t length);
+static struct simap_node *simap_find__(const struct simap *,
+                                       const char *name, size_t name_len,
+                                       size_t hash);
+static struct simap_node *simap_add_nocopy__(struct simap *,
+                                             char *name, unsigned int data,
+                                             size_t hash);
+static int compare_nodes_by_name(const void *a_, const void *b_);
+
+/* Initializes 'simap' as an empty string-to-integer map. */
+void
+simap_init(struct simap *simap)
+{
+    hmap_init(&simap->map);
+}
+
+/* Frees all the data that 'simap' contains. */
+void
+simap_destroy(struct simap *simap)
+{
+    if (simap) {
+        simap_clear(simap);
+        hmap_destroy(&simap->map);
+    }
+}
+
+/* Exchanges the contents of 'a' and 'b'. */
+void
+simap_swap(struct simap *a, struct simap *b)
+{
+    hmap_swap(&a->map, &b->map);
+}
+
+/* Adjusts 'simap' so that it is still valid after it has been moved around in
+ * memory (e.g. due to realloc()). */
+void
+simap_moved(struct simap *simap)
+{
+    hmap_moved(&simap->map);
+}
+
+/* Removes all of the mappings from 'simap' and frees them. */
+void
+simap_clear(struct simap *simap)
+{
+    struct simap_node *node, *next;
+
+    SIMAP_FOR_EACH_SAFE (node, next, simap) {
+        hmap_remove(&simap->map, &node->node);
+        free(node->name);
+        free(node);
+    }
+}
+
+/* Returns true if 'simap' contains no mappings, false if it contains at least
+ * one. */
+bool
+simap_is_empty(const struct simap *simap)
+{
+    return hmap_is_empty(&simap->map);
+}
+
+/* Returns the number of mappings in 'simap'. */
+size_t
+simap_count(const struct simap *simap)
+{
+    return hmap_count(&simap->map);
+}
+
+/* Inserts a mapping from 'name' to 'data' into 'simap', replacing any
+ * existing mapping for 'name'.  Returns true if a new mapping was added,
+ * false if an existing mapping's value was replaced.
+ *
+ * The caller retains ownership of 'name'. */
+bool
+simap_put(struct simap *simap, const char *name, unsigned int data)
+{
+    size_t length = strlen(name);
+    size_t hash = hash_name(name, length);
+    struct simap_node *node;
+
+    node = simap_find__(simap, name, length, hash);
+    if (node) {
+        node->data = data;
+        return false;
+    } else {
+        simap_add_nocopy__(simap, xmemdup0(name, length), data, hash);
+        return true;
+    }
+}
+
+/* Increases the data value in the mapping for 'name' by 'amt', or inserts a
+ * mapping from 'name' to 'amt' if no such mapping exists.  Returns the
+ * new total data value for the mapping.
+ *
+ * If 'amt' is zero, this function does nothing and returns 0.  That is, this
+ * function won't create a mapping with a initial value of 0.
+ *
+ * The caller retains ownership of 'name'. */
+unsigned int
+simap_increase(struct simap *simap, const char *name, unsigned int amt)
+{
+    if (amt) {
+        size_t length = strlen(name);
+        size_t hash = hash_name(name, length);
+        struct simap_node *node;
+
+        node = simap_find__(simap, name, length, hash);
+        if (node) {
+            node->data += amt;
+        } else {
+            node = simap_add_nocopy__(simap, xmemdup0(name, length),
+                                      amt, hash);
+        }
+        return node->data;
+    } else {
+        return 0;
+    }
+}
+
+/* Deletes 'node' from 'simap' and frees its associated memory. */
+void
+simap_delete(struct simap *simap, struct simap_node *node)
+{
+    hmap_remove(&simap->map, &node->node);
+    free(node->name);
+    free(node);
+}
+
+/* Searches 'simap' for a mapping with the given 'name'.  Returns it, if found,
+ * or a null pointer if not. */
+struct simap_node *
+simap_find(const struct simap *simap, const char *name)
+{
+    return simap_find_len(simap, name, strlen(name));
+}
+
+/* Searches 'simap' for a mapping whose name is the first 'name_len' bytes
+ * starting at 'name'.  Returns it, if found, or a null pointer if not. */
+struct simap_node *
+simap_find_len(const struct simap *simap, const char *name, size_t len)
+{
+    return simap_find__(simap, name, len, hash_name(name, len));
+}
+
+/* Searches 'simap' for a mapping with the given 'name'.  Returns the
+ * associated data value, if found, otherwise zero. */
+unsigned int
+simap_get(const struct simap *simap, const char *name)
+{
+    struct simap_node *node = simap_find(simap, name);
+    return node ? node->data : 0;
+}
+
+/* Returns an array that contains a pointer to each mapping in 'simap',
+ * ordered alphabetically by name.  The returned array has simap_count(simap)
+ * elements.
+ *
+ * The caller is responsible for freeing the returned array (with free()).  It
+ * should not free the individual "simap_node"s in the array, because they are
+ * still part of 'simap'. */
+const struct simap_node **
+simap_sort(const struct simap *simap)
+{
+    if (simap_is_empty(simap)) {
+        return NULL;
+    } else {
+        const struct simap_node **nodes;
+        struct simap_node *node;
+        size_t i, n;
+
+        n = simap_count(simap);
+        nodes = xmalloc(n * sizeof *nodes);
+        i = 0;
+        SIMAP_FOR_EACH (node, simap) {
+            nodes[i++] = node;
+        }
+        assert(i == n);
+
+        qsort(nodes, n, sizeof *nodes, compare_nodes_by_name);
+
+        return nodes;
+    }
+}
+\f
+static size_t
+hash_name(const char *name, size_t length)
+{
+    return hash_bytes(name, length, 0);
+}
+
+static struct simap_node *
+simap_find__(const struct simap *simap, const char *name, size_t name_len,
+             size_t hash)
+{
+    struct simap_node *node;
+
+    HMAP_FOR_EACH_WITH_HASH (node, node, hash, &simap->map) {
+        if (!strncmp(node->name, name, name_len) && !node->name[name_len]) {
+            return node;
+        }
+    }
+    return NULL;
+}
+
+static struct simap_node *
+simap_add_nocopy__(struct simap *simap, char *name, unsigned int data,
+                   size_t hash)
+{
+    struct simap_node *node = xmalloc(sizeof *node);
+    node->name = name;
+    node->data = data;
+    hmap_insert(&simap->map, &node->node, hash);
+    return node;
+}
+
+static int
+compare_nodes_by_name(const void *a_, const void *b_)
+{
+    const struct simap_node *const *a = a_;
+    const struct simap_node *const *b = b_;
+    return strcmp((*a)->name, (*b)->name);
+}
diff --git a/lib/simap.h b/lib/simap.h
new file mode 100644 (file)
index 0000000..e7bf80b
--- /dev/null
@@ -0,0 +1,70 @@
+/*
+ * Copyright (c) 2009, 2010, 2011, 2012 Nicira, Inc.
+ *
+ * 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 SIMAP_H
+#define SIMAP_H 1
+
+#include "hmap.h"
+
+#ifdef  __cplusplus
+extern "C" {
+#endif
+
+/* A map from strings to unsigned integers. */
+struct simap {
+    struct hmap map;            /* Contains "struct simap_node"s. */
+};
+
+struct simap_node {
+    struct hmap_node node;      /* In struct simap's 'map' hmap. */
+    char *name;
+    unsigned int data;
+};
+
+#define SIMAP_INITIALIZER(SIMAP) { HMAP_INITIALIZER(&(SIMAP)->map) }
+
+#define SIMAP_FOR_EACH(SIMAP_NODE, SIMAP) \
+    HMAP_FOR_EACH (SIMAP_NODE, node, &(SIMAP)->map)
+
+#define SIMAP_FOR_EACH_SAFE(SIMAP_NODE, NEXT, SIMAP) \
+    HMAP_FOR_EACH_SAFE (SIMAP_NODE, NEXT, node, &(SIMAP)->map)
+
+void simap_init(struct simap *);
+void simap_destroy(struct simap *);
+void simap_swap(struct simap *, struct simap *);
+void simap_moved(struct simap *);
+void simap_clear(struct simap *);
+
+bool simap_is_empty(const struct simap *);
+size_t simap_count(const struct simap *);
+
+bool simap_put(struct simap *, const char *, unsigned int);
+unsigned int simap_increase(struct simap *, const char *, unsigned int);
+
+unsigned int simap_get(const struct simap *, const char *);
+struct simap_node *simap_find(const struct simap *, const char *);
+struct simap_node *simap_find_len(const struct simap *,
+                                  const char *, size_t len);
+
+void simap_delete(struct simap *, struct simap_node *);
+
+const struct simap_node **simap_sort(const struct simap *);
+
+#ifdef  __cplusplus
+}
+#endif
+
+#endif /* simap.h */
index d70b630517930fd2dad2a323e3835569a995bbd9..aa4cf4eaadf1dc8a3c0d0539b972b20336a597d4 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2008, 2009, 2010, 2011 Nicira, Inc.
+ * Copyright (c) 2008, 2009, 2010, 2011, 2012 Nicira, Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -33,7 +33,7 @@
 #include "openflow/openflow.h"
 #include "poll-loop.h"
 #include "rconn.h"
-#include "shash.h"
+#include "simap.h"
 #include "stream-ssl.h"
 #include "timeval.h"
 #include "unixctl.h"
@@ -76,8 +76,8 @@ static bool mute = false;
 /* -q, --queue: default OpenFlow queue, none if UINT32_MAX. */
 static uint32_t default_queue = UINT32_MAX;
 
-/* -Q, --port-queue: map from port name to port number (cast to void *). */
-static struct shash port_queues = SHASH_INITIALIZER(&port_queues);
+/* -Q, --port-queue: map from port name to port number. */
+static struct simap port_queues = SIMAP_INITIALIZER(&port_queues);
 
 /* --with-flows: Flows to send to switch. */
 static struct ofputil_flow_mod *default_flows;
@@ -274,8 +274,7 @@ add_port_queue(char *s)
                   "\"<port-name>:<queue-id>\"");
     }
 
-    if (!shash_add_once(&port_queues, port_name,
-                        (void *) (uintptr_t) atoi(queue_id))) {
+    if (!simap_put(&port_queues, port_name, atoi(queue_id))) {
         ovs_fatal(0, "<port-name> arguments for -Q or --port-queue must "
                   "be unique");
     }
@@ -398,7 +397,7 @@ parse_options(int argc, char *argv[])
     }
     free(short_options);
 
-    if (!shash_is_empty(&port_queues) || default_queue != UINT32_MAX) {
+    if (!simap_is_empty(&port_queues) || default_queue != UINT32_MAX) {
         if (action_normal) {
             ovs_error(0, "queue IDs are incompatible with -N or --normal; "
                       "not using OFPP_NORMAL");
index 7c191164b8d2b981d88ed20ec7e43cc832657678..6cb05b88733eeaf563f889a5a76e9a2dcc9eb6df 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2008, 2009, 2010, 2011 Nicira, Inc.
+ * Copyright (c) 2008, 2009, 2010, 2011, 2012 Nicira, Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -43,6 +43,7 @@
 #include "ofpbuf.h"
 #include "packets.h"
 #include "shash.h"
+#include "simap.h"
 #include "sset.h"
 #include "timeval.h"
 #include "util.h"
@@ -826,7 +827,7 @@ sort_output_actions(struct nlattr *actions, size_t length)
 static void
 do_normalize_actions(int argc, char *argv[])
 {
-    struct shash port_names;
+    struct simap port_names;
     struct ofpbuf keybuf;
     struct flow flow;
     struct ofpbuf odp_actions;
@@ -841,7 +842,7 @@ do_normalize_actions(int argc, char *argv[])
 
     ds_init(&s);
 
-    shash_init(&port_names);
+    simap_init(&port_names);
     for (i = 3; i < argc; i++) {
         char name[16];
         int number;
@@ -849,7 +850,7 @@ do_normalize_actions(int argc, char *argv[])
 
         if (sscanf(argv[i], "%15[^=]=%d%n", name, &number, &n) > 0 && n > 0) {
             uintptr_t n = number;
-            shash_add(&port_names, name, (void *) n);
+            simap_put(&port_names, name, n);
         } else {
             ovs_fatal(0, "%s: expected NAME=NUMBER", argv[i]);
         }