cmap: Merge CMAP_FOR_EACH_SAFE into CMAP_FOR_EACH.

[cascardo/ovs.git] / lib / cmap.h

diff --git a/lib/cmap.h b/lib/cmap.h
index b9e3671..038db6c 100644 (file)
--- a/lib/cmap.h
+++ b/lib/cmap.h
@@ -34,16 +34,16 @@
  *
  * The general rules are:
  *
- *    - Only a single thread may safely call into cmap_insert() or
- *      cmap_remove() at any given time.
+ *    - Only a single thread may safely call into cmap_insert(),
+ *      cmap_remove(), or cmap_replace() at any given time.
  *
  *    - Any number of threads may use functions and macros that search or
  *      iterate through a given cmap, even in parallel with other threads
- *      calling cmap_insert() or cmap_remove().
+ *      calling cmap_insert(), cmap_remove(), or cmap_replace().
  *
  *      There is one exception: cmap_find_protected() is only safe if no thread
- *      is currently calling cmap_insert() or cmap_remove().  (Use ordinary
- *      cmap_find() if that is not guaranteed.)
+ *      is currently calling cmap_insert(), cmap_remove(), or cmap_replace().
+ *      (Use ordinary cmap_find() if that is not guaranteed.)
  *
  *    - See "Iteration" below for additional thread safety rules.
  *
@@ -90,6 +90,8 @@ bool cmap_is_empty(const struct cmap *);
 /* Insertion and deletion. */
 void cmap_insert(struct cmap *, struct cmap_node *, uint32_t hash);
 void cmap_remove(struct cmap *, struct cmap_node *, uint32_t hash);
+void cmap_replace(struct cmap *, struct cmap_node *old_node,
+                  struct cmap_node *new_node, uint32_t hash);
 
 /* Search.
  *
@@ -161,26 +163,46 @@ struct cmap_node *cmap_find_protected(const struct cmap *, uint32_t hash);
  *         ...operate on my_node...
  *     }
  *
- * There is no CMAP_FOR_EACH_SAFE variant because it would be rarely useful:
- * usually destruction of an element has to wait for an RCU grace period to
- * expire.
+ * CMAP_FOR_EACH is "safe" in the sense of HMAP_FOR_EACH_SAFE.  That is, it is
+ * safe to free the current node before going on to the next iteration.  Most
+ * of the time, though, this doesn't matter for a cmap because node
+ * deallocation has to be postponed until the next grace period.  This means
+ * that this guarantee is useful only in deallocation code already executing at
+ * postponed time, when it is known that the RCU grace period has already
+ * expired.
  */
-#define CMAP_FOR_EACH(NODE, MEMBER, CURSOR, CMAP)                       \
-    for ((cmap_cursor_init(CURSOR, CMAP),                               \
-          ASSIGN_CONTAINER(NODE, cmap_cursor_next(CURSOR, NULL), MEMBER)); \
-         NODE != OBJECT_CONTAINING(NULL, NODE, MEMBER);                 \
-         ASSIGN_CONTAINER(NODE, cmap_cursor_next(CURSOR, &(NODE)->MEMBER), \
-                          MEMBER))
+
+#define CMAP_CURSOR_FOR_EACH__(NODE, CURSOR, MEMBER)    \
+    ((CURSOR)->node                                     \
+     ? (ASSIGN_CONTAINER(NODE, (CURSOR)->node, MEMBER), \
+        cmap_cursor_advance(CURSOR),                    \
+        true)                                           \
+     : false)
+
+#define CMAP_CURSOR_FOR_EACH(NODE, MEMBER, CURSOR, CMAP)    \
+    for (*(CURSOR) = cmap_cursor_start(CMAP);               \
+         CMAP_CURSOR_FOR_EACH__(NODE, CURSOR, MEMBER);      \
+        )
+
+#define CMAP_CURSOR_FOR_EACH_CONTINUE(NODE, MEMBER, CURSOR)   \
+    while (CMAP_CURSOR_FOR_EACH__(NODE, CURSOR, MEMBER))
 
 struct cmap_cursor {
     const struct cmap_impl *impl;
     uint32_t bucket_idx;
     int entry_idx;
+    struct cmap_node *node;
 };
 
-void cmap_cursor_init(struct cmap_cursor *, const struct cmap *);
-struct cmap_node *cmap_cursor_next(struct cmap_cursor *,
-                                   const struct cmap_node *);
+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);       \
+        )
+
+static inline struct cmap_node *cmap_first(const struct cmap *);
 
 /* Another, less preferred, form of iteration, for use in situations where it
  * is difficult to maintain a pointer to a cmap_node. */
@@ -193,4 +215,14 @@ struct cmap_position {
 struct cmap_node *cmap_next_position(const struct cmap *,
                                      struct cmap_position *);
 
+/* Returns the first node in 'cmap', in arbitrary order, or a null pointer if
+ * 'cmap' is empty. */
+static inline struct cmap_node *
+cmap_first(const struct cmap *cmap)
+{
+    struct cmap_position pos = { 0, 0, 0 };
+
+    return cmap_next_position(cmap, &pos);
+}
+
 #endif /* cmap.h */