]>
Commit | Line | Data |
---|---|---|
064af421 | 1 | /* |
b71273f6 | 2 | * Copyright (c) 2008, 2009, 2010, 2011, 2012, 2013, 2014 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 | #ifndef BITMAP_H | |
18 | #define BITMAP_H 1 | |
19 | ||
20 | #include <limits.h> | |
21 | #include <stdlib.h> | |
22 | #include "util.h" | |
23 | ||
064af421 BP |
24 | static inline unsigned long * |
25 | bitmap_unit__(const unsigned long *bitmap, size_t offset) | |
26 | { | |
ebc56baa | 27 | return CONST_CAST(unsigned long *, &bitmap[offset / BITMAP_ULONG_BITS]); |
064af421 BP |
28 | } |
29 | ||
30 | static inline unsigned long | |
31 | bitmap_bit__(size_t offset) | |
32 | { | |
33 | return 1UL << (offset % BITMAP_ULONG_BITS); | |
34 | } | |
35 | ||
17d18afb BP |
36 | static inline size_t |
37 | bitmap_n_longs(size_t n_bits) | |
38 | { | |
1af1ed85 | 39 | return BITMAP_N_LONGS(n_bits); |
17d18afb BP |
40 | } |
41 | ||
42 | static inline size_t | |
43 | bitmap_n_bytes(size_t n_bits) | |
44 | { | |
45 | return bitmap_n_longs(n_bits) * sizeof(unsigned long int); | |
46 | } | |
47 | ||
064af421 BP |
48 | static inline unsigned long * |
49 | bitmap_allocate(size_t n_bits) | |
50 | { | |
17d18afb | 51 | return xzalloc(bitmap_n_bytes(n_bits)); |
064af421 BP |
52 | } |
53 | ||
795b3288 JR |
54 | /* Initializes bitmap to all-1-bits and returns the bitmap pointer. */ |
55 | static inline unsigned long * | |
56 | bitmap_init1(unsigned long *bitmap, size_t n_bits) | |
57 | { | |
58 | size_t n_longs = bitmap_n_longs(n_bits); | |
59 | size_t n_bytes = bitmap_n_bytes(n_bits); | |
60 | size_t r_bits = n_bits % BITMAP_ULONG_BITS; | |
61 | ||
62 | memset(bitmap, 0xff, n_bytes); | |
63 | if (r_bits) { | |
64 | bitmap[n_longs - 1] >>= BITMAP_ULONG_BITS - r_bits; | |
65 | } | |
66 | return bitmap; | |
67 | } | |
68 | ||
69 | /* Allocates and returns a bitmap initialized to all-1-bits. */ | |
70 | static inline unsigned long * | |
71 | bitmap_allocate1(size_t n_bits) | |
72 | { | |
73 | return bitmap_init1(xmalloc(bitmap_n_bytes(n_bits)), n_bits); | |
74 | } | |
77d895d6 | 75 | |
2a4ae635 BP |
76 | static inline unsigned long * |
77 | bitmap_clone(const unsigned long *bitmap, size_t n_bits) | |
78 | { | |
79 | return xmemdup(bitmap, bitmap_n_bytes(n_bits)); | |
80 | } | |
81 | ||
064af421 BP |
82 | static inline void |
83 | bitmap_free(unsigned long *bitmap) | |
84 | { | |
85 | free(bitmap); | |
86 | } | |
87 | ||
88 | static inline bool | |
89 | bitmap_is_set(const unsigned long *bitmap, size_t offset) | |
90 | { | |
91 | return (*bitmap_unit__(bitmap, offset) & bitmap_bit__(offset)) != 0; | |
92 | } | |
93 | ||
795b3288 | 94 | static inline unsigned long * |
064af421 BP |
95 | bitmap_set1(unsigned long *bitmap, size_t offset) |
96 | { | |
97 | *bitmap_unit__(bitmap, offset) |= bitmap_bit__(offset); | |
795b3288 | 98 | return bitmap; |
064af421 BP |
99 | } |
100 | ||
795b3288 | 101 | static inline unsigned long * |
064af421 BP |
102 | bitmap_set0(unsigned long *bitmap, size_t offset) |
103 | { | |
104 | *bitmap_unit__(bitmap, offset) &= ~bitmap_bit__(offset); | |
795b3288 | 105 | return bitmap; |
064af421 BP |
106 | } |
107 | ||
795b3288 | 108 | static inline unsigned long * |
064af421 BP |
109 | bitmap_set(unsigned long *bitmap, size_t offset, bool value) |
110 | { | |
795b3288 JR |
111 | return (value) ? bitmap_set1(bitmap, offset) : bitmap_set0(bitmap, offset); |
112 | } | |
113 | ||
114 | /* Sets 'n' bits of a single unit. */ | |
115 | static inline void | |
116 | bitmap_set_n__(unsigned long *bitmap, size_t start, size_t n, bool value) | |
117 | { | |
118 | unsigned long mask = ((1UL << n) - 1) << start % BITMAP_ULONG_BITS; | |
119 | ||
064af421 | 120 | if (value) { |
795b3288 | 121 | *bitmap_unit__(bitmap, start) |= mask; |
064af421 | 122 | } else { |
795b3288 JR |
123 | *bitmap_unit__(bitmap, start) &= ~mask; |
124 | } | |
125 | } | |
126 | ||
127 | /* Sets 'count' consecutive bits in 'bitmap', starting at bit offset 'start', | |
128 | * to 'value'. */ | |
129 | static inline unsigned long * | |
130 | bitmap_set_multiple(unsigned long *bitmap, size_t start, size_t count, | |
131 | bool value) | |
132 | { | |
133 | if (count && start % BITMAP_ULONG_BITS) { | |
134 | size_t n = MIN(count, BITMAP_ULONG_BITS - start % BITMAP_ULONG_BITS); | |
135 | ||
136 | bitmap_set_n__(bitmap, start, n, value); | |
137 | count -= n; | |
138 | start += n; | |
139 | } | |
140 | for (; count >= BITMAP_ULONG_BITS; count -= BITMAP_ULONG_BITS) { | |
141 | *bitmap_unit__(bitmap, start) = (unsigned long)!value - 1; | |
142 | start += BITMAP_ULONG_BITS; | |
143 | } | |
144 | if (count) { | |
145 | bitmap_set_n__(bitmap, start, count, value); | |
146 | } | |
147 | return bitmap; | |
148 | } | |
149 | ||
150 | /* Returns the number of 1-bits in the 'n'-bit bitmap at 'bitmap'. */ | |
151 | static inline size_t | |
152 | bitmap_count1(const unsigned long int *bitmap, size_t n) | |
153 | { | |
154 | size_t i; | |
155 | size_t count = 0; | |
156 | ||
157 | BUILD_ASSERT(ULONG_MAX <= UINT64_MAX); | |
158 | for (i = 0; i < BITMAP_N_LONGS(n); i++) { | |
159 | count += count_1bits(bitmap[i]); | |
064af421 | 160 | } |
795b3288 | 161 | return count; |
064af421 BP |
162 | } |
163 | ||
795b3288 JR |
164 | /* "dst &= arg;" for n-bit dst and arg. */ |
165 | static inline unsigned long * | |
166 | bitmap_and(unsigned long *dst, const unsigned long *arg, size_t n) | |
167 | { | |
168 | size_t i; | |
169 | ||
170 | for (i = 0; i < BITMAP_N_LONGS(n); i++) { | |
171 | dst[i] &= arg[i]; | |
172 | } | |
173 | return dst; | |
174 | } | |
175 | ||
176 | /* "dst |= arg;" for n-bit dst and arg. */ | |
177 | static inline unsigned long * | |
178 | bitmap_or(unsigned long *dst, const unsigned long *arg, size_t n) | |
179 | { | |
180 | size_t i; | |
181 | ||
182 | for (i = 0; i < BITMAP_N_LONGS(n); i++) { | |
183 | dst[i] |= arg[i]; | |
184 | } | |
185 | return dst; | |
186 | } | |
187 | ||
188 | /* "dst = ~dst;" for n-bit dst. */ | |
189 | static inline unsigned long * | |
190 | bitmap_not(unsigned long *dst, size_t n) | |
191 | { | |
192 | size_t i; | |
193 | ||
194 | for (i = 0; i < n / BITMAP_ULONG_BITS; i++) { | |
195 | dst[i] = ~dst[i]; | |
196 | } | |
197 | if (n % BITMAP_ULONG_BITS) { | |
198 | dst[i] ^= (1UL << (n % BITMAP_ULONG_BITS)) - 1; | |
199 | } | |
200 | return dst; | |
201 | } | |
7cc48aed | 202 | |
795b3288 JR |
203 | /* Compares the 'n' bits in bitmaps 'a' and 'b'. Returns true if all bits are |
204 | * equal, false otherwise. */ | |
205 | static inline bool | |
206 | bitmap_equal(const unsigned long *a, const unsigned long *b, size_t n) | |
207 | { | |
208 | if (memcmp(a, b, n / BITMAP_ULONG_BITS * sizeof(unsigned long))) { | |
209 | return false; | |
210 | } | |
211 | if (n % BITMAP_ULONG_BITS) { | |
212 | unsigned long mask = (1UL << n % BITMAP_ULONG_BITS) - 1; | |
213 | unsigned long diff = *bitmap_unit__(a, n) ^ *bitmap_unit__(b, n); | |
65d3b0fe | 214 | |
795b3288 JR |
215 | return !(diff & mask); |
216 | } | |
217 | return true; | |
218 | } | |
219 | ||
220 | /* Scans 'bitmap' from bit offset 'start' to 'end', excluding 'end' itself. | |
221 | * Returns the bit offset of the lowest-numbered bit set to 'target', or 'end' | |
222 | * if all of the bits are set to '!target'. 'target' is typically a | |
223 | * compile-time constant, so it makes sense to inline this. Compiler may also | |
224 | * optimize parts away depending on the 'start' and 'end' values passed in. */ | |
225 | static inline size_t | |
226 | bitmap_scan(const unsigned long *bitmap, bool target, size_t start, size_t end) | |
227 | { | |
228 | if (OVS_LIKELY(start < end)) { | |
229 | unsigned long *p, unit; | |
230 | ||
231 | p = bitmap_unit__(bitmap, start); | |
232 | unit = (target ? *p : ~*p) >> (start % BITMAP_ULONG_BITS); | |
233 | if (!unit) { | |
234 | start -= start % BITMAP_ULONG_BITS; /* Round down. */ | |
235 | start += BITMAP_ULONG_BITS; /* Start of the next unit. */ | |
236 | ||
237 | for (; start < end; start += BITMAP_ULONG_BITS) { | |
238 | unit = target ? *++p : ~*++p; | |
239 | if (unit) { | |
240 | goto found; | |
241 | } | |
242 | } | |
243 | return end; | |
244 | } | |
245 | found: | |
246 | start += raw_ctz(unit); /* unit != 0 */ | |
247 | if (OVS_LIKELY(start < end)) { | |
248 | return start; | |
249 | } | |
250 | } | |
251 | return end; | |
252 | } | |
253 | ||
254 | /* Returns true if all of the 'n' bits in 'bitmap' are 0, | |
255 | * false if at least one bit is a 1.*/ | |
256 | static inline bool | |
257 | bitmap_is_all_zeros(const unsigned long *bitmap, size_t n) | |
258 | { | |
259 | return bitmap_scan(bitmap, true, 0, n) == n; | |
260 | } | |
65d3b0fe | 261 | |
795b3288 JR |
262 | #define BITMAP_FOR_EACH_1_RANGE(IDX, BEGIN, END, BITMAP) \ |
263 | for ((IDX) = bitmap_scan(BITMAP, true, BEGIN, END); (IDX) < (END); \ | |
264 | (IDX) = bitmap_scan(BITMAP, true, (IDX) + 1, END)) | |
265 | #define BITMAP_FOR_EACH_1(IDX, SIZE, BITMAP) \ | |
266 | BITMAP_FOR_EACH_1_RANGE(IDX, 0, SIZE, BITMAP) | |
064af421 | 267 | |
3ee6026a JG |
268 | /* More efficient access to a map of single ullong. */ |
269 | #define ULLONG_FOR_EACH_1(IDX, MAP) \ | |
270 | for (uint64_t map__ = (MAP); \ | |
52a524eb JR |
271 | map__ && (((IDX) = raw_ctz(map__)), true); \ |
272 | map__ = zero_rightmost_1bit(map__)) | |
273 | ||
3ee6026a JG |
274 | #define ULLONG_SET0(MAP, OFFSET) ((MAP) &= ~(1ULL << (OFFSET))) |
275 | #define ULLONG_SET1(MAP, OFFSET) ((MAP) |= 1ULL << (OFFSET)) | |
52a524eb | 276 | |
1cb20095 JG |
277 | /* Returns the value of a bit in a map as a bool. */ |
278 | #define ULLONG_GET(MAP, OFFSET) !!((MAP) & (1ULL << (OFFSET))) | |
279 | ||
064af421 | 280 | #endif /* bitmap.h */ |