xref: /linux/tools/testing/selftests/kvm/include/sparsebit.h (revision 79790b6818e96c58fe2bffee1b418c16e64e7b80)
17a338472SThomas Gleixner /* SPDX-License-Identifier: GPL-2.0-only */
2783e9e51SPaolo Bonzini /*
3783e9e51SPaolo Bonzini  * tools/testing/selftests/kvm/include/sparsebit.h
4783e9e51SPaolo Bonzini  *
5783e9e51SPaolo Bonzini  * Copyright (C) 2018, Google LLC.
6783e9e51SPaolo Bonzini  *
7783e9e51SPaolo Bonzini  * Header file that describes API to the sparsebit library.
8783e9e51SPaolo Bonzini  * This library provides a memory efficient means of storing
9783e9e51SPaolo Bonzini  * the settings of bits indexed via a uint64_t.  Memory usage
10783e9e51SPaolo Bonzini  * is reasonable, significantly less than (2^64 / 8) bytes, as
11783e9e51SPaolo Bonzini  * long as bits that are mostly set or mostly cleared are close
12783e9e51SPaolo Bonzini  * to each other.  This library is efficient in memory usage
13783e9e51SPaolo Bonzini  * even in the case where most bits are set.
14783e9e51SPaolo Bonzini  */
15783e9e51SPaolo Bonzini 
16cc68765dSAndrew Jones #ifndef SELFTEST_KVM_SPARSEBIT_H
17cc68765dSAndrew Jones #define SELFTEST_KVM_SPARSEBIT_H
18783e9e51SPaolo Bonzini 
19783e9e51SPaolo Bonzini #include <stdbool.h>
20783e9e51SPaolo Bonzini #include <stdint.h>
21783e9e51SPaolo Bonzini #include <stdio.h>
22783e9e51SPaolo Bonzini 
23783e9e51SPaolo Bonzini #ifdef __cplusplus
24783e9e51SPaolo Bonzini extern "C" {
25783e9e51SPaolo Bonzini #endif
26783e9e51SPaolo Bonzini 
27783e9e51SPaolo Bonzini struct sparsebit;
28783e9e51SPaolo Bonzini typedef uint64_t sparsebit_idx_t;
29783e9e51SPaolo Bonzini typedef uint64_t sparsebit_num_t;
30783e9e51SPaolo Bonzini 
31783e9e51SPaolo Bonzini struct sparsebit *sparsebit_alloc(void);
32783e9e51SPaolo Bonzini void sparsebit_free(struct sparsebit **sbitp);
3335f50c91SMichael Roth void sparsebit_copy(struct sparsebit *dstp, const struct sparsebit *src);
34783e9e51SPaolo Bonzini 
3535f50c91SMichael Roth bool sparsebit_is_set(const struct sparsebit *sbit, sparsebit_idx_t idx);
3635f50c91SMichael Roth bool sparsebit_is_set_num(const struct sparsebit *sbit,
37783e9e51SPaolo Bonzini 			  sparsebit_idx_t idx, sparsebit_num_t num);
3835f50c91SMichael Roth bool sparsebit_is_clear(const struct sparsebit *sbit, sparsebit_idx_t idx);
3935f50c91SMichael Roth bool sparsebit_is_clear_num(const struct sparsebit *sbit,
40783e9e51SPaolo Bonzini 			    sparsebit_idx_t idx, sparsebit_num_t num);
4135f50c91SMichael Roth sparsebit_num_t sparsebit_num_set(const struct sparsebit *sbit);
4235f50c91SMichael Roth bool sparsebit_any_set(const struct sparsebit *sbit);
4335f50c91SMichael Roth bool sparsebit_any_clear(const struct sparsebit *sbit);
4435f50c91SMichael Roth bool sparsebit_all_set(const struct sparsebit *sbit);
4535f50c91SMichael Roth bool sparsebit_all_clear(const struct sparsebit *sbit);
4635f50c91SMichael Roth sparsebit_idx_t sparsebit_first_set(const struct sparsebit *sbit);
4735f50c91SMichael Roth sparsebit_idx_t sparsebit_first_clear(const struct sparsebit *sbit);
4835f50c91SMichael Roth sparsebit_idx_t sparsebit_next_set(const struct sparsebit *sbit, sparsebit_idx_t prev);
4935f50c91SMichael Roth sparsebit_idx_t sparsebit_next_clear(const struct sparsebit *sbit, sparsebit_idx_t prev);
5035f50c91SMichael Roth sparsebit_idx_t sparsebit_next_set_num(const struct sparsebit *sbit,
51783e9e51SPaolo Bonzini 				       sparsebit_idx_t start, sparsebit_num_t num);
5235f50c91SMichael Roth sparsebit_idx_t sparsebit_next_clear_num(const struct sparsebit *sbit,
53783e9e51SPaolo Bonzini 					 sparsebit_idx_t start, sparsebit_num_t num);
54783e9e51SPaolo Bonzini 
55783e9e51SPaolo Bonzini void sparsebit_set(struct sparsebit *sbitp, sparsebit_idx_t idx);
56783e9e51SPaolo Bonzini void sparsebit_set_num(struct sparsebit *sbitp, sparsebit_idx_t start,
57783e9e51SPaolo Bonzini 		       sparsebit_num_t num);
58783e9e51SPaolo Bonzini void sparsebit_set_all(struct sparsebit *sbitp);
59783e9e51SPaolo Bonzini 
60783e9e51SPaolo Bonzini void sparsebit_clear(struct sparsebit *sbitp, sparsebit_idx_t idx);
61783e9e51SPaolo Bonzini void sparsebit_clear_num(struct sparsebit *sbitp,
62783e9e51SPaolo Bonzini 			 sparsebit_idx_t start, sparsebit_num_t num);
63783e9e51SPaolo Bonzini void sparsebit_clear_all(struct sparsebit *sbitp);
64783e9e51SPaolo Bonzini 
6535f50c91SMichael Roth void sparsebit_dump(FILE *stream, const struct sparsebit *sbit,
66783e9e51SPaolo Bonzini 		    unsigned int indent);
6735f50c91SMichael Roth void sparsebit_validate_internal(const struct sparsebit *sbit);
68783e9e51SPaolo Bonzini 
69*57e19f05SAckerley Tng /*
70*57e19f05SAckerley Tng  * Iterate over an inclusive ranges within sparsebit @s. In each iteration,
71*57e19f05SAckerley Tng  * @range_begin and @range_end will take the beginning and end of the set
72*57e19f05SAckerley Tng  * range, which are of type sparsebit_idx_t.
73*57e19f05SAckerley Tng  *
74*57e19f05SAckerley Tng  * For example, if the range [3, 7] (inclusive) is set, within the
75*57e19f05SAckerley Tng  * iteration,@range_begin will take the value 3 and @range_end will take
76*57e19f05SAckerley Tng  * the value 7.
77*57e19f05SAckerley Tng  *
78*57e19f05SAckerley Tng  * Ensure that there is at least one bit set before using this macro with
79*57e19f05SAckerley Tng  * sparsebit_any_set(), because sparsebit_first_set() will abort if none
80*57e19f05SAckerley Tng  * are set.
81*57e19f05SAckerley Tng  */
82*57e19f05SAckerley Tng #define sparsebit_for_each_set_range(s, range_begin, range_end)         \
83*57e19f05SAckerley Tng 	for (range_begin = sparsebit_first_set(s),                      \
84*57e19f05SAckerley Tng 	     range_end = sparsebit_next_clear(s, range_begin) - 1;	\
85*57e19f05SAckerley Tng 	     range_begin && range_end;                                  \
86*57e19f05SAckerley Tng 	     range_begin = sparsebit_next_set(s, range_end),            \
87*57e19f05SAckerley Tng 	     range_end = sparsebit_next_clear(s, range_begin) - 1)
88*57e19f05SAckerley Tng 
89783e9e51SPaolo Bonzini #ifdef __cplusplus
90783e9e51SPaolo Bonzini }
91783e9e51SPaolo Bonzini #endif
92783e9e51SPaolo Bonzini 
93cc68765dSAndrew Jones #endif /* SELFTEST_KVM_SPARSEBIT_H */
94