]>
Commit | Line | Data |
---|---|---|
064af421 | 1 | /* |
e0edde6f | 2 | * Copyright (c) 2008, 2009, 2010, 2011 Nicira, Inc. |
064af421 | 3 | * |
a14bc59f BP |
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: | |
064af421 | 7 | * |
a14bc59f BP |
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. | |
064af421 BP |
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); | |
c3930478 | 52 | int y = (seed >> LOG2_N_TAG_BITS) % (N_TAG_BITS - 1); |
064af421 BP |
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 | ||
d12f7113 BP |
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 | ||
064af421 BP |
89 | /* Adds 'tag' to 'set'. */ |
90 | void | |
91 | tag_set_add(struct tag_set *set, tag_type tag) | |
92 | { | |
d12f7113 | 93 | if (tag_is_worth_adding(set, tag)) { |
064af421 BP |
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 | ||
1e2e7110 BP |
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 | } |