Branch data Line data Source code
1 : : /*
2 : : * Copyright (c) 2008, 2009, 2010, 2011, 2012, 2013, 2014 Nicira, Inc.
3 : : *
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:
7 : : *
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.
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 : : static inline unsigned long *
25 : 14924032 : bitmap_unit__(const unsigned long *bitmap, size_t offset)
26 : : {
27 : 14924032 : return CONST_CAST(unsigned long *, &bitmap[offset / BITMAP_ULONG_BITS]);
28 : : }
29 : :
30 : : static inline unsigned long
31 : 13461440 : bitmap_bit__(size_t offset)
32 : : {
33 : 13461440 : return 1UL << (offset % BITMAP_ULONG_BITS);
34 : : }
35 : :
36 : : static inline size_t
37 : 202750 : bitmap_n_longs(size_t n_bits)
38 : : {
39 : 202750 : return BITMAP_N_LONGS(n_bits);
40 : : }
41 : :
42 : : static inline size_t
43 : 202748 : bitmap_n_bytes(size_t n_bits)
44 : : {
45 : 202748 : return bitmap_n_longs(n_bits) * sizeof(unsigned long int);
46 : : }
47 : :
48 : : static inline unsigned long *
49 : 86943 : bitmap_allocate(size_t n_bits)
50 : : {
51 : 86943 : return xzalloc(bitmap_n_bytes(n_bits));
52 : : }
53 : :
54 : : /* Initializes bitmap to all-1-bits and returns the bitmap pointer. */
55 : : static inline unsigned long *
56 : 2 : bitmap_init1(unsigned long *bitmap, size_t n_bits)
57 : : {
58 : 2 : size_t n_longs = bitmap_n_longs(n_bits);
59 : 2 : size_t n_bytes = bitmap_n_bytes(n_bits);
60 : 2 : size_t r_bits = n_bits % BITMAP_ULONG_BITS;
61 : :
62 : 2 : memset(bitmap, 0xff, n_bytes);
63 [ - + ]: 2 : if (r_bits) {
64 : 0 : bitmap[n_longs - 1] >>= BITMAP_ULONG_BITS - r_bits;
65 : : }
66 : 2 : return bitmap;
67 : : }
68 : :
69 : : /* Allocates and returns a bitmap initialized to all-1-bits. */
70 : : static inline unsigned long *
71 : 2 : bitmap_allocate1(size_t n_bits)
72 : : {
73 : 2 : return bitmap_init1(xmalloc(bitmap_n_bytes(n_bits)), n_bits);
74 : : }
75 : :
76 : : static inline unsigned long *
77 : 6 : bitmap_clone(const unsigned long *bitmap, size_t n_bits)
78 : : {
79 : 6 : return xmemdup(bitmap, bitmap_n_bytes(n_bits));
80 : : }
81 : :
82 : : static inline void
83 : 5598 : bitmap_free(unsigned long *bitmap)
84 : : {
85 : 5598 : free(bitmap);
86 : 5598 : }
87 : :
88 : : static inline bool
89 : 6285160 : bitmap_is_set(const unsigned long *bitmap, size_t offset)
90 : : {
91 : 6285160 : return (*bitmap_unit__(bitmap, offset) & bitmap_bit__(offset)) != 0;
92 : : }
93 : :
94 : : static inline unsigned long *
95 : 7176177 : bitmap_set1(unsigned long *bitmap, size_t offset)
96 : : {
97 : 7176177 : *bitmap_unit__(bitmap, offset) |= bitmap_bit__(offset);
98 : 7176177 : return bitmap;
99 : : }
100 : :
101 : : static inline unsigned long *
102 : 103 : bitmap_set0(unsigned long *bitmap, size_t offset)
103 : : {
104 : 103 : *bitmap_unit__(bitmap, offset) &= ~bitmap_bit__(offset);
105 : 103 : return bitmap;
106 : : }
107 : :
108 : : static inline unsigned long *
109 : : bitmap_set(unsigned long *bitmap, size_t offset, bool value)
110 : : {
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 : 28772 : bitmap_set_n__(unsigned long *bitmap, size_t start, size_t n, bool value)
117 : : {
118 : 28772 : unsigned long mask = ((1UL << n) - 1) << start % BITMAP_ULONG_BITS;
119 : :
120 [ + + ]: 28772 : if (value) {
121 : 28743 : *bitmap_unit__(bitmap, start) |= mask;
122 : : } else {
123 : 29 : *bitmap_unit__(bitmap, start) &= ~mask;
124 : : }
125 : 28772 : }
126 : :
127 : : /* Sets 'count' consecutive bits in 'bitmap', starting at bit offset 'start',
128 : : * to 'value'. */
129 : : static inline unsigned long *
130 : 28775 : bitmap_set_multiple(unsigned long *bitmap, size_t start, size_t count,
131 : : bool value)
132 : : {
133 [ + + ][ + + ]: 28775 : if (count && start % BITMAP_ULONG_BITS) {
134 : 9711 : size_t n = MIN(count, BITMAP_ULONG_BITS - start % BITMAP_ULONG_BITS);
135 : :
136 : 9711 : bitmap_set_n__(bitmap, start, n, value);
137 : 9711 : count -= n;
138 : 9711 : start += n;
139 : : }
140 [ + + ]: 28796 : for (; count >= BITMAP_ULONG_BITS; count -= BITMAP_ULONG_BITS) {
141 : 21 : *bitmap_unit__(bitmap, start) = (unsigned long)!value - 1;
142 : 21 : start += BITMAP_ULONG_BITS;
143 : : }
144 [ + + ]: 28775 : if (count) {
145 : 19061 : bitmap_set_n__(bitmap, start, count, value);
146 : : }
147 : 28775 : return bitmap;
148 : : }
149 : :
150 : : /* Returns the number of 1-bits in the 'n'-bit bitmap at 'bitmap'. */
151 : : static inline size_t
152 : 38179 : bitmap_count1(const unsigned long int *bitmap, size_t n)
153 : : {
154 : : size_t i;
155 : 38179 : size_t count = 0;
156 : :
157 : : BUILD_ASSERT(ULONG_MAX <= UINT64_MAX);
158 [ + + ]: 114555 : for (i = 0; i < BITMAP_N_LONGS(n); i++) {
159 : 76376 : count += count_1bits(bitmap[i]);
160 : : }
161 : 38179 : return count;
162 : : }
163 : :
164 : : /* "dst &= arg;" for n-bit dst and arg. */
165 : : static inline unsigned long *
166 : 1017 : bitmap_and(unsigned long *dst, const unsigned long *arg, size_t n)
167 : : {
168 : : size_t i;
169 : :
170 [ + + ]: 4068 : for (i = 0; i < BITMAP_N_LONGS(n); i++) {
171 : 3051 : dst[i] &= arg[i];
172 : : }
173 : 1017 : return dst;
174 : : }
175 : :
176 : : /* "dst |= arg;" for n-bit dst and arg. */
177 : : static inline unsigned long *
178 : 4067 : bitmap_or(unsigned long *dst, const unsigned long *arg, size_t n)
179 : : {
180 : : size_t i;
181 : :
182 [ + + ]: 16268 : for (i = 0; i < BITMAP_N_LONGS(n); i++) {
183 : 12201 : dst[i] |= arg[i];
184 : : }
185 : 4067 : return dst;
186 : : }
187 : :
188 : : /* "dst = ~dst;" for n-bit dst. */
189 : : static inline unsigned long *
190 : 762 : bitmap_not(unsigned long *dst, size_t n)
191 : : {
192 : : size_t i;
193 : :
194 [ + + ]: 2286 : for (i = 0; i < n / BITMAP_ULONG_BITS; i++) {
195 : 1524 : dst[i] = ~dst[i];
196 : : }
197 [ + - ]: 762 : if (n % BITMAP_ULONG_BITS) {
198 : 762 : dst[i] ^= (1UL << (n % BITMAP_ULONG_BITS)) - 1;
199 : : }
200 : 762 : return dst;
201 : : }
202 : :
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 : 45274 : bitmap_equal(const unsigned long *a, const unsigned long *b, size_t n)
207 : : {
208 [ + + ]: 45274 : if (memcmp(a, b, n / BITMAP_ULONG_BITS * sizeof(unsigned long))) {
209 : 1477 : return false;
210 : : }
211 [ + + ]: 43797 : if (n % BITMAP_ULONG_BITS) {
212 : 43795 : unsigned long mask = (1UL << n % BITMAP_ULONG_BITS) - 1;
213 : 43795 : unsigned long diff = *bitmap_unit__(a, n) ^ *bitmap_unit__(b, n);
214 : :
215 : 43795 : return !(diff & mask);
216 : : }
217 : 2 : 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 : 1370979 : bitmap_scan(const unsigned long *bitmap, bool target, size_t start, size_t end)
227 : : {
228 [ + + ]: 1370979 : if (OVS_LIKELY(start < end)) {
229 : : unsigned long *p, unit;
230 : :
231 : 1346209 : p = bitmap_unit__(bitmap, start);
232 [ + + ]: 1346209 : unit = (target ? *p : ~*p) >> (start % BITMAP_ULONG_BITS);
233 [ + + ]: 1346209 : if (!unit) {
234 : 142387 : start -= start % BITMAP_ULONG_BITS; /* Round down. */
235 : 142387 : start += BITMAP_ULONG_BITS; /* Start of the next unit. */
236 : :
237 [ + + ]: 160233 : for (; start < end; start += BITMAP_ULONG_BITS) {
238 [ + + ]: 21837 : unit = target ? *++p : ~*++p;
239 [ + + ]: 21837 : if (unit) {
240 : 3991 : goto found;
241 : : }
242 : : }
243 : 138396 : return end;
244 : : }
245 : : found:
246 : 1207813 : start += raw_ctz(unit); /* unit != 0 */
247 [ + + ]: 1207813 : if (OVS_LIKELY(start < end)) {
248 : 1207812 : return start;
249 : : }
250 : : }
251 : 24771 : 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 : 51957 : bitmap_is_all_zeros(const unsigned long *bitmap, size_t n)
258 : : {
259 : 51957 : return bitmap_scan(bitmap, true, 0, n) == n;
260 : : }
261 : :
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)
267 : :
268 : : /* More efficient access to a map of single ullong. */
269 : : #define ULLONG_FOR_EACH_1(IDX, MAP) \
270 : : for (uint64_t map__ = (MAP); \
271 : : map__ && (((IDX) = raw_ctz(map__)), true); \
272 : : map__ = zero_rightmost_1bit(map__))
273 : :
274 : : #define ULLONG_SET0(MAP, OFFSET) ((MAP) &= ~(1ULL << (OFFSET)))
275 : : #define ULLONG_SET1(MAP, OFFSET) ((MAP) |= 1ULL << (OFFSET))
276 : :
277 : : /* Returns the value of a bit in a map as a bool. */
278 : : #define ULLONG_GET(MAP, OFFSET) !!((MAP) & (1ULL << (OFFSET)))
279 : :
280 : : #endif /* bitmap.h */
|
