DPDK
24.11.0-rc1
|
#include <limits.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <rte_bitops.h>
#include <rte_branch_prediction.h>
#include <rte_common.h>
#include <rte_compat.h>
#include <rte_debug.h>
#include <rte_memcpy.h>
Go to the source code of this file.
Macros | |
#define | RTE_BITSET_WORD_SIZE (sizeof(uint64_t)) |
#define | RTE_BITSET_WORD_BITS (RTE_BITSET_WORD_SIZE * CHAR_BIT) |
#define | RTE_BITSET_NUM_WORDS(size) ((size + RTE_BITSET_WORD_BITS - 1) / RTE_BITSET_WORD_BITS) |
#define | RTE_BITSET_SIZE(size) ((size_t)(RTE_BITSET_NUM_WORDS(size) * RTE_BITSET_WORD_SIZE)) |
#define | RTE_BITSET_DECLARE(name, size) uint64_t name[RTE_BITSET_NUM_WORDS(size)] |
#define | RTE_BITSET_FOREACH_SET(var, bitset, size) __RTE_BITSET_FOREACH(var, bitset, size, 0, size, 0) |
#define | RTE_BITSET_FOREACH_CLEAR(var, bitset, size) __RTE_BITSET_FOREACH(var, bitset, size, 0, size, __RTE_BITSET_FIND_FLAG_FIND_CLEAR) |
#define | RTE_BITSET_FOREACH_SET_RANGE(var, bitset, size, start_bit, len) __RTE_BITSET_FOREACH(var, bitset, size, start_bit, len, 0) |
#define | RTE_BITSET_FOREACH_CLEAR_RANGE(var, bitset, size, start_bit, len) __RTE_BITSET_FOREACH(var, bitset, size, start_bit, len, __RTE_BITSET_FIND_FLAG_FIND_CLEAR) |
Functions | |
static __rte_experimental void | rte_bitset_init (uint64_t *bitset, size_t size) |
static __rte_experimental bool | rte_bitset_test (const uint64_t *bitset, size_t bit_num) |
static __rte_experimental void | rte_bitset_set (uint64_t *bitset, size_t bit_num) |
static __rte_experimental void | rte_bitset_clear (uint64_t *bitset, size_t bit_num) |
static __rte_experimental void | rte_bitset_assign (uint64_t *bitset, size_t bit_num, bool bit_value) |
static __rte_experimental void | rte_bitset_flip (uint64_t *bitset, size_t bit_num) |
static __rte_experimental bool | rte_bitset_atomic_test (const uint64_t *bitset, size_t bit_num, int memory_order) |
static __rte_experimental void | rte_bitset_atomic_set (uint64_t *bitset, size_t bit_num, int memory_order) |
static __rte_experimental void | rte_bitset_atomic_clear (uint64_t *bitset, size_t bit_num, int memory_order) |
static __rte_experimental void | rte_bitset_atomic_assign (uint64_t *bitset, size_t bit_num, bool bit_value, int memory_order) |
static __rte_experimental void | rte_bitset_atomic_flip (uint64_t *bitset, size_t bit_num, int memory_order) |
static __rte_experimental void | rte_bitset_set_all (uint64_t *bitset, size_t size) |
static __rte_experimental void | rte_bitset_clear_all (uint64_t *bitset, size_t size) |
static __rte_experimental size_t | rte_bitset_count_set (const uint64_t *bitset, size_t size) |
static __rte_experimental size_t | rte_bitset_count_clear (const uint64_t *bitset, size_t size) |
static __rte_experimental ssize_t | rte_bitset_find_first_set (const uint64_t *bitset, size_t size) |
static __rte_experimental ssize_t | rte_bitset_find_set (const uint64_t *bitset, size_t size, size_t start_bit, size_t len) |
static __rte_experimental ssize_t | rte_bitset_find_set_wrap (const uint64_t *bitset, size_t size, size_t start_bit, size_t len) |
static __rte_experimental ssize_t | rte_bitset_find_first_clear (const uint64_t *bitset, size_t size) |
static __rte_experimental ssize_t | rte_bitset_find_clear (const uint64_t *bitset, size_t size, size_t start_bit, size_t len) |
static __rte_experimental ssize_t | rte_bitset_find_clear_wrap (const uint64_t *bitset, size_t size, size_t start_bit, size_t len) |
static __rte_experimental void | rte_bitset_copy (uint64_t *__rte_restrict dst_bitset, const uint64_t *__rte_restrict src_bitset, size_t size) |
static __rte_experimental void | rte_bitset_or (uint64_t *dst_bitset, const uint64_t *src_bitset0, const uint64_t *src_bitset1, size_t size) |
static __rte_experimental void | rte_bitset_and (uint64_t *dst_bitset, const uint64_t *src_bitset0, const uint64_t *src_bitset1, size_t size) |
static __rte_experimental void | rte_bitset_xor (uint64_t *dst_bitset, const uint64_t *src_bitset0, const uint64_t *src_bitset1, size_t size) |
static __rte_experimental void | rte_bitset_complement (uint64_t *dst_bitset, const uint64_t *src_bitset, size_t size) |
static __rte_experimental void | rte_bitset_shift_left (uint64_t *dst_bitset, const uint64_t *src_bitset, size_t size, size_t shift_bits) |
static __rte_experimental void | rte_bitset_shift_right (uint64_t *dst_bitset, const uint64_t *src_bitset, size_t size, size_t shift_bits) |
static __rte_experimental bool | rte_bitset_equal (const uint64_t *bitset_a, const uint64_t *bitset_b, size_t size) |
__rte_experimental ssize_t | rte_bitset_to_str (const uint64_t *bitset, size_t size, char *buf, size_t capacity) |
RTE Bitset
This file provides functions and macros for querying and manipulating sets of bits kept in arrays of uint64_t-sized
elements.
The bits in a bitset are numbered from 0 to size
- 1, with the lowest index being the least significant bit.
The bitset array must be properly aligned.
For optimal performance, the size
parameter, required by many of the API's functions, should be a compile-time constant.
For large bitsets, the rte_bitmap.h API may be more appropriate.
Definition in file rte_bitset.h.
#define RTE_BITSET_WORD_SIZE (sizeof(uint64_t)) |
The size (in bytes) of each element in the array used to represent a bitset.
Definition at line 53 of file rte_bitset.h.
#define RTE_BITSET_WORD_BITS (RTE_BITSET_WORD_SIZE * CHAR_BIT) |
The size (in bits) of each element in the array used to represent a bitset.
Definition at line 59 of file rte_bitset.h.
#define RTE_BITSET_NUM_WORDS | ( | size | ) | ((size + RTE_BITSET_WORD_BITS - 1) / RTE_BITSET_WORD_BITS) |
Computes the number of words required to store size
bits.
Definition at line 64 of file rte_bitset.h.
#define RTE_BITSET_SIZE | ( | size | ) | ((size_t)(RTE_BITSET_NUM_WORDS(size) * RTE_BITSET_WORD_SIZE)) |
Computes the amount of memory (in bytes) required to fit a bitset holding size
bits.
Definition at line 71 of file rte_bitset.h.
#define RTE_BITSET_DECLARE | ( | name, | |
size | |||
) | uint64_t name[RTE_BITSET_NUM_WORDS(size)] |
Declare a bitset.
Declare (e.g., as a struct field) or define (e.g., as a stack variable) a bitset of the specified size.
size | The number of bits the bitset must be able to represent. Must be a compile-time constant. |
name | The field or variable name of the resulting definition. |
Definition at line 104 of file rte_bitset.h.
#define RTE_BITSET_FOREACH_SET | ( | var, | |
bitset, | |||
size | |||
) | __RTE_BITSET_FOREACH(var, bitset, size, 0, size, 0) |
Iterate over all bits set.
This macro iterates over all bits set (i.e., all ones) in the bitset, in the forward direction (i.e., starting with the least significant '1').
var | An iterator variable of type ssize_t . For each successive iteration, this variable will hold the bit index of a set bit. |
bitset | A const uint64_t * pointer to the bitset array. |
size | The size of the bitset (in bits). |
Definition at line 135 of file rte_bitset.h.
#define RTE_BITSET_FOREACH_CLEAR | ( | var, | |
bitset, | |||
size | |||
) | __RTE_BITSET_FOREACH(var, bitset, size, 0, size, __RTE_BITSET_FIND_FLAG_FIND_CLEAR) |
Iterate over all bits cleared.
This macro iterates over all bits cleared in the bitset, in the forward direction (i.e., starting with the lowest-indexed set bit).
var | An iterator variable of type ssize_t . For each successive iteration, this variable will hold the bit index of a cleared bit. |
bitset | A const uint64_t * pointer to the bitset array. |
size | The size of the bitset (in bits). |
Definition at line 155 of file rte_bitset.h.
#define RTE_BITSET_FOREACH_SET_RANGE | ( | var, | |
bitset, | |||
size, | |||
start_bit, | |||
len | |||
) | __RTE_BITSET_FOREACH(var, bitset, size, start_bit, len, 0) |
Iterate over all bits set within a range.
This macro iterates over all bits set (i.e., all ones) in the specified range, in the forward direction (i.e., starting with the least significant '1').
var | An iterator variable of type ssize_t . For each successive iteration, this variable will hold the bit index of a set bit. |
bitset | A const uint64_t * pointer to the bitset array. |
size | The size of the bitset (in bits). |
start_bit | The index of the first bit to check. Must be less than size . |
len | The length (in bits) of the range. start_bit + len must be less than or equal to size . |
Definition at line 181 of file rte_bitset.h.
#define RTE_BITSET_FOREACH_CLEAR_RANGE | ( | var, | |
bitset, | |||
size, | |||
start_bit, | |||
len | |||
) | __RTE_BITSET_FOREACH(var, bitset, size, start_bit, len, __RTE_BITSET_FIND_FLAG_FIND_CLEAR) |
Iterate over all cleared bits within a range.
This macro iterates over all bits cleared (i.e., all zeroes) in the specified range, in the forward direction (i.e., starting with the least significant '0').
var | An iterator variable of type ssize_t . For each successive iteration, this variable will hold the bit index of a set bit. |
bitset | A const uint64_t * pointer to the bitset array. |
size | The size of the bitset (in bits). |
start_bit | The index of the first bit to check. Must be less than size . |
len | The length (in bits) of the range. start_bit + len must be less than or equal to size . |
Definition at line 207 of file rte_bitset.h.
|
inlinestatic |
Initializes a bitset.
All bits are cleared.
In case all words in the bitset array are already set to zero by other means (e.g., at the time of memory allocation), this function need not be called.
bitset | A pointer to the array of bitset 64-bit words. |
size | The size of the bitset (in bits). |
Definition at line 236 of file rte_bitset.h.
|
inlinestatic |
Test if a bit is set.
bitset | A pointer to the array of words making up the bitset. |
bit_num | Index of the bit to test. Index 0 is the least significant bit. |
Definition at line 256 of file rte_bitset.h.
|
inlinestatic |
Set a bit in the bitset.
Bits are numbered from 0 to (size - 1) (inclusive).
The operation is not guaranteed to be atomic.
bitset | A pointer to the array of words making up the bitset. |
bit_num | The index of the bit to be set. |
Definition at line 278 of file rte_bitset.h.
|
inlinestatic |
Clear a bit in the bitset.
Bits are numbered 0 to (size - 1) (inclusive).
The operation is not guaranteed to be atomic.
bitset | A pointer to the array of words making up the bitset. |
bit_num | The index of the bit to be cleared. |
Definition at line 300 of file rte_bitset.h.
|
inlinestatic |
Set or clear a bit in the bitset.
Bits are numbered 0 to (size - 1) (inclusive).
The operation is not guaranteed to be atomic.
bitset | A pointer to the array of words making up the bitset. |
bit_num | The index of the bit to be set or cleared. |
bit_value | Control if the bit should be set or cleared. |
Definition at line 324 of file rte_bitset.h.
|
inlinestatic |
Change the value of a bit in the bitset.
Bits are numbered 0 to (size - 1) (inclusive).
The operation is not guaranteed to be atomic.
bitset | A pointer to the array of words making up the bitset. |
bit_num | The index of the bit to be flipped. |
Definition at line 346 of file rte_bitset.h.
|
inlinestatic |
Atomically test if a bit is set.
Atomically test if a bit in a bitset is set with the specified memory ordering.
bitset | A pointer to the array of words making up the bitset. |
bit_num | Index of the bit to test. Index 0 is the least significant bit. |
memory_order | The memory order to use. |
Definition at line 371 of file rte_bitset.h.
|
inlinestatic |
Atomically set a bit in the bitset.
Set a bit in a bitset as an atomic operation, with the specified memory ordering.
rte_bitset_atomic_set() is multi-thread safe, provided all threads acting in parallel on the same bitset does so through rte_bitset_atomic_*
() functions.
Bits are numbered from 0 to (size - 1) (inclusive).
bitset | A pointer to the array of words making up the bitset. |
bit_num | The index of the bit to be set. |
memory_order | The memory order to use. |
Definition at line 400 of file rte_bitset.h.
|
inlinestatic |
Atomically clear a bit in the bitset.
Clear a bit in a bitset as an atomic operation, with the specified memory ordering.
rte_bitset_atomic_clear() is multi-thread safe, provided all threads acting in parallel on the same bitset does so through rte_bitset_atomic_*
() functions.
Bits are numbered from 0 to (size - 1) (inclusive).
bitset | A pointer to the array of words making up the bitset. |
bit_num | The index of the bit to be cleared. |
memory_order | The memory order to use. |
Definition at line 429 of file rte_bitset.h.
|
inlinestatic |
Atomically set or clear a bit in the bitset.
Assign a value to a bit in a bitset as an atomic operation, with the specified memory ordering.
rte_bitset_atomic_assign() is multi-thread safe, provided all threads acting in parallel on the same bitset does so through rte_bitset_atomic_*
() functions.
Bits are numbered from 0 to (size - 1) (inclusive).
bitset | A pointer to the array of words making up the bitset. |
bit_num | The index of the bit to be set or cleared. |
bit_value | Control if the bit should be set or cleared. |
memory_order | The memory order to use. |
Definition at line 460 of file rte_bitset.h.
|
inlinestatic |
Atomically change the value of a bit in the bitset.
Flip a bit in a bitset as an atomic operation, with the specified memory ordering.
rte_bitset_atomic_flip() is multi-thread safe, provided all threads acting in parallel on the same bitset does so through rte_bitset_atomic_*
() functions.
Bits are numbered from 0 to (size - 1) (inclusive).
bitset | A pointer to the array of words making up the bitset. |
bit_num | The index of the bit to be flipped. |
memory_order | The memory order to use. |
Definition at line 489 of file rte_bitset.h.
|
inlinestatic |
Set all bits in the bitset.
bitset | A pointer to the array of words making up the bitset. |
size | The size of the bitset (in bits). |
Definition at line 507 of file rte_bitset.h.
|
inlinestatic |
Clear all bits in the bitset.
bitset | A pointer to the array of words making up the bitset. |
size | The size of the bitset (in bits). |
Definition at line 525 of file rte_bitset.h.
|
inlinestatic |
Count all set bits (also known as the weight).
bitset | A pointer to the array of words making up the bitset. |
size | The size of the bitset (in bits). |
Definition at line 545 of file rte_bitset.h.
|
inlinestatic |
Count all cleared bits.
bitset | A pointer to the array of words making up the bitset. |
size | The size of the bitset (in bits). |
Definition at line 577 of file rte_bitset.h.
|
inlinestatic |
Find first bit set.
Scans the bitset in the forward direction (i.e., starting at the least significant bit), and returns the index of the first '1'.
bitset | A pointer to the array of words making up the bitset. |
size | The size of the bitset (in bits). |
Definition at line 679 of file rte_bitset.h.
|
inlinestatic |
Find first bit set at offset.
Scans the bitset in the forward direction (i.e., starting at the least significant bit), starting at an offset start_bit
into the bitset, and returns the index of the first '1' encountered.
bitset | A pointer to the array of words making up the bitset. |
size | The size of the bitset (in bits). |
start_bit | The index of the first bit to check. Must be less than size . |
len | The number of bits to scan. start_bit + len must be less than or equal to size . |
Definition at line 709 of file rte_bitset.h.
|
inlinestatic |
Find first bit set at offset, with wrap-around.
Scans the bitset in the forward direction (i.e., starting at the least significant bit), starting at an offset start_bit
into the bitset. If no '1' is encountered before the end of the bitset, the search will continue at index 0.
bitset | A pointer to the array of words making up the bitset. |
size | The size of the bitset (in bits). |
start_bit | The index of the first bit to check. Must be less than size . |
len | The number of bits to scan. start_bit + len must be less than or equal to size . |
Definition at line 740 of file rte_bitset.h.
|
inlinestatic |
Find first cleared bit.
Scans the bitset in the forward direction (i.e., starting at the least significant bit), and returns the index of the first '0'.
bitset | A pointer to the array of words making up the bitset. |
size | The size of the bitset (in bits). |
Definition at line 764 of file rte_bitset.h.
|
inlinestatic |
Find first cleared bit at offset.
Scans the bitset in the forward direction (i.e., starting at the least significant bit), starting at an offset start_bit
into the bitset, and returns the index of the first '0' encountered.
bitset | A pointer to the array of words making up the bitset. |
size | The size of the bitset (in bits). |
start_bit | The index of the first bit to check. Must be less than size . |
len | The number of bits to scan. start_bit + len must be less than or equal to size . |
Definition at line 794 of file rte_bitset.h.
|
inlinestatic |
Find first cleared bit at offset, with wrap-around.
Scans the bitset in the forward direction (i.e., starting at the least significant bit), starting at an offset start_bit
into the bitset. If no '0' is encountered before the end of the bitset, the search will continue at index 0.
bitset | A pointer to the array of words making up the bitset. |
size | The size of the bitset (in bits). |
start_bit | The index of the first bit to check. Must be less than size . |
len | The number of bits to scan. start_bit + len must be less than or equal to size . |
Definition at line 825 of file rte_bitset.h.
|
inlinestatic |
Copy bitset.
Copy the bits of the src_bitset
to the dst_bitset
.
The bitsets may not overlap and must be of equal size.
dst_bitset | A pointer to the array of words making up the bitset. |
src_bitset | A pointer to the array of words making up the bitset. |
size | The size of the bitsets (in bits). |
Definition at line 850 of file rte_bitset.h.
|
inlinestatic |
Bitwise or two bitsets.
Perform a bitwise OR operation on all bits in the two equal-size bitsets src_bitset0
and src_bitset1
, and store the results in dst_bitset
.
dst_bitset | A pointer to the destination bitset. |
src_bitset0 | A pointer to the first source bitset. |
src_bitset1 | A pointer to the second source bitset. |
size | The size of the bitsets (in bits). |
Definition at line 877 of file rte_bitset.h.
|
inlinestatic |
Bitwise and two bitsets.
Perform a bitwise AND operation on all bits in the two equal-size bitsets src_bitset0
and src_bitset1
, and store the result in dst_bitset
.
dst_bitset | A pointer to the destination bitset. |
src_bitset0 | A pointer to the first source bitset. |
src_bitset1 | A pointer to the second source bitset. |
size | The size of the bitsets (in bits). |
Definition at line 907 of file rte_bitset.h.
|
inlinestatic |
Bitwise xor two bitsets.
Perform a bitwise XOR operation on all bits in the two equal-size bitsets src_bitset0
and src_bitset1
, and store the result in dst_bitset
.
dst_bitset | A pointer to the destination bitset. |
src_bitset0 | A pointer to the first source bitset. |
src_bitset1 | A pointer to the second source bitset. |
size | The size of the bitsets (in bits). |
Definition at line 937 of file rte_bitset.h.
|
inlinestatic |
Compute the bitwise complement of a bitset.
Flip every bit in the src_bitset
, and store the result in dst_bitset
.
dst_bitset | A pointer to the destination bitset. |
src_bitset | A pointer to the source bitset. |
size | The size of the bitsets (in bits). |
Definition at line 964 of file rte_bitset.h.
|
inlinestatic |
Shift bitset left.
Perform a logical shift left of (multiply) src_bitset
, and store the result in dst_bitset
.
dst_bitset | A pointer to the destination bitset. |
src_bitset | A pointer to the source bitset. |
size | The size of the bitsets (in bits). |
shift_bits | The number of bits to shift the bitset. |
Definition at line 992 of file rte_bitset.h.
|
inlinestatic |
Shift bitset right.
Perform a logical shift right of (divide) src_bitset
, and store the result in dst_bitset
.
dst_bitset | A pointer to the destination bitset. |
src_bitset | A pointer to the source bitset. |
size | The size of the bitsets (in bits). |
shift_bits | The number of bits to shift the bitset. |
Definition at line 1037 of file rte_bitset.h.
|
inlinestatic |
Compare two bitsets.
Compare two bitsets for equality.
bitset_a | A pointer to the destination bitset. |
bitset_b | A pointer to the source bitset. |
size | The size of the bitsets (in bits). |
Definition at line 1090 of file rte_bitset.h.
__rte_experimental ssize_t rte_bitset_to_str | ( | const uint64_t * | bitset, |
size_t | size, | ||
char * | buf, | ||
size_t | capacity | ||
) |
Converts a bitset to a string.
This function prints a string representation of the bitstring to the supplied buffer.
Each bit is represented either by '0' or '1' in the output, with the first (left-most) character in the output being the most significant bit. The resulting string is NUL terminated.
bitset | A pointer to the array of bitset 64-bit words. |
size | The number of bits the bitset represent. |
buf | A buffer to hold the output. |
capacity | The size of the buffer. Must be size + 1 or larger. |
size
+ 1), or -EINVAL in case the buffer capacity was too small.