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