python: Update build system to ensure dirs.py is created.

[mirror_ovs.git] / lib / cmap.h

diff --git a/lib/cmap.h b/lib/cmap.h
index c653424a84eca934c27bfc6b452a4222b4666451..d9db3c915cbfab48e98e3f033e1200a8855260a8 100644 (file)
--- a/lib/cmap.h
+++ b/lib/cmap.h
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2014 Nicira, Inc.
+ * Copyright (c) 2014, 2016 Nicira, Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -79,6 +79,12 @@ struct cmap {
     OVSRCU_TYPE(struct cmap_impl *) impl;
 };
 
+/* Initializer for an empty cmap. */
+#define CMAP_INITIALIZER {                                              \
+        .impl = OVSRCU_INITIALIZER((struct cmap_impl *) &empty_cmap)    \
+    }
+extern OVS_ALIGNED_VAR(CACHE_LINE_SIZE) const struct cmap_impl empty_cmap;
+
 /* Initialization. */
 void cmap_init(struct cmap *);
 void cmap_destroy(struct cmap *);
@@ -134,11 +140,22 @@ size_t cmap_replace(struct cmap *, struct cmap_node *old_node,
 #define CMAP_FOR_EACH_WITH_HASH(NODE, MEMBER, HASH, CMAP)   \
     CMAP_NODE_FOR_EACH(NODE, MEMBER, cmap_find(CMAP, HASH))
 #define CMAP_FOR_EACH_WITH_HASH_PROTECTED(NODE, MEMBER, HASH, CMAP)     \
-    CMAP_NODE_FOR_EACH_PROTECTED(NODE, MEMBER, cmap_find_locked(CMAP, HASH))
+    CMAP_NODE_FOR_EACH_PROTECTED(NODE, MEMBER, cmap_find_protected(CMAP, HASH))
 
 const struct cmap_node *cmap_find(const struct cmap *, uint32_t hash);
 struct cmap_node *cmap_find_protected(const struct cmap *, uint32_t hash);
 
+/* Find node by index or find index by hash. The 'index' of a cmap entry is a
+ * way to combine the specific bucket and the entry of the bucket into a
+ * convenient single integer value. In other words, it is the index of the
+ * entry and each entry has an unique index. It is not used internally by
+ * cmap.
+ * Currently the functions assume index will not be larger than uint32_t. In
+ * OvS table size is usually much smaller than this size.*/
+const struct cmap_node * cmap_find_by_index(const struct cmap *,
+                                            uint32_t index);
+uint32_t cmap_find_index(const struct cmap *, uint32_t hash);
+
 /* Looks up multiple 'hashes', when the corresponding bit in 'map' is 1,
  * and sets the corresponding pointer in 'nodes', if the hash value was
  * found from the 'cmap'.  In other cases the 'nodes' values are not changed,
@@ -169,6 +186,11 @@ unsigned long cmap_find_batch(const struct cmap *cmap, unsigned long map,
  *       node being deleted may be visited once or not at all.  Other nodes
  *       will be visited once.)
  *
+ *     - If the cmap is changing, it is not safe to quiesce while iterating.
+ *       Even if the changes are done by the same thread that's performing the
+ *       iteration (Corollary: it is not safe to call cmap_remove() and quiesce
+ *       in the loop body).
+ *
  *
  * Example
  * =======
@@ -178,13 +200,12 @@ unsigned long cmap_find_batch(const struct cmap *cmap, unsigned long map,
  *         int extra_data;
  *     };
  *
- *     struct cmap_cursor cursor;
- *     struct my_node *iter;
  *     struct cmap my_map;
+ *     struct my_node *my_node;
  *
- *     cmap_init(&cmap);
+ *     cmap_init(&my_map);
  *     ...add data...
- *     CMAP_FOR_EACH (my_node, cmap_node, &cursor, &cmap) {
+ *     CMAP_FOR_EACH (my_node, cmap_node, &my_map) {
  *         ...operate on my_node...
  *     }
  *
@@ -222,11 +243,20 @@ struct cmap_cursor {
 struct cmap_cursor cmap_cursor_start(const struct cmap *);
 void cmap_cursor_advance(struct cmap_cursor *);
 
-#define CMAP_FOR_EACH(NODE, MEMBER, CMAP)                       \
-    for (struct cmap_cursor cursor__ = cmap_cursor_start(CMAP); \
-         CMAP_CURSOR_FOR_EACH__(NODE, &cursor__, MEMBER);       \
+/* Generate a unique name for the cursor with the __COUNTER__ macro to
+ * allow nesting of CMAP_FOR_EACH loops. */
+#define CURSOR_JOIN2(x,y) x##y
+#define CURSOR_JOIN(x, y) CURSOR_JOIN2(x,y)
+
+#define CMAP_FOR_EACH__(NODE, MEMBER, CMAP, CURSOR_NAME)           \
+    for (struct cmap_cursor CURSOR_NAME = cmap_cursor_start(CMAP); \
+         CMAP_CURSOR_FOR_EACH__(NODE, &CURSOR_NAME, MEMBER);       \
         )
 
+#define CMAP_FOR_EACH(NODE, MEMBER, CMAP) \
+          CMAP_FOR_EACH__(NODE, MEMBER, CMAP, \
+                CURSOR_JOIN(cursor_, __COUNTER__))
+
 static inline struct cmap_node *cmap_first(const struct cmap *);
 
 /* Another, less preferred, form of iteration, for use in situations where it