From b71273f60dbb2315330874809595048ce3c6ac68 Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Sun, 23 Mar 2014 23:00:17 -0700 Subject: [PATCH] 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 --- lib/bitmap.c | 11 ++++++----- lib/bitmap.h | 9 +++++---- lib/nx-match.h | 3 ++- ovsdb/transaction.c | 4 ++-- vswitchd/bridge.c | 4 ++-- 5 files changed, 17 insertions(+), 14 deletions(-) diff --git a/lib/bitmap.c b/lib/bitmap.c index 51ad5bf91..4b4e13e56 100644 --- 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 5e6f8ed0c..afe6151b4 100644 --- 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 ee3f24ced..edd79481a 100644 --- 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 4cbe9f051..98a7a3fab 100644 --- 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 1d56bbd85..db85856cc 100644 --- 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; } -- 2.47.0