bitmap: Make bitmap_scan() able to scan for 0-bits or 1-bits.

An upcoming commit will make use of this feature.

Signed-off-by: Ben Pfaff <blp@nicira.com>

diff --git a/lib/bitmap.c b/lib/bitmap.c
index 51ad5bf..4b4e13e 100644 (file)
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2008, 2009, 2011 Nicira, Inc.
+ * Copyright (c) 2008, 2009, 2011, 2014 Nicira, Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -78,16 +78,17 @@ bitmap_equal(const unsigned long *a, const unsigned long *b, size_t n)
 }
 
 /* Scans 'bitmap' from bit offset 'start' to 'end', excluding 'end' itself.
- * Returns the bit offset of the lowest-numbered bit set to 1, or 'end' if
- * all of the bits are set to 0. */
+ * Returns the bit offset of the lowest-numbered bit set to 'target', or 'end'
+ * if all of the bits are set to '!target'. */
 size_t
-bitmap_scan(const unsigned long int *bitmap, size_t start, size_t end)
+bitmap_scan(const unsigned long int *bitmap, bool target,
+            size_t start, size_t end)
 {
     /* XXX slow */
     size_t i;
 
     for (i = start; i < end; i++) {
-        if (bitmap_is_set(bitmap, i)) {
+        if (bitmap_is_set(bitmap, i) == target) {
             break;
         }
     }

diff --git a/lib/bitmap.h b/lib/bitmap.h
index 5e6f8ed..afe6151 100644 (file)
--- a/lib/bitmap.h
+++ b/lib/bitmap.h
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2008, 2009, 2010, 2011, 2012, 2013 Nicira, Inc.
+ * Copyright (c) 2008, 2009, 2010, 2011, 2012, 2013, 2014 Nicira, Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -100,11 +100,12 @@ bitmap_set(unsigned long *bitmap, size_t offset, bool value)
 void bitmap_set_multiple(unsigned long *, size_t start, size_t count,
                          bool value);
 bool bitmap_equal(const unsigned long *, const unsigned long *, size_t n);
-size_t bitmap_scan(const unsigned long int *, size_t start, size_t end);
+size_t bitmap_scan(const unsigned long int *, bool target,
+                   size_t start, size_t end);
 size_t bitmap_count1(const unsigned long *, size_t n);
 
 #define BITMAP_FOR_EACH_1(IDX, SIZE, BITMAP) \
-    for ((IDX) = bitmap_scan(BITMAP, 0, SIZE); (IDX) < (SIZE); \
-         (IDX) = bitmap_scan(BITMAP, (IDX) + 1, SIZE))
+    for ((IDX) = bitmap_scan(BITMAP, 1, 0, SIZE); (IDX) < (SIZE);    \
+         (IDX) = bitmap_scan(BITMAP, 1, (IDX) + 1, SIZE))
 
 #endif /* bitmap.h */

diff --git a/lib/nx-match.h b/lib/nx-match.h
index ee3f24c..edd7948 100644 (file)
--- a/lib/nx-match.h
+++ b/lib/nx-match.h
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2010, 2011, 2012, 2013 Nicira, Inc.
+ * Copyright (c) 2010, 2011, 2012, 2013, 2014 Nicira, Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -27,6 +27,7 @@
 
 struct ds;
 struct match;
+struct mf_field;
 struct mf_subfield;
 struct ofpact_reg_move;
 struct ofpact_reg_load;

diff --git a/ovsdb/transaction.c b/ovsdb/transaction.c
index 4cbe9f0..98a7a3f 100644 (file)
--- a/ovsdb/transaction.c
+++ b/ovsdb/transaction.c
@@ -1,4 +1,4 @@
-/* Copyright (c) 2009, 2010, 2011, 2012, 2013 Nicira, Inc.
+/* Copyright (c) 2009, 2010, 2011, 2012, 2013, 2014 Nicira, Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -653,7 +653,7 @@ duplicate_index_row__(const struct ovsdb_column_set *index,
     ds_put_format(out, "%s row, with UUID "UUID_FMT", ",
                   title, UUID_ARGS(ovsdb_row_get_uuid(row)));
     if (!row->txn_row
-        || bitmap_scan(row->txn_row->changed, 0, n_columns) == n_columns) {
+        || bitmap_scan(row->txn_row->changed, 1, 0, n_columns) == n_columns) {
         ds_put_cstr(out, "existed in the database before this "
                     "transaction and was not modified by the transaction.");
     } else if (!row->txn_row->old) {

diff --git a/vswitchd/bridge.c b/vswitchd/bridge.c
index 1d56bbd..db85856 100644 (file)
--- a/vswitchd/bridge.c
+++ b/vswitchd/bridge.c
@@ -1326,7 +1326,7 @@ bridge_configure_stp(struct bridge *br)
             }
         }
 
-        if (bitmap_scan(port_num_bitmap, 0, STP_MAX_PORTS) != STP_MAX_PORTS
+        if (bitmap_scan(port_num_bitmap, 1, 0, STP_MAX_PORTS) != STP_MAX_PORTS
                     && port_num_counter) {
             VLOG_ERR("bridge %s: must manually configure all STP port "
                      "IDs or none, disabling", br->name);
@@ -4111,7 +4111,7 @@ collect_splinter_vlans(const struct ovsrec_open_vswitch *ovs_cfg)
 
     sset_destroy(&splinter_ifaces);
 
-    if (bitmap_scan(splinter_vlans, 0, 4096) >= 4096) {
+    if (bitmap_scan(splinter_vlans, 1, 0, 4096) >= 4096) {
         free(splinter_vlans);
         return NULL;
     }