[ovs-dev] [PATCH 03/10] flow.c: Improve minimask_equal() and minimask_has_extra().

[Jarno Rajahalme]

minimask_equal() and minimask_has_extra() can take benefit from the
fact that minimasks have no zero data.

Signed-off-by: Jarno Rajahalme <jrajahalme at nicira.com>
---
 lib/flow.c |   27 ++++++++++++++++++---------
 lib/flow.h |    5 +++--
 2 files changed, 21 insertions(+), 11 deletions(-)

diff --git a/lib/flow.c b/lib/flow.c
index f1bcad6..141c3d8 100644
--- a/lib/flow.c
+++ b/lib/flow.c
@@ -2131,11 +2131,16 @@ minimask_get(const struct minimask *mask, unsigned int u32_ofs)
     return miniflow_get(&mask->masks, u32_ofs);
 }
 
-/* Returns true if 'a' and 'b' are the same flow mask, false otherwise.  */
+/* Returns true if 'a' and 'b' are the same flow mask, false otherwise.
+ * Minimasks may not have zero data values, so for the minimasks to be the
+ * same, they need to have the same map and the same data values. */
 bool
 minimask_equal(const struct minimask *a, const struct minimask *b)
 {
-    return miniflow_equal(&a->masks, &b->masks);
+    return a->masks.map == b->masks.map &&
+        !memcmp(miniflow_get_u32_values(&a->masks),
+                miniflow_get_u32_values(&b->masks),
+                count_1bits(a->masks.map) * sizeof *a->masks.inline_values);
 }
 
 /* Returns true if at least one bit matched by 'b' is wildcarded by 'a',
@@ -2143,15 +2148,19 @@ minimask_equal(const struct minimask *a, const struct minimask *b)
 bool
 minimask_has_extra(const struct minimask *a, const struct minimask *b)
 {
-    const uint32_t *p = miniflow_get_u32_values(&b->masks);
-    uint64_t map;
+    const uint32_t *ap = miniflow_get_u32_values(&a->masks);
+    const uint32_t *bp = miniflow_get_u32_values(&b->masks);
+    int idx;
 
-    for (map = b->masks.map; map; map = zero_rightmost_1bit(map)) {
-        uint32_t a_u32 = minimask_get(a, raw_ctz(map));
-        uint32_t b_u32 = *p++;
+    MAP_FOR_EACH_INDEX(idx, b->masks.map) {
+        uint32_t b_u32 = *bp++;
 
-        if ((a_u32 & b_u32) != b_u32) {
-            return true;
+        /* 'b_u32' is non-zero, check if the data in 'a' is either zero
+         * or misses some of the bits in 'b_u32'. */
+        if (!(a->masks.map & (UINT64_C(1) << idx))
+            || ((MINIFLOW_VALUES_GET__(ap, a->masks.map, idx) & b_u32)
+                != b_u32)) {
+            return true; /* 'a' wildcards some bits 'b' doesn't. */
         }
     }
 
diff --git a/lib/flow.h b/lib/flow.h
index 3e0ac28..2ef5c7b 100644
--- a/lib/flow.h
+++ b/lib/flow.h
@@ -553,9 +553,10 @@ mf_get_next_in_map(struct mf_for_each_in_map_aux *aux, uint32_t *value)
 
 /* This macro can be used when it is known that the 'U32_IDX' is set in the
  * map of 'MF'. */
+#define MINIFLOW_VALUES_GET__(VALUES, MAP, U32_IDX)                     \
+    ((VALUES)[count_1bits((MAP) & ((UINT64_C(1) << (U32_IDX)) - 1))])
 #define MINIFLOW_GET__(MF, U32_IDX)                                     \
-    (miniflow_get_u32_values(MF)                                        \
-     [count_1bits((MF)->map & ((UINT64_C(1) << (U32_IDX)) - 1))])
+    MINIFLOW_VALUES_GET__(miniflow_get_u32_values(MF), (MF)->map, U32_IDX)
 
 /* Get the value of 'FIELD' of an up to 4 byte wide integer type 'TYPE' of
  * a miniflow. */
-- 
1.7.10.4