Nifty. We've needed something like this for a while. Looks Good. Ethan
On Tue, Apr 26, 2011 at 09:24, Ben Pfaff <b...@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@openvswitch.org > http://openvswitch.org/mailman/listinfo/dev > _______________________________________________ dev mailing list dev@openvswitch.org http://openvswitch.org/mailman/listinfo/dev
