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