[ovs-dev] [next 24/35] hmapx: New data structure.

Ethan Jackson ethan at nicira.com
Tue May 3 21:37:03 UTC 2011


Nifty.  We've needed something like this for a while.  Looks Good.

Ethan

On Tue, Apr 26, 2011 at 09:24, Ben Pfaff <blp at nicira.com> wrote:
> ---
>  lib/automake.mk |    2 +
>  lib/hmapx.c     |  197 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
>  lib/hmapx.h     |   71 ++++++++++++++++++++
>  3 files changed, 270 insertions(+), 0 deletions(-)
>  create mode 100644 lib/hmapx.c
>  create mode 100644 lib/hmapx.h
>
> diff --git a/lib/automake.mk b/lib/automake.mk
> index c87ee5f..878afe8 100644
> --- a/lib/automake.mk
> +++ b/lib/automake.mk
> @@ -55,6 +55,8 @@ lib_libopenvswitch_a_SOURCES = \
>        lib/hash.h \
>        lib/hmap.c \
>        lib/hmap.h \
> +       lib/hmapx.c \
> +       lib/hmapx.h \
>        lib/json.c \
>        lib/json.h \
>        lib/jsonrpc.c \
> diff --git a/lib/hmapx.c b/lib/hmapx.c
> new file mode 100644
> index 0000000..bcdd7a8
> --- /dev/null
> +++ b/lib/hmapx.c
> @@ -0,0 +1,197 @@
> +/*
> + * 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 "hmapx.h"
> +
> +#include <assert.h>
> +
> +#include "hash.h"
> +
> +static struct hmapx_node *
> +hmapx_find__(const struct hmapx *map, const void *data, size_t hash)
> +{
> +    struct hmapx_node *node;
> +
> +    HMAP_FOR_EACH_IN_BUCKET (node, hmap_node, hash, &map->map) {
> +        if (node->data == data) {
> +            return node;
> +        }
> +    }
> +    return NULL;
> +}
> +
> +static struct hmapx_node *
> +hmapx_add__(struct hmapx *map, void *data, size_t hash)
> +{
> +    struct hmapx_node *node = xmalloc(sizeof *node);
> +    node->data = data;
> +    hmap_insert(&map->map, &node->hmap_node, hash);
> +    return node;
> +}
> +
> +/* Initializes 'map' as an empty set of pointers. */
> +void
> +hmapx_init(struct hmapx *map)
> +{
> +    hmap_init(&map->map);
> +}
> +
> +/* Destroys 'map'. */
> +void
> +hmapx_destroy(struct hmapx *map)
> +{
> +    if (map) {
> +        hmapx_clear(map);
> +        hmap_destroy(&map->map);
> +    }
> +}
> +
> +/* Initializes 'map' to contain the same pointers as 'orig'. */
> +void
> +hmapx_clone(struct hmapx *map, const struct hmapx *orig)
> +{
> +    struct hmapx_node *node;
> +
> +    hmapx_init(map);
> +    HMAP_FOR_EACH (node, hmap_node, &orig->map) {
> +        hmapx_add__(map, node->data, node->hmap_node.hash);
> +    }
> +}
> +
> +/* Exchanges the contents of 'a' and 'b'. */
> +void
> +hmapx_swap(struct hmapx *a, struct hmapx *b)
> +{
> +    hmap_swap(&a->map, &b->map);
> +}
> +
> +/* Adjusts 'map' so that it is still valid after it has been moved around in
> + * memory (e.g. due to realloc()). */
> +void
> +hmapx_moved(struct hmapx *map)
> +{
> +    hmap_moved(&map->map);
> +}
> +
> +/* Returns true if 'map' contains no nodes, false if it contains at least one
> + * node. */
> +bool
> +hmapx_is_empty(const struct hmapx *map)
> +{
> +    return hmap_is_empty(&map->map);
> +}
> +
> +/* Returns the number of nodes in 'map'. */
> +size_t
> +hmapx_count(const struct hmapx *map)
> +{
> +    return hmap_count(&map->map);
> +}
> +
> +/* Adds 'data' to 'map'.  If 'data' is new, returns the new hmapx_node;
> + * otherwise (if a 'data' already existed in 'map'), returns NULL. */
> +struct hmapx_node *
> +hmapx_add(struct hmapx *map, void *data)
> +{
> +    uint32_t hash = hash_pointer(data, 0);
> +    return (hmapx_find__(map, data, hash)
> +            ? NULL
> +            : hmapx_add__(map, data, hash));
> +}
> +
> +/* Adds 'data' to 'map'.  Assert-fails if 'data' was already in 'map'. */
> +void
> +hmapx_add_assert(struct hmapx *map, void *data)
> +{
> +    bool added OVS_UNUSED = hmapx_add(map, data);
> +    assert(added);
> +}
> +
> +/* Removes all of the nodes from 'map'. */
> +void
> +hmapx_clear(struct hmapx *map)
> +{
> +    struct hmapx_node *node, *next;
> +
> +    HMAPX_FOR_EACH_SAFE (node, next, map) {
> +        hmapx_delete(map, node);
> +    }
> +}
> +
> +/* Deletes 'node' from 'map' and frees 'node'. */
> +void
> +hmapx_delete(struct hmapx *map, struct hmapx_node *node)
> +{
> +    hmap_remove(&map->map, &node->hmap_node);
> +    free(node);
> +}
> +
> +/* Searches for 'data' in 'map'.  If found, deletes it and returns true.  If
> + * not found, returns false without modifying 'map'. */
> +bool
> +hmapx_find_and_delete(struct hmapx *map, const void *data)
> +{
> +    struct hmapx_node *node = hmapx_find(map, data);
> +    if (node) {
> +        hmapx_delete(map, node);
> +    }
> +    return node != NULL;
> +}
> +
> +/* Searches for 'data' in 'map' and deletes it.  Assert-fails if 'data' is not
> + * in 'map'. */
> +void
> +hmapx_find_and_delete_assert(struct hmapx *map, const void *data)
> +{
> +    bool deleted OVS_UNUSED = hmapx_find_and_delete(map, data);
> +    assert(deleted);
> +}
> +
> +/* Searches for 'data' in 'map'.  Returns its node, if found, otherwise a null
> + * pointer. */
> +struct hmapx_node *
> +hmapx_find(const struct hmapx *map, const void *data)
> +{
> +    return hmapx_find__(map, data, hash_pointer(data, 0));
> +}
> +
> +/* Returns true if 'map' contains 'data', false otherwise. */
> +bool
> +hmapx_contains(const struct hmapx *map, const void *data)
> +{
> +    return hmapx_find(map, data) != NULL;
> +}
> +
> +/* Returns true if 'a' and 'b' contain the same pointers, false otherwise. */
> +bool
> +hmapx_equals(const struct hmapx *a, const struct hmapx *b)
> +{
> +    struct hmapx_node *node;
> +
> +    if (hmapx_count(a) != hmapx_count(b)) {
> +        return false;
> +    }
> +
> +    HMAP_FOR_EACH (node, hmap_node, &a->map) {
> +        if (!hmapx_find__(b, node->data, node->hmap_node.hash)) {
> +            return false;
> +        }
> +    }
> +
> +    return true;
> +}
> diff --git a/lib/hmapx.h b/lib/hmapx.h
> new file mode 100644
> index 0000000..226255d
> --- /dev/null
> +++ b/lib/hmapx.h
> @@ -0,0 +1,71 @@
> +/*
> + * 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 HMAPX_H
> +#define HMAPX_H
> +
> +#include "hmap.h"
> +
> +struct hmapx_node {
> +    struct hmap_node hmap_node;
> +    void *data;
> +};
> +
> +/* A set of "void *" pointers. */
> +struct hmapx {
> +    struct hmap map;
> +};
> +
> +#define HMAPX_INITIALIZER(HMAPX) { HMAP_INITIALIZER(&(HMAPX)->map) }
> +
> +/* Basics. */
> +void hmapx_init(struct hmapx *);
> +void hmapx_destroy(struct hmapx *);
> +void hmapx_clone(struct hmapx *, const struct hmapx *);
> +void hmapx_swap(struct hmapx *, struct hmapx *);
> +void hmapx_moved(struct hmapx *);
> +
> +/* Count. */
> +bool hmapx_is_empty(const struct hmapx *);
> +size_t hmapx_count(const struct hmapx *);
> +
> +/* Insertion. */
> +struct hmapx_node *hmapx_add(struct hmapx *, void *);
> +void hmapx_add_assert(struct hmapx *, void *);
> +
> +/* Deletion. */
> +void hmapx_clear(struct hmapx *);
> +void hmapx_delete(struct hmapx *, struct hmapx_node *);
> +bool hmapx_find_and_delete(struct hmapx *, const void *);
> +void hmapx_find_and_delete_assert(struct hmapx *, const void *);
> +
> +/* Search. */
> +struct hmapx_node *hmapx_find(const struct hmapx *, const void *);
> +bool hmapx_contains(const struct hmapx *, const void *);
> +bool hmapx_equals(const struct hmapx *, const struct hmapx *);
> +
> +/* Iteration. */
> +
> +/* Iterates through every hmapx_node in HMAPX. */
> +#define HMAPX_FOR_EACH(NODE, HMAPX)             \
> +    HMAP_FOR_EACH(NODE, hmap_node, &(HMAPX)->map)
> +
> +/* Safe when NODE may be freed (not needed when NODE may be removed from the
> + * hash map but its members remain accessible and intact). */
> +#define HMAPX_FOR_EACH_SAFE(NODE, NEXT, HMAPX)                  \
> +    HMAP_FOR_EACH_SAFE(NODE, NEXT, hmap_node, &(HMAPX)->map)
> +
> +#endif /* hmapx.h */
> --
> 1.7.4.4
>
> _______________________________________________
> dev mailing list
> dev at openvswitch.org
> http://openvswitch.org/mailman/listinfo/dev
>



More information about the dev mailing list