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 24extern "C" { 25#endif 26 27struct sparsebit; 28typedef uint64_t sparsebit_idx_t; 29typedef uint64_t sparsebit_num_t; 30 31struct sparsebit *sparsebit_alloc(void); 32void sparsebit_free(struct sparsebit **sbitp); 33void sparsebit_copy(struct sparsebit *dstp, const struct sparsebit *src); 34 35bool sparsebit_is_set(const struct sparsebit *sbit, sparsebit_idx_t idx); 36bool sparsebit_is_set_num(const struct sparsebit *sbit, 37 sparsebit_idx_t idx, sparsebit_num_t num); 38bool sparsebit_is_clear(const struct sparsebit *sbit, sparsebit_idx_t idx); 39bool sparsebit_is_clear_num(const struct sparsebit *sbit, 40 sparsebit_idx_t idx, sparsebit_num_t num); 41sparsebit_num_t sparsebit_num_set(const struct sparsebit *sbit); 42bool sparsebit_any_set(const struct sparsebit *sbit); 43bool sparsebit_any_clear(const struct sparsebit *sbit); 44bool sparsebit_all_set(const struct sparsebit *sbit); 45bool sparsebit_all_clear(const struct sparsebit *sbit); 46sparsebit_idx_t sparsebit_first_set(const struct sparsebit *sbit); 47sparsebit_idx_t sparsebit_first_clear(const struct sparsebit *sbit); 48sparsebit_idx_t sparsebit_next_set(const struct sparsebit *sbit, sparsebit_idx_t prev); 49sparsebit_idx_t sparsebit_next_clear(const struct sparsebit *sbit, sparsebit_idx_t prev); 50sparsebit_idx_t sparsebit_next_set_num(const struct sparsebit *sbit, 51 sparsebit_idx_t start, sparsebit_num_t num); 52sparsebit_idx_t sparsebit_next_clear_num(const struct sparsebit *sbit, 53 sparsebit_idx_t start, sparsebit_num_t num); 54 55void sparsebit_set(struct sparsebit *sbitp, sparsebit_idx_t idx); 56void sparsebit_set_num(struct sparsebit *sbitp, sparsebit_idx_t start, 57 sparsebit_num_t num); 58void sparsebit_set_all(struct sparsebit *sbitp); 59 60void sparsebit_clear(struct sparsebit *sbitp, sparsebit_idx_t idx); 61void sparsebit_clear_num(struct sparsebit *sbitp, 62 sparsebit_idx_t start, sparsebit_num_t num); 63void sparsebit_clear_all(struct sparsebit *sbitp); 64 65void sparsebit_dump(FILE *stream, const struct sparsebit *sbit, 66 unsigned int indent); 67void 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