FD.io VPP  v18.01.2-1-g9b554f3
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 clfib_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;
388  for (i = 0; i < vec_len (ai); i++)
389  {
390  uword x = ai[i];
391  if (x != 0)
392  return i * BITS (ai[0]) + log2_first_set (x);
393  }
394  return ~0;
395 }
396 
397 /** Return the higest numbered set bit in a bitmap
398  @param ai - pointer to the bitmap
399  @returns lowest numbered set bit, or ~0 if the entire bitmap is zero
400 */
403 {
404  uword i;
405 
406  for (i = vec_len (ai); i > 0; i--)
407  {
408  uword x = ai[i - 1];
409  if (x != 0)
410  {
411  uword first_bit;
412  count_leading_zeros (first_bit, x);
413  return (i) * BITS (ai[0]) - first_bit - 1;
414  }
415  }
416  return ~0;
417 }
418 
419 /** Return the lowest numbered clear bit in a bitmap
420  @param ai - pointer to the bitmap
421  @returns lowest numbered clear bit
422 */
425 {
426  uword i;
427  for (i = 0; i < vec_len (ai); i++)
428  {
429  uword x = ~ai[i];
430  if (x != 0)
431  return i * BITS (ai[0]) + log2_first_set (x);
432  }
433  return i * BITS (ai[0]);
434 }
435 
436 /** Return the number of set bits in a bitmap
437  @param ai - pointer to the bitmap
438  @returns the number of set bits in the bitmap
439 */
442 {
443  uword i;
444  uword n_set = 0;
445  for (i = 0; i < vec_len (ai); i++)
446  n_set += count_set_bits (ai[i]);
447  return n_set;
448 }
449 
450 /** Logical operator across two bitmaps
451 
452  @param ai - pointer to the destination bitmap
453  @param bi - pointer to the source bitmap
454  @returns ai = ai and bi. ai is modified, bi is not modified
455 */
457 
458 /** Logical operator across two bitmaps
459 
460  @param ai - pointer to the destination bitmap
461  @param bi - pointer to the source bitmap
462  @returns ai = ai & ~bi. ai is modified, bi is not modified
463 */
465 
466 /** Logical operator across two bitmaps
467 
468  @param ai - pointer to the destination bitmap
469  @param bi - pointer to the source bitmap
470  @returns ai = ai & ~bi. ai is modified, bi is not modified
471 */
473 /** Logical operator across two bitmaps
474 
475  @param ai - pointer to the destination bitmap
476  @param bi - pointer to the source bitmap
477  @returns ai = ai or bi. ai is modified, bi is not modified
478 */
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 xor bi. ai is modified, bi is not modified
486 */
488 
489 /* ALU function definition macro for functions taking two bitmaps. */
490 #define _(name, body, check_zero) \
491 always_inline uword * \
492 clib_bitmap_##name (uword * ai, uword * bi) \
493 { \
494  uword i, a, b, bi_len, n_trailing_zeros; \
495  \
496  n_trailing_zeros = 0; \
497  bi_len = vec_len (bi); \
498  if (bi_len > 0) \
499  clib_bitmap_vec_validate (ai, bi_len - 1); \
500  for (i = 0; i < vec_len (ai); i++) \
501  { \
502  a = ai[i]; \
503  b = i < bi_len ? bi[i] : 0; \
504  do { body; } while (0); \
505  ai[i] = a; \
506  if (check_zero) \
507  n_trailing_zeros = a ? 0 : (n_trailing_zeros + 1); \
508  } \
509  if (check_zero) \
510  _vec_len (ai) -= n_trailing_zeros; \
511  return ai; \
512 }
513 
514 /* ALU functions: */
515 _(and, a = a & b, 1)
516 _(andnot, a = a & ~b, 1) _(or, a = a | b, 0) _(xor, a = a ^ b, 1)
517 #undef _
518 /** Logical operator across two bitmaps which duplicates the first bitmap
519 
520  @param ai - pointer to the destination bitmap
521  @param bi - pointer to the source bitmap
522  @returns aiDup = ai and bi. Neither ai nor bi are modified
523 */
525  clib_bitmap_dup_and (uword * ai, uword * bi);
526 
527 /** Logical operator across two bitmaps which duplicates the first bitmap
528 
529  @param ai - pointer to the destination bitmap
530  @param bi - pointer to the source bitmap
531  @returns aiDup = ai & ~bi. Neither ai nor bi are modified
532 */
534  clib_bitmap_dup_andnot (uword * ai, uword * bi);
535 
536 /** Logical operator across two bitmaps which duplicates the first bitmap
537 
538  @param ai - pointer to the destination bitmap
539  @param bi - pointer to the source bitmap
540  @returns aiDup = ai or bi. Neither ai nor bi are modified
541 */
543  clib_bitmap_dup_or (uword * ai, uword * bi);
544 
545 /** Logical operator across two bitmaps which duplicates the first bitmap
546 
547  @param ai - pointer to the destination bitmap
548  @param bi - pointer to the source bitmap
549  @returns aiDup = ai xor bi. Neither ai nor bi are modified
550 */
552  clib_bitmap_dup_xor (uword * ai, uword * bi);
553 
554 #define _(name) \
555  always_inline uword * \
556  clib_bitmap_dup_##name (uword * ai, uword * bi) \
557 { return clib_bitmap_##name (clib_bitmap_dup (ai), bi); }
558 
559 _(and);
560 _(andnot);
561 _(or);
562 _(xor);
563 
564 #undef _
565 
566 /* ALU function definition macro for functions taking one bitmap and an immediate. */
567 #define _(name, body, check_zero) \
568 always_inline uword * \
569 clib_bitmap_##name (uword * ai, uword i) \
570 { \
571  uword i0 = i / BITS (ai[0]); \
572  uword i1 = i % BITS (ai[0]); \
573  uword a, b; \
574  clib_bitmap_vec_validate (ai, i0); \
575  a = ai[i0]; \
576  b = (uword) 1 << i1; \
577  do { body; } while (0); \
578  ai[i0] = a; \
579  if (check_zero && a == 0) \
580  ai = _clib_bitmap_remove_trailing_zeros (ai); \
581  return ai; \
582 }
583 
584 /* ALU functions immediate: */
585 _(andi, a = a & b, 1)
586 _(andnoti, a = a & ~b, 1) _(ori, a = a | b, 0) _(xori, a = a ^ b, 1)
587 #undef _
588 /** Return a random bitmap of the requested length
589  @param ai - pointer to the destination bitmap
590  @param n_bits - number of bits to allocate
591  @param [in,out] seed - pointer to the random number seed
592  @returns a reasonably random bitmap based. See random.h.
593 */
595  clib_bitmap_random (uword * ai, uword n_bits, u32 * seed)
596 {
597  vec_reset_length (ai);
598 
599  if (n_bits > 0)
600  {
601  uword i = n_bits - 1;
602  uword i0, i1;
603  uword log2_rand_max;
604 
605  log2_rand_max = min_log2 (random_u32_max ());
606 
607  i0 = i / BITS (ai[0]);
608  i1 = i % BITS (ai[0]);
609 
610  clib_bitmap_vec_validate (ai, i0);
611  for (i = 0; i <= i0; i++)
612  {
613  uword n;
614  for (n = 0; n < BITS (ai[i]); n += log2_rand_max)
615  ai[i] |= random_u32 (seed) << n;
616  }
617  if (i1 + 1 < BITS (ai[0]))
618  ai[i0] &= (((uword) 1 << (i1 + 1)) - 1);
619  }
620  return ai;
621 }
622 
623 /** Return the next set bit in a bitmap starting at bit i
624  @param ai - pointer to the bitmap
625  @param i - first bit position to test
626  @returns first set bit position at or after i,
627  ~0 if no further set bits are found
628 */
631 {
632  uword i0 = i / BITS (ai[0]);
633  uword i1 = i % BITS (ai[0]);
634  uword t;
635 
636  if (i0 < vec_len (ai))
637  {
638  t = (ai[i0] >> i1) << i1;
639  if (t)
640  return log2_first_set (t) + i0 * BITS (ai[0]);
641 
642  for (i0++; i0 < vec_len (ai); i0++)
643  {
644  t = ai[i0];
645  if (t)
646  return log2_first_set (t) + i0 * BITS (ai[0]);
647  }
648  }
649 
650  return ~0;
651 }
652 
653 /** Return the next clear bit in a bitmap starting at bit i
654  @param ai - pointer to the bitmap
655  @param i - first bit position to test
656  @returns first clear bit position at or after i
657 */
660 {
661  uword i0 = i / BITS (ai[0]);
662  uword i1 = i % BITS (ai[0]);
663  uword t;
664 
665  if (i0 < vec_len (ai))
666  {
667  t = (~ai[i0] >> i1) << i1;
668  if (t)
669  return log2_first_set (t) + i0 * BITS (ai[0]);
670 
671  for (i0++; i0 < vec_len (ai); i0++)
672  {
673  t = ~ai[i0];
674  if (t)
675  return log2_first_set (t) + i0 * BITS (ai[0]);
676  }
677  }
678  return i;
679 }
680 
681 /** unformat a list of bit ranges into a bitmap (eg "0-3,5-7,11" )
682 
683  uword * bitmap;
684  rv = unformat ("%U", unformat_bitmap_list, &bitmap);
685 
686  Standard unformat_function_t arguments
687 
688  @param input - pointer an unformat_input_t
689  @param va - varargs list comprising a single uword **
690  @returns 1 on success, 0 on failure
691 */
692 static inline uword
693 unformat_bitmap_list (unformat_input_t * input, va_list * va)
694 {
695  uword **bitmap_return = va_arg (*va, uword **);
696  uword *bitmap = 0;
697 
698  u32 a, b;
699 
701  {
702  int i;
703  if (unformat (input, "%u-%u,", &a, &b))
704  ;
705  else if (unformat (input, "%u,", &a))
706  b = a;
707  else if (unformat (input, "%u-%u", &a, &b))
708  ;
709  else if (unformat (input, "%u", &a))
710  b = a;
711  else if (bitmap)
712  {
713  unformat_put_input (input);
714  break;
715  }
716  else
717  goto error;
718 
719  if (b < a)
720  goto error;
721 
722  for (i = a; i <= b; i++)
723  bitmap = clib_bitmap_set (bitmap, i, 1);
724  }
725  *bitmap_return = bitmap;
726  return 1;
727 error:
728  clib_bitmap_free (bitmap);
729  return 0;
730 }
731 
732 /** Format a bitmap as a string of hex bytes
733 
734  uword * bitmap;
735  s = format ("%U", format_bitmap_hex, bitmap);
736 
737  Standard format_function_t arguments
738 
739  @param s - string under construction
740  @param args - varargs list comprising a single uword *
741  @returns string under construction
742 */
743 static inline u8 *
744 format_bitmap_hex (u8 * s, va_list * args)
745 {
746  uword *bitmap = va_arg (*args, uword *);
747  int i, is_trailing_zero = 1;
748 
749  if (!bitmap)
750  return format (s, "0");
751 
752  i = vec_bytes (bitmap) * 2;
753 
754  while (i > 0)
755  {
756  u8 x = clib_bitmap_get_multiple (bitmap, --i * 4, 4);
757 
758  if (x && is_trailing_zero)
759  is_trailing_zero = 0;
760 
761  if (x || !is_trailing_zero)
762  s = format (s, "%x", x);
763  }
764  return s;
765 }
766 #endif /* included_clib_bitmap_h */
767 
768 /*
769  * fd.io coding-style-patch-verification: ON
770  *
771  * Local Variables:
772  * eval: (c-set-style "gnu")
773  * End:
774  */
static u8 * format_bitmap_hex(u8 *s, va_list *args)
Format a bitmap as a string of hex bytes.
Definition: bitmap.h:744
sll srl srl sll sra u16x4 i
Definition: vector_sse2.h:337
static uword clib_bitmap_next_clear(uword *ai, uword i)
Return the next clear bit in a bitmap starting at bit i.
Definition: bitmap.h:659
a
Definition: bitmap.h:516
static uword log2_first_set(uword x)
Definition: clib.h:304
static uword * clib_bitmap_or(uword *ai, uword *bi)
Logical operator across two bitmaps.
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:419
#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_random(uword *ai, uword n_bits, u32 *seed)
Return a random bitmap of the requested length.
Definition: bitmap.h:595
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
static uword min_log2(uword x)
Definition: clib.h:197
#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
#define always_inline
Definition: clib.h:92
static uword pow2_mask(uword x)
Definition: clib.h:265
static uword clib_bitmap_is_zero(uword *ai)
predicate function; is an entire bitmap empty?
Definition: bitmap.h:57
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:402
struct _unformat_input_t unformat_input_t
static void unformat_put_input(unformat_input_t *input)
Definition: format.h:203
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:143
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.
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)
unsigned int u32
Definition: types.h:88
#define clib_bitmap_free(v)
Free a bitmap.
Definition: bitmap.h:92
static uword * clfib_bitmap_set_region(uword *bitmap, uword i, uword value, uword n_bits)
Definition: bitmap.h:317
u64 uword
Definition: types.h:112
static uword clib_bitmap_count_set_bits(uword *ai)
Return the number of set bits in a bitmap.
Definition: bitmap.h:441
i64 word
Definition: types.h:111
#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.
unsigned char u8
Definition: types.h:56
static uword unformat_bitmap_list(unformat_input_t *input, va_list *va)
unformat a list of bit ranges into a bitmap (eg "0-3,5-7,11" )
Definition: bitmap.h:693
Linear Congruential Random Number Generator.
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:424
#define BITS(x)
Definition: clib.h:58
static uword clib_bitmap_next_set(uword *ai, uword i)
Return the next set bit in a bitmap starting at bit i.
Definition: bitmap.h:630
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:169