/*
- * Copyright (c) 2008, 2009 Nicira Networks.
+ * Copyright (c) 2008, 2009, 2010, 2011 Nicira, Inc.
*
- * Permission to use, copy, modify, and/or distribute this software for any
- * purpose with or without fee is hereby granted, provided that the above
- * copyright notice and this permission notice appear in all copies.
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
*
- * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
- * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
- * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
- * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
- * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
- * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
- * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
*/
#include <config.h>
tag_create_deterministic(uint32_t seed)
{
int x = seed & (N_TAG_BITS - 1);
- int y = (seed >> LOG2_N_TAG_BITS) % 31;
+ int y = (seed >> LOG2_N_TAG_BITS) % (N_TAG_BITS - 1);
y += y >= x;
return (1u << x) | (1u << y);
}
memset(set, 0, sizeof *set);
}
+static bool
+tag_is_worth_adding(const struct tag_set *set, tag_type tag)
+{
+ if (!tag) {
+ /* Nothing to add. */
+ return false;
+ } else if ((set->total & tag) != tag) {
+ /* 'set' doesn't have all the bits in 'tag', so we need to add it. */
+ return true;
+ } else {
+ /* We can drop it if some member of 'set' already includes all of the
+ * 1-bits in 'tag'. (tag_set_intersects() does a different test:
+ * whether some member of 'set' has at least two 1-bit in common with
+ * 'tag'.) */
+ int i;
+
+ for (i = 0; i < TAG_SET_SIZE; i++) {
+ if ((set->tags[i] & tag) == tag) {
+ return false;
+ }
+ }
+ return true;
+ }
+}
+
/* Adds 'tag' to 'set'. */
void
tag_set_add(struct tag_set *set, tag_type tag)
{
- if (tag && (!tag_is_valid(tag) || !tag_set_intersects(set, tag))) {
+ if (tag_is_worth_adding(set, tag)) {
/* XXX We could do better by finding the set member to which we would
* add the fewest number of 1-bits. This would reduce the amount of
* ambiguity, since e.g. three 1-bits match 3 * 2 / 2 = 3 unique tags
}
}
+/* Adds all the tags in 'other' to 'set'. */
+void
+tag_set_union(struct tag_set *set, const struct tag_set *other)
+{
+ size_t i;
+
+ for (i = 0; i < TAG_SET_SIZE; i++) {
+ tag_set_add(set, other->tags[i]);
+ }
+}