lib/tag.c

   1 /*
   2  * Copyright (c) 2008, 2009, 2010, 2011 Nicira, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include <config.h>
  18 #include "tag.h"
  19 #include <limits.h>
  20 #include "random.h"
  21 #include "type-props.h"
  22 #include "util.h"
  23
  24 #define N_TAG_BITS (CHAR_BIT * sizeof(tag_type))
  25 BUILD_ASSERT_DECL(IS_POW2(N_TAG_BITS));
  26
  27 #define LOG2_N_TAG_BITS (N_TAG_BITS == 32 ? 5 : N_TAG_BITS == 64 ? 6 : 0)
  28 BUILD_ASSERT_DECL(LOG2_N_TAG_BITS > 0);
  29
  30 /* Returns a randomly selected tag. */
  31 tag_type
  32 tag_create_random(void)
  33 {
  34     int x, y;
  35     do {
  36         uint16_t r = random_uint16();
  37         x = r & (N_TAG_BITS - 1);
  38         y = r >> (16 - LOG2_N_TAG_BITS);
  39     } while (x == y);
  40     return (1u << x) | (1u << y);
  41 }
  42
  43 /* Returns a tag deterministically generated from 'seed'.
  44  *
  45  * 'seed' should have data in all of its bits; if it has data only in its
  46  * low-order bits then the resulting tags will be poorly distributed.  Use a
  47  * hash function such as hash_bytes() to generate 'seed' if necessary. */
  48 tag_type
  49 tag_create_deterministic(uint32_t seed)
  50 {
  51     int x = seed & (N_TAG_BITS - 1);
  52     int y = (seed >> LOG2_N_TAG_BITS) % (N_TAG_BITS - 1);
  53     y += y >= x;
  54     return (1u << x) | (1u << y);
  55 }
  56
  57 /* Initializes 'set' as an empty tag set. */
  58 void
  59 tag_set_init(struct tag_set *set)
  60 {
  61     memset(set, 0, sizeof *set);
  62 }
  63
  64 static bool
  65 tag_is_worth_adding(const struct tag_set *set, tag_type tag)
  66 {
  67     if (!tag) {
  68         /* Nothing to add. */
  69         return false;
  70     } else if ((set->total & tag) != tag) {
  71         /* 'set' doesn't have all the bits in 'tag', so we need to add it. */
  72         return true;
  73     } else {
  74         /* We can drop it if some member of 'set' already includes all of the
  75          * 1-bits in 'tag'.  (tag_set_intersects() does a different test:
  76          * whether some member of 'set' has at least two 1-bit in common with
  77          * 'tag'.) */
  78         int i;
  79
  80         for (i = 0; i < TAG_SET_SIZE; i++) {
  81             if ((set->tags[i] & tag) == tag) {
  82                 return false;
  83             }
  84         }
  85         return true;
  86     }
  87 }
  88
  89 /* Adds 'tag' to 'set'. */
  90 void
  91 tag_set_add(struct tag_set *set, tag_type tag)
  92 {
  93     if (tag_is_worth_adding(set, tag)) {
  94         /* XXX We could do better by finding the set member to which we would
  95          * add the fewest number of 1-bits.  This would reduce the amount of
  96          * ambiguity, since e.g. three 1-bits match 3 * 2 / 2 = 3 unique tags
  97          * whereas four 1-bits match 4 * 3 / 2 = 6 unique tags. */
  98         tag_type *t = &set->tags[set->n++ % TAG_SET_SIZE];
  99         *t |= tag;
 100         if (*t == TYPE_MAXIMUM(tag_type)) {
 101             set->tags[0] = *t;
 102         }
 103
 104         set->total |= tag;
 105     }
 106 }
 107
 108 /* Adds all the tags in 'other' to 'set'. */
 109 void
 110 tag_set_union(struct tag_set *set, const struct tag_set *other)
 111 {
 112     size_t i;
 113
 114     for (i = 0; i < TAG_SET_SIZE; i++) {
 115         tag_set_add(set, other->tags[i]);
 116     }
 117 }