Line data Source code
1 : /*
2 : * Copyright (c) 2015 Cisco and/or its affiliates.
3 : * Licensed under the Apache License, Version 2.0 (the "License");
4 : * you may not use this file except in compliance with the License.
5 : * You may obtain a copy of the License at:
6 : *
7 : * http://www.apache.org/licenses/LICENSE-2.0
8 : *
9 : * Unless required by applicable law or agreed to in writing, software
10 : * distributed under the License is distributed on an "AS IS" BASIS,
11 : * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 : * See the License for the specific language governing permissions and
13 : * limitations under the License.
14 : */
15 : /*
16 : Copyright (c) 2001, 2002, 2003, 2005 Eliot Dresselhaus
17 :
18 : Permission is hereby granted, free of charge, to any person obtaining
19 : a copy of this software and associated documentation files (the
20 : "Software"), to deal in the Software without restriction, including
21 : without limitation the rights to use, copy, modify, merge, publish,
22 : distribute, sublicense, and/or sell copies of the Software, and to
23 : permit persons to whom the Software is furnished to do so, subject to
24 : the following conditions:
25 :
26 : The above copyright notice and this permission notice shall be
27 : included in all copies or substantial portions of the Software.
28 :
29 : THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
30 : EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
31 : MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
32 : NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
33 : LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
34 : OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
35 : WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
36 : */
37 :
38 : #ifndef included_clib_bitmap_h
39 : #define included_clib_bitmap_h
40 :
41 : /** \file
42 : Bitmaps built as vectors of machine words
43 : */
44 :
45 : #include <vppinfra/vec.h>
46 : #include <vppinfra/random.h>
47 : #include <vppinfra/error.h>
48 :
49 : typedef uword clib_bitmap_t;
50 :
51 : /** predicate function; is an entire bitmap empty?
52 : @param ai - pointer to a bitmap
53 : @returns 1 if the entire bitmap is zero, 0 otherwise
54 : */
55 : always_inline uword
56 6042049 : clib_bitmap_is_zero (uword * ai)
57 : {
58 : uword i;
59 6963479 : for (i = 0; i < vec_len (ai); i++)
60 5650636 : if (ai[i] != 0)
61 4729206 : return 0;
62 1312841 : return 1;
63 : }
64 :
65 : /** predicate function; are two bitmaps equal?
66 : @param a - pointer to a bitmap
67 : @param b - pointer to a bitmap
68 : @returns 1 if the bitmaps are equal, 0 otherwise
69 : */
70 : always_inline uword
71 : clib_bitmap_is_equal (uword * a, uword * b)
72 : {
73 : uword i;
74 : if (vec_len (a) != vec_len (b))
75 : return 0;
76 : for (i = 0; i < vec_len (a); i++)
77 : if (a[i] != b[i])
78 : return 0;
79 : return 1;
80 : }
81 :
82 : /** Duplicate a bitmap
83 : @param v - pointer to a bitmap
84 : @returns a duplicate of the bitmap
85 : */
86 : #define clib_bitmap_dup(v) vec_dup(v)
87 :
88 : /** Free a bitmap
89 : @param v - pointer to the bitmap to free
90 : */
91 : #define clib_bitmap_free(v) vec_free(v)
92 :
93 : /** Number of bytes in a bitmap
94 : @param v - pointer to the bitmap
95 : */
96 : #define clib_bitmap_bytes(v) vec_bytes(v)
97 :
98 : /** Clear a bitmap
99 : @param v - pointer to the bitmap to clear
100 : */
101 : #define clib_bitmap_zero(v) vec_zero(v)
102 :
103 : /** Allocate a bitmap with the supplied number of bits
104 : @param [out] v - the resulting bitmap
105 : @param n_bits - the required number of bits
106 : */
107 :
108 : #define clib_bitmap_alloc(v,n_bits) \
109 : v = vec_new (uword, ((n_bits) + BITS (uword) - 1) / BITS (uword))
110 :
111 : #define clib_bitmap_vec_validate(v,i) vec_validate_aligned((v),(i),sizeof(uword))
112 :
113 : /* Make sure that a bitmap is at least n_bits in size */
114 : #define clib_bitmap_validate(v,n_bits) \
115 : clib_bitmap_vec_validate ((v), ((n_bits) - 1) / BITS (uword))
116 :
117 : /** Copy a bitmap
118 : @param dst - copy to
119 : @param src - copy from
120 : */
121 : static_always_inline void
122 : clib_bitmap_copy (clib_bitmap_t **dst, const clib_bitmap_t *src)
123 : {
124 : if (vec_len (src))
125 : {
126 : clib_bitmap_vec_validate (*dst, vec_len (src) - 1);
127 : vec_copy (*dst, src);
128 : }
129 : else
130 : {
131 : vec_reset_length (*dst);
132 : }
133 : }
134 :
135 : /* low-level routine to remove trailing zeros from a bitmap */
136 : always_inline uword *
137 91149257 : _clib_bitmap_remove_trailing_zeros (uword * a)
138 : {
139 : word i;
140 91149257 : if (a)
141 : {
142 104888600 : for (i = _vec_len (a) - 1; i >= 0; i--)
143 102737538 : if (a[i] != 0)
144 88998195 : break;
145 91149257 : vec_set_len (a, i + 1);
146 : }
147 91149257 : return a;
148 : }
149 :
150 : /** Sets the ith bit of a bitmap to new_value.
151 : No sanity checking. Be careful.
152 : @param a - pointer to the bitmap
153 : @param i - the bit position to interrogate
154 : @param new_value - new value for the bit
155 : @returns the old value of the bit
156 : */
157 : always_inline uword
158 5380019 : clib_bitmap_set_no_check (uword * a, uword i, uword new_value)
159 : {
160 5380019 : uword i0 = i / BITS (a[0]);
161 5380019 : uword i1 = i % BITS (a[0]);
162 5380019 : uword bit = (uword) 1 << i1;
163 : uword ai, old_value;
164 :
165 : /* Removed ASSERT since uword * a may not be a vector. */
166 : /* ASSERT (i0 < vec_len (a)); */
167 :
168 5380019 : ai = a[i0];
169 5380019 : old_value = (ai & bit) != 0;
170 5380019 : ai &= ~bit;
171 5380019 : ai |= ((uword) (new_value != 0)) << i1;
172 5380019 : a[i0] = ai;
173 5380019 : return old_value;
174 : }
175 :
176 : /** Sets the ith bit of a bitmap to new_value
177 : Removes trailing zeros from the bitmap
178 : @param ai - pointer to the bitmap
179 : @param i - the bit position to interrogate
180 : @param value - new value for the bit
181 : @returns the (possibly reallocated) bitmap object pointer
182 : */
183 : always_inline uword *
184 767431101 : clib_bitmap_set (uword * ai, uword i, uword value)
185 : {
186 767431101 : uword i0 = i / BITS (ai[0]);
187 767431101 : uword i1 = i % BITS (ai[0]);
188 : uword a;
189 :
190 : /* Check for writing a zero to beyond end of bitmap. */
191 767431101 : if (value == 0 && i0 >= vec_len (ai))
192 660161199 : return ai; /* Implied trailing zeros. */
193 :
194 107268902 : clib_bitmap_vec_validate (ai, i0);
195 :
196 107269902 : a = ai[i0];
197 107269902 : a &= ~((uword) 1 << i1);
198 107269902 : a |= ((uword) (value != 0)) << i1;
199 107269902 : ai[i0] = a;
200 :
201 : /* If bits have been cleared, test for zero. */
202 107269902 : if (a == 0)
203 90679222 : ai = _clib_bitmap_remove_trailing_zeros (ai);
204 :
205 107269902 : return ai;
206 : }
207 :
208 : always_inline u8
209 4 : clib_bitmap_will_expand (uword *ai, uword i)
210 : {
211 4 : return (i / BITS (ai[0])) >= vec_max_len (ai);
212 : }
213 :
214 : /** Gets the ith bit value from a bitmap
215 : @param ai - pointer to the bitmap
216 : @param i - the bit position to interrogate
217 : @returns the indicated bit value
218 : */
219 : always_inline uword
220 2463173411 : clib_bitmap_get (uword * ai, uword i)
221 : {
222 2463173411 : uword i0 = i / BITS (ai[0]);
223 2463173411 : uword i1 = i % BITS (ai[0]);
224 2463173411 : return i0 < vec_len (ai) && 0 != ((ai[i0] >> i1) & 1);
225 : }
226 :
227 : /** Gets the ith bit value from a bitmap
228 : Does not sanity-check the bit position. Be careful.
229 : @param ai - pointer to the bitmap
230 : @param i - the bit position to interrogate
231 : @returns the indicated bit value, or garbage if the bit position is
232 : out of range.
233 : */
234 : always_inline uword
235 2392603 : clib_bitmap_get_no_check (uword * ai, uword i)
236 : {
237 2392603 : uword i0 = i / BITS (ai[0]);
238 2392603 : uword i1 = i % BITS (ai[0]);
239 2392603 : return 0 != ((ai[i0] >> i1) & 1);
240 : }
241 :
242 : always_inline uword
243 : clib_bitmap_get_multiple_no_check (uword * ai, uword i, uword n_bits)
244 : {
245 : uword i0 = i / BITS (ai[0]);
246 : uword i1 = i % BITS (ai[0]);
247 : ASSERT (i1 + n_bits <= BITS (uword));
248 : return 0 != ((ai[i0] >> i1) & pow2_mask (n_bits));
249 : }
250 :
251 : /** Gets the ith through ith + n_bits bit values from a bitmap
252 : @param bitmap - pointer to the bitmap
253 : @param i - the first bit position to retrieve
254 : @param n_bits - the number of bit positions to retrieve
255 : @returns the indicated range of bits
256 : */
257 : always_inline uword
258 960 : clib_bitmap_get_multiple (uword * bitmap, uword i, uword n_bits)
259 : {
260 : uword i0, i1, result;
261 960 : uword l = vec_len (bitmap);
262 :
263 960 : ASSERT (n_bits <= BITS (result));
264 :
265 960 : i0 = i / BITS (bitmap[0]);
266 960 : i1 = i % BITS (bitmap[0]);
267 :
268 : /* Check first word. */
269 960 : result = 0;
270 960 : if (i0 < l)
271 : {
272 960 : result |= (bitmap[i0] >> i1);
273 960 : if (n_bits < BITS (bitmap[0]))
274 960 : result &= (((uword) 1 << n_bits) - 1);
275 : }
276 :
277 : /* Check for overlap into next word. */
278 960 : i0++;
279 960 : if (i1 + n_bits > BITS (bitmap[0]) && i0 < l)
280 : {
281 0 : n_bits -= BITS (bitmap[0]) - i1;
282 0 : result |=
283 0 : (bitmap[i0] & (((uword) 1 << n_bits) - 1)) << (BITS (bitmap[0]) - i1);
284 : }
285 :
286 960 : return result;
287 : }
288 :
289 : /** sets the ith through ith + n_bits bits in a bitmap
290 : @param bitmap - pointer to the bitmap
291 : @param i - the first bit position to retrieve
292 : @param value - the values to set
293 : @param n_bits - the number of bit positions to set
294 : @returns a pointer to the updated bitmap, which may expand and move
295 : */
296 :
297 : always_inline uword *
298 5 : clib_bitmap_set_multiple (uword * bitmap, uword i, uword value, uword n_bits)
299 : {
300 : uword i0, i1, l, t, m;
301 :
302 5 : ASSERT (n_bits <= BITS (value));
303 :
304 5 : i0 = i / BITS (bitmap[0]);
305 5 : i1 = i % BITS (bitmap[0]);
306 :
307 : /* Allocate bitmap. */
308 5 : clib_bitmap_vec_validate (bitmap, (i + n_bits - 1) / BITS (bitmap[0]));
309 5 : l = vec_len (bitmap);
310 :
311 5 : m = ~0;
312 5 : if (n_bits < BITS (value))
313 1 : m = (((uword) 1 << n_bits) - 1);
314 5 : value &= m;
315 :
316 : /* Insert into first word. */
317 5 : t = bitmap[i0];
318 5 : t &= ~(m << i1);
319 5 : t |= value << i1;
320 5 : bitmap[i0] = t;
321 :
322 : /* Insert into second word. */
323 5 : i0++;
324 5 : if (i1 + n_bits > BITS (bitmap[0]) && i0 < l)
325 : {
326 3 : t = BITS (bitmap[0]) - i1;
327 3 : value >>= t;
328 3 : n_bits -= t;
329 3 : t = bitmap[i0];
330 3 : m = ((uword) 1 << n_bits) - 1;
331 3 : t &= ~m;
332 3 : t |= value;
333 3 : bitmap[i0] = t;
334 : }
335 :
336 5 : return bitmap;
337 : }
338 :
339 : always_inline uword *
340 578 : clib_bitmap_set_region (uword * bitmap, uword i, uword value, uword n_bits)
341 : {
342 : uword a0, a1, b0, b1;
343 : uword i_end, mask;
344 :
345 578 : a0 = i / BITS (bitmap[0]);
346 578 : a1 = i % BITS (bitmap[0]);
347 :
348 578 : i_end = i + n_bits - 1;
349 578 : b0 = i_end / BITS (bitmap[0]);
350 578 : b1 = i_end % BITS (bitmap[0]);
351 :
352 578 : clib_bitmap_vec_validate (bitmap, b0);
353 :
354 : /* First word. */
355 578 : mask = n_bits < BITS (bitmap[0]) ? pow2_mask (n_bits) : ~0;
356 578 : mask <<= a1;
357 :
358 578 : if (value)
359 577 : bitmap[a0] |= mask;
360 : else
361 1 : bitmap[a0] &= ~mask;
362 :
363 590 : for (a0++; a0 < b0; a0++)
364 12 : bitmap[a0] = value ? ~0 : 0;
365 :
366 578 : if (a0 == b0)
367 : {
368 2 : mask = (uword) ~0 >> (BITS (bitmap[0]) - b1 - 1);
369 2 : if (value)
370 2 : bitmap[a0] |= mask;
371 : else
372 0 : bitmap[a0] &= ~mask;
373 : }
374 :
375 578 : return bitmap;
376 : }
377 :
378 : /** Macro to iterate across set bits in a bitmap
379 :
380 : @param i - the current set bit
381 : @param ai - the bitmap
382 : @param body - the expression to evaluate for each set bit
383 : */
384 : #define clib_bitmap_foreach(i,ai) \
385 : if (ai) \
386 : for (i = clib_bitmap_first_set (ai); \
387 : i != ~0; \
388 : i = clib_bitmap_next_set (ai, i + 1))
389 :
390 : /** Return the lowest numbered set bit in a bitmap
391 : @param ai - pointer to the bitmap
392 : @returns lowest numbered set bit, or ~0 if the entire bitmap is zero
393 : */
394 : always_inline uword
395 57532526 : clib_bitmap_first_set (uword * ai)
396 : {
397 57532526 : uword i = 0;
398 : #if uword_bits == 64
399 : #if defined(CLIB_HAVE_VEC256)
400 3084 : while (i + 7 < vec_len (ai))
401 : {
402 : u64x4 v;
403 0 : v = u64x4_load_unaligned (ai + i) | u64x4_load_unaligned (ai + i + 4);
404 0 : if (!u64x4_is_all_zero (v))
405 0 : break;
406 0 : i += 8;
407 : }
408 : #elif defined(CLIB_HAVE_VEC128) && defined(CLIB_HAVE_VEC128_UNALIGNED_LOAD_STORE)
409 58031345 : while (i + 3 < vec_len (ai))
410 : {
411 : u64x2 v;
412 852548 : v = u64x2_load_unaligned (ai + i) | u64x2_load_unaligned (ai + i + 2);
413 852548 : if (!u64x2_is_all_zero (v))
414 350644 : break;
415 501904 : i += 4;
416 : }
417 : #endif
418 : #endif
419 78016538 : for (; i < vec_len (ai); i++)
420 : {
421 57753232 : uword x = ai[i];
422 57753232 : if (x != 0)
423 37269322 : return i * BITS (ai[0]) + log2_first_set (x);
424 : }
425 20263203 : return ~0;
426 : }
427 :
428 : /** Return the higest numbered set bit in a bitmap
429 : @param ai - pointer to the bitmap
430 : @returns lowest numbered set bit, or ~0 if the entire bitmap is zero
431 : */
432 : always_inline uword
433 1878603 : clib_bitmap_last_set (uword * ai)
434 : {
435 : uword i;
436 :
437 3218043 : for (i = vec_len (ai); i > 0; i--)
438 : {
439 1878603 : uword x = ai[i - 1];
440 1878603 : if (x != 0)
441 : {
442 : uword first_bit;
443 539161 : first_bit = count_leading_zeros (x);
444 539161 : return (i) * BITS (ai[0]) - first_bit - 1;
445 : }
446 : }
447 1339440 : return ~0;
448 : }
449 :
450 : /** Return the lowest numbered clear bit in a bitmap
451 : @param ai - pointer to the bitmap
452 : @returns lowest numbered clear bit
453 : */
454 : always_inline uword
455 158448899 : clib_bitmap_first_clear (uword * ai)
456 : {
457 : uword i;
458 158449772 : for (i = 0; i < vec_len (ai); i++)
459 : {
460 158216391 : uword x = ~ai[i];
461 158216391 : if (x != 0)
462 158215518 : return i * BITS (ai[0]) + log2_first_set (x);
463 : }
464 233205 : return i * BITS (ai[0]);
465 : }
466 :
467 : /** Return the number of set bits in a bitmap
468 : @param ai - pointer to the bitmap
469 : @returns the number of set bits in the bitmap
470 : */
471 : always_inline uword
472 974271 : clib_bitmap_count_set_bits (uword * ai)
473 : {
474 : uword i;
475 974271 : uword n_set = 0;
476 2128855 : for (i = 0; i < vec_len (ai); i++)
477 1154584 : n_set += count_set_bits (ai[i]);
478 974271 : return n_set;
479 : }
480 :
481 : /** Logical operator across two bitmaps
482 :
483 : @param ai - pointer to the destination bitmap
484 : @param bi - pointer to the source bitmap
485 : @returns ai = ai and bi. ai is modified, bi is not modified
486 : */
487 : always_inline uword *clib_bitmap_and (uword * ai, uword * bi);
488 :
489 : /** Logical operator across two bitmaps
490 :
491 : @param ai - pointer to the destination bitmap
492 : @param bi - pointer to the source bitmap
493 : @returns ai = ai & ~bi. ai is modified, bi is not modified
494 : */
495 : always_inline uword *clib_bitmap_andnot (uword * ai, uword * bi);
496 :
497 : /** Logical operator across two bitmaps
498 :
499 : @param ai - pointer to the destination bitmap
500 : @param bi - pointer to the source bitmap
501 : @returns ai = ai & ~bi. ai is modified, bi is not modified
502 : */
503 : always_inline uword *clib_bitmap_or (uword * ai, uword * bi);
504 : /** Logical operator across two bitmaps
505 :
506 : @param ai - pointer to the destination bitmap
507 : @param bi - pointer to the source bitmap
508 : @returns ai = ai or bi. ai is modified, bi is not modified
509 : */
510 : always_inline uword *clib_bitmap_or (uword * ai, uword * bi);
511 :
512 : /** Logical operator across two bitmaps
513 :
514 : @param ai - pointer to the destination bitmap
515 : @param bi - pointer to the source bitmap
516 : @returns ai = ai xor bi. ai is modified, bi is not modified
517 : */
518 : always_inline uword *clib_bitmap_xor (uword * ai, uword * bi);
519 :
520 : /* ALU function definition macro for functions taking two bitmaps. */
521 : #define _(name, body, check_zero) \
522 : always_inline uword *clib_bitmap_##name (uword *ai, uword *bi) \
523 : { \
524 : uword i, a, b, bi_len, n_trailing_zeros; \
525 : \
526 : n_trailing_zeros = 0; \
527 : bi_len = vec_len (bi); \
528 : if (bi_len > 0) \
529 : clib_bitmap_vec_validate (ai, bi_len - 1); \
530 : for (i = 0; i < vec_len (ai); i++) \
531 : { \
532 : a = ai[i]; \
533 : b = i < bi_len ? bi[i] : 0; \
534 : do \
535 : { \
536 : body; \
537 : } \
538 : while (0); \
539 : ai[i] = a; \
540 : if (check_zero) \
541 : n_trailing_zeros = a ? 0 : (n_trailing_zeros + 1); \
542 : } \
543 : if (check_zero) \
544 : vec_dec_len (ai, n_trailing_zeros); \
545 : return ai; \
546 : }
547 :
548 : /* ALU functions: */
549 : /* *INDENT-OFF* */
550 10806581 : _(and, a = a & b, 1)
551 3676560 : _(andnot, a = a & ~b, 1)
552 30 : _(or, a = a | b, 0)
553 19292 : _(xor, a = a ^ b, 1)
554 : /* *INDENT-ON* */
555 : #undef _
556 : /** Logical operator across two bitmaps which duplicates the first bitmap
557 :
558 : @param ai - pointer to the destination bitmap
559 : @param bi - pointer to the source bitmap
560 : @returns aiDup = ai and bi. Neither ai nor bi are modified
561 : */
562 : always_inline uword *clib_bitmap_dup_and (uword * ai, uword * bi);
563 :
564 : /** Logical operator across two bitmaps which duplicates the first bitmap
565 :
566 : @param ai - pointer to the destination bitmap
567 : @param bi - pointer to the source bitmap
568 : @returns aiDup = ai & ~bi. Neither ai nor bi are modified
569 : */
570 : always_inline uword *clib_bitmap_dup_andnot (uword * ai, uword * bi);
571 :
572 : /** Logical operator across two bitmaps which duplicates the first bitmap
573 :
574 : @param ai - pointer to the destination bitmap
575 : @param bi - pointer to the source bitmap
576 : @returns aiDup = ai or bi. Neither ai nor bi are modified
577 : */
578 : always_inline uword *clib_bitmap_dup_or (uword * ai, uword * bi);
579 :
580 : /** Logical operator across two bitmaps which duplicates the first bitmap
581 :
582 : @param ai - pointer to the destination bitmap
583 : @param bi - pointer to the source bitmap
584 : @returns aiDup = ai xor bi. Neither ai nor bi are modified
585 : */
586 : always_inline uword *clib_bitmap_dup_xor (uword * ai, uword * bi);
587 :
588 : #define _(name) \
589 : always_inline uword * \
590 : clib_bitmap_dup_##name (uword * ai, uword * bi) \
591 : { return clib_bitmap_##name (clib_bitmap_dup (ai), bi); }
592 :
593 : /* *INDENT-OFF* */
594 1 : _(and);
595 : _(andnot);
596 18 : _(or);
597 9646 : _(xor);
598 : /* *INDENT-ON* */
599 : #undef _
600 :
601 : /* ALU function definition macro for functions taking one bitmap and an
602 : * immediate. */
603 : #define _(name, body, check_zero) \
604 : always_inline uword * \
605 : clib_bitmap_##name (uword * ai, uword i) \
606 : { \
607 : uword i0 = i / BITS (ai[0]); \
608 : uword i1 = i % BITS (ai[0]); \
609 : uword a, b; \
610 : clib_bitmap_vec_validate (ai, i0); \
611 : a = ai[i0]; \
612 : b = (uword) 1 << i1; \
613 : do { body; } while (0); \
614 : ai[i0] = a; \
615 : if (check_zero && a == 0) \
616 : ai = _clib_bitmap_remove_trailing_zeros (ai); \
617 : return ai; \
618 : }
619 :
620 : /* ALU functions immediate: */
621 : /* *INDENT-OFF* */
622 1 : _(andi, a = a & b, 1)
623 524724 : _(andnoti, a = a & ~b, 1)
624 18319417 : _(ori, a = a | b, 0)
625 3 : _(xori, a = a ^ b, 1)
626 : /* *INDENT-ON* */
627 : #undef _
628 :
629 : /* ALU function definition macro for functions taking one bitmap and an
630 : * immediate. No tail trimming */
631 : #define _(name, body) \
632 : always_inline uword * \
633 : clib_bitmap_##name##_notrim (uword * ai, uword i) \
634 : { \
635 : uword i0 = i / BITS (ai[0]); \
636 : uword i1 = i % BITS (ai[0]); \
637 : uword a, b; \
638 : clib_bitmap_vec_validate (ai, i0); \
639 : a = ai[i0]; \
640 : b = (uword) 1 << i1; \
641 : do { body; } while (0); \
642 : ai[i0] = a; \
643 : return ai; \
644 : }
645 :
646 : /* ALU functions immediate: */
647 : /* *INDENT-OFF* */
648 : _(andi, a = a & b)
649 3820278 : _(andnoti, a = a & ~b)
650 4151189 : _(ori, a = a | b)
651 : _(xori, a = a ^ b)
652 : #undef _
653 : /* *INDENT-ON* */
654 :
655 : /** Return a random bitmap of the requested length
656 : @param ai - pointer to the destination bitmap
657 : @param n_bits - number of bits to allocate
658 : @param [in,out] seed - pointer to the random number seed
659 : @returns a reasonably random bitmap based. See random.h.
660 : */
661 : always_inline uword *
662 : clib_bitmap_random (uword * ai, uword n_bits, u32 * seed)
663 : {
664 : vec_reset_length (ai);
665 :
666 : if (n_bits > 0)
667 : {
668 : uword i = n_bits - 1;
669 : uword i0, i1;
670 : uword log2_rand_max;
671 :
672 : log2_rand_max = min_log2 (random_u32_max ());
673 :
674 : i0 = i / BITS (ai[0]);
675 : i1 = i % BITS (ai[0]);
676 :
677 : clib_bitmap_vec_validate (ai, i0);
678 : for (i = 0; i <= i0; i++)
679 : {
680 : uword n;
681 : for (n = 0; n < BITS (ai[i]); n += log2_rand_max)
682 : ai[i] |= random_u32 (seed) << n;
683 : }
684 : if (i1 + 1 < BITS (ai[0]))
685 : ai[i0] &= (((uword) 1 << (i1 + 1)) - 1);
686 : }
687 : return ai;
688 : }
689 :
690 : /** Return the next set bit in a bitmap starting at bit i
691 : @param ai - pointer to the bitmap
692 : @param i - first bit position to test
693 : @returns first set bit position at or after i,
694 : ~0 if no further set bits are found
695 : */
696 : always_inline uword
697 147577485 : clib_bitmap_next_set (uword * ai, uword i)
698 : {
699 147577485 : uword i0 = i / BITS (ai[0]);
700 147577485 : uword i1 = i % BITS (ai[0]);
701 : uword t;
702 :
703 147577485 : if (i0 < vec_len (ai))
704 : {
705 122858131 : t = (ai[i0] >> i1) << i1;
706 122858131 : if (t)
707 79205204 : return log2_first_set (t) + i0 * BITS (ai[0]);
708 :
709 46163441 : for (i0++; i0 < vec_len (ai); i0++)
710 : {
711 10124114 : t = ai[i0];
712 10124114 : if (t)
713 7613683 : return log2_first_set (t) + i0 * BITS (ai[0]);
714 : }
715 : }
716 :
717 60758671 : return ~0;
718 : }
719 :
720 : /** Return the next clear bit in a bitmap starting at bit i
721 : @param ai - pointer to the bitmap
722 : @param i - first bit position to test
723 : @returns first clear bit position at or after i
724 : */
725 : always_inline uword
726 280376188 : clib_bitmap_next_clear (uword * ai, uword i)
727 : {
728 280376188 : uword i0 = i / BITS (ai[0]);
729 280376188 : uword i1 = i % BITS (ai[0]);
730 : uword t;
731 :
732 280376188 : if (i0 < vec_len (ai))
733 : {
734 277175940 : t = (~ai[i0] >> i1) << i1;
735 277175940 : if (t)
736 277172559 : return log2_first_set (t) + i0 * BITS (ai[0]);
737 :
738 9846 : for (i0++; i0 < vec_len (ai); i0++)
739 : {
740 9846 : t = ~ai[i0];
741 9846 : if (t)
742 3381 : return log2_first_set (t) + i0 * BITS (ai[0]);
743 : }
744 :
745 0 : return i0 * BITS (ai[0]);
746 : }
747 3199894 : return i;
748 : }
749 :
750 : uword unformat_bitmap_mask (unformat_input_t *input, va_list *va);
751 : uword unformat_bitmap_list (unformat_input_t *input, va_list *va);
752 : u8 *format_bitmap_hex (u8 *s, va_list *args);
753 : u8 *format_bitmap_list (u8 *s, va_list *args);
754 :
755 : #endif /* included_clib_bitmap_h */
756 :
757 : /*
758 : * fd.io coding-style-patch-verification: ON
759 : *
760 : * Local Variables:
761 : * eval: (c-set-style "gnu")
762 : * End:
763 : */
|
