]>
Commit | Line | Data |
---|---|---|
064af421 BP |
1 | /* |
2 | * Copyright (c) 2008, 2009 Nicira Networks. | |
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); | |
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 |