lib/tag.c

   1 /*
   2  * Copyright (c) 2008, 2009 Nicira Networks.
   3  *
   4  * Permission to use, copy, modify, and/or distribute this software for any
   5  * purpose with or without fee is hereby granted, provided that the above
   6  * copyright notice and this permission notice appear in all copies.
   7  *
   8  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
   9  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  10  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  11  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  12  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  13  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  14  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  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) % 31;
  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 /* Adds 'tag' to 'set'. */
  65 void
  66 tag_set_add(struct tag_set *set, tag_type tag)
  67 {
  68     if (tag && (!tag_is_valid(tag) || !tag_set_intersects(set, tag))) {
  69         /* XXX We could do better by finding the set member to which we would
  70          * add the fewest number of 1-bits.  This would reduce the amount of
  71          * ambiguity, since e.g. three 1-bits match 3 * 2 / 2 = 3 unique tags
  72          * whereas four 1-bits match 4 * 3 / 2 = 6 unique tags. */
  73         tag_type *t = &set->tags[set->n++ % TAG_SET_SIZE];
  74         *t |= tag;
  75         if (*t == TYPE_MAXIMUM(tag_type)) {
  76             set->tags[0] = *t;
  77         }
  78
  79         set->total |= tag;
  80     }
  81 }
  82