lib/flow: Optimize minimask_has_extra() and minimask_is_catchall()

We only need to iterate over the bits masked by the 'b' in
minimask_has_extra(), since for zeroes in 'b' there can be no 'extra'
wildcards in 'a', as 'b' has already wildcarded all the bits.

minimask_is_catchall() can be simplified by the invariant that mask's
map never has 1-bits for all-zero values.

Signed-off-by: Jarno Rajahalme <jrajahalme@nicira.com>
Acked-by: Ethan Jackson <ethan@nicira.com>

diff --git a/lib/flow.c b/lib/flow.c
index f7704fb..2112031 100644 (file)
--- a/lib/flow.c
+++ b/lib/flow.c
@@ -1859,19 +1859,17 @@ minimask_equal(const struct minimask *a, const struct minimask *b)
     return miniflow_equal(&a->masks, &b->masks);
 }
 
     return miniflow_equal(&a->masks, &b->masks);
 }
 

-/* Returns true if at least one bit is wildcarded in 'a_' but not in 'b_',
+/* Returns true if at least one bit matched by 'b' is wildcarded by 'a',

  * false otherwise. */
 bool
  * false otherwise. */
 bool

-minimask_has_extra(const struct minimask *a_, const struct minimask *b_)
+minimask_has_extra(const struct minimask *a, const struct minimask *b)

 {
 {

-    const struct miniflow *a = &a_->masks;
-    const struct miniflow *b = &b_->masks;
+    const uint32_t *p = b->masks.values;

     uint64_t map;
 
     uint64_t map;
 

-    for (map = a->map | b->map; map; map = zero_rightmost_1bit(map)) {
-        int ofs = raw_ctz(map);
-        uint32_t a_u32 = miniflow_get(a, ofs);
-        uint32_t b_u32 = miniflow_get(b, ofs);
+    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++;

 
         if ((a_u32 & b_u32) != b_u32) {
             return true;
 
         if ((a_u32 & b_u32) != b_u32) {
             return true;


@@ -1880,20 +1878,3 @@ minimask_has_extra(const struct minimask *a_, const struct minimask *b_)
 
     return false;
 }
 
     return false;
 }

-
-/* Returns true if 'mask' matches every packet, false if 'mask' fixes any bits
- * or fields. */
-bool
-minimask_is_catchall(const struct minimask *mask_)
-{
-    const struct miniflow *mask = &mask_->masks;
-    const uint32_t *p = mask->values;
-    uint64_t map;
-
-    for (map = mask->map; map; map = zero_rightmost_1bit(map)) {
-        if (*p++) {
-            return false;
-        }
-    }
-    return true;
-}

diff --git a/lib/flow.h b/lib/flow.h
index f0e3a34..36d453a 100644 (file)
--- a/lib/flow.h
+++ b/lib/flow.h
@@ -484,7 +484,17 @@ static inline ovs_be64 minimask_get_metadata_mask(const struct minimask *);
 
 bool minimask_equal(const struct minimask *a, const struct minimask *b);
 bool minimask_has_extra(const struct minimask *, const struct minimask *);
 
 bool minimask_equal(const struct minimask *a, const struct minimask *b);
 bool minimask_has_extra(const struct minimask *, const struct minimask *);

-bool minimask_is_catchall(const struct minimask *);
+
+/* Returns true if 'mask' matches every packet, false if 'mask' fixes any bits
+ * or fields. */
+static inline bool
+minimask_is_catchall(const struct minimask *mask)
+{
+    /* For every 1-bit in mask's map, the corresponding value is non-zero,
+     * so the only way the mask can not fix any bits or fields is for the
+     * map the be zero. */
+    return mask->masks.map == 0;
+}

 
 \f
 
 
 \f