[ovs-dev] [PATCH 1/2] simap: New data structure for string-to-integer maps.
Ethan Jackson
ethan at nicira.com
Wed May 16 00:40:38 UTC 2012
It feels a bit fragile to me that we use hash_name() in some places
and hash_bytes() in others. If the implementation of hash_string()
changes, this is going to break. Minimally I think we should change
hash_name() to use hash_bytes() directly instead of going through
hash_string(). We could also just get rid of simap_find_len() which
is the only direct caller of hash_bytes(), not sure if it will be used
later or not.
s/freee()/free()/
The comment of simap_destroy() says it frees 'simap', when it actually
only frees it's data.
Looks good, thanks this will be useful.
Ethan
On Tue, May 8, 2012 at 3:47 PM, Ben Pfaff <blp at nicira.com> wrote:
> 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 at nicira.com>
> ---
> lib/automake.mk | 2 +
> lib/learning-switch.c | 7 +-
> lib/learning-switch.h | 6 +-
> lib/odp-util.c | 31 +++---
> lib/odp-util.h | 6 +-
> lib/simap.c | 241 ++++++++++++++++++++++++++++++++++++++++++++
> lib/simap.h | 70 +++++++++++++
> utilities/ovs-controller.c | 13 +--
> utilities/ovs-dpctl.c | 9 +-
> 9 files changed, 349 insertions(+), 36 deletions(-)
> create mode 100644 lib/simap.c
> create mode 100644 lib/simap.h
>
> diff --git a/lib/automake.mk b/lib/automake.mk
> index 6217526..920babd 100644
> --- a/lib/automake.mk
> +++ b/lib/automake.mk
> @@ -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 \
> diff --git a/lib/learning-switch.c b/lib/learning-switch.c
> index 4e7ceda..595b7f0 100644
> --- a/lib/learning-switch.c
> +++ b/lib/learning-switch.c
> @@ -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);
> }
> }
> diff --git a/lib/learning-switch.h b/lib/learning-switch.h
> index e42aec1..c3c37f2 100644
> --- a/lib/learning-switch.h
> +++ b/lib/learning-switch.h
> @@ -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 *);
> diff --git a/lib/odp-util.c b/lib/odp-util.c
> index fef42ba..c24045f 100644
> --- a/lib/odp-util.c
> +++ b/lib/odp-util.c
> @@ -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);
>
> @@ -295,7 +295,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
> @@ -320,12 +320,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;
> }
> }
> @@ -468,7 +467,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;
> @@ -785,7 +784,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
> @@ -832,14 +831,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;
> }
> }
> @@ -1116,15 +1115,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;
> diff --git a/lib/odp-util.h b/lib/odp-util.h
> index 0ea801a..85dd146 100644
> --- a/lib/odp-util.h
> +++ b/lib/odp-util.h
> @@ -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
> index 0000000..68e58c3
> --- /dev/null
> +++ b/lib/simap.c
> @@ -0,0 +1,241 @@
> +/*
> + * 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 *);
> +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 'simap' and all the mappings that it 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 hash = hash_name(name);
> + struct simap_node *node;
> +
> + node = simap_find__(simap, name, strlen(name), hash);
> + if (node) {
> + node->data = data;
> + return false;
> + } else {
> + simap_add_nocopy__(simap, xstrdup(name), 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 hash = hash_name(name);
> + struct simap_node *node;
> +
> + node = simap_find__(simap, name, strlen(name), hash);
> + if (node) {
> + node->data += amt;
> + } else {
> + node = simap_add_nocopy__(simap, xstrdup(name), 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_bytes(name, len, 0));
> +}
> +
> +/* 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 freee()). 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;
> + }
> +}
> +
> +static size_t
> +hash_name(const char *name)
> +{
> + return hash_string(name, 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
> index 0000000..e7bf80b
> --- /dev/null
> +++ b/lib/simap.h
> @@ -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 */
> diff --git a/utilities/ovs-controller.c b/utilities/ovs-controller.c
> index d70b630..aa4cf4e 100644
> --- a/utilities/ovs-controller.c
> +++ b/utilities/ovs-controller.c
> @@ -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");
> diff --git a/utilities/ovs-dpctl.c b/utilities/ovs-dpctl.c
> index 7c19116..6cb05b8 100644
> --- a/utilities/ovs-dpctl.c
> +++ b/utilities/ovs-dpctl.c
> @@ -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]);
> }
> --
> 1.7.2.5
>
> _______________________________________________
> dev mailing list
> dev at openvswitch.org
> http://openvswitch.org/mailman/listinfo/dev
More information about the dev
mailing list