Branch data Line data Source code
1 : : /* SPDX-License-Identifier: BSD-3-Clause
2 : : * Copyright(c) 2023 Ericsson AB
3 : : */
4 : :
5 : : #ifndef _RTE_BITSET_H_
6 : : #define _RTE_BITSET_H_
7 : :
8 : : /**
9 : : * @file
10 : : * RTE Bitset
11 : : *
12 : : * This file provides functions and macros for querying and
13 : : * manipulating sets of bits kept in arrays of @c uint64_t-sized
14 : : * elements.
15 : : *
16 : : * The bits in a bitset are numbered from 0 to @c size - 1, with the
17 : : * lowest index being the least significant bit.
18 : : *
19 : : * The bitset array must be properly aligned.
20 : : *
21 : : * For optimal performance, the @c size parameter, required by
22 : : * many of the API's functions, should be a compile-time constant.
23 : : *
24 : : * For large bitsets, the rte_bitmap.h API may be more appropriate.
25 : : *
26 : : * @warning
27 : : * All functions modifying a bitset may overwrite any unused bits of
28 : : * the last word. Such unused bits are ignored by all functions reading
29 : : * bits.
30 : : */
31 : :
32 : : #include <limits.h>
33 : : #include <stdbool.h>
34 : : #include <stddef.h>
35 : : #include <stdint.h>
36 : :
37 : : #include <rte_bitops.h>
38 : : #include <rte_branch_prediction.h>
39 : : #include <rte_common.h>
40 : : #include <rte_compat.h>
41 : : #include <rte_debug.h>
42 : : #include <rte_memcpy.h>
43 : :
44 : : #ifdef __cplusplus
45 : : extern "C" {
46 : : #endif
47 : :
48 : : /**
49 : : * The size (in bytes) of each element in the array used to represent
50 : : * a bitset.
51 : : */
52 : : #define RTE_BITSET_WORD_SIZE (sizeof(uint64_t))
53 : :
54 : : /**
55 : : * The size (in bits) of each element in the array used to represent
56 : : * a bitset.
57 : : */
58 : : #define RTE_BITSET_WORD_BITS (RTE_BITSET_WORD_SIZE * CHAR_BIT)
59 : :
60 : : /**
61 : : * Computes the number of words required to store @c size bits.
62 : : */
63 : : #define RTE_BITSET_NUM_WORDS(size) \
64 : : ((size + RTE_BITSET_WORD_BITS - 1) / RTE_BITSET_WORD_BITS)
65 : :
66 : : /**
67 : : * Computes the amount of memory (in bytes) required to fit a bitset
68 : : * holding @c size bits.
69 : : */
70 : : #define RTE_BITSET_SIZE(size) \
71 : : ((size_t)(RTE_BITSET_NUM_WORDS(size) * RTE_BITSET_WORD_SIZE))
72 : :
73 : : #define __RTE_BITSET_WORD_IDX(bit_num) ((bit_num) / RTE_BITSET_WORD_BITS)
74 : : #define __RTE_BITSET_BIT_OFFSET(bit_num) ((bit_num) % RTE_BITSET_WORD_BITS)
75 : : #define __RTE_BITSET_UNUSED(size) \
76 : : ((RTE_BITSET_NUM_WORDS(size) * RTE_BITSET_WORD_BITS) - (size))
77 : : #define __RTE_BITSET_USED_MASK(size) \
78 : : (UINT64_MAX >> __RTE_BITSET_UNUSED(size))
79 : :
80 : : #define __RTE_BITSET_DELEGATE_N(fun, bitset, bit_num, ...) \
81 : : fun(&(bitset)[__RTE_BITSET_WORD_IDX(bit_num)], __RTE_BITSET_BIT_OFFSET(bit_num), \
82 : : __VA_ARGS__)
83 : :
84 : : /* MSVC doesn't have ##__VA_ARGS__, so argument-less -> special case */
85 : : #define __RTE_BITSET_DELEGATE(fun, bitset, bit_num) \
86 : : fun(&(bitset)[__RTE_BITSET_WORD_IDX(bit_num)], __RTE_BITSET_BIT_OFFSET(bit_num))
87 : :
88 : : /**
89 : : * Declare a bitset.
90 : : *
91 : : * Declare (e.g., as a struct field) or define (e.g., as a stack
92 : : * variable) a bitset of the specified size.
93 : : *
94 : : * @param size
95 : : * The number of bits the bitset must be able to represent. Must be
96 : : * a compile-time constant.
97 : : * @param name
98 : : * The field or variable name of the resulting definition.
99 : : */
100 : : #define RTE_BITSET_DECLARE(name, size) \
101 : : uint64_t name[RTE_BITSET_NUM_WORDS(size)]
102 : :
103 : : #define __RTE_BITSET_FOREACH_LEFT(var, size, start_bit, len) \
104 : : ((len) - 1 - ((var) >= (start_bit) ? (var) - (start_bit) : (size) - (start_bit) + (var)))
105 : :
106 : : #define __RTE_BITSET_FOREACH(var, bitset, size, start_bit, len, flags) \
107 : : for ((var) = __rte_bitset_find(bitset, size, start_bit, len, flags); \
108 : : (var) != -1; \
109 : : (var) = __RTE_BITSET_FOREACH_LEFT(var, size, start_bit, len) > 0 ? \
110 : : __rte_bitset_find(bitset, size, ((var) + 1) % (size), \
111 : : __RTE_BITSET_FOREACH_LEFT(var, size, start_bit, len), flags) : -1)
112 : :
113 : : /**
114 : : * Iterate over all bits set.
115 : : *
116 : : * This macro iterates over all bits set (i.e., all ones) in the
117 : : * bitset, in the forward direction (i.e., starting with the least
118 : : * significant '1').
119 : : *
120 : : * @param var
121 : : * An iterator variable of type @c ssize_t. For each successive
122 : : * iteration, this variable will hold the bit index of a set bit.
123 : : * @param bitset
124 : : * A <tt>const uint64_t *</tt> pointer to the bitset array.
125 : : * @param size
126 : : * The size of the bitset (in bits).
127 : : */
128 : : #define RTE_BITSET_FOREACH_SET(var, bitset, size) \
129 : : __RTE_BITSET_FOREACH(var, bitset, size, 0, size, 0)
130 : :
131 : : /**
132 : : * Iterate over all bits cleared.
133 : : *
134 : : * This macro iterates over all bits cleared in the bitset, in the
135 : : * forward direction (i.e., starting with the lowest-indexed set bit).
136 : : *
137 : : * @param var
138 : : * An iterator variable of type @c ssize_t. For each successive iteration,
139 : : * this variable will hold the bit index of a cleared bit.
140 : : * @param bitset
141 : : * A <tt>const uint64_t *</tt> pointer to the bitset array.
142 : : * @param size
143 : : * The size of the bitset (in bits).
144 : : */
145 : : #define RTE_BITSET_FOREACH_CLEAR(var, bitset, size) \
146 : : __RTE_BITSET_FOREACH(var, bitset, size, 0, size, __RTE_BITSET_FIND_FLAG_FIND_CLEAR)
147 : :
148 : : /**
149 : : * Iterate over all bits set within a range.
150 : : *
151 : : * This macro iterates over all bits set (i.e., all ones) in the
152 : : * specified range, in the forward direction (i.e., starting with the
153 : : * least significant '1').
154 : : *
155 : : * @param var
156 : : * An iterator variable of type @c ssize_t. For each successive iteration,
157 : : * this variable will hold the bit index of a set bit.
158 : : * @param bitset
159 : : * A <tt>const uint64_t *</tt> pointer to the bitset array.
160 : : * @param size
161 : : * The size of the bitset (in bits).
162 : : * @param start_bit
163 : : * The index of the first bit to check. Must be less than @c size.
164 : : * @param len
165 : : * The length (in bits) of the range. @c start_bit + @c len must be less
166 : : * than or equal to @c size.
167 : : */
168 : : #define RTE_BITSET_FOREACH_SET_RANGE(var, bitset, size, start_bit, len) \
169 : : __RTE_BITSET_FOREACH(var, bitset, size, start_bit, len, 0)
170 : :
171 : : /**
172 : : * Iterate over all cleared bits within a range.
173 : : *
174 : : * This macro iterates over all bits cleared (i.e., all zeroes) in the
175 : : * specified range, in the forward direction (i.e., starting with the
176 : : * least significant '0').
177 : : *
178 : : * @param var
179 : : * An iterator variable of type @c ssize_t. For each successive iteration,
180 : : * this variable will hold the bit index of a set bit.
181 : : * @param bitset
182 : : * A <tt>const uint64_t *</tt> pointer to the bitset array.
183 : : * @param size
184 : : * The size of the bitset (in bits).
185 : : * @param start_bit
186 : : * The index of the first bit to check. Must be less than @c size.
187 : : * @param len
188 : : * The length (in bits) of the range. @c start_bit + @c len must be less
189 : : * than or equal to @c size.
190 : : */
191 : : #define RTE_BITSET_FOREACH_CLEAR_RANGE(var, bitset, size, start_bit, len) \
192 : : __RTE_BITSET_FOREACH(var, bitset, size, start_bit, len, __RTE_BITSET_FIND_FLAG_FIND_CLEAR)
193 : :
194 : : #define RTE_BITSET_FOREACH_SET_WRAP(var, bitset, size, start_bit, len) \
195 : : __RTE_BITSET_FOREACH(var, bitset, size, start_bit, len, __RTE_BITSET_FIND_FLAG_WRAP)
196 : :
197 : : #define RTE_BITSET_FOREACH_CLEAR_WRAP(var, bitset, size, start_bit, len) \
198 : : __RTE_BITSET_FOREACH(var, bitset, size, start_bit, len, \
199 : : __RTE_BITSET_FIND_FLAG_WRAP | __RTE_BITSET_FIND_FLAG_FIND_CLEAR)
200 : :
201 : : /**
202 : : * Initializes a bitset.
203 : : *
204 : : * All bits are cleared.
205 : : *
206 : : * In case all words in the bitset array are already set to zero by
207 : : * other means (e.g., at the time of memory allocation), this function
208 : : * need not be called.
209 : : *
210 : : * @param bitset
211 : : * A pointer to the array of bitset 64-bit words.
212 : : * @param size
213 : : * The size of the bitset (in bits).
214 : : */
215 : : static inline void
216 : : rte_bitset_init(uint64_t *bitset, size_t size)
217 : : {
218 : 140005 : memset(bitset, 0, RTE_BITSET_SIZE(size));
219 : : }
220 : :
221 : : /**
222 : : * Test if a bit is set.
223 : : *
224 : : * @param bitset
225 : : * A pointer to the array of words making up the bitset.
226 : : * @param bit_num
227 : : * Index of the bit to test. Index 0 is the least significant bit.
228 : : * @return
229 : : * Returns true if the bit is '1', and false if the bit is '0'.
230 : : */
231 : : static inline bool
232 : 15001499 : rte_bitset_test(const uint64_t *bitset, size_t bit_num)
233 : : {
234 [ + + + + : 15864989 : return __RTE_BITSET_DELEGATE(rte_bit_test, bitset, bit_num);
- + ]
235 : : }
236 : :
237 : : /**
238 : : * Set a bit in the bitset.
239 : : *
240 : : * Bits are numbered from 0 to (size - 1) (inclusive).
241 : : *
242 : : * The operation is not guaranteed to be atomic.
243 : : *
244 : : * @param bitset
245 : : * A pointer to the array of words making up the bitset.
246 : : * @param bit_num
247 : : * The index of the bit to be set.
248 : : */
249 : : static inline void
250 : 2522115 : rte_bitset_set(uint64_t *bitset, size_t bit_num)
251 : : {
252 [ + + + - ]: 17161734 : __RTE_BITSET_DELEGATE(rte_bit_set, bitset, bit_num);
253 : 8744510 : }
254 : :
255 : : /**
256 : : * Clear a bit in the bitset.
257 : : *
258 : : * Bits are numbered 0 to (size - 1) (inclusive).
259 : : *
260 : : * The operation is not guaranteed to be atomic.
261 : : *
262 : : * @param bitset
263 : : * A pointer to the array of words making up the bitset.
264 : : * @param bit_num
265 : : * The index of the bit to be cleared.
266 : : */
267 : : static inline void
268 : 2518822 : rte_bitset_clear(uint64_t *bitset, size_t bit_num)
269 : : {
270 : 8932521 : __RTE_BITSET_DELEGATE(rte_bit_clear, bitset, bit_num);
271 : 8742970 : }
272 : :
273 : : /**
274 : : * Set or clear a bit in the bitset.
275 : : *
276 : : * Bits are numbered 0 to (size - 1) (inclusive).
277 : : *
278 : : * The operation is not guaranteed to be atomic.
279 : : *
280 : : * @param bitset
281 : : * A pointer to the array of words making up the bitset.
282 : : * @param bit_num
283 : : * The index of the bit to be set or cleared.
284 : : * @param bit_value
285 : : * Control if the bit should be set or cleared.
286 : : */
287 : : static inline void
288 : 4980281 : rte_bitset_assign(uint64_t *bitset, size_t bit_num, bool bit_value)
289 : : {
290 [ + + + + : 26675495 : __RTE_BITSET_DELEGATE_N(rte_bit_assign, bitset, bit_num, bit_value);
+ + + + +
+ + + ]
291 : 4980281 : }
292 : :
293 : : /**
294 : : * Change the value of a bit in the bitset.
295 : : *
296 : : * Bits are numbered 0 to (size - 1) (inclusive).
297 : : *
298 : : * The operation is not guaranteed to be atomic.
299 : : *
300 : : * @param bitset
301 : : * A pointer to the array of words making up the bitset.
302 : : * @param bit_num
303 : : * The index of the bit to be flipped.
304 : : */
305 : : static inline void
306 : 4980281 : rte_bitset_flip(uint64_t *bitset, size_t bit_num)
307 : : {
308 [ + + ]: 4980281 : __RTE_BITSET_DELEGATE(rte_bit_flip, bitset, bit_num);
309 : 4980281 : }
310 : :
311 : : /**
312 : : * Atomically test if a bit is set.
313 : : *
314 : : * Atomically test if a bit in a bitset is set with the specified
315 : : * memory ordering.
316 : : *
317 : : * @param bitset
318 : : * A pointer to the array of words making up the bitset.
319 : : * @param bit_num
320 : : * Index of the bit to test. Index 0 is the least significant bit.
321 : : * @param memory_order
322 : : * The memory order to use.
323 : : * @return
324 : : * Returns true if the bit is '1', and false if the bit is '0'.
325 : : */
326 : : static inline bool
327 : : rte_bitset_atomic_test(const uint64_t *bitset, size_t bit_num, int memory_order)
328 : : {
329 : 14971660 : return __RTE_BITSET_DELEGATE_N(rte_bit_atomic_test, bitset, bit_num, memory_order);
330 : : }
331 : :
332 : : /**
333 : : * Atomically set a bit in the bitset.
334 : : *
335 : : * Set a bit in a bitset as an atomic operation, with the specified
336 : : * memory ordering.
337 : : *
338 : : * rte_bitset_atomic_set() is multi-thread safe, provided all threads
339 : : * acting in parallel on the same bitset does so through
340 : : * @c rte_bitset_atomic_*() functions.
341 : : *
342 : : * Bits are numbered from 0 to (size - 1) (inclusive).
343 : : *
344 : : * @param bitset
345 : : * A pointer to the array of words making up the bitset.
346 : : * @param bit_num
347 : : * The index of the bit to be set.
348 : : * @param memory_order
349 : : * The memory order to use.
350 : : */
351 : : static inline void
352 : : rte_bitset_atomic_set(uint64_t *bitset, size_t bit_num, int memory_order)
353 : : {
354 : 2509899 : __RTE_BITSET_DELEGATE_N(rte_bit_atomic_set, bitset, bit_num, memory_order);
355 : : }
356 : :
357 : : /**
358 : : * Atomically clear a bit in the bitset.
359 : : *
360 : : * Clear a bit in a bitset as an atomic operation, with the specified
361 : : * memory ordering.
362 : : *
363 : : * rte_bitset_atomic_clear() is multi-thread safe, provided all
364 : : * threads acting in parallel on the same bitset does so through @c
365 : : * rte_bitset_atomic_*() functions.
366 : : *
367 : : * Bits are numbered from 0 to (size - 1) (inclusive).
368 : : *
369 : : * @param bitset
370 : : * A pointer to the array of words making up the bitset.
371 : : * @param bit_num
372 : : * The index of the bit to be cleared.
373 : : * @param memory_order
374 : : * The memory order to use.
375 : : */
376 : : static inline void
377 : : rte_bitset_atomic_clear(uint64_t *bitset, size_t bit_num, int memory_order)
378 : : {
379 : 2512449 : __RTE_BITSET_DELEGATE_N(rte_bit_atomic_clear, bitset, bit_num, memory_order);
380 : : }
381 : :
382 : : /**
383 : : * Atomically set or clear a bit in the bitset.
384 : : *
385 : : * Assign a value to a bit in a bitset as an atomic operation, with
386 : : * the specified memory ordering.
387 : : *
388 : : * rte_bitset_atomic_assign() is multi-thread safe, provided all
389 : : * threads acting in parallel on the same bitset does so through
390 : : * @c rte_bitset_atomic_*() functions.
391 : : *
392 : : * Bits are numbered from 0 to (size - 1) (inclusive).
393 : : *
394 : : * @param bitset
395 : : * A pointer to the array of words making up the bitset.
396 : : * @param bit_num
397 : : * The index of the bit to be set or cleared.
398 : : * @param bit_value
399 : : * Control if the bit should be set or cleared.
400 : : * @param memory_order
401 : : * The memory order to use.
402 : : */
403 : : static inline void
404 : : rte_bitset_atomic_assign(uint64_t *bitset, size_t bit_num, bool bit_value, int memory_order)
405 : : {
406 : 4974656 : __RTE_BITSET_DELEGATE_N(rte_bit_atomic_assign, bitset, bit_num, bit_value, memory_order);
407 : : }
408 : :
409 : : /**
410 : : * Atomically change the value of a bit in the bitset.
411 : : *
412 : : * Flip a bit in a bitset as an atomic operation, with the specified
413 : : * memory ordering.
414 : : *
415 : : * rte_bitset_atomic_flip() is multi-thread safe, provided all threads
416 : : * acting in parallel on the same bitset does so through
417 : : * @c rte_bitset_atomic_*() functions.
418 : : *
419 : : * Bits are numbered from 0 to (size - 1) (inclusive).
420 : : *
421 : : * @param bitset
422 : : * A pointer to the array of words making up the bitset.
423 : : * @param bit_num
424 : : * The index of the bit to be flipped.
425 : : * @param memory_order
426 : : * The memory order to use.
427 : : */
428 : : static inline void
429 : : rte_bitset_atomic_flip(uint64_t *bitset, size_t bit_num, int memory_order)
430 : : {
431 : 4974656 : __RTE_BITSET_DELEGATE_N(rte_bit_atomic_flip, bitset, bit_num, memory_order);
432 : : }
433 : :
434 : : /**
435 : : * Set all bits in the bitset.
436 : : *
437 : : * @param bitset
438 : : * A pointer to the array of words making up the bitset.
439 : : * @param size
440 : : * The size of the bitset (in bits).
441 : : */
442 : : static inline void
443 : : rte_bitset_set_all(uint64_t *bitset, size_t size)
444 : : {
445 : : memset(bitset, 0xFF, RTE_BITSET_SIZE(size));
446 : : }
447 : :
448 : : /**
449 : : * Clear all bits in the bitset.
450 : : *
451 : : * @param bitset
452 : : * A pointer to the array of words making up the bitset.
453 : : * @param size
454 : : * The size of the bitset (in bits).
455 : : */
456 : : static inline void
457 : : rte_bitset_clear_all(uint64_t *bitset, size_t size)
458 : : {
459 : : rte_bitset_init(bitset, size);
460 : 0 : }
461 : :
462 : : /**
463 : : * Count all set bits (also known as the @e weight).
464 : : *
465 : : * @param bitset
466 : : * A pointer to the array of words making up the bitset.
467 : : * @param size
468 : : * The size of the bitset (in bits).
469 : : * @return
470 : : * Returns the number of '1' bits in the bitset.
471 : : */
472 : : static inline size_t
473 : 60069 : rte_bitset_count_set(const uint64_t *bitset, size_t size)
474 : : {
475 : : size_t i;
476 : : size_t total = 0;
477 : :
478 : : /*
479 : : * Unused bits in a rte_bitset are always '0', and thus are
480 : : * not included in this count.
481 : : */
482 [ + + ]: 497770 : for (i = 0; i < RTE_BITSET_NUM_WORDS(size) - 1; i++)
483 : 437701 : total += rte_popcount64(bitset[i]);
484 : :
485 : 60069 : total += rte_popcount64(bitset[i] & __RTE_BITSET_USED_MASK(size));
486 : :
487 : 60069 : return total;
488 : : }
489 : :
490 : : /**
491 : : * Count all cleared bits.
492 : : *
493 : : * @param bitset
494 : : * A pointer to the array of words making up the bitset.
495 : : * @param size
496 : : * The size of the bitset (in bits).
497 : : * @return
498 : : * Returns the number of '0' bits in the bitset.
499 : : */
500 : : static inline size_t
501 : : rte_bitset_count_clear(const uint64_t *bitset, size_t size)
502 : : {
503 : 18 : return size - rte_bitset_count_set(bitset, size);
504 : : }
505 : :
506 : : #define __RTE_BITSET_FIND_FLAG_FIND_CLEAR (1U << 0)
507 : : #define __RTE_BITSET_FIND_FLAG_WRAP (1U << 1)
508 : :
509 : : static inline ssize_t
510 : 6136901 : __rte_bitset_find_nowrap(const uint64_t *bitset, size_t __rte_unused size, size_t start_bit,
511 : : size_t len, bool find_clear)
512 : : {
513 : : size_t word_idx;
514 : : size_t offset;
515 : 6136901 : size_t end_bit = start_bit + len;
516 : :
517 : : RTE_ASSERT(end_bit <= size);
518 : :
519 [ + + ]: 6136901 : if (unlikely(len == 0))
520 : : return -1;
521 : :
522 : 6124885 : word_idx = __RTE_BITSET_WORD_IDX(start_bit);
523 : 6124885 : offset = __RTE_BITSET_BIT_OFFSET(start_bit);
524 : :
525 [ + + ]: 6401767 : while (word_idx <= __RTE_BITSET_WORD_IDX(end_bit - 1)) {
526 : : uint64_t word;
527 : :
528 : 6206611 : word = bitset[word_idx];
529 [ + + ]: 6206611 : if (find_clear)
530 : 2912216 : word = ~word;
531 : :
532 : 6206611 : word >>= offset;
533 : :
534 [ + + ]: 6206611 : if (word != 0) {
535 : 5929729 : size_t ffs = start_bit + rte_bsf64(word);
536 : :
537 : : /*
538 : : * Check if set bit were among the last,
539 : : * unused bits, in the last word.
540 : : */
541 [ + + ]: 5929729 : if (unlikely(ffs >= end_bit))
542 : : return -1;
543 : :
544 : 5890511 : return ffs;
545 : : }
546 : :
547 : 276882 : start_bit += (RTE_BITSET_WORD_BITS - offset);
548 : 276882 : word_idx++;
549 : : offset = 0;
550 : : }
551 : :
552 : : return -1;
553 : :
554 : : }
555 : :
556 : : static inline ssize_t
557 : 6121886 : __rte_bitset_find(const uint64_t *bitset, size_t size, size_t start_bit, size_t len,
558 : : unsigned int flags)
559 : : {
560 : 6121886 : bool find_clear = flags & __RTE_BITSET_FIND_FLAG_FIND_CLEAR;
561 : 6121886 : bool may_wrap = flags & __RTE_BITSET_FIND_FLAG_WRAP;
562 : 6121886 : bool does_wrap = (start_bit + len) > size;
563 : : ssize_t rc;
564 : :
565 : : RTE_ASSERT(len <= size);
566 : : if (!may_wrap)
567 : : RTE_ASSERT(!does_wrap);
568 : :
569 [ + + ]: 6121886 : if (may_wrap && does_wrap) {
570 : 1837966 : size_t len0 = size - start_bit;
571 : 1837966 : size_t len1 = len - len0;
572 : :
573 : 1837966 : rc = __rte_bitset_find_nowrap(bitset, size, start_bit, len0, find_clear);
574 [ + + ]: 1837966 : if (rc < 0)
575 : 15015 : rc = __rte_bitset_find_nowrap(bitset, size, 0, len1, find_clear);
576 : : } else
577 : 4283920 : rc = __rte_bitset_find_nowrap(bitset, size, start_bit, len, find_clear);
578 : :
579 : 6121886 : return rc;
580 : : }
581 : :
582 : : /**
583 : : * Find first bit set.
584 : : *
585 : : * Scans the bitset in the forward direction (i.e., starting at the
586 : : * least significant bit), and returns the index of the first '1'.
587 : : *
588 : : * @param bitset
589 : : * A pointer to the array of words making up the bitset.
590 : : * @param size
591 : : * The size of the bitset (in bits).
592 : : * @return
593 : : * Returns the index of the least significant '1', or -1 if all
594 : : * bits are '0'.
595 : : */
596 : : static inline ssize_t
597 : : rte_bitset_find_first_set(const uint64_t *bitset, size_t size)
598 : : {
599 : 214 : return __rte_bitset_find(bitset, size, 0, size, 0);
600 : : }
601 : :
602 : : /**
603 : : * Find first bit set at offset.
604 : : *
605 : : * Scans the bitset in the forward direction (i.e., starting at the
606 : : * least significant bit), starting at an offset @c start_bit into the
607 : : * bitset, and returns the index of the first '1' encountered.
608 : : *
609 : : * @param bitset
610 : : * A pointer to the array of words making up the bitset.
611 : : * @param size
612 : : * The size of the bitset (in bits).
613 : : * @param start_bit
614 : : * The index of the first bit to check. Must be less than @c size.
615 : : * @param len
616 : : * The number of bits to scan. @c start_bit + @c len must be less
617 : : * than or equal to @c size.
618 : : * @return
619 : : * Returns the index of the least significant '1', or -1 if all
620 : : * bits are '0'.
621 : : */
622 : : static inline ssize_t
623 : : rte_bitset_find_set(const uint64_t *bitset, size_t size, size_t start_bit, size_t len)
624 : : {
625 : 252875 : return __rte_bitset_find(bitset, size, start_bit, len, 0);
626 : : }
627 : :
628 : : /**
629 : : * Find first bit set at offset, with wrap-around.
630 : : *
631 : : * Scans the bitset in the forward direction (i.e., starting at the
632 : : * least significant bit), starting at an offset @c start_bit into the
633 : : * bitset. If no '1' is encountered before the end of the bitset, the search
634 : : * will continue at index 0.
635 : : *
636 : : * @param bitset
637 : : * A pointer to the array of words making up the bitset.
638 : : * @param size
639 : : * The size of the bitset (in bits).
640 : : * @param start_bit
641 : : * The index of the first bit to check. Must be less than @c size.
642 : : * @param len
643 : : * The number of bits to scan. @c start_bit + @c len must be less
644 : : * than or equal to @c size.
645 : : * @return
646 : : * Returns the index of the least significant '1', or -1 if all
647 : : * bits are '0'.
648 : : */
649 : : static inline ssize_t
650 : : rte_bitset_find_set_wrap(const uint64_t *bitset, size_t size, size_t start_bit, size_t len)
651 : : {
652 : 746911 : return __rte_bitset_find(bitset, size, start_bit, len, __RTE_BITSET_FIND_FLAG_WRAP);
653 : : }
654 : :
655 : : /**
656 : : * Find first cleared bit.
657 : : *
658 : : * Scans the bitset in the forward direction (i.e., starting at the
659 : : * least significant bit), and returns the index of the first '0'.
660 : : *
661 : : * @param bitset
662 : : * A pointer to the array of words making up the bitset.
663 : : * @param size
664 : : * The size of the bitset (in bits).
665 : : * @return
666 : : * Returns the index of the least significant '0', or -1 if all
667 : : * bits are '1'.
668 : : */
669 : : static inline ssize_t
670 : : rte_bitset_find_first_clear(const uint64_t *bitset, size_t size)
671 : : {
672 [ + + ]: 345 : return __rte_bitset_find(bitset, size, 0, size, __RTE_BITSET_FIND_FLAG_FIND_CLEAR);
673 : : }
674 : :
675 : : /**
676 : : * Find first cleared bit at offset.
677 : : *
678 : : * Scans the bitset in the forward direction (i.e., starting at the
679 : : * least significant bit), starting at an offset @c start_bit into the
680 : : * bitset, and returns the index of the first '0' encountered.
681 : : *
682 : : * @param bitset
683 : : * A pointer to the array of words making up the bitset.
684 : : * @param size
685 : : * The size of the bitset (in bits).
686 : : * @param start_bit
687 : : * The index of the first bit to check. Must be less than @c size.
688 : : * @param len
689 : : * The number of bits to scan. @c start_bit + @c len must be less
690 : : * than or equal to @c size.
691 : : * @return
692 : : * Returns the index of the least significant '0', or -1 if all
693 : : * bits are '1'.
694 : : */
695 : : static inline ssize_t
696 : : rte_bitset_find_clear(const uint64_t *bitset, size_t size, size_t start_bit, size_t len)
697 : : {
698 : 252479 : return __rte_bitset_find(bitset, size, start_bit, len, __RTE_BITSET_FIND_FLAG_FIND_CLEAR);
699 : : }
700 : :
701 : : /**
702 : : * Find first cleared bit at offset, with wrap-around.
703 : : *
704 : : * Scans the bitset in the forward direction (i.e., starting at the
705 : : * least significant bit), starting at an offset @c start_bit into the
706 : : * bitset. If no '0' is encountered before the end of the bitset, the
707 : : * search will continue at index 0.
708 : : *
709 : : * @param bitset
710 : : * A pointer to the array of words making up the bitset.
711 : : * @param size
712 : : * The size of the bitset (in bits).
713 : : * @param start_bit
714 : : * The index of the first bit to check. Must be less than @c size.
715 : : * @param len
716 : : * The number of bits to scan. @c start_bit + @c len must be less
717 : : * than or equal to @c size.
718 : : * @return
719 : : * Returns the index of the least significant '0', or -1 if all
720 : : * bits are '1'.
721 : : */
722 : : static inline ssize_t
723 : : rte_bitset_find_clear_wrap(const uint64_t *bitset, size_t size, size_t start_bit, size_t len)
724 : : {
725 : 747305 : return __rte_bitset_find(bitset, size, start_bit, len,
726 : : __RTE_BITSET_FIND_FLAG_FIND_CLEAR | __RTE_BITSET_FIND_FLAG_WRAP);
727 : : }
728 : :
729 : : /**
730 : : * Copy bitset.
731 : : *
732 : : * Copy the bits of the @c src_bitset to the @c dst_bitset.
733 : : *
734 : : * The bitsets may not overlap and must be of equal size.
735 : : *
736 : : * @param dst_bitset
737 : : * A pointer to the array of words making up the bitset.
738 : : * @param src_bitset
739 : : * A pointer to the array of words making up the bitset.
740 : : * @param size
741 : : * The size of the bitsets (in bits).
742 : : */
743 : : static inline void
744 : 9954937 : rte_bitset_copy(uint64_t *__rte_restrict dst_bitset, const uint64_t *__rte_restrict src_bitset,
745 : : size_t size)
746 : : {
747 [ + + ]: 9954937 : rte_memcpy(dst_bitset, src_bitset, RTE_BITSET_SIZE(size));
748 : 1 : }
749 : :
750 : : /**
751 : : * Bitwise or two bitsets.
752 : : *
753 : : * Perform a bitwise OR operation on all bits in the two equal-size
754 : : * bitsets @c src_bitset0 and @c src_bitset1, and store the results in
755 : : * @c dst_bitset.
756 : : *
757 : : * @param dst_bitset
758 : : * A pointer to the destination bitset.
759 : : * @param src_bitset0
760 : : * A pointer to the first source bitset.
761 : : * @param src_bitset1
762 : : * A pointer to the second source bitset.
763 : : * @param size
764 : : * The size of the bitsets (in bits).
765 : : */
766 : : static inline void
767 : 1 : rte_bitset_or(uint64_t *dst_bitset, const uint64_t *src_bitset0, const uint64_t *src_bitset1,
768 : : size_t size)
769 : : {
770 : : size_t i;
771 : :
772 [ + + ]: 4 : for (i = 0; i < RTE_BITSET_NUM_WORDS(size); i++)
773 : 3 : dst_bitset[i] = src_bitset0[i] | src_bitset1[i];
774 : 1 : }
775 : :
776 : : /**
777 : : * Bitwise and two bitsets.
778 : : *
779 : : * Perform a bitwise AND operation on all bits in the two equal-size
780 : : * bitsets @c src_bitset0 and @c src_bitset1, and store the result in
781 : : * @c dst_bitset.
782 : : *
783 : : * @param dst_bitset
784 : : * A pointer to the destination bitset.
785 : : * @param src_bitset0
786 : : * A pointer to the first source bitset.
787 : : * @param src_bitset1
788 : : * A pointer to the second source bitset.
789 : : * @param size
790 : : * The size of the bitsets (in bits).
791 : : */
792 : : static inline void
793 : 1 : rte_bitset_and(uint64_t *dst_bitset, const uint64_t *src_bitset0, const uint64_t *src_bitset1,
794 : : size_t size)
795 : : {
796 : : size_t i;
797 : :
798 [ + + ]: 2 : for (i = 0; i < RTE_BITSET_NUM_WORDS(size); i++)
799 : 1 : dst_bitset[i] = src_bitset0[i] & src_bitset1[i];
800 : 1 : }
801 : :
802 : : /**
803 : : * Bitwise xor two bitsets.
804 : : *
805 : : * Perform a bitwise XOR operation on all bits in the two equal-size
806 : : * bitsets @c src_bitset0 and @c src_bitset1, and store the result in
807 : : * @c dst_bitset.
808 : : *
809 : : * @param dst_bitset
810 : : * A pointer to the destination bitset.
811 : : * @param src_bitset0
812 : : * A pointer to the first source bitset.
813 : : * @param src_bitset1
814 : : * A pointer to the second source bitset.
815 : : * @param size
816 : : * The size of the bitsets (in bits).
817 : : */
818 : : static inline void
819 : 1 : rte_bitset_xor(uint64_t *dst_bitset, const uint64_t *src_bitset0, const uint64_t *src_bitset1,
820 : : size_t size)
821 : : {
822 : : size_t i;
823 : :
824 [ + + ]: 4 : for (i = 0; i < RTE_BITSET_NUM_WORDS(size); i++)
825 : 3 : dst_bitset[i] = src_bitset0[i] ^ src_bitset1[i];
826 : 1 : }
827 : :
828 : : /**
829 : : * Compute the bitwise complement of a bitset.
830 : : *
831 : : * Flip every bit in the @c src_bitset, and store the result in @c
832 : : * dst_bitset.
833 : : *
834 : : * @param dst_bitset
835 : : * A pointer to the destination bitset.
836 : : * @param src_bitset
837 : : * A pointer to the source bitset.
838 : : * @param size
839 : : * The size of the bitsets (in bits).
840 : : */
841 : : static inline void
842 : : rte_bitset_complement(uint64_t *dst_bitset, const uint64_t *src_bitset, size_t size)
843 : : {
844 : : size_t i;
845 : :
846 [ + + ]: 94005 : for (i = 0; i < RTE_BITSET_NUM_WORDS(size); i++)
847 : 84005 : dst_bitset[i] = ~src_bitset[i];
848 : : }
849 : :
850 : : /**
851 : : * Shift bitset left.
852 : : *
853 : : * Perform a logical shift left of (multiply) @c src_bitset, and store
854 : : * the result in @c dst_bitset.
855 : : *
856 : : * @param dst_bitset
857 : : * A pointer to the destination bitset.
858 : : * @param src_bitset
859 : : * A pointer to the source bitset.
860 : : * @param size
861 : : * The size of the bitsets (in bits).
862 : : * @param shift_bits
863 : : * The number of bits to shift the bitset.
864 : : */
865 : : static inline void
866 : 10000 : rte_bitset_shift_left(uint64_t *dst_bitset, const uint64_t *src_bitset, size_t size,
867 : : size_t shift_bits)
868 : : {
869 : 10000 : const int src_word_offset = shift_bits / RTE_BITSET_WORD_BITS;
870 : 10000 : const int src_bit_offset = shift_bits % RTE_BITSET_WORD_BITS;
871 : : unsigned int dst_idx;
872 : :
873 [ + + ]: 54245 : for (dst_idx = 0; dst_idx < RTE_BITSET_NUM_WORDS(size); dst_idx++) {
874 : 44245 : int src_high_idx = dst_idx - src_word_offset;
875 : : uint64_t low_bits = 0;
876 : : uint64_t high_bits = 0;
877 : :
878 [ + + ]: 44245 : if (src_high_idx >= 0) {
879 : 20695 : int src_low_idx = src_high_idx - 1;
880 : :
881 : 20695 : high_bits = src_bitset[src_high_idx] << src_bit_offset;
882 : :
883 [ + + ]: 20695 : if (src_bit_offset > 0 && src_low_idx >= 0)
884 : 12628 : low_bits = src_bitset[src_low_idx] >>
885 : 12628 : (RTE_BITSET_WORD_BITS - src_bit_offset);
886 : : }
887 : 44245 : dst_bitset[dst_idx] = low_bits | high_bits;
888 : : }
889 : 10000 : }
890 : :
891 : : /**
892 : : * Shift bitset right.
893 : : *
894 : : * Perform a logical shift right of (divide) @c src_bitset, and store
895 : : * the result in @c dst_bitset.
896 : : *
897 : : * @param dst_bitset
898 : : * A pointer to the destination bitset.
899 : : * @param src_bitset
900 : : * A pointer to the source bitset.
901 : : * @param size
902 : : * The size of the bitsets (in bits).
903 : : * @param shift_bits
904 : : * The number of bits to shift the bitset.
905 : : */
906 : : static inline void
907 : 10000 : rte_bitset_shift_right(uint64_t *dst_bitset, const uint64_t *src_bitset, size_t size,
908 : : size_t shift_bits)
909 : : {
910 : 10000 : const int num_words = RTE_BITSET_NUM_WORDS(size);
911 : 10000 : const uint64_t used_mask = __RTE_BITSET_USED_MASK(size);
912 : 10000 : const int src_word_offset = shift_bits / RTE_BITSET_WORD_BITS;
913 : 10000 : const int src_bit_offset = shift_bits % RTE_BITSET_WORD_BITS;
914 : : int dst_idx;
915 : :
916 [ + + ]: 53988 : for (dst_idx = 0; dst_idx < num_words; dst_idx++) {
917 : 43988 : int src_low_idx = src_word_offset + dst_idx;
918 : 43988 : int src_high_idx = src_low_idx + 1;
919 : : uint64_t src_low_word_bits = 0;
920 : : uint64_t src_high_word_bits = 0;
921 : :
922 [ + + ]: 43988 : if (src_low_idx < num_words) {
923 : 20575 : src_low_word_bits = src_bitset[src_low_idx];
924 : :
925 [ + + ]: 20575 : if (src_low_idx == (num_words - 1))
926 : 7892 : src_low_word_bits &= used_mask;
927 : :
928 : 20575 : src_low_word_bits >>= src_bit_offset;
929 : :
930 [ + + ]: 20575 : if (src_bit_offset > 0 && src_high_idx < num_words) {
931 : 12453 : src_high_word_bits = src_bitset[src_high_idx];
932 : :
933 [ + + ]: 12453 : if (src_high_idx == (num_words - 1))
934 : 4899 : src_high_word_bits &= used_mask;
935 : :
936 : 12453 : src_high_word_bits <<= (RTE_BITSET_WORD_BITS - src_bit_offset);
937 : : }
938 : : }
939 : 43988 : dst_bitset[dst_idx] = src_low_word_bits | src_high_word_bits;
940 : : }
941 : 10000 : }
942 : :
943 : : /**
944 : : * Compare two bitsets.
945 : : *
946 : : * Compare two bitsets for equality.
947 : : *
948 : : * @param bitset_a
949 : : * A pointer to the destination bitset.
950 : : * @param bitset_b
951 : : * A pointer to the source bitset.
952 : : * @param size
953 : : * The size of the bitsets (in bits).
954 : : */
955 : : static inline bool
956 : 9974937 : rte_bitset_equal(const uint64_t *bitset_a, const uint64_t *bitset_b, size_t size)
957 : : {
958 : : size_t i;
959 : : uint64_t last_a, last_b;
960 : :
961 [ + + + + : 108804212 : for (i = 0; i < RTE_BITSET_NUM_WORDS(size) - 1; i++)
+ + + + ]
962 [ + - + - : 98829272 : if (bitset_a[i] != bitset_b[i])
+ - + - ]
963 : : return false;
964 : :
965 : 9974940 : last_a = bitset_a[i] << __RTE_BITSET_UNUSED(size);
966 : 9974940 : last_b = bitset_b[i] << __RTE_BITSET_UNUSED(size);
967 : :
968 : 9974940 : return last_a == last_b;
969 : : }
970 : :
971 : : /**
972 : : * Converts a bitset to a string.
973 : : *
974 : : * This function prints a string representation of the bitstring to
975 : : * the supplied buffer.
976 : : *
977 : : * Each bit is represented either by '0' or '1' in the output, with
978 : : * the first (left-most) character in the output being the most
979 : : * significant bit. The resulting string is NUL terminated.
980 : : *
981 : : * @param bitset
982 : : * A pointer to the array of bitset 64-bit words.
983 : : * @param size
984 : : * The number of bits the bitset represent.
985 : : * @param buf
986 : : * A buffer to hold the output.
987 : : * @param capacity
988 : : * The size of the buffer. Must be @c size + 1 or larger.
989 : : * @return
990 : : * Returns the number of bytes written (i.e., @c size + 1), or -EINVAL
991 : : * in case the buffer capacity was too small.
992 : : */
993 : : ssize_t
994 : : rte_bitset_to_str(const uint64_t *bitset, size_t size, char *buf, size_t capacity);
995 : :
996 : : #ifdef __cplusplus
997 : : }
998 : : #endif
999 : :
1000 : : #endif /* _RTE_BITSET_H_ */
|
