[ovs-dev] [PATCH 1/3] lib: Add imap
Andy Zhou
azhou at ovn.org
Fri Mar 31 20:42:01 UTC 2017
'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 <azhou at ovn.org>
---
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
More information about the dev
mailing list