1 /* SPDX-License-Identifier: GPL-2.0-only */ 2 /* 3 * tools/testing/selftests/kvm/include/sparsebit.h 4 * 5 * Copyright (C) 2018, Google LLC. 6 * 7 * Header file that describes API to the sparsebit library. 8 * This library provides a memory efficient means of storing 9 * the settings of bits indexed via a uint64_t. Memory usage 10 * is reasonable, significantly less than (2^64 / 8) bytes, as 11 * long as bits that are mostly set or mostly cleared are close 12 * to each other. This library is efficient in memory usage 13 * even in the case where most bits are set. 14 */ 15 16 #ifndef SELFTEST_KVM_SPARSEBIT_H 17 #define SELFTEST_KVM_SPARSEBIT_H 18 19 #include <stdbool.h> 20 #include <stdint.h> 21 #include <stdio.h> 22 23 #ifdef __cplusplus 24 extern "C" { 25 #endif 26 27 struct sparsebit; 28 typedef uint64_t sparsebit_idx_t; 29 typedef uint64_t sparsebit_num_t; 30 31 struct sparsebit *sparsebit_alloc(void); 32 void sparsebit_free(struct sparsebit **sbitp); 33 void sparsebit_copy(struct sparsebit *dstp, const struct sparsebit *src); 34 35 bool sparsebit_is_set(const struct sparsebit *sbit, sparsebit_idx_t idx); 36 bool sparsebit_is_set_num(const struct sparsebit *sbit, 37 sparsebit_idx_t idx, sparsebit_num_t num); 38 bool sparsebit_is_clear(const struct sparsebit *sbit, sparsebit_idx_t idx); 39 bool sparsebit_is_clear_num(const struct sparsebit *sbit, 40 sparsebit_idx_t idx, sparsebit_num_t num); 41 sparsebit_num_t sparsebit_num_set(const struct sparsebit *sbit); 42 bool sparsebit_any_set(const struct sparsebit *sbit); 43 bool sparsebit_any_clear(const struct sparsebit *sbit); 44 bool sparsebit_all_set(const struct sparsebit *sbit); 45 bool sparsebit_all_clear(const struct sparsebit *sbit); 46 sparsebit_idx_t sparsebit_first_set(const struct sparsebit *sbit); 47 sparsebit_idx_t sparsebit_first_clear(const struct sparsebit *sbit); 48 sparsebit_idx_t sparsebit_next_set(const struct sparsebit *sbit, sparsebit_idx_t prev); 49 sparsebit_idx_t sparsebit_next_clear(const struct sparsebit *sbit, sparsebit_idx_t prev); 50 sparsebit_idx_t sparsebit_next_set_num(const struct sparsebit *sbit, 51 sparsebit_idx_t start, sparsebit_num_t num); 52 sparsebit_idx_t sparsebit_next_clear_num(const struct sparsebit *sbit, 53 sparsebit_idx_t start, sparsebit_num_t num); 54 55 void sparsebit_set(struct sparsebit *sbitp, sparsebit_idx_t idx); 56 void sparsebit_set_num(struct sparsebit *sbitp, sparsebit_idx_t start, 57 sparsebit_num_t num); 58 void sparsebit_set_all(struct sparsebit *sbitp); 59 60 void sparsebit_clear(struct sparsebit *sbitp, sparsebit_idx_t idx); 61 void sparsebit_clear_num(struct sparsebit *sbitp, 62 sparsebit_idx_t start, sparsebit_num_t num); 63 void sparsebit_clear_all(struct sparsebit *sbitp); 64 65 void sparsebit_dump(FILE *stream, const struct sparsebit *sbit, 66 unsigned int indent); 67 void sparsebit_validate_internal(const struct sparsebit *sbit); 68 69 /* 70 * Iterate over an inclusive ranges within sparsebit @s. In each iteration, 71 * @range_begin and @range_end will take the beginning and end of the set 72 * range, which are of type sparsebit_idx_t. 73 * 74 * For example, if the range [3, 7] (inclusive) is set, within the 75 * iteration,@range_begin will take the value 3 and @range_end will take 76 * the value 7. 77 * 78 * Ensure that there is at least one bit set before using this macro with 79 * sparsebit_any_set(), because sparsebit_first_set() will abort if none 80 * are set. 81 */ 82 #define sparsebit_for_each_set_range(s, range_begin, range_end) \ 83 for (range_begin = sparsebit_first_set(s), \ 84 range_end = sparsebit_next_clear(s, range_begin) - 1; \ 85 range_begin && range_end; \ 86 range_begin = sparsebit_next_set(s, range_end), \ 87 range_end = sparsebit_next_clear(s, range_begin) - 1) 88 89 #ifdef __cplusplus 90 } 91 #endif 92 93 #endif /* SELFTEST_KVM_SPARSEBIT_H */ 94