vppinfra: initial RISC-V support
[vpp.git] / src / vppinfra / bitmap.h
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
50 typedef uword clib_bitmap_t;
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 */
56 always_inline uword
57 clib_bitmap_is_zero (uword * ai)
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 */
71 always_inline uword
72 clib_bitmap_is_equal (uword * a, uword * b)
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 /** Copy a bitmap
119     @param dst - copy to
120     @param src - copy from
121 */
122 static_always_inline void
123 clib_bitmap_copy (clib_bitmap_t **dst, const clib_bitmap_t *src)
124 {
125   if (vec_len (src))
126     {
127       clib_bitmap_vec_validate (*dst, vec_len (src) - 1);
128       vec_copy (*dst, src);
129     }
130   else
131     {
132       vec_reset_length (*dst);
133     }
134 }
135
136 /* low-level routine to remove trailing zeros from a bitmap */
137 always_inline uword *
138 _clib_bitmap_remove_trailing_zeros (uword * a)
139 {
140   word i;
141   if (a)
142     {
143       for (i = _vec_len (a) - 1; i >= 0; i--)
144         if (a[i] != 0)
145           break;
146       _vec_len (a) = i + 1;
147     }
148   return a;
149 }
150
151 /** Sets the ith bit of a bitmap to new_value.
152     No sanity checking. Be careful.
153     @param a - pointer to the bitmap
154     @param i - the bit position to interrogate
155     @param new_value - new value for the bit
156     @returns the old value of the bit
157 */
158 always_inline uword
159 clib_bitmap_set_no_check (uword * a, uword i, uword new_value)
160 {
161   uword i0 = i / BITS (a[0]);
162   uword i1 = i % BITS (a[0]);
163   uword bit = (uword) 1 << i1;
164   uword ai, old_value;
165
166   /* Removed ASSERT since uword * a may not be a vector. */
167   /* ASSERT (i0 < vec_len (a)); */
168
169   ai = a[i0];
170   old_value = (ai & bit) != 0;
171   ai &= ~bit;
172   ai |= ((uword) (new_value != 0)) << i1;
173   a[i0] = ai;
174   return old_value;
175 }
176
177 /** Sets the ith bit of a bitmap to new_value
178     Removes trailing zeros from the bitmap
179     @param ai - pointer to the bitmap
180     @param i - the bit position to interrogate
181     @param value - new value for the bit
182     @returns the old value of the bit
183 */
184 always_inline uword *
185 clib_bitmap_set (uword * ai, uword i, uword value)
186 {
187   uword i0 = i / BITS (ai[0]);
188   uword i1 = i % BITS (ai[0]);
189   uword a;
190
191   /* Check for writing a zero to beyond end of bitmap. */
192   if (value == 0 && i0 >= vec_len (ai))
193     return ai;                  /* Implied trailing zeros. */
194
195   clib_bitmap_vec_validate (ai, i0);
196
197   a = ai[i0];
198   a &= ~((uword) 1 << i1);
199   a |= ((uword) (value != 0)) << i1;
200   ai[i0] = a;
201
202   /* If bits have been cleared, test for zero. */
203   if (a == 0)
204     ai = _clib_bitmap_remove_trailing_zeros (ai);
205
206   return ai;
207 }
208
209 /** Gets the ith bit value from a bitmap
210     @param ai - pointer to the bitmap
211     @param i - the bit position to interrogate
212     @returns the indicated bit value
213 */
214 always_inline uword
215 clib_bitmap_get (uword * ai, uword i)
216 {
217   uword i0 = i / BITS (ai[0]);
218   uword i1 = i % BITS (ai[0]);
219   return i0 < vec_len (ai) && 0 != ((ai[i0] >> i1) & 1);
220 }
221
222 /** Gets the ith bit value from a bitmap
223     Does not sanity-check the bit position. Be careful.
224     @param ai - pointer to the bitmap
225     @param i - the bit position to interrogate
226     @returns the indicated bit value, or garbage if the bit position is
227     out of range.
228 */
229 always_inline uword
230 clib_bitmap_get_no_check (uword * ai, uword i)
231 {
232   uword i0 = i / BITS (ai[0]);
233   uword i1 = i % BITS (ai[0]);
234   return 0 != ((ai[i0] >> i1) & 1);
235 }
236
237 always_inline uword
238 clib_bitmap_get_multiple_no_check (uword * ai, uword i, uword n_bits)
239 {
240   uword i0 = i / BITS (ai[0]);
241   uword i1 = i % BITS (ai[0]);
242   ASSERT (i1 + n_bits <= BITS (uword));
243   return 0 != ((ai[i0] >> i1) & pow2_mask (n_bits));
244 }
245
246 /** Gets the ith through ith + n_bits bit values from a bitmap
247     @param bitmap - pointer to the bitmap
248     @param i - the first bit position to retrieve
249     @param n_bits - the number of bit positions to retrieve
250     @returns the indicated range of bits
251 */
252 always_inline uword
253 clib_bitmap_get_multiple (uword * bitmap, uword i, uword n_bits)
254 {
255   uword i0, i1, result;
256   uword l = vec_len (bitmap);
257
258   ASSERT (n_bits <= BITS (result));
259
260   i0 = i / BITS (bitmap[0]);
261   i1 = i % BITS (bitmap[0]);
262
263   /* Check first word. */
264   result = 0;
265   if (i0 < l)
266     {
267       result |= (bitmap[i0] >> i1);
268       if (n_bits < BITS (bitmap[0]))
269         result &= (((uword) 1 << n_bits) - 1);
270     }
271
272   /* Check for overlap into next word. */
273   i0++;
274   if (i1 + n_bits > BITS (bitmap[0]) && i0 < l)
275     {
276       n_bits -= BITS (bitmap[0]) - i1;
277       result |=
278         (bitmap[i0] & (((uword) 1 << n_bits) - 1)) << (BITS (bitmap[0]) - i1);
279     }
280
281   return result;
282 }
283
284 /** sets the ith through ith + n_bits bits in a bitmap
285     @param bitmap - pointer to the bitmap
286     @param i - the first bit position to retrieve
287     @param value - the values to set
288     @param n_bits - the number of bit positions to set
289     @returns a pointer to the updated bitmap, which may expand and move
290 */
291
292 always_inline uword *
293 clib_bitmap_set_multiple (uword * bitmap, uword i, uword value, uword n_bits)
294 {
295   uword i0, i1, l, t, m;
296
297   ASSERT (n_bits <= BITS (value));
298
299   i0 = i / BITS (bitmap[0]);
300   i1 = i % BITS (bitmap[0]);
301
302   /* Allocate bitmap. */
303   clib_bitmap_vec_validate (bitmap, (i + n_bits) / BITS (bitmap[0]));
304   l = vec_len (bitmap);
305
306   m = ~0;
307   if (n_bits < BITS (value))
308     m = (((uword) 1 << n_bits) - 1);
309   value &= m;
310
311   /* Insert into first word. */
312   t = bitmap[i0];
313   t &= ~(m << i1);
314   t |= value << i1;
315   bitmap[i0] = t;
316
317   /* Insert into second word. */
318   i0++;
319   if (i1 + n_bits > BITS (bitmap[0]) && i0 < l)
320     {
321       t = BITS (bitmap[0]) - i1;
322       value >>= t;
323       n_bits -= t;
324       t = bitmap[i0];
325       m = ((uword) 1 << n_bits) - 1;
326       t &= ~m;
327       t |= value;
328       bitmap[i0] = t;
329     }
330
331   return bitmap;
332 }
333
334 always_inline uword *
335 clib_bitmap_set_region (uword * bitmap, uword i, uword value, uword n_bits)
336 {
337   uword a0, a1, b0;
338   uword i_end, mask;
339
340   a0 = i / BITS (bitmap[0]);
341   a1 = i % BITS (bitmap[0]);
342
343   i_end = i + n_bits;
344   b0 = i_end / BITS (bitmap[0]);
345
346   clib_bitmap_vec_validate (bitmap, b0);
347
348   /* First word. */
349   mask = n_bits < BITS (bitmap[0]) ? pow2_mask (n_bits) : ~0;
350   mask <<= a1;
351
352   if (value)
353     bitmap[a0] |= mask;
354   else
355     bitmap[a0] &= ~mask;
356
357   for (a0++; a0 < b0; a0++)
358     bitmap[a0] = value ? ~0 : 0;
359
360   if (a0 == b0)
361     {
362       word n_bits_left = n_bits - (BITS (bitmap[0]) - a1);
363       mask = pow2_mask (n_bits_left);
364       if (value)
365         bitmap[a0] |= mask;
366       else
367         bitmap[a0] &= ~mask;
368     }
369
370   return bitmap;
371 }
372
373 /** Macro to iterate across set bits in a bitmap
374
375     @param i - the current set bit
376     @param ai - the bitmap
377     @param body - the expression to evaluate for each set bit
378 */
379 #define clib_bitmap_foreach(i,ai)                                       \
380   if (ai)                                                               \
381     for (i = clib_bitmap_first_set (ai);                                \
382          i != ~0;                                                       \
383          i = clib_bitmap_next_set (ai, i + 1))
384
385 /** Return the lowest numbered set bit in a bitmap
386     @param ai - pointer to the bitmap
387     @returns lowest numbered set bit, or ~0 if the entire bitmap is zero
388 */
389 always_inline uword
390 clib_bitmap_first_set (uword * ai)
391 {
392   uword i = 0;
393 #if uword_bits == 64
394 #if defined(CLIB_HAVE_VEC256)
395   while (i + 7 < vec_len (ai))
396     {
397       u64x4 v;
398       v = u64x4_load_unaligned (ai + i) | u64x4_load_unaligned (ai + i + 4);
399       if (!u64x4_is_all_zero (v))
400         break;
401       i += 8;
402     }
403 #elif defined(CLIB_HAVE_VEC128) && defined(CLIB_HAVE_VEC128_UNALIGNED_LOAD_STORE)
404   while (i + 3 < vec_len (ai))
405     {
406       u64x2 v;
407       v = u64x2_load_unaligned (ai + i) | u64x2_load_unaligned (ai + i + 2);
408       if (!u64x2_is_all_zero (v))
409         break;
410       i += 4;
411     }
412 #endif
413 #endif
414   for (; i < vec_len (ai); i++)
415     {
416       uword x = ai[i];
417       if (x != 0)
418         return i * BITS (ai[0]) + log2_first_set (x);
419     }
420   return ~0;
421 }
422
423 /** Return the higest numbered set bit in a bitmap
424     @param ai - pointer to the bitmap
425     @returns lowest numbered set bit, or ~0 if the entire bitmap is zero
426 */
427 always_inline uword
428 clib_bitmap_last_set (uword * ai)
429 {
430   uword i;
431
432   for (i = vec_len (ai); i > 0; i--)
433     {
434       uword x = ai[i - 1];
435       if (x != 0)
436         {
437           uword first_bit;
438           first_bit = count_leading_zeros (x);
439           return (i) * BITS (ai[0]) - first_bit - 1;
440         }
441     }
442   return ~0;
443 }
444
445 /** Return the lowest numbered clear bit in a bitmap
446     @param ai - pointer to the bitmap
447     @returns lowest numbered clear bit
448 */
449 always_inline uword
450 clib_bitmap_first_clear (uword * ai)
451 {
452   uword i;
453   for (i = 0; i < vec_len (ai); i++)
454     {
455       uword x = ~ai[i];
456       if (x != 0)
457         return i * BITS (ai[0]) + log2_first_set (x);
458     }
459   return i * BITS (ai[0]);
460 }
461
462 /** Return the number of set bits in a bitmap
463     @param ai - pointer to the bitmap
464     @returns the number of set bits in the bitmap
465 */
466 always_inline uword
467 clib_bitmap_count_set_bits (uword * ai)
468 {
469   uword i;
470   uword n_set = 0;
471   for (i = 0; i < vec_len (ai); i++)
472     n_set += count_set_bits (ai[i]);
473   return n_set;
474 }
475
476 /** Logical operator across two bitmaps
477
478     @param ai - pointer to the destination bitmap
479     @param bi - pointer to the source bitmap
480     @returns ai = ai and bi. ai is modified, bi is not modified
481 */
482 always_inline uword *clib_bitmap_and (uword * ai, uword * bi);
483
484 /** Logical operator across two bitmaps
485
486     @param ai - pointer to the destination bitmap
487     @param bi - pointer to the source bitmap
488     @returns ai = ai & ~bi. ai is modified, bi is not modified
489 */
490 always_inline uword *clib_bitmap_andnot (uword * ai, uword * bi);
491
492 /** Logical operator across two bitmaps
493
494     @param ai - pointer to the destination bitmap
495     @param bi - pointer to the source bitmap
496     @returns ai = ai & ~bi. ai is modified, bi is not modified
497 */
498 always_inline uword *clib_bitmap_or (uword * ai, uword * bi);
499 /** Logical operator across two bitmaps
500
501     @param ai - pointer to the destination bitmap
502     @param bi - pointer to the source bitmap
503     @returns ai = ai or bi. ai is modified, bi is not modified
504 */
505 always_inline uword *clib_bitmap_or (uword * ai, uword * bi);
506
507 /** Logical operator across two bitmaps
508
509     @param ai - pointer to the destination bitmap
510     @param bi - pointer to the source bitmap
511     @returns ai = ai xor bi. ai is modified, bi is not modified
512 */
513 always_inline uword *clib_bitmap_xor (uword * ai, uword * bi);
514
515 /* ALU function definition macro for functions taking two bitmaps. */
516 #define _(name, body, check_zero)                               \
517 always_inline uword *                                           \
518 clib_bitmap_##name (uword * ai, uword * bi)                     \
519 {                                                               \
520   uword i, a, b, bi_len, n_trailing_zeros;                      \
521                                                                 \
522   n_trailing_zeros = 0;                                         \
523   bi_len = vec_len (bi);                                        \
524   if (bi_len > 0)                                               \
525     clib_bitmap_vec_validate (ai, bi_len - 1);                  \
526   for (i = 0; i < vec_len (ai); i++)                            \
527     {                                                           \
528       a = ai[i];                                                \
529       b = i < bi_len ? bi[i] : 0;                               \
530       do { body; } while (0);                                   \
531       ai[i] = a;                                                \
532       if (check_zero)                                           \
533         n_trailing_zeros = a ? 0 : (n_trailing_zeros + 1);      \
534     }                                                           \
535   if (check_zero)                                               \
536     _vec_len (ai) -= n_trailing_zeros;                          \
537   return ai;                                                    \
538 }
539
540 /* ALU functions: */
541 /* *INDENT-OFF* */
542 _(and, a = a & b, 1)
543 _(andnot, a = a & ~b, 1)
544 _(or, a = a | b, 0)
545 _(xor, a = a ^ b, 1)
546 /* *INDENT-ON* */
547 #undef _
548 /** Logical operator across two bitmaps which duplicates the first bitmap
549
550     @param ai - pointer to the destination bitmap
551     @param bi - pointer to the source bitmap
552     @returns aiDup = ai and bi. Neither ai nor bi are modified
553 */
554 always_inline uword *clib_bitmap_dup_and (uword * ai, uword * bi);
555
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 & ~bi. Neither ai nor bi are modified
561 */
562 always_inline uword *clib_bitmap_dup_andnot (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 or bi. Neither ai nor bi are modified
569 */
570 always_inline uword *clib_bitmap_dup_or (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 xor bi. Neither ai nor bi are modified
577 */
578 always_inline uword *clib_bitmap_dup_xor (uword * ai, uword * bi);
579
580 #define _(name)                                         \
581   always_inline uword *                                 \
582   clib_bitmap_dup_##name (uword * ai, uword * bi)       \
583 { return clib_bitmap_##name (clib_bitmap_dup (ai), bi); }
584
585 /* *INDENT-OFF* */
586 _(and);
587 _(andnot);
588 _(or);
589 _(xor);
590 /* *INDENT-ON* */
591 #undef _
592
593 /* ALU function definition macro for functions taking one bitmap and an
594  * immediate. */
595 #define _(name, body, check_zero)                       \
596 always_inline uword *                                   \
597 clib_bitmap_##name (uword * ai, uword i)                \
598 {                                                       \
599   uword i0 = i / BITS (ai[0]);                          \
600   uword i1 = i % BITS (ai[0]);                          \
601   uword a, b;                                           \
602   clib_bitmap_vec_validate (ai, i0);                    \
603   a = ai[i0];                                           \
604   b = (uword) 1 << i1;                                  \
605   do { body; } while (0);                               \
606   ai[i0] = a;                                           \
607   if (check_zero && a == 0)                             \
608     ai = _clib_bitmap_remove_trailing_zeros (ai);       \
609   return ai;                                            \
610 }
611
612 /* ALU functions immediate: */
613 /* *INDENT-OFF* */
614 _(andi, a = a & b, 1)
615 _(andnoti, a = a & ~b, 1)
616 _(ori, a = a | b, 0)
617 _(xori, a = a ^ b, 1)
618 /* *INDENT-ON* */
619 #undef _
620
621 /* ALU function definition macro for functions taking one bitmap and an
622  * immediate. No tail trimming */
623 #define _(name, body)                                   \
624 always_inline uword *                                   \
625 clib_bitmap_##name##_notrim (uword * ai, uword i)       \
626 {                                                       \
627   uword i0 = i / BITS (ai[0]);                          \
628   uword i1 = i % BITS (ai[0]);                          \
629   uword a, b;                                           \
630   clib_bitmap_vec_validate (ai, i0);                    \
631   a = ai[i0];                                           \
632   b = (uword) 1 << i1;                                  \
633   do { body; } while (0);                               \
634   ai[i0] = a;                                           \
635   return ai;                                            \
636 }
637
638 /* ALU functions immediate: */
639 /* *INDENT-OFF* */
640 _(andi, a = a & b)
641 _(andnoti, a = a & ~b)
642 _(ori, a = a | b)
643 _(xori, a = a ^ b)
644 #undef _
645 /* *INDENT-ON* */
646
647 /** Return a random bitmap of the requested length
648     @param ai - pointer to the destination bitmap
649     @param n_bits - number of bits to allocate
650     @param [in,out] seed - pointer to the random number seed
651     @returns a reasonably random bitmap based. See random.h.
652 */
653 always_inline uword *
654 clib_bitmap_random (uword * ai, uword n_bits, u32 * seed)
655 {
656   vec_reset_length (ai);
657
658   if (n_bits > 0)
659     {
660       uword i = n_bits - 1;
661       uword i0, i1;
662       uword log2_rand_max;
663
664       log2_rand_max = min_log2 (random_u32_max ());
665
666       i0 = i / BITS (ai[0]);
667       i1 = i % BITS (ai[0]);
668
669       clib_bitmap_vec_validate (ai, i0);
670       for (i = 0; i <= i0; i++)
671         {
672           uword n;
673           for (n = 0; n < BITS (ai[i]); n += log2_rand_max)
674             ai[i] |= random_u32 (seed) << n;
675         }
676       if (i1 + 1 < BITS (ai[0]))
677         ai[i0] &= (((uword) 1 << (i1 + 1)) - 1);
678     }
679   return ai;
680 }
681
682 /** Return the next set bit in a bitmap starting at bit i
683     @param ai - pointer to the bitmap
684     @param i - first bit position to test
685     @returns first set bit position at or after i,
686     ~0 if no further set bits are found
687 */
688 always_inline uword
689 clib_bitmap_next_set (uword * ai, uword i)
690 {
691   uword i0 = i / BITS (ai[0]);
692   uword i1 = i % BITS (ai[0]);
693   uword t;
694
695   if (i0 < vec_len (ai))
696     {
697       t = (ai[i0] >> i1) << i1;
698       if (t)
699         return log2_first_set (t) + i0 * BITS (ai[0]);
700
701       for (i0++; i0 < vec_len (ai); i0++)
702         {
703           t = ai[i0];
704           if (t)
705             return log2_first_set (t) + i0 * BITS (ai[0]);
706         }
707     }
708
709   return ~0;
710 }
711
712 /** Return the next clear bit in a bitmap starting at bit i
713     @param ai - pointer to the bitmap
714     @param i - first bit position to test
715     @returns first clear bit position at or after i
716 */
717 always_inline uword
718 clib_bitmap_next_clear (uword * ai, uword i)
719 {
720   uword i0 = i / BITS (ai[0]);
721   uword i1 = i % BITS (ai[0]);
722   uword t;
723
724   if (i0 < vec_len (ai))
725     {
726       t = (~ai[i0] >> i1) << i1;
727       if (t)
728         return log2_first_set (t) + i0 * BITS (ai[0]);
729
730       for (i0++; i0 < vec_len (ai); i0++)
731         {
732           t = ~ai[i0];
733           if (t)
734             return log2_first_set (t) + i0 * BITS (ai[0]);
735         }
736
737       /* no clear bit left in bitmap, return bit just beyond bitmap */
738       return (i0 * BITS (ai[0])) + 1;
739     }
740   return i;
741 }
742
743 uword unformat_bitmap_mask (unformat_input_t *input, va_list *va);
744 uword unformat_bitmap_list (unformat_input_t *input, va_list *va);
745 u8 *format_bitmap_hex (u8 *s, va_list *args);
746 u8 *format_bitmap_list (u8 *s, va_list *args);
747
748 #endif /* included_clib_bitmap_h */
749
750 /*
751  * fd.io coding-style-patch-verification: ON
752  *
753  * Local Variables:
754  * eval: (c-set-style "gnu")
755  * End:
756  */