'imap' implements a sparse array that maps a uint32_t value to a pointer of arbitrary object. Future patches will make use of this library.
Signed-off-by: Andy Zhou <[email protected]> --- lib/automake.mk | 2 + lib/imap.c | 129 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ lib/imap.h | 63 +++++++++++++++++++++++++++ 3 files changed, 194 insertions(+) create mode 100644 lib/imap.c create mode 100644 lib/imap.h diff --git a/lib/automake.mk b/lib/automake.mk index b266af13e4c7..5056c923827c 100644 --- a/lib/automake.mk +++ b/lib/automake.mk @@ -105,6 +105,8 @@ lib_libopenvswitch_la_SOURCES = \ lib/hmapx.h \ lib/id-pool.c \ lib/id-pool.h \ + lib/imap.h \ + lib/imap.c \ lib/jhash.c \ lib/jhash.h \ lib/json.c \ diff --git a/lib/imap.c b/lib/imap.c new file mode 100644 index 000000000000..556ed6200105 --- /dev/null +++ b/lib/imap.c @@ -0,0 +1,129 @@ +/* Copyright (c) 2017 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 "imap.h" + + +/* Public Functions. */ +void +imap_init(struct imap *imap) +{ + hmap_init(&imap->map); +} + +void +imap_destroy(struct imap *imap) +{ + if (imap) { + imap_clear(imap); + hmap_destroy(&imap->map); + } +} + +/* Adds 'index' paired with 'data' to 'imap'. It is the caller's + * responsibility to avoid duplicate keys if desirable. */ +struct imap_node * +imap_add(struct imap *imap, uint32_t index, void *data) +{ + struct imap_node *node = xmalloc(sizeof *node); + node->index = index; + node->data = data; + hmap_insert(&imap->map, &node->node, hash_int(index, 0)); + return node; +} + +/* Attempts to add 'index' to 'imap' associated with 'data'. If 'index' + * already exists in 'imap', does nothing and returns false. Otherwise, + * performs the addition and returns true. */ +bool +imap_add_once(struct imap *imap, uint32_t index, void *data) +{ + if (imap_get(imap, index)) { + return false; + } + + imap_add(imap, index, data); + return true; +} + +/* If 'index' is in 'imap', removes it. Otherwise does nothing. */ +void +imap_remove(struct imap *imap, uint32_t index) +{ + struct imap_node *node = imap_get_node(imap, index); + + if (node) { + imap_remove_node(imap, node); + } +} + +/* Removes 'node' from 'imap'. */ +void +imap_remove_node(struct imap *imap, struct imap_node *node) +{ + hmap_remove(&imap->map, &node->node); + free(node->data); + free(node); +} + +/* Removes all indexes from 'imap'. */ +void +imap_clear(struct imap *imap) +{ + struct imap_node *node, *next; + + IMAP_FOR_EACH_SAFE (node, next, imap) { + imap_remove_node(imap, node); + } +} + +/* Returns the data associated with 'index' in 'imap'. + * If 'imap' does not contain 'index', returns NULL. */ +void * +imap_get(const struct imap *imap, uint32_t index) +{ + struct imap_node *node = imap_get_node(imap, index); + return node ? node->data : NULL; +} + +/* Returns the node associated with 'index' in 'imap', or NULL. */ +struct imap_node * +imap_get_node(const struct imap *imap, uint32_t index) +{ + struct imap_node *node; + uint32_t hash = hash_int(index, 0); + + HMAP_FOR_EACH_WITH_HASH (node, node, hash, &imap->map) { + if (node->index == index) { + return node; + } + } + + return NULL; +} + +/* Returns true of there are no elements in 'imap'. */ +bool +imap_is_empty(const struct imap *imap) +{ + return hmap_is_empty(&imap->map); +} + +/* Returns the number of elements in 'imap'. */ +size_t +imap_count(const struct imap *imap) +{ + return hmap_count(&imap->map); +} diff --git a/lib/imap.h b/lib/imap.h new file mode 100644 index 000000000000..c90d02351ff8 --- /dev/null +++ b/lib/imap.h @@ -0,0 +1,63 @@ +/* Copyright (c) 2017 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 IMAP_H +#define IMAP_H 1 + +#include <netinet/in.h> +#include "hash.h" +#include "openvswitch/hmap.h" + +/* Sparse array, A map from uint32_t to arbitrary data. */ +struct imap { + struct hmap map; /* Contains "struct imap_node"s. */ +}; + +struct imap_node { + struct hmap_node node; /* In struct imap's 'map' hmap. */ + uint32_t index; + void *data; +}; + +#define IMAP_INITIALIZER(IMAP) { HMAP_INITIALIZER(&(IMAP)->map) } + +#define IMAP_FOR_EACH(IMAP_NODE, IMAP) \ + HMAP_FOR_EACH_INIT (IMAP_NODE, node, &(IMAP)->map, \ + BUILD_ASSERT_TYPE(IMAP_NODE, struct imap_node *), \ + BUILD_ASSERT_TYPE(IMAP, struct imap *)) + +#define IMAP_FOR_EACH_SAFE(IMAP_NODE, NEXT, IMAP) \ + HMAP_FOR_EACH_SAFE_INIT ( \ + IMAP_NODE, NEXT, node, &(IMAP)->map, \ + BUILD_ASSERT_TYPE(IMAP_NODE, struct imap_node *), \ + BUILD_ASSERT_TYPE(NEXT, struct imap_node *), \ + BUILD_ASSERT_TYPE(IMAP, struct imap *)) + +void imap_init(struct imap *); +void imap_destroy(struct imap *); + +struct imap_node *imap_add(struct imap *, uint32_t, void *); +bool imap_add_once(struct imap *, uint32_t, void *); + +void imap_remove(struct imap *, uint32_t); +void imap_remove_node(struct imap *, struct imap_node *); + +void *imap_get(const struct imap *, uint32_t); +struct imap_node *imap_get_node(const struct imap *, uint32_t); + +void imap_clear(struct imap *); +bool imap_is_empty(const struct imap *); +size_t imap_count(const struct imap *); + +#endif /* imap.h */ -- 1.8.3.1 _______________________________________________ dev mailing list [email protected] https://mail.openvswitch.org/mailman/listinfo/ovs-dev
