classifier: Avoid accumulating junk in cls_partition 'tags'.

It's easy to add two tags together, but it's hard to subtract them.  The
new "tag_tracker" data structure provides a solution.

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

1 files changed, 29 insertions, 4 deletions

diff --git a/lib/tag.c b/lib/tag.c
index b45bcd55..13d18292 100644
--- a/lib/tag.c
+++ b/lib/tag.c
@@ -16,10 +16,6 @@
 
 #include <config.h>
 #include "tag.h"
-#include <limits.h>
-
-#define N_TAG_BITS (CHAR_BIT * sizeof(tag_type))
-BUILD_ASSERT_DECL(IS_POW2(N_TAG_BITS));
 
 #define LOG2_N_TAG_BITS (N_TAG_BITS == 32 ? 5 : N_TAG_BITS == 64 ? 6 : 0)
 BUILD_ASSERT_DECL(LOG2_N_TAG_BITS > 0);
@@ -37,3 +33,32 @@ tag_create_deterministic(uint32_t seed)
     y += y >= x;
     return (1u << x) | (1u << y);
 }
+
+/* Initializes 'tracker'. */
+void
+tag_tracker_init(struct tag_tracker *tracker)
+{
+    memset(tracker, 0, sizeof *tracker);
+}
+
+/* Adds 'add' to '*tags' and records the bits added in 'tracker'. */
+void
+tag_tracker_add(struct tag_tracker *tracker, tag_type *tags, tag_type add)
+{
+    *tags |= add;
+    for (; add; add = zero_rightmost_1bit(add)) {
+        tracker->counts[rightmost_1bit_idx(add)]++;
+    }
+}
+
+/* Removes 'sub' from 'tracker' and unsets any bits in '*tags' that no
+ * remaining tag includes. */
+void
+tag_tracker_subtract(struct tag_tracker *tracker, tag_type *tags, tag_type sub)
+{
+    for (; sub; sub = zero_rightmost_1bit(sub)) {
+        if (!--tracker->counts[rightmost_1bit_idx(sub)]) {
+            *tags &= ~rightmost_1bit(sub);
+        }
+    }
+}