FD.io VPP  v19.04.4-rc0-5-ge88582fac
Vector Packet Processing
bitmap.h
Go to the documentation of this file.
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 #include <vppinfra/bitops.h> /* for count_set_bits */
49 
51 
52 /** predicate function; is an entire bitmap empty?
53  @param ai - pointer to a bitmap
54  @returns 1 if the entire bitmap is zero, 0 otherwise
55 */
58 {
59  uword i;
60  for (i = 0; i < vec_len (ai); i++)
61  if (ai[i] != 0)
62  return 0;
63  return 1;
64 }
65 
66 /** predicate function; are two bitmaps equal?
67  @param a - pointer to a bitmap
68  @param b - pointer to a bitmap
69  @returns 1 if the bitmaps are equal, 0 otherwise
70 */
73 {
74  uword i;
75  if (vec_len (a) != vec_len (b))
76  return 0;
77  for (i = 0; i < vec_len (a); i++)
78  if (a[i] != b[i])
79  return 0;
80  return 1;
81 }
82 
83 /** Duplicate a bitmap
84  @param v - pointer to a bitmap
85  @returns a duplicate of the bitmap
86 */
87 #define clib_bitmap_dup(v) vec_dup(v)
88 
89 /** Free a bitmap
90  @param v - pointer to the bitmap to free
91 */
92 #define clib_bitmap_free(v) vec_free(v)
93 
94 /** Number of bytes in a bitmap
95  @param v - pointer to the bitmap
96 */
97 #define clib_bitmap_bytes(v) vec_bytes(v)
98 
99 /** Clear a bitmap
100  @param v - pointer to the bitmap to clear
101 */
102 #define clib_bitmap_zero(v) vec_zero(v)
103 
104 /** Allocate a bitmap with the supplied number of bits
105  @param [out] v - the resulting bitmap
106  @param n_bits - the required number of bits
107 */
108 
109 #define clib_bitmap_alloc(v,n_bits) \
110  v = vec_new (uword, ((n_bits) + BITS (uword) - 1) / BITS (uword))
111 
112 #define clib_bitmap_vec_validate(v,i) vec_validate_aligned((v),(i),sizeof(uword))
113 
114 /* Make sure that a bitmap is at least n_bits in size */
115 #define clib_bitmap_validate(v,n_bits) \
116  clib_bitmap_vec_validate ((v), ((n_bits) - 1) / BITS (uword))
117 
118 /* low-level routine to remove trailing zeros from a bitmap */
120 _clib_bitmap_remove_trailing_zeros (uword * a)
121 {
122  word i;
123  if (a)
124  {
125  for (i = _vec_len (a) - 1; i >= 0; i--)
126  if (a[i] != 0)
127  break;
128  _vec_len (a) = i + 1;
129  }
130  return a;
131 }
132 
133 /** Sets the ith bit of a bitmap to new_value.
134  No sanity checking. Be careful.
135  @param a - pointer to the bitmap
136  @param i - the bit position to interrogate
137  @param new_value - new value for the bit
138  @returns the old value of the bit
139 */
142 {
143  uword i0 = i / BITS (a[0]);
144  uword i1 = i % BITS (a[0]);
145  uword bit = (uword) 1 << i1;
146  uword ai, old_value;
147 
148  /* Removed ASSERT since uword * a may not be a vector. */
149  /* ASSERT (i0 < vec_len (a)); */
150 
151  ai = a[i0];
152  old_value = (ai & bit) != 0;
153  ai &= ~bit;
154  ai |= ((uword) (new_value != 0)) << i1;
155  a[i0] = ai;
156  return old_value;
157 }
158 
159 /** Sets the ith bit of a bitmap to new_value
160  Removes trailing zeros from the bitmap
161  @param ai - pointer to the bitmap
162  @param i - the bit position to interrogate
163  @param value - new value for the bit
164  @returns the old value of the bit
165 */
168 {
169  uword i0 = i / BITS (ai[0]);
170  uword i1 = i % BITS (ai[0]);
171  uword a;
172 
173  /* Check for writing a zero to beyond end of bitmap. */
174  if (value == 0 && i0 >= vec_len (ai))
175  return ai; /* Implied trailing zeros. */
176 
177  clib_bitmap_vec_validate (ai, i0);
178 
179  a = ai[i0];
180  a &= ~((uword) 1 << i1);
181  a |= ((uword) (value != 0)) << i1;
182  ai[i0] = a;
183 
184  /* If bits have been cleared, test for zero. */
185  if (a == 0)
186  ai = _clib_bitmap_remove_trailing_zeros (ai);
187 
188  return ai;
189 }
190 
191 /** Gets the ith bit value from a bitmap
192  @param ai - pointer to the bitmap
193  @param i - the bit position to interrogate
194  @returns the indicated bit value
195 */
198 {
199  uword i0 = i / BITS (ai[0]);
200  uword i1 = i % BITS (ai[0]);
201  return i0 < vec_len (ai) && 0 != ((ai[i0] >> i1) & 1);
202 }
203 
204 /** Gets the ith bit value from a bitmap
205  Does not sanity-check the bit position. Be careful.
206  @param ai - pointer to the bitmap
207  @param i - the bit position to interrogate
208  @returns the indicated bit value, or garbage if the bit position is
209  out of range.
210 */
213 {
214  uword i0 = i / BITS (ai[0]);
215  uword i1 = i % BITS (ai[0]);
216  return 0 != ((ai[i0] >> i1) & 1);
217 }
218 
221 {
222  uword i0 = i / BITS (ai[0]);
223  uword i1 = i % BITS (ai[0]);
224  ASSERT (i1 + n_bits <= BITS (uword));
225  return 0 != ((ai[i0] >> i1) & pow2_mask (n_bits));
226 }
227 
228 /** Gets the ith through ith + n_bits bit values from a bitmap
229  @param bitmap - pointer to the bitmap
230  @param i - the first bit position to retrieve
231  @param n_bits - the number of bit positions to retrieve
232  @returns the indicated range of bits
233 */
236 {
237  uword i0, i1, result;
238  uword l = vec_len (bitmap);
239 
240  ASSERT (n_bits <= BITS (result));
241 
242  i0 = i / BITS (bitmap[0]);
243  i1 = i % BITS (bitmap[0]);
244 
245  /* Check first word. */
246  result = 0;
247  if (i0 < l)
248  {
249  result |= (bitmap[i0] >> i1);
250  if (n_bits < BITS (bitmap[0]))
251  result &= (((uword) 1 << n_bits) - 1);
252  }
253 
254  /* Check for overlap into next word. */
255  i0++;
256  if (i1 + n_bits > BITS (bitmap[0]) && i0 < l)
257  {
258  n_bits -= BITS (bitmap[0]) - i1;
259  result |=
260  (bitmap[i0] & (((uword) 1 << n_bits) - 1)) << (BITS (bitmap[0]) - i1);
261  }
262 
263  return result;
264 }
265 
266 /** sets the ith through ith + n_bits bits in a bitmap
267  @param bitmap - pointer to the bitmap
268  @param i - the first bit position to retrieve
269  @param value - the values to set
270  @param n_bits - the number of bit positions to set
271  @returns a pointer to the updated bitmap, which may expand and move
272 */
273 
275 clib_bitmap_set_multiple (uword * bitmap, uword i, uword value, uword n_bits)
276 {
277  uword i0, i1, l, t, m;
278 
279  ASSERT (n_bits <= BITS (value));
280 
281  i0 = i / BITS (bitmap[0]);
282  i1 = i % BITS (bitmap[0]);
283 
284  /* Allocate bitmap. */
285  clib_bitmap_vec_validate (bitmap, (i + n_bits) / BITS (bitmap[0]));
286  l = vec_len (bitmap);
287 
288  m = ~0;
289  if (n_bits < BITS (value))
290  m = (((uword) 1 << n_bits) - 1);
291  value &= m;
292 
293  /* Insert into first word. */
294  t = bitmap[i0];
295  t &= ~(m << i1);
296  t |= value << i1;
297  bitmap[i0] = t;
298 
299  /* Insert into second word. */
300  i0++;
301  if (i1 + n_bits > BITS (bitmap[0]) && i0 < l)
302  {
303  t = BITS (bitmap[0]) - i1;
304  value >>= t;
305  n_bits -= t;
306  t = bitmap[i0];
307  m = ((uword) 1 << n_bits) - 1;
308  t &= ~m;
309  t |= value;
310  bitmap[i0] = t;
311  }
312 
313  return bitmap;
314 }
315 
317 clib_bitmap_set_region (uword * bitmap, uword i, uword value, uword n_bits)
318 {
319  uword a0, a1, b0;
320  uword i_end, mask;
321 
322  a0 = i / BITS (bitmap[0]);
323  a1 = i % BITS (bitmap[0]);
324 
325  i_end = i + n_bits;
326  b0 = i_end / BITS (bitmap[0]);
327 
328  clib_bitmap_vec_validate (bitmap, b0);
329 
330  /* First word. */
331  mask = n_bits < BITS (bitmap[0]) ? pow2_mask (n_bits) : ~0;
332  mask <<= a1;
333 
334  if (value)
335  bitmap[a0] |= mask;
336  else
337  bitmap[a0] &= ~mask;
338 
339  for (a0++; a0 < b0; a0++)
340  bitmap[a0] = value ? ~0 : 0;
341 
342  if (a0 == b0)
343  {
344  word n_bits_left = n_bits - (BITS (bitmap[0]) - a1);
345  mask = pow2_mask (n_bits_left);
346  if (value)
347  bitmap[a0] |= mask;
348  else
349  bitmap[a0] &= ~mask;
350  }
351 
352  return bitmap;
353 }
354 
355 /** Macro to iterate across set bits in a bitmap
356 
357  @param i - the current set bit
358  @param ai - the bitmap
359  @param body - the expression to evaluate for each set bit
360 */
361 #define clib_bitmap_foreach(i,ai,body) \
362 do { \
363  uword __bitmap_i, __bitmap_ai, __bitmap_len, __bitmap_first_set; \
364  __bitmap_len = vec_len ((ai)); \
365  for (__bitmap_i = 0; __bitmap_i < __bitmap_len; __bitmap_i++) \
366  { \
367  __bitmap_ai = (ai)[__bitmap_i]; \
368  while (__bitmap_ai != 0) \
369  { \
370  __bitmap_first_set = first_set (__bitmap_ai); \
371  (i) = (__bitmap_i * BITS ((ai)[0]) \
372  + min_log2 (__bitmap_first_set)); \
373  do { body; } while (0); \
374  __bitmap_ai ^= __bitmap_first_set; \
375  } \
376  } \
377 } while (0)
378 
379 
380 /** Return the lowest numbered set bit in a bitmap
381  @param ai - pointer to the bitmap
382  @returns lowest numbered set bit, or ~0 if the entire bitmap is zero
383 */
386 {
387  uword i = 0;
388 #if uword_bits == 64
389 #if defined(CLIB_HAVE_VEC256)
390  while (i + 7 < vec_len (ai))
391  {
392  u64x4 v;
393  v = u64x4_load_unaligned (ai + i) | u64x4_load_unaligned (ai + i + 4);
394  if (!u64x4_is_all_zero (v))
395  break;
396  i += 8;
397  }
398 #elif defined(CLIB_HAVE_VEC128) && defined(CLIB_HAVE_VEC128_UNALIGNED_LOAD_STORE)
399  while (i + 3 < vec_len (ai))
400  {
401  u64x2 v;
402  v = u64x2_load_unaligned (ai + i) | u64x2_load_unaligned (ai + i + 2);
403  if (!u64x2_is_all_zero (v))
404  break;
405  i += 4;
406  }
407 #endif
408 #endif
409  for (; i < vec_len (ai); i++)
410  {
411  uword x = ai[i];
412  if (x != 0)
413  return i * BITS (ai[0]) + log2_first_set (x);
414  }
415  return ~0;
416 }
417 
418 /** Return the higest numbered set bit in a bitmap
419  @param ai - pointer to the bitmap
420  @returns lowest numbered set bit, or ~0 if the entire bitmap is zero
421 */
424 {
425  uword i;
426 
427  for (i = vec_len (ai); i > 0; i--)
428  {
429  uword x = ai[i - 1];
430  if (x != 0)
431  {
432  uword first_bit;
433  first_bit = count_leading_zeros (x);
434  return (i) * BITS (ai[0]) - first_bit - 1;
435  }
436  }
437  return ~0;
438 }
439 
440 /** Return the lowest numbered clear bit in a bitmap
441  @param ai - pointer to the bitmap
442  @returns lowest numbered clear bit
443 */
446 {
447  uword i;
448  for (i = 0; i < vec_len (ai); i++)
449  {
450  uword x = ~ai[i];
451  if (x != 0)
452  return i * BITS (ai[0]) + log2_first_set (x);
453  }
454  return i * BITS (ai[0]);
455 }
456 
457 /** Return the number of set bits in a bitmap
458  @param ai - pointer to the bitmap
459  @returns the number of set bits in the bitmap
460 */
463 {
464  uword i;
465  uword n_set = 0;
466  for (i = 0; i < vec_len (ai); i++)
467  n_set += count_set_bits (ai[i]);
468  return n_set;
469 }
470 
471 /** Logical operator across two bitmaps
472 
473  @param ai - pointer to the destination bitmap
474  @param bi - pointer to the source bitmap
475  @returns ai = ai and bi. ai is modified, bi is not modified
476 */
478 
479 /** Logical operator across two bitmaps
480 
481  @param ai - pointer to the destination bitmap
482  @param bi - pointer to the source bitmap
483  @returns ai = ai & ~bi. ai is modified, bi is not modified
484 */
486 
487 /** Logical operator across two bitmaps
488 
489  @param ai - pointer to the destination bitmap
490  @param bi - pointer to the source bitmap
491  @returns ai = ai & ~bi. ai is modified, bi is not modified
492 */
494 /** Logical operator across two bitmaps
495 
496  @param ai - pointer to the destination bitmap
497  @param bi - pointer to the source bitmap
498  @returns ai = ai or bi. ai is modified, bi is not modified
499 */
501 
502 /** Logical operator across two bitmaps
503 
504  @param ai - pointer to the destination bitmap
505  @param bi - pointer to the source bitmap
506  @returns ai = ai xor bi. ai is modified, bi is not modified
507 */
509 
510 /* ALU function definition macro for functions taking two bitmaps. */
511 #define _(name, body, check_zero) \
512 always_inline uword * \
513 clib_bitmap_##name (uword * ai, uword * bi) \
514 { \
515  uword i, a, b, bi_len, n_trailing_zeros; \
516  \
517  n_trailing_zeros = 0; \
518  bi_len = vec_len (bi); \
519  if (bi_len > 0) \
520  clib_bitmap_vec_validate (ai, bi_len - 1); \
521  for (i = 0; i < vec_len (ai); i++) \
522  { \
523  a = ai[i]; \
524  b = i < bi_len ? bi[i] : 0; \
525  do { body; } while (0); \
526  ai[i] = a; \
527  if (check_zero) \
528  n_trailing_zeros = a ? 0 : (n_trailing_zeros + 1); \
529  } \
530  if (check_zero) \
531  _vec_len (ai) -= n_trailing_zeros; \
532  return ai; \
533 }
534 
535 /* ALU functions: */
536 /* *INDENT-OFF* */
537 _(and, a = a & b, 1)
538 _(andnot, a = a & ~b, 1)
539 _(or, a = a | b, 0)
540 _(xor, a = a ^ b, 1)
541 /* *INDENT-ON* */
542 #undef _
543 /** Logical operator across two bitmaps which duplicates the first bitmap
544 
545  @param ai - pointer to the destination bitmap
546  @param bi - pointer to the source bitmap
547  @returns aiDup = ai and bi. Neither ai nor bi are modified
548 */
550 
551 /** Logical operator across two bitmaps which duplicates the first bitmap
552 
553  @param ai - pointer to the destination bitmap
554  @param bi - pointer to the source bitmap
555  @returns aiDup = ai & ~bi. Neither ai nor bi are modified
556 */
558 
559 /** Logical operator across two bitmaps which duplicates the first bitmap
560 
561  @param ai - pointer to the destination bitmap
562  @param bi - pointer to the source bitmap
563  @returns aiDup = ai or bi. Neither ai nor bi are modified
564 */
566 
567 /** Logical operator across two bitmaps which duplicates the first bitmap
568 
569  @param ai - pointer to the destination bitmap
570  @param bi - pointer to the source bitmap
571  @returns aiDup = ai xor bi. Neither ai nor bi are modified
572 */
574 
575 #define _(name) \
576  always_inline uword * \
577  clib_bitmap_dup_##name (uword * ai, uword * bi) \
578 { return clib_bitmap_##name (clib_bitmap_dup (ai), bi); }
579 
580 /* *INDENT-OFF* */
581 _(and);
582 _(andnot);
583 _(or);
584 _(xor);
585 /* *INDENT-ON* */
586 #undef _
587 
588 /* ALU function definition macro for functions taking one bitmap and an
589  * immediate. */
590 #define _(name, body, check_zero) \
591 always_inline uword * \
592 clib_bitmap_##name (uword * ai, uword i) \
593 { \
594  uword i0 = i / BITS (ai[0]); \
595  uword i1 = i % BITS (ai[0]); \
596  uword a, b; \
597  clib_bitmap_vec_validate (ai, i0); \
598  a = ai[i0]; \
599  b = (uword) 1 << i1; \
600  do { body; } while (0); \
601  ai[i0] = a; \
602  if (check_zero && a == 0) \
603  ai = _clib_bitmap_remove_trailing_zeros (ai); \
604  return ai; \
605 }
606 
607 /* ALU functions immediate: */
608 /* *INDENT-OFF* */
609 _(andi, a = a & b, 1)
610 _(andnoti, a = a & ~b, 1)
611 _(ori, a = a | b, 0)
612 _(xori, a = a ^ b, 1)
613 /* *INDENT-ON* */
614 #undef _
615 
616 /* ALU function definition macro for functions taking one bitmap and an
617  * immediate. No tail trimming */
618 #define _(name, body) \
619 always_inline uword * \
620 clib_bitmap_##name##_notrim (uword * ai, uword i) \
621 { \
622  uword i0 = i / BITS (ai[0]); \
623  uword i1 = i % BITS (ai[0]); \
624  uword a, b; \
625  clib_bitmap_vec_validate (ai, i0); \
626  a = ai[i0]; \
627  b = (uword) 1 << i1; \
628  do { body; } while (0); \
629  ai[i0] = a; \
630  return ai; \
631 }
632 
633 /* ALU functions immediate: */
634 /* *INDENT-OFF* */
635 _(andi, a = a & b)
636 _(andnoti, a = a & ~b)
637 _(ori, a = a | b)
638 _(xori, a = a ^ b)
639 #undef _
640 /* *INDENT-ON* */
641 
642 /** Return a random bitmap of the requested length
643  @param ai - pointer to the destination bitmap
644  @param n_bits - number of bits to allocate
645  @param [in,out] seed - pointer to the random number seed
646  @returns a reasonably random bitmap based. See random.h.
647 */
649 clib_bitmap_random (uword * ai, uword n_bits, u32 * seed)
650 {
651  vec_reset_length (ai);
652 
653  if (n_bits > 0)
654  {
655  uword i = n_bits - 1;
656  uword i0, i1;
657  uword log2_rand_max;
658 
659  log2_rand_max = min_log2 (random_u32_max ());
660 
661  i0 = i / BITS (ai[0]);
662  i1 = i % BITS (ai[0]);
663 
664  clib_bitmap_vec_validate (ai, i0);
665  for (i = 0; i <= i0; i++)
666  {
667  uword n;
668  for (n = 0; n < BITS (ai[i]); n += log2_rand_max)
669  ai[i] |= random_u32 (seed) << n;
670  }
671  if (i1 + 1 < BITS (ai[0]))
672  ai[i0] &= (((uword) 1 << (i1 + 1)) - 1);
673  }
674  return ai;
675 }
676 
677 /** Return the next set bit in a bitmap starting at bit i
678  @param ai - pointer to the bitmap
679  @param i - first bit position to test
680  @returns first set bit position at or after i,
681  ~0 if no further set bits are found
682 */
684 clib_bitmap_next_set (uword * ai, uword i)
685 {
686  uword i0 = i / BITS (ai[0]);
687  uword i1 = i % BITS (ai[0]);
688  uword t;
689 
690  if (i0 < vec_len (ai))
691  {
692  t = (ai[i0] >> i1) << i1;
693  if (t)
694  return log2_first_set (t) + i0 * BITS (ai[0]);
695 
696  for (i0++; i0 < vec_len (ai); i0++)
697  {
698  t = ai[i0];
699  if (t)
700  return log2_first_set (t) + i0 * BITS (ai[0]);
701  }
702  }
703 
704  return ~0;
705 }
706 
707 /** Return the next clear bit in a bitmap starting at bit i
708  @param ai - pointer to the bitmap
709  @param i - first bit position to test
710  @returns first clear bit position at or after i
711 */
713 clib_bitmap_next_clear (uword * ai, uword i)
714 {
715  uword i0 = i / BITS (ai[0]);
716  uword i1 = i % BITS (ai[0]);
717  uword t;
718 
719  if (i0 < vec_len (ai))
720  {
721  t = (~ai[i0] >> i1) << i1;
722  if (t)
723  return log2_first_set (t) + i0 * BITS (ai[0]);
724 
725  for (i0++; i0 < vec_len (ai); i0++)
726  {
727  t = ~ai[i0];
728  if (t)
729  return log2_first_set (t) + i0 * BITS (ai[0]);
730  }
731 
732  /* no clear bit left in bitmap, return bit just beyond bitmap */
733  return (i0 + 1) * BITS (ai[0]);
734  }
735  return i;
736 }
737 
738 /** unformat an any sized hexadecimal bitmask into a bitmap
739 
740  uword * bitmap;
741  rv = unformat ("%U", unformat_bitmap_mask, &bitmap);
742 
743  Standard unformat_function_t arguments
744 
745  @param input - pointer an unformat_input_t
746  @param va - varargs list comprising a single uword **
747  @returns 1 on success, 0 on failure
748 */
749 static inline uword
750 unformat_bitmap_mask (unformat_input_t * input, va_list * va)
751 {
752  u8 *v = 0; /* hexadecimal vector */
753  uword **bitmap_return = va_arg (*va, uword **);
754  uword *bitmap = 0;
755 
756  if (unformat (input, "%U", unformat_hex_string, &v))
757  {
758  int i, s = vec_len (v) - 1; /* 's' for significance or shift */
759 
760  /* v[0] holds the most significant byte */
761  for (i = 0; s >= 0; i++, s--)
762  bitmap = clib_bitmap_set_multiple (bitmap,
763  s * BITS (v[i]), v[i],
764  BITS (v[i]));
765 
766  vec_free (v);
767  *bitmap_return = bitmap;
768  return 1;
769  }
770 
771  return 0;
772 }
773 
774 /** unformat a list of bit ranges into a bitmap (eg "0-3,5-7,11" )
775 
776  uword * bitmap;
777  rv = unformat ("%U", unformat_bitmap_list, &bitmap);
778 
779  Standard unformat_function_t arguments
780 
781  @param input - pointer an unformat_input_t
782  @param va - varargs list comprising a single uword **
783  @returns 1 on success, 0 on failure
784 */
785 static inline uword
786 unformat_bitmap_list (unformat_input_t * input, va_list * va)
787 {
788  uword **bitmap_return = va_arg (*va, uword **);
789  uword *bitmap = 0;
790 
791  u32 a, b;
792 
794  {
795  int i;
796  if (unformat (input, "%u-%u,", &a, &b))
797  ;
798  else if (unformat (input, "%u,", &a))
799  b = a;
800  else if (unformat (input, "%u-%u", &a, &b))
801  ;
802  else if (unformat (input, "%u", &a))
803  b = a;
804  else if (bitmap)
805  {
806  unformat_put_input (input);
807  break;
808  }
809  else
810  goto error;
811 
812  if (b < a)
813  goto error;
814 
815  for (i = a; i <= b; i++)
816  bitmap = clib_bitmap_set (bitmap, i, 1);
817  }
818  *bitmap_return = bitmap;
819  return 1;
820 error:
821  clib_bitmap_free (bitmap);
822  return 0;
823 }
824 
825 /** Format a bitmap as a string of hex bytes
826 
827  uword * bitmap;
828  s = format ("%U", format_bitmap_hex, bitmap);
829 
830  Standard format_function_t arguments
831 
832  @param s - string under construction
833  @param args - varargs list comprising a single uword *
834  @returns string under construction
835 */
836 static inline u8 *
837 format_bitmap_hex (u8 * s, va_list * args)
838 {
839  uword *bitmap = va_arg (*args, uword *);
840  int i, is_trailing_zero = 1;
841 
842  if (!bitmap)
843  return format (s, "0");
844 
845  i = vec_bytes (bitmap) * 2;
846 
847  while (i > 0)
848  {
849  u8 x = clib_bitmap_get_multiple (bitmap, --i * 4, 4);
850 
851  if (x && is_trailing_zero)
852  is_trailing_zero = 0;
853 
854  if (x || !is_trailing_zero)
855  s = format (s, "%x", x);
856  }
857  return s;
858 }
859 #endif /* included_clib_bitmap_h */
860 
861 /*
862  * fd.io coding-style-patch-verification: ON
863  *
864  * Local Variables:
865  * eval: (c-set-style "gnu")
866  * End:
867  */
a
Definition: bitmap.h:538
static uword log2_first_set(uword x)
Definition: clib.h:259
static uword * clib_bitmap_set_region(uword *bitmap, uword i, uword value, uword n_bits)
Definition: bitmap.h:317
#define count_leading_zeros(x)
Definition: clib.h:138
static uword * clib_bitmap_or(uword *ai, uword *bi)
Logical operator across two bitmaps.
unformat_function_t unformat_hex_string
Definition: format.h:288
int i
static uword * clib_bitmap_set(uword *ai, uword i, uword value)
Sets the ith bit of a bitmap to new_value Removes trailing zeros from the bitmap. ...
Definition: bitmap.h:167
u8 * format(u8 *s, const char *fmt,...)
Definition: format.c:424
#define vec_bytes(v)
Number of data bytes in vector.
static uword clib_bitmap_get_multiple_no_check(uword *ai, uword i, uword n_bits)
Definition: bitmap.h:220
static uword clib_bitmap_get_no_check(uword *ai, uword i)
Gets the ith bit value from a bitmap Does not sanity-check the bit position.
Definition: bitmap.h:212
unsigned char u8
Definition: types.h:56
static uword min_log2(uword x)
Definition: clib.h:144
#define vec_reset_length(v)
Reset vector length to zero NULL-pointer tolerant.
static uword clib_bitmap_set_no_check(uword *a, uword i, uword new_value)
Sets the ith bit of a bitmap to new_value.
Definition: bitmap.h:141
static uword clib_bitmap_is_equal(uword *a, uword *b)
predicate function; are two bitmaps equal?
Definition: bitmap.h:72
i64 word
Definition: types.h:111
#define always_inline
Definition: clib.h:98
static uword pow2_mask(uword x)
Definition: clib.h:220
static uword clib_bitmap_is_zero(uword *ai)
predicate function; is an entire bitmap empty?
Definition: bitmap.h:57
unsigned int u32
Definition: types.h:88
epu8_epi32 epu16_epi32 u64x2
Definition: vector_sse42.h:665
static uword clib_bitmap_first_set(uword *ai)
Return the lowest numbered set bit in a bitmap.
Definition: bitmap.h:385
static uword clib_bitmap_last_set(uword *ai)
Return the higest numbered set bit in a bitmap.
Definition: bitmap.h:423
struct _unformat_input_t unformat_input_t
static void unformat_put_input(unformat_input_t *input)
Definition: format.h:204
static uword clib_bitmap_get_multiple(uword *bitmap, uword i, uword n_bits)
Gets the ith through ith + n_bits bit values from a bitmap.
Definition: bitmap.h:235
static uword * clib_bitmap_dup_andnot(uword *ai, uword *bi)
Logical operator across two bitmaps which duplicates the first bitmap.
static uword * clib_bitmap_xor(uword *ai, uword *bi)
Logical operator across two bitmaps.
#define UNFORMAT_END_OF_INPUT
Definition: format.h:144
static u32 random_u32_max(void)
Maximum value returned by random_u32()
Definition: random.h:80
static uword * clib_bitmap_dup_xor(uword *ai, uword *bi)
Logical operator across two bitmaps which duplicates the first bitmap.
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:341
static uword * clib_bitmap_dup_or(uword *ai, uword *bi)
Logical operator across two bitmaps which duplicates the first bitmap.
static uword * clib_bitmap_andnot(uword *ai, uword *bi)
Logical operator across two bitmaps.
static uword * clib_bitmap_set_multiple(uword *bitmap, uword i, uword value, uword n_bits)
sets the ith through ith + n_bits bits in a bitmap
Definition: bitmap.h:275
static uword clib_bitmap_get(uword *ai, uword i)
Gets the ith bit value from a bitmap.
Definition: bitmap.h:197
#define clib_bitmap_vec_validate(v, i)
Definition: bitmap.h:112
#define ASSERT(truth)
#define clib_bitmap_free(v)
Free a bitmap.
Definition: bitmap.h:92
static uword clib_bitmap_count_set_bits(uword *ai)
Return the number of set bits in a bitmap.
Definition: bitmap.h:462
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
static uword * clib_bitmap_dup_and(uword *ai, uword *bi)
Logical operator across two bitmaps which duplicates the first bitmap.
u64 uword
Definition: types.h:112
Linear Congruential Random Number Generator.
u64x4
Definition: vector_avx2.h:121
static u32 random_u32(u32 *seed)
32-bit random number generator
Definition: random.h:69
uword clib_bitmap_t
Definition: bitmap.h:50
static uword count_set_bits(uword x)
Definition: bitops.h:45
static uword clib_bitmap_first_clear(uword *ai)
Return the lowest numbered clear bit in a bitmap.
Definition: bitmap.h:445
#define BITS(x)
Definition: clib.h:61
static uword * clib_bitmap_and(uword *ai, uword *bi)
Logical operator across two bitmaps.
uword unformat(unformat_input_t *i, const char *fmt,...)
Definition: unformat.c:972
CLIB vectors are ubiquitous dynamically resized arrays with by user defined "headers".
static uword unformat_check_input(unformat_input_t *i)
Definition: format.h:170